How the Best Move is Determined

Some people wonder if I really know what the best move is. These suspicious people are quite right, I don't know. However, I do know which is the best among the moves that are in the database, which is a much easier thing.

Here's how I figure it out. This is what is called a "recursive" problem, because at each board, the best move depends on which moves are best for the resulting boards that arise when each of the possible moves are played on this one. So this keeps depending on later and later moves, until the last move is played and the game is won or lost. For this reason, I actually start figuring this out by beginning at the last moves of the games on file, and that's easy: the last move of each game is the one that won the game, so it has to be the best. Then I work backwards towards the beginning.

For moves that aren't the last, for each move there is a board which arises when that move is played; let's call it the next board. There are two cases:

The next board has all losing moves, or possibly losing moves, but no winning or possibly winning moves. These are moves for the opponent, and he's going to lose if he only uses the moves in the database, so the move that gives rise to this next board is a winning move.
The next board has at least one winning move, or possibly winning move. These are moves for the opponent, and and we give him credit for always choosing a winning move if there is one, so he's going to win if we only uses the moves in the database, so the move that gives rise to this next board is a losing move.

Now, knowing which are the winning and losing moves, we consider the current board. If all the moves are losing, the best we can do is choose the losing move that delays the end as long as possible. That's the "best move" when all there are is losing moves. If there are any winning moves, we're going to want to use one of them, and the best of them is the one that wins in the least number of additional moves.

I keep track of how many moves are in the 'best' game of each board, and use the information when figuring which is the best move on the board that comes before.

For those who prefer a more rigorous, mathematical, treatment, my apologies. I don't know enough about game theory for that. But you can think of it this way: I'm actually judging the moves in a derivative game where the only legal moves are the ones that are already in the database. In that game, all the "possible" winners actually do win, and the analysis above (slightly restated) finds the winners and losers.

Of course, nobody actually plays that derivative game, and the real game of hex, played by good players, is very different from it. But it's a start, and that's all I ask.