Game Trees

Games like Tic Tac Toe, Othello, checkers and Chess share a common characteristic that a player tends to think several moves in advance. A player would often select a move for himself and then think a best move for his opponent. If the overall result comes favourable for the player then he plays that move else selects another move and so on. A player which can look ahead for several moves would have a considerable advantage over a player who would look ahead for the immediate move only. The more is the depth of look ahead, the better is the chances of winning. This characteristic of these games can be exploited to implement a basic logic for an computer opponent for these games.

Game Trees

The sequence of moves can be pictorially shown in form of a tree known as a Game Tree. The root of the tree denotes the initial position. The descendants of the root are be different moves which correspond to different board position of the game. Tic Tac Toe game tree for player 'X' in the middle of game is shown below

The root is the position of the board for which best move has to be determined. At the first level moves for player 'X' are explored. At the next level moves for player 'O' are explored. The possibilities are explored till all valid moves are exhausted.

To evaluate whether a move is good or bad, the move can be given some points according to the strength of the position of player. At the next level down, as the moves for the opponent would be evaluated. Negative points would be awarded at this level. So the more stronger is the position of the opponent after the move, lesser would be points awarded.

A score of infinity is given for a win. Eventually a branch which has the maximum score till leaf will be chosen. In the above case player 'X' will choose the middle move.

We have given a score of infinity for a win. Practically it means a very high value for score is given somewhere near the maximum value of the data type. Keeping a very high value for a win insures that the logic will give preference to a branch which might not look promising first but eventually lead to victory e.g. the computer would think about sacrificing a pawn to capture the king.

The lower the value of infinity, more defensive the computer would be. A very low value make the computer to not accept any setbacks even if the chances of winning are very bright within next few moves. However, a very high value of infinity may cause the computer to go for a winning brach every time.

int lookahead(Player player, int level, Move move)

{

int i;

int points=-32767;

int tpoints=0;

Move bestmove= NULL;

if(level==MAXLEVEL)

return(0);

ValidMoves (P, L);

for each move M in List L do

{

makemove(player, M);

tpoints=analyzeposition(player);

if(win()==player)

{

undomove(i);

*move=i;

return(30000/level);

}

/* Substract the points of

best move of the opponent */

tpoints = tpoints - (lookahead(Opponent,level+1,M)/level);

if(tpoints>=points)

/* If the new move is better than the last

best move then save it*/

{

points=tpoints;

bestmove=M;

}

undomove(M);

}

Move=bestmove;

/* Verifying that a better move was found */

if(bestmove!=NULL)

return(points);

else

/* If each move is equally worst

i.e. with a score of -32767 then return 0. */

return(0);

}

Here, we have divided the score "tpoints" with level so that between two equally fruitful moves the move which occurs after least number of moves will be preferred. For the same reason a win situation after two moves will be preferred before a win situation after three moves.

In general, the points accumulated can be shown as:

BPoints(P,i) = Points for the best move for player P at level i

BPoints(P,0) = BPoints(P,1)/1 - ( BPoints(Opponent(P,2)/2 - ( BPoints(Opponent(Opponent(P,3)/3) - ... )))

Since Opponent function applied on P odd number of time will give us P so

BPoints(P,0) = BPoints(P,1)/1 - BPoints(Opponent(P,2)/2 + BPoints(P,3)/3 - ...