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?

  • \$\begingroup\$ Shows little research effort. Have you looked up what MiniMax is? \$\endgroup\$ – Anko Dec 8 '12 at 9:39
  • \$\begingroup\$ I already have a player, and in end of game player look up the end state (no more possible moves), but I need evaluation function to good play first 10 moves \$\endgroup\$ – JohnDow Dec 8 '12 at 9:43
  • 1
    \$\begingroup\$ Ah, that makes it clear! I'll edit the question to make it clearer. \$\endgroup\$ – Anko Dec 8 '12 at 9:49

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 )
    // 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.


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.

  • \$\begingroup\$ Yes, I really want to do this, but I need good evaluation function, because if I use my current ev. function, I need calculate every move to do first move -> 3^64 possible moves. \$\endgroup\$ – JohnDow Dec 8 '12 at 11:01
  • \$\begingroup\$ Normally one only looks ahead a certain number of moves, rather than all the way to the end of the match. \$\endgroup\$ – Trevor Powell Dec 8 '12 at 12:17
  • \$\begingroup\$ And it's why I need evualation function \$\endgroup\$ – JohnDow Dec 8 '12 at 12:19
  • \$\begingroup\$ Quick Google search shows this link? cs.cornell.edu/~yuli/othello/othello.html \$\endgroup\$ – Trevor Powell Dec 8 '12 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.