Tic Tac Toe implementation using NegaScout algorithm ( c++ )

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