Determining Stable discs in Othello

Question

I'm trying to determine which discs of an Othello board are stable ones (those that can't be flipped for the rest of the game).

I've read that the disc needs to be stable in all four directions (horizontally, vertically and both diagonals). For it to be stable in any direction, either the direction is full of discs so that no more can be placed in that direction, it is on the edge of the board, or it is adjacent to a stable disc of the same color.

I understand the first two parts, but is there a specific order in which I need to evaluate the stability of discs, because there could be a chain reaction that induces stability.

Answer 1

I don't think there is explicit algorithm (short-cut) to solve it.

If you don't mind caching, brute force can solve your problem easily.

Brute force = solving case by case.

At first, I has a board with some discs placed (2+2 disc), the first player can place black disc at {i1,i2,i3,...}.

If the first player pick i1, the second player can pick one of location {i11,i12,i13,...} to place white disc.

If the second player pick i11, the first player can pick one of location {i111,i112,i113,...} to place black disc.

... and so on.

It is not much (at most 64-4 steps).

Do it as a batch! .... leave your computer alone (for a few hours, may be).
Finally you would get a complete database.

It seems to be a fun task to code.
After you see the report, you may notice possibility of a better algorithm.

Answer 2

The simple approach is to iterate until nothing changes. Start with all the discs marked as unstable. Then make a pass through the discs to see if any of them meet the criteria for stability. Change the disc state from unstable to stable for every disc that meets the criteria.

If none of the discs change state during a pass, then you're done. If all of the discs are marked as stable at the end of a pass, then you're done. Worst case case is 64 passes, since at least one disc has to change states on each pass.

Answer 3

In "An Analysis of Heuristics in Othello" by Vaishnavi Sannidhanam and Muthukaruppan Annamalai, those guys propose you divide discs in 3 categories:

• stable - cannot be flipped (assign +1 score)
• unstable - can be flipped by opponents next move (assign -1 score)
• semistable - can be flipped, but not in next move (assign 0 score)

Like you said, stable discs can be found easily. Then you get all legal opponent moves, apply them and test for flipped discs in new configuration - those that flipped would be unstable. Once you have stable and unstable sets, semistable would be pretty easy to compute :)

Answer 4

The way you are thinking about what qualifies for a disc to be stable right now

For it to be stable in any direction, either the direction can be full of discs so that no more can be placed, it can be next to the edge of the board, or it is adjacent to a stable disc of the same color.

makes it extremely hard to design a correct and reliable method to find stability for all discs. Let's instead think about what qualifies for a disc to be stable from a basic standpoint and work our way from there.

There are 8 directions around any square in the board with 4 pairs of opposing directions, i.e. up and down. In order for a disc to be marked as stable, then for each pair of opposing directions, it cannot have a blank square on either side that the opponent can potentially place at to capture that disc. This is only the case when at least one of the directions for each pair hits a border for the board (by passing through discs of the same color) — which is why corner discs are always going to be stable, they are "protected" for all 4 directional pairs. Likewise, edge discs by themselves are not stable since they have a non-protected directional pair parallel to the border they are adjacent to even though the other 3 pairs are protected.

So the brute force method seems to be to go through each disc currently on the board, go through all the directional pairs for that disc, and check to see if all of them hit the border at least once (when allowed to travel through discs of the same color); if that's the case, then we would mark that disc as stable.

However, this can be optimized in two major ways.

1. Notice that the only way any discs are going to be stable is if any of the corners are occupied. So if none of the corners are occupied by a disc, automatically return the number of stable discs as 0.
2. We can also notice that for adjacent discs going in a certain direction, for that corresponding direction pair, all the discs of that color will either be protected or not protected. So rather than checking whether that direction pair is protected for every disc (of that color), you could reuse that value after determining it for only one.

To summarize, a disc is only stable if for every pair of directions, at least one of the directions in the pair is able to reach the border (and thus an opponent's disc can't "get behind" it) or it is already between two opposing color discs. Then to get all the stable discs, first determine if any of the discs are in the corners. If there are, then recursively check all 4 direction pairs of that disc, updating directional pairs for discs that are adjacent to it, making sure to reuse protected values for discs when applicable. Then at the end, for every disc whose 4 directional pairs are protected, mark that disc as stable.

Pseudocode to calculate this would look like the following:

calculate_protection(board, discs, index):
    for each pair of directions that is marked as None:
        calculate what squares it passes through for that pair of directions
        i.e. either a border, blank square, or disc of opposing color
        (Take note of what it passes through)
        if for both directions in the pair at least one reaches a border
            mark that direction pair as protected
        else if both directions in the pair hits an opposing color disc
            mark that direction pair as protected 
        else
            mark that direction pair as not protected

        for every disc that it passed through for that pair of directions (including an opposing color disc if it reached it):
            if that disc is the same color:
                mark that disc's direction pair as the same value for this one
            
            call calculate_protection for that disc and update discs
    return discs

calculate_stable_discs(board, color):
    create a dictionary of discs where the key is the index of the disc, and it has a dictionary of direction pairs and their values (initially set as None)

    if none of the corners have a disc:
        return None

    call calculate_protection on the first index that has a token

    for every disc in the dictionary keys:
        if all the numbers in the direction pairs are 1:
            increment number of stable discs by 1

    return number of stable discs

Note that to return the number of semi-stable and unstable discs as well, you would have to update what calculate_stable_discs checks for in the dictionary, as well as what calculate_protection marks directional pairs as, however the overall algorithm would remain the same.