Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
Shows little research effort. Have you looked up what MiniMax is? –  Anko Dec 8 '12 at 9:39
    
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 –  JohnDow Dec 8 '12 at 9:43
1  
Ah, that makes it clear! I'll edit the question to make it clearer. –  Anko Dec 8 '12 at 9:49
    
@Aku Thank you. –  JohnDow Dec 8 '12 at 9:55
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  JohnDow Dec 8 '12 at 11:01
    
Normally one only looks ahead a certain number of moves, rather than all the way to the end of the match. –  Trevor Powell Dec 8 '12 at 12:17
    
And it's why I need evualation function –  JohnDow Dec 8 '12 at 12:19
    
Quick Google search shows this link? cs.cornell.edu/~yuli/othello/othello.html –  Trevor Powell Dec 8 '12 at 12:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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