DOWNLOAD SOURCE CODE
code compiled using gnu gcc complier
This Tic Tac Toe game implementation uses NegaScout algorithm
Why use NegaScout algorithm ?
Its is a refinement over NegaMax alpha-beta algorithm and it could increase the efficiency of a chess engine by 10% if used with good move ordering. My implementation doesn't use move ordering.
What makes it more efficient ?
NegaScout and Principal Variation Search (PVS) are two similar refinements of alpha-beta using
minimal windows.
The basic idea behind NegaScout is that most moves after the first will result in cutoffs, so
evaluating them precisely is useless. Instead it tries to prove them inferior by searching a minimal alpha-betawindow first.
So for subtrees that cannot improve the previously computed value, NegaScout is superior to alpha-
beta due to the smaller window.
However sometimes the move in question is a better choice. In such a case
the corresponding subtree must be revisited to compute the precise minimax value.
PSEUDO CODE :
// pos : current board position
// d: search depth
// alpha: lower bound of expected value of the tree
// beta: upper bound of expected value of the tree
// Search game tree to given depth, and return evaluation of root.
int NegaScout(pos, d, alpha, beta)
{
if (d=0 || game is over)
return Eval (pos);
// evaluate leaf position from current player’s standpoint
score = - INFINITY;
// preset return value
n = beta;
moves = Generate(pos);
// generate successor moves
for i =1 to sizeof(moves) do
{
// look over all moves
Make(moves[i]);
// execute current move
cur = -NegaScout(pos, d-1, -n, -alpha);
if (cur > score)
{
if (n = beta) OR (d <= 2)
score = cur; // compare returned value and score value, note new best score if necessary
else
score = -NegaScout(pos, d-1, -beta, -cur);
}
if (score > alpha) alpha = score; //adjust the search window
Undo(moves[i]);
// retract current move
if (alpha >= beta) return alpha; // cut off
n = alpha + 1;
}
return score;
}
Figure illustrates how NegaScout prunes nodes (node N and O) which alpha-beta must visit. After the
left subtree has been visited, NegaScout gets the temporary minimax value cur = 6. So the right successor is visited with the minimal window (-7, -6). Then at node F, the leftmost child’s value (-9) causes cutoffs of its right successors
