Reversi/Othello early-game evaluation function

Question

I've written my own Reversi player, based on the MiniMax algorithm, with Alpha-Beta pruning, but in the first 10 moves my evaluation function is too slow. I need a good early-game evaluation function.

I'm trying to do it with this matrix (corresponding to the board) which determines how favourable that square is to have:

   { 30, -25, 10, 5, 5, 10, -25,  30,},
   {-25, -25,  1, 1, 1,  1, -25, -25,},
   { 10,   1,  5, 2, 2,  5,   1,  10,},
   {  5,   1,  2, 1, 1,  2,   1,   5,},
   {  5,   1,  2, 1, 1,  2,   1,   5,},
   { 10,   1,  5, 2, 2,  5,   1,  10,},
   {-25, -25,  1, 1, 1,  1, -25, -25,},
   { 30, -25, 10, 5, 5, 10, -25,  30,},}; 

But it doesn't work well.

Have you even written an early-game evaluation function for Reversi?

Answer 1

I see you've already figured out the positional strategy.

One very simple heuristic that works pretty good early in the game is "give-away", aka "evaporation": boards that have more enemy stones and fewer of your stones are better. (This is a little counter-intuitive, because the opposite is true at the end of the game).

So a simple board evaluation function could be something like

early_game := (total_stones < 40)
if( early_game ){
    // give-away in the early game
    count_goodness := K1*( enemy_stones - friendly_stones )
}else{
    // take-back later in the game
    count_goodness := K2*( friendly_stones - enemy_stones )
}
positional_goodness = K3*position_matrix_evaluation;
total_board_goodness = count_goodness + positional_goodness

where K1, K2, and K3 are tweaked to make it "play well".

You may want to glance over the Strategy Guide for Reversi & Reversed Reversi for more complicated heuristics.

Answer 2

In many board games, it is common for the first 'n' moves to be pre-calculated into an "opening book", which is just a file containing all the possible game positions within that number of moves, and the preferred responses to take for each.

To generate the opening book you use the same heuristic as you do for normal play, but instead of doing it on the fly while the game is being played, you calculate all possible moves within those first 'n', and store the results into a file that you ship with the game. Then when the game is actually playing, for those first 'n' moves, instead of running the heuristic (which as you say, can be quite slow), you instead look up the pre-calculated results from the opening book you saved out earlier.