Game Playing
DR. LAVIKA GOEL
Introduction
Game require different search procedure. Basically they are based on generate and test
procedure. Generator generates individual moves in the search space and Tester then evaluates
that and selects the most promising one.
Games require a large amount of knowledge. For example, in chess, the average branching
factor is around 35. In an average game, each player makes 50 moves. So, in order to examine
the complete game tree, we will have to examine 35^100 positions.
Thus, it is clear that to improve the effectiveness of search procedure, we need to:
1) Improve the generate procedure so that only good moves are generated.
2) Improve the test procedure so that the best moves are explored first.
Thus, heuristic search procedure is needed.
Knowledge based Components of a good
game playing program
Plausible move generator is used in game playing techniques. This type of generator generates
the set of the most promising moves instead of all the legal moves generated by the legal move
generator.
However, in games like chess, the depth of the resulting tree and its branching factor is so high
that even with a good plausible move generator, it is not possible to search until the goal state is
reached and it can only generate 10 or 20 moves (ply).
By incorporating heuristic knowledge into both the generator and the tester, the performance of
the overall system can be improved. Thus, we use a static evaluation function which evaluates
the individual board positions by estimating how likely they are to lead to a win.
Need of a search procedure
Plausible move generator and static evaluation functions both need a large amount of domain
knowledge to work so we need a search procedure that can look ahead some moves further to
see what may occur.
For one person games, A* algorithm is used.
For two-person games, minimax search is used.
Minimax Search procedure
It is a depth-first, depth limited search procedure.
The idea is to start at the current position and use the plausible move generator to generate the
set of possible successor positions.
Next, we apply the static evaluation function to those positions and choose the best one.
We then back up that value to the starting position.
Our aim is to maximize the value of the static evaluation function of the next board position.
Example
The static evaluation functions converts all judgments about board situation into a single overall
quality number by convention.
Maximizing ply A
- positive number indicates favor to one player
- negative number indicates favor to other B C D
(8) (3) (-2)
- 0 an even match.
Need of a Look ahead search
Example: In chess, after one move of ours, the situation may appear good but if we look one
move ahead, then one of our pieces might get captured because of that move and so the move
is actually not that good as it had seemed to be. So, we would like to look ahead to see what
happens to each of the new game positions at the next move which will be made by the
opponent.
Thus, we apply the plausible move generator to generate the next positions for each position
(two ply look ahead) and then apply the static evaluation function to each of these positions.
Example of Two ply look ahead
If we choose move B, opponent will
choose move F which will in turn lead
us to a state one move later with a (-2)
score of -6 and it is very bad for us. Maximizing ply A
At the opponent’s level, the (-4)
minimum value is chosen and backed (-6) (-2)
up . At our level, the maximum value Minimizing ply B C D
is chosen and backed up.
Once the values from the second ply
are backed up, it is clear that the H I
correct move for us to make at the E F G J K
first level is C which has a worst case
score of -2 and it is better than that (9) (-6) (0) (8) (-2) (-4) (-3)
through B (score=-6).
Minimax Search
This process can be repeated for as many ply as time allows, and the more accurate evaluations
that are produced can be used to choose the correct move at the top level.
The alternation of maximizing and minimizing at alternate ply when evaluations are pushed back
up corresponds to the opposing strategies of the 2 players and gives this method the name
minimax.
It is a straightforward recursive procedure that has 2 functions:
MOVEGEN(Position, Player) → Plausible moves generator that returns a list of moves that can be
made by the Player in the Position.
STATIC (Position, Player) → The Static evaluation function that returns a number representing
the goodness of Position from the viewpoint of the Player.
Minimax Search
When should the minimax search stop the recursion and call the static evaluation function? Factors
responsible:
Has one side won?
How many ply have we already explored?
How promising is this path?
How much time is left?
How stable is the configuration?
DEEP-ENOUGH –After evaluating all the above factors, it returns true if the search is to be stopped at
the current level otherwise false. It takes 2 parameters Position and Depth and ignores Position
parameter and returns True if the Depth parameter exceeds a constant cutoff value.
Implementing Minimax Search
Minimax search returns 2 things:
1) The backed up value of the path it chooses (VALUE).
2) The path itself (PATH).
Recursive call of Minimax Search takes 3 parameters- a board position, the current depth of the
search and the player to move. So the initial call to compute the best move from the position
CURRENT is:
MINIMAX(CURRENT, 0, PLAYER-ONE) if PLAYER-ONE is to move
or
MINIMAX(CURRENT, 0, PLAYER-TWO) if PLAYER-TWO is to move
Algorithm
Adding Alpha beta cut-offs
Efficiency of minimax search can be improved by using branch and bound techniques in which
partial solutions that are clearly worse than known solutions can be abandoned early.
We modify our search procedure to handle both maximizing and minimizing players. For this, we
modify the branch and bound strategy to include 2 bounds, one for each of the players. This
modified strategy is called as the alpha-beta pruning.
There are 2 threshold values-
1) Alpha- lower bound on the value that a maximizing node may be assigned.
2) Beta- upper bound on the value that a minimizing node may be assigned.
Working of alpha-beta procedure
After examining F, we know that the opponent is guaranteed a score of -5 or less at C (since the
opponent is the minimizing player). But we also know that we are guaranteed a score of 3 or
greater at A, which we can achieve if we move to B. Any other move that produces a score of
less than 3 is worse than the move to B and we can ignore it.
After examining only F, we are sure that a move to C will be worse (<=5) regardless of the value
at G. So, we can leave the exploration of G.
Use of alpha-beta thresholds
Node A will expect
a score of atleast 3
so alpha=3.
Alpha value helps
us to skip the
exploration of
node L.
Explanation
Use of alpha value: After K is examined, we see that I is guaranteed a maximum score of 0,
which means that F is guaranteed a minimum of 0. But this is less than the alpha value of 3 so no
more branches of I need to be considered.
The maximizing player already knows not to choose to move to C and then to I since, if that
move is made, the resulting score will be no better than 0 and a score of 3 can be achieved by
moving to B instead.
Use of beta value: After cutting off further exploration of I, J is examined, yielding a value of 5
which is assigned as the value of F (since it is the maximum of 5 and 0). This value is the value of
beta at C. It means that C is guaranteed to get a score of 5 or less.
Going through G, we examine M with a score of 7 so G will have a tentative score of 7 or greater.
When we compare 7 with beta (5), it is greater and the player whose turn it is at C is trying to
minimize. So this player will not choose G which will have atleast 7 score because the move
through F has a score of 5. So, we can ignore exploration of other branches of G.