Othello Evaluation Function

Question

I am currently developing a simple AI for Othello using minimax and alpha-beta pruning.

My question is related to the evaluation function for the state of the board.

I am currently looking to evaluate it by looking at:

1. Disc count (parity)

2. Number of legal moves

3. Importance of particular positions

So lets say the root node is the initial game state. The first action is the the AI's action while the second action is the opponent's action.

                   0    
                  / \           AI's Action
                 1   1
                / \   \         Opponent's action
               2   2   2

At node level 1, do I evaluate the disc count of my AI's chips and the number of legal moves it can make at the point of time after it has completed an action?

At node level 2, do I evaluate the disc count of the opponent's chips and the number of legal moves it can make at the point of time after the opponent has completed an action?

Meaning AI move -> Opponent move ==> At this point of time I evaluate the opponent's disc count and the number of legal the opponent can make.

Ornithine

Just to be sure: are you using the number of possible moves in your heuristic utility function? – Glidden

Yes, because disc count alone is a terrible heuristic function. – Ornithine

Answer 1

When generating games trees, you shouldn't evaluate a node unless it is a leaf node. That is, you generate a tree until a level N (which corresponds to a board with N moves made ahead of the current state of the board) unless you have reached a node which corresponds to an end of game situation. It is only in those nodes when you should evaluate the state of the board game with your evaluation function. That is what the minimax algorithm is about. The only case I know in which you evaluate a node after every player move is in iterative deepening algorithm which seems you are not using.

The evaluation function is responsible for providing a quick assessment of the "score" of a particular position - in other words, which side is winning and by how much. It is also called static evaluation function because it looks only at a specific board configuration. So yes, when you reach level N you can count the possible moves of both the computer and the user and substract them. For example, if the result is positive it would mean that the computer has the advantage, if it is 0 it would mean a tie and it it is negative it will represent a disadvantage situation for the user in terms of mobility. Scoring a node which represents an end of game board configuration is trivial, assign a maximum value if you win and minimum value if you lose.

Mobility is one of the most important features to be considered in the evaluation function of most board games (those in which it is valuable). And to evaluate it, you count the possible moves of each player given a static board configuration no matter whose turn is next. Even if a player recently made a move, you are giving scores to boards in the same level N of the tree when the same player made the last move (therefore, scoring them in the same conditions) and picking of those the one which has the best score.

The features you are considering in your evaluation are very good. Usually, you want to consider material and mobility (which you are) in games in which they are very valuable (though, I don't know if material is always an advantage in Othello, you should know it better as it is the game you are working on) for a winning situation so I guess you are on the correct path.

EDIT: Be careful! In a leaf node the only thing you want to do is assign a particular score to a board configuration. It is in its parent node where that score is returned and compared with the other scores (corresponding to other children). In order to choose which is the best move available for a particular player, do the following: If the parent node corresponds to an opponent's move, then pick the one with the least (min)value. If it is the computer's turn to move, pick the score with the highest (max)value so that it represents the best possible move for this player.

Plagioclase

Lets say i use both the number of legal moves to evaluate a leaf node. At the leaf node i'd want to choose the min as it would be the opponent's move. However if i use the difference and get a -ve result (which means the opponent is favored), the min function will choose the "best" result in some way or another. Which i reckon we do not want. – Ornithine

@NathanielChan please see the edit. Let me know if I can be more clear. – Plagioclase

Ok i have some what got the general idea of what and how to evaluate, thanks for the help. – Ornithine

Answer 2

End game evaluation function

If your search reaches a full board then the evaluation should simply be based on the disc count to determine who won.

Mid game evaluation function

The number of legal moves is useful in the opening and midgame as a large number of moves for you (and a low number for the opponent) normally indicates that you have a good position with lots of stable discs that your opponent cannot attack, while the opponent has a bad position where they may run out of moves and be forced to play a bad move (e.g. to let you play in the corner).

For this purpose, it does not matter greatly whose turn it is when counting the moves so I think you are on the correct path.

(Note that in the early stages of the game it is often an advantage to be the person with fewer discs as this normally means your opponent has few safe moves.)

Random evaluation function

Once upon a time I heard that just using a random number for the Othello evaluation function is (surprisingly to me) also a perfectly reasonable choice.

The logic is that the player with the most choices will be able to steer the game to get the highest random number, and so this approach again means that the AI will favour moves which give it lots of choices, and his opponent few.

Abiosis

I just implemented an alpha beta negamax depth 8 AI using the random evaluation function you suggested, and it beat me! (I'm not bad at othello either). I'm thoroughly surprised! Thanks for the interesting idea :) – Bouton