MIN-MAX Search
Games have always been an important application area for heuristic
algorithms. In playing games whose state space may be exhaustively delineated,
the primary difficulty is in accounting for the actions of the opponent. This
can be handled easily by assuming that the opponent uses the same knowledge of
the state space as us and applies that knowledge in a consistent effort to win
the game. Minmax implements game search under referred to as MIN and MAX.
The min max search procedure 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. To decide
one move, it explores the possibilities of winning by looking ahead to more
than one step. This is called a ply. Thus in a two ply search, to decide the
current move, game tree would be explored two levels farther.
Consider the below example
Figure Tree showing two ply
search
In this tree, node A represents current state of any game and nodes B, C
and D represent three possible valid moves from state A. similarly E, F, G
represents possible moves from B, H, I from C and J, K, L, from D. to decide
which move to be taken from A, the different possibilities are explored to two
next steps. 0, -3, 3, 4, 5, 6, -5, 0 represent the utility values of respective
move. They indicate goodness of a move. The utility value is back propagated to
ancestor node, according to situation whether it is max ply or min ply. As it
is a two player game, the utility value is alternatively maximized and
minimized. Here as the second player’s move is maximizing, so maximum value of
all children of one node will be back propagated to node. Thus, the nodes B, C,
D, get the values 4, 5, 6 respectively. Again as ply 1 is minimizing, so the
minimum value out of these i.e. 4 is propagated to A. then from A move will be
taken to B.
MIN MAX procedure is straightforward recursive procedure that relies on
two auxiliary procedures that are specific to the game being played.
1.
MOVEGEN (position, player): the
move generator which returns a list of nodes representing the moves that can be
made by player in position. We may have 2 players namely PLAYER-TWO in a chess
problem.
2.
STATIC (position, player): the
static evaluation function, which returns a number representing the goodness of
position from the standpoint of player.
We assume that MIN MAX returns a structure containing both results and
that we have two functions, VALUE and PATH that extract the separate
components. A function LAST PLY is taken which is assumed to evaluate all of
the factors and to return TRUE if the search should be stopped at the current
level and FALSE otherwise.
MIN MAX procedure takes three parameters like a board position, a
current depth of the search and the players to move. So the initial call to
compute the best move from the position CURRENT should be
MIN MAX (CURRENT, 0, PLAYER-ONE)
(If player is to move)
Or
MIN MAX (CURRENT, 0, PLAYER-TWO)
(If player two is to move)
Let us follow the algorithm of MIN MAX
Algorithm: MINMAX (position, depth, player)
1.
If LAST PLY (position, depth)
Then RETURN VALUE = STATIC
(position, player) PATH = nil.
2.
Else, generate one more ply of
the tree by calling the function MOVE_GEN (position, player) and set SUCCESORS
to the list it returns.
3.
If SUCESSORS is empty,
THEN no moves to be made
RETURN the same structure that would have been
returned if LAST_PLY had returned TRUE.
4.
If SUCCESORS is not empty,
THEN examine each element in turn and keep track of
the best one.
5.
After examining all the nodes,
RETURNVALUE = BEST- SCORE
PATH = BEST- PATH
When the initial call to MIN MAX returns, the best move from CURRENT is
the first element in the PATH.
Alpha- Beta (α-β) Pruning
When a number of states of a game increase and it cannot be predicted
about the states, then we can use the method pruning. Pruning is a method which
is used to reduce the no. of states in a game. Alpha- beta is one such pruning
technique. The problem with minmax search is that the number of game states it
has to examine is exponential in the number of moves. Unfortunately we cannot
eliminate the exponent, but we can effectively cut it in half. Alpha-beta
pruning is one of the solutions to the problem of minmax search tree. When α-β
pruning is applied to a standard minmax tree, it returns the same move as
minmax would, but prunes away branches that cannot possibly influence the final
decision.
The idea of alpha beta pruning is very simple. Alpha beta search
proceeds in a depth first fashion rather than searching the entire space.
Generally two values, called alpha and beta, are created during the search. The
alpha value is associated with MAX nodes and the beta value is with MIN values.
The value of alpha can never decrease; on the other hand the value of beta
never increases. Suppose the alpha value of A MAX node is 5. The MAX node then
need not consider any transmitted value less than or equal to 5 which is
associated with any MIN node below it. Alpha is the worst that MAX can score
given that MIN will also do its best. Similarly, if a MIN has a beta value of
5, it need not further consider any MAX node below it that has a value of 6 or
more.
The general principal is that: consider a node η somewhere in the search
tree, such that player has a choice of moving to that node. If player has a
better choice К either at the parent node of η or at any choice point further
up, then η will never be reached in actual play. So once we have found out
enough about η (by examining some of its descendents) to reach this conclusion,
we can prune it.
We can also say that “ α” is the value of the best choice we have found
so far at any choice point along the path for MAX. Similarly “ β” is the value
of the best choice we have found so far at any choice point along the path for
MIN. Consider the following example
Here at MIN ply, the best value from three nodes is - 4, 5, 0. These
will be back propagated towards root and a maximizing move 5 will be taken. Now
the node E has the value 8 is far more, then accepted as it is minimizing ply.
So, further node E will not be explored. In the situation when more plies are
considered, whole sub tree below E will be pruned. Similarly if α=0, β=7, all
the nodes and related sub trees having value less than 0 at maximizing ply and
more than 7 at minimizing ply will be pruned.
Alpha beta search updates the value of α and β as it goes along and
prunes the remaining branches at a node as soon as the value of the current
node is known to be worse than the current α and β value for MAX or MIN
respectively. The effectiveness of alpha- beta pruning is highly dependent on
the order in which the successors are examined suppose in a search tree the
branching factor is x and depth d. the α-β search needs examining only x0/9 nodes to pick up best move, instead of x0 for MINMAX.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.