I'm coding a Othello (Reversi) engine, and I want to count the number of stable tokens for each player, but I don't know what's the best way of doing it.
I can easily count the stable pieces along the edge, but I'm not sure how to account for the other ones. Currently, I'm using a 1-D array to represent the board.
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.
Direct Answer
Simply go through the board in a spiral pattern, keeping track of which discs you found to be stable. If a token is directly adjacent to a stable disc of the same color or is directly adjacent to a border in all four directions (horizontal, vertical, left diagonal, right diagonal), then it will be stable - as that is the definition of a stable disc.
Example diagram for spiral:
If you encounter a "loop" that lacks any stable discs, then you can stop searching the inner spiral as there will not be anymore stable discs. Moreover, to optimize it, you can first check if a corner is taken, if there isn't, there will be no stable discs at all.
You can read more about it in this research paper.
Additional Thoughts
If you are using the number of stable discs as part of a heuristic, would it not be more prudent to also check the number of unstable and semistable discs? In this case, the spiral wouldn't be applicable and you should check the stability of every disc.
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:
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.
