11 Jul 2004 Bram   » (Master)

Board evaluation in hex

I came up with an interesting heuristic for playing hex the other day. We will compute a score for all remaining cells, and move on the cell with the highest score. To compute scores, we will conduct several million independant random trial runs, each of which increase the scores of some cells. On each trial run, randomly place the remaining pieces in unoccupied cells. If you win, throw the run out. If the opponent wins, find each cell owned by the opponent for which the winner would be changed if that single cell were converted to your side, and increase the score of each of those cells by one.

One bad aspect of this algorithm is that it will play randomly when one side or the other has a near lock, since all scores will be zero. That could be fixed by changing the number of remaining cells owned by the opponent, to produce 'optimistic' or 'pessimistic' play. Comparisons of optimistic vs. pessimistic evaluations of about equal positions would be interesting.

The stochastic nature of this algorithm might superficially seem quite ludicrous and computationally wasteful. Ironically, all that CPU-eating is quite refreshing. We have unbelievable quantities of CPU, but when one tries to throw it at hex the same way one throws it at chess, the cycles simply disappear down a black hole.

I'm optimistic that this heuristic will do well. Clearly experimentation is needed.

Interestingly, this algorithm bears a strong resemblance to some trust metric ones I've suggested before. I think that's because hex sort of is like a trust metric - one side is trying to get two sides of the board to trust each other, and the other side is trying to keep that from happening.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!