Counting stable discs in Othello

Question

I'm coding a Othello (reversi) engine, as a training to implement a chess engine later. I want to count the number of stable pieces, but don't know what's the best way of doing it.

I can easily count the 'edge stable' pieces, but i'm not sure on how to account for the other ones. I'm using a 1-D array to represent the board.

Appreciate any tips on that!

Answer 1

from http://en.wikipedia.org/wiki/Reversi

"generally, a piece is stable when, along all four axes (horizontal, vertical, and each diagonal), it is on a boundary, in a filled row, or next to a stable piece of the same color."

You've mentioned the boundaries already - filled rows can be checked by just counting the pieces, though there are probably many optimisations here, e.g. find the filled rows first and then mark each position on the full row as potentially stable, rather than iterating over every position and then checking all the relevant directions, which will lead to wasted effort.

This page has some more details on calculating stability.

If you are interested in computer Othello, make sure you look up the publications on Logistello, which was (at least a few years ago) the world champion. The author, Michael Buro, wrote his PhD thesis on this topic. The source code is now available, so you can inspect the data structures used. From memory, I think he used ternary numbers (i.e. values black, white, empty) to enable fast lookups - and also maintained the state of various patterns (rows, columns, diagonals, corners, and others) to speed up the evaluation function.

Answer 2

Hm, it belongs on your datastructure I think. To check if a piece is stable you must check if all fields next to it (horizontal, vertical, diagonal) are following one of these rules:

• It is a boundary
• It is a stable piece of the same color
• It is in a filled row

How you would check this depends on your datastructure. Maybe you can chose a 2 dimensional array, so you have a closer 'picture' to the real gameboard, a 8x8 matrix.