CS557

Chapter 6 Minimax search

The routines for minimax search are rather straightforward. The minimizer returns the minimum of its expected scores while the maximizer returns the maximum of its expected stores.

minimizer(board)

{

if noMoreMoves()

return eval(board)

    min = +infinity
    for each move m
        {
        makeMove(board, m)
        result = maximizer(board)
        if (result < min)
            min = result
        retractMove(board, m)
        }
    return min
}

maximizer(board)
{
if noMoreMoves()
return eval(board)

    max = -infinity
    for each move m
        {
        makeMove(board, m)
        result = minimizer(board)
        if (result > max)
            max = result
        retractMove(board, m)
        }
    return max
}

At the top level, the minimizer (or maximizer) keeps track of the best move and after searching, makes that move. The moves made at the lower levels are not usually saved since they can be more easily be recreated the next time a move needs to be made.

As noted in class, the minimax routines sometimes do needless search. Suppose two pieces of information are available to the minimizer and the maximizer: best and worst. Let best stand for "the best that can be expected" and worst stand for "worst case possible". Note that the minimizer's best that can be expected is the maximizer's worst case possible and vice versa. Let's modify the routines so that they take advantage of this information.

minimizer(board, best, worst)

{

if noMoreMoves()

return eval(board)

    for each move m
        {
        if worst <= best then break
        makeMove(board, m)
        result = maximizer(board, best, worst)
        if (result < worst)
            worst = result
        retractMove(board, m)
        }
    return worst
}

maximizer(board, worst, best)
{
if noMoreMoves()
return eval(board)

    for each move m
        {
        if worst >= best then break
        makeMove(board, m)
        result = minimizer(board, worst, best)
        if (result > worst)
            worst = result
        retractMove(board, m)
        }
    return worst
}

Note that when the worst case possible becomes better than the best that can be hoped for, searching can stop because the adversary (who invoked the routine) will never allow the state of the game to progress to this situation. Furthermore, if the result of calling the adversary is better than the worst case possible, then the worst case possible has improved and the variable worst is reset to reflect this additional information. After all the children have been explored, the final value of worst is returned, indicating that for this situation, the best move is reflected in the updated worst. The variable best is used only for efficiency reasons (to stop searching when searching becomes fruitless).

These two routines are often combined into a single routine. Since best for minimizer is worst for maximizer, and vice versa, the variables alpha and beta are used instead of best and worst to avoid confusion. Let alpha and beta represent the range of possible results. The minimizer is interested in improving its knowledge of the worst case possible, which, for it, is beta since it represents the top end of the range. The maximizer is interested in improving its knowledge of its worst possible case which is represented by alpha. The minimizer, therefore, updates beta while the maximizer updates alpha.

alphaBeta(board, mover, alpha, beta)

{

if noMoreMoves()

return eval(board)

    for each move m
        {
        if alpha >= beta then break
        makeMove(board, m)
        result = alphaBeta(board, !mover, alpha, beta)
        if mover is minimizer and result < beta
            beta = result
        else if mover is maximizer and result > alpha
            alpha = result
        retractMove(board, m)
        }

    if mover is minimizer
        return beta
    else
        return alpha
}