Alpha-Beta

Minimax

Negamax

Quiescence Search

Minimax is an algorithm used to determine the score in a zero-sum game after a certain number of moves, with best play according to an evaluation function.

int maxi( int depth ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    for ( all moves) {
        score = mini( depth - 1 );
        if( score > max )
            max = score;
    }
    return max;
}
 
int mini( int depth ) {
    if ( depth == 0 ) return -evaluate();
    int min = +oo;
    for ( all moves) {
        score = maxi( depth - 1 );
        if( score < min )
            min = score;
    }
    return min;
}

Negamax is a common way of implementing minimax and derived algorithms.

• Instead of using two separate subroutines for the Min player and the Max player, it passes on the negated score due to following mathematical relation:

max(a, b) == -min(-a, -b)

This is how the pseudo-code of the recursive algorithm looks like. For clarity move making and unmaking is omitted.

int negaMax( int depth ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    for ( all moves)  {
        score = -negaMax( depth - 1 );
        if( score > max )
            max = score;
    }
    return max;
}

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;
 
    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();
 
        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

http://web.archive.org/web/20120421170110/http://chessprogramming.wikispaces.com/Alpha-Beta

http://web.archive.org/web/20120209041607/http://chessprogramming.wikispaces.com/Minimax

http://web.archive.org/web/20120209042116/http://chessprogramming.wikispaces.com/Negamax

http://web.archive.org/web/20120427185347/http://chessprogramming.wikispaces.com/Quiescence+Search