Struggling with Alpha-Beta.

[Suji]

Right now, I'm taking an Artificial Intelligence class, and we're doing a program with either the alpha-beta or minimax algorithm. I'm the only person modifying the alpha-beta code that came from the book, and everyone else is using the minimax algorithm.

I've run into a little snag. We're just trying to modify the source from the book to play 5x5 tic-tac-toe with a max depth of greater than or equal to 4. I've gotten the 5x5 portion to work. My professor wanted us to use his heuristic number of wins minus the number of losses. Either my program picks along the bottom row, and blocks wins (by taking forever) or plays in various spots and lets me win.

I can't figure out how to fix that.

Here's the code. It was originally in C, but I'm more fluent in C++ so I'm having it compile in MSVS as a C++ program. Right now it lets you win if you pick 12, 22, 17, 7, and 2 in that order.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHILD_NODES 25
#define MAX_PLIES 4

#define EMPTY 0
#define X_PLAYER 1
#define O_PLAYER 2

#define MAX_INFINITY 100
#define DRAW 0
#define MIN_INFINITY -100

int boards_checked;
int evalshortcut(int player, unsigned long long board);
int checkpossiblewins(int player, unsigned long long board);
int checkpossiblelosses(int player, unsigned long long board);

int getCell( int cell, unsigned long long board )
{
return ((board >> (cell*2)) & 0x3);
}

void putCell( int player, int cell, unsigned long long *board )
{
*board |= (( (unsigned long long) player << (cell*2)));
return;
}


char convert( int contents )
{
if (contents == X_PLAYER) return 'X';
else if (contents == O_PLAYER) return 'O';

return ' ';
}


void emitBoard( unsigned long long board )
{
/* Emit the current board */
printf("\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(24,board)),
convert(getCell(23,board)),
convert(getCell(22,board)),
convert(getCell(21,board)),
convert(getCell(20,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(19,board)),
convert(getCell(18,board)),
convert(getCell(17,board)),
convert(getCell(16,board)),
convert(getCell(15,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(14,board)),
convert(getCell(13,board)),
convert(getCell(12,board)),
convert(getCell(11,board)),
convert(getCell(10,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(9,board)),
convert(getCell(8,board)),
convert(getCell(7,board)),
convert(getCell(6,board)),
convert(getCell(5,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n\n",
convert(getCell(4,board)),
convert(getCell(3,board)),
convert(getCell(2,board)),
convert(getCell(1,board)),
convert(getCell(0,board)) );

return;
}


void getHumanMove( unsigned long long *board )
{
int selection;

/* Get human move */
while (1) {
printf("Select a move (24=upper-left, 0=lower-right): ");
scanf("%d", &selection);
printf("\n");
if (selection < MAX_CHILD_NODES) {
if (getCell(selection, *board) == EMPTY) break;
printf("cell taken -- choose again.\n");
}
}

putCell( X_PLAYER, selection, board );

return;
}


#define MAX_TESTS 12

typedef struct {
unsigned char test[5];
} test_t;

const test_t tests[MAX_TESTS]={
{{ 24, 23, 22, 21, 20 }},
{{ 19, 18, 17, 16, 15 }},
{{ 14, 13, 12, 11, 10 }},
{{ 9, 8, 7, 6, 5 }},
{{ 4, 3, 2, 1, 0 }},

{{ 24, 19, 14, 9, 4 }},
{{ 23, 18, 13, 8, 3 }},
{{ 22, 17, 12, 7, 2 }},
{{ 21, 16, 11, 6, 1 }},
{{ 20, 15, 10, 5, 0 }},

{{ 24, 18, 12, 6, 0 }},
{{ 20, 16, 12, 8, 4 }} };


int checkPlayerWin(int player, unsigned long long cur_board)
{
int i;

for (i = 0 ; i < MAX_TESTS ; i++) {

if ((getCell(tests.test[0], cur_board) == player) &&
(getCell(tests.test[1], cur_board) == player) &&
(getCell(tests.test[2], cur_board) == player) &&
(getCell(tests.test[3], cur_board) == player) &&
(getCell(tests.test[4], cur_board) == player)) return 1;
}

return 0;
}


short evaluateHumanMove( unsigned long long board, int depth,
int alpha, int beta )
{
int i, value;
unsigned long long new_board;
short min = MAX_INFINITY+1;

short evaluateComputerMove( unsigned long long, int, int, int );

boards_checked++;

/* The computer (max) just made a move, so we evaluate that move here */
if (checkPlayerWin(O_PLAYER, board)) return MAX_INFINITY;

for (i = 0 ; i < MAX_CHILD_NODES ; i++) {

if (getCell(i, board) == EMPTY) {

new_board = board;
putCell( X_PLAYER, i, &new_board );

value = evaluateComputerMove( new_board, depth+1, alpha, beta );

if (value < min) {
min = value;
}

if (value < beta) beta = value;

/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return beta;

}

}

/* No move is possible -- draw */
if (min == MAX_INFINITY+1) {
return DRAW;
}

return min;
}


int computer_move;
int moves = 0;

short evaluateComputerMove( unsigned long long board, int depth, int alpha, int beta )
{
int i, value;
unsigned long long new_board;
short max = MIN_INFINITY-1;

boards_checked++;

/* The human (min) just made a move, so we evaluate that move here */
if (checkPlayerWin(X_PLAYER, board)) return MIN_INFINITY;

for (i = 0 ; i < MAX_CHILD_NODES ; i++)
{
if (getCell(i, board) == EMPTY) {

new_board = board;
putCell( O_PLAYER, i, &new_board );

if(depth > MAX_PLIES)
{
value = evalshortcut(O_PLAYER, new_board);
if (value > max)
{
max = value;
if (depth == 0) computer_move = i;
}
if (value > alpha) alpha = value;
/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return alpha;

computer_move = i;
}
else
{
value = evaluateHumanMove( new_board, depth+1, alpha, beta );
}
if (value > max)
{
max = value;
if (depth == 0) computer_move = i;
}

if (value > alpha) alpha = value;
/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return alpha;
}
}
/* No move is possible -- draw */
if (max == MIN_INFINITY-1)
{
return DRAW;
}

return max;
}


void getComputerMove( unsigned long long *board )
{
boards_checked = 0;

evaluateComputerMove( *board, 0, MIN_INFINITY-1, MAX_INFINITY+1 );

printf("move is %d (boards checked %d)\n", computer_move, boards_checked);

putCell( O_PLAYER, computer_move, board );
moves++;

return;
}

int evalshortcut(int player, unsigned long long board)
{
int possiblewins = checkpossiblewins(player, board);
int possiblelosses = checkpossiblelosses(player, board);

return (possiblewins - possiblelosses);
}

int checkpossiblewins(int player, unsigned long long board)
{
int wins = 0;

for (int i = 0; i < MAX_TESTS; i++)
{
if (((getCell(tests.test[0], board) == O_PLAYER) ||
(getCell(tests.test[0], board) == EMPTY)) &&
((getCell(tests.test[1], board) == O_PLAYER) ||
(getCell(tests.test[1], board) == EMPTY)) &&
((getCell(tests.test[2], board) == O_PLAYER) ||
(getCell(tests[i].test[2], board) == EMPTY)) &&
((getCell(tests[i].test[3], board) == O_PLAYER) ||
(getCell(tests[i].test[3], board) == EMPTY))&&
((getCell(tests[i].test[4], board) == O_PLAYER) ||
(getCell(tests[i].test[4], board) == EMPTY)))
{
wins++;
}
}

return wins;
}

int checkpossiblelosses(int player, unsigned long long board)
{
int losses = 0;

for (int i = 0 ; i < MAX_TESTS ; i++)
{
if (((getCell(tests[i].test[0], board) == X_PLAYER) ||
(getCell(tests[i].test[0], board) == EMPTY)) &&
((getCell(tests[i].test[1], board) == X_PLAYER) ||
(getCell(tests[i].test[1], board) == EMPTY)) &&
((getCell(tests[i].test[2], board) == X_PLAYER) ||
(getCell(tests[i].test[2], board) == EMPTY)) &&
((getCell(tests[i].test[3], board) == X_PLAYER) ||
(getCell(tests[i].test[3], board) == EMPTY)) &&
((getCell(tests[i].test[4], board) == X_PLAYER) ||
(getCell(tests[i].test[4], board) == EMPTY)))
{
losses++;
}
}

return losses;
}

int main()
{
unsigned long long cur_board = 0;
int won = 0;

while (!won) {

emitBoard( cur_board );

getHumanMove( &cur_board );

emitBoard( cur_board );

won = checkPlayerWin( X_PLAYER, cur_board );
moves++;

if ((!won) && (moves == MAX_CHILD_NODES)) {
printf("draw\n");
break;
}

if (!won) {

/* Build the game tree */
getComputerMove( &cur_board );

won = checkPlayerWin( O_PLAYER, cur_board );

if (won) {
printf("\nYou lose!\n");
}

} else {

printf("\nYou win!\n");

}

}

emitBoard( cur_board );

return 0;
}

Any insights would be much appreciated.

[micron]

For a start, this line is clearly a bug and should be removed:

Code: Select all

computer_move = i;

Robert P.

[JuLieN]

Hello Adam,

I just took a look at you max part (evaluateComputerMove) and there is something strange with it : you made it in such a way that you have two times the following structure :

Code: Select all

if (value > max) 
{ 
  max = value; 
  if (depth == 0) computer_move = i; 
} 

if (value > alpha) alpha = value; 
/* Prune this subtree by not checking any further successors */ 
if (alpha >= beta) return alpha; 

which is the sign of a conceptual error.

Also, the evaluation of the terminal leave is normally done out of the recurrent calls... I mean, typically it's done that way :

Code: Select all

if (currentdepth == targetDepth) 
{
  return positionEvaluation;
}
else
{
  //and here you put you min/max recurrent stuff
}

Something else : is the separate use of a Min and a Max functions mandatory? Because if not you should take a look at the Negamax way of doing it : it is MUCH more simple, and you end up with only one function (Negamax) that calls itself using "-beta, -alpha" instead of having a max calling Min(alpha, beta) and a Min calling Max(alpha,beta).

More explanations there :
http://chessprogramming.wikispaces.com/Negamax
(adding an alphabeta to this negamaxed minimax is really easy).

Also, you should make your program a bit more user friendly : one shouldn't have to count from 0 to 25 starting from the bottom-right corner to the left-top one ^^ Try to make a conversion function that allows the player to enter "3,3" instead of "12"

[tvrzsky]

Your evaluateComputerMove function is not correct, let's change it this way:

Code: Select all

short evaluateComputerMove( unsigned long long board, int depth, int alpha, int beta ) 
{ 
int i, value; 
unsigned long long new_board; 
short max = MIN_INFINITY-1; 
boards_checked++; 
/* The human (min) just made a move, so we evaluate that move here */ 
if (checkPlayerWin(X_PLAYER, board)) return MIN_INFINITY; 
if (depth > MAX_PLIES) return evalshortcut(O_PLAYER, board);
for &#40;i = 0 ; i < MAX_CHILD_NODES ; i++)
&#123;
  if &#40;getCell&#40;i, board&#41; == EMPTY&#41;
  &#123; 
	 new_board = board; 
	 putCell&#40; O_PLAYER, i, &new_board ); 
	 value = evaluateHumanMove&#40; new_board, depth+1, alpha, beta ); 
	 if &#40;value > max&#41; 
	 &#123; 
	   max = value; 
 	  if &#40;depth == 0&#41; computer_move = i; 
      if &#40;value > alpha&#41; alpha = value; 
/* Prune this subtree by not checking any further successors */ 
 	  if &#40;alpha >= beta&#41; return alpha; 
 	&#125; 
  &#125; 
&#125;
/* No move is possible -- draw */ 
if &#40;max == MIN_INFINITY-1&#41; return DRAW; 
return max; 
&#125; 

[Don]

Many years ago I wrote a tic-tac-toe program and I still have the source code. I think you could learn much from it although it's not written for clarity. But it's so simple that any C expert would quickly be able to figure out what it's doing.

It is fully alpha/beta. No null move pruning or LMR (that's a joke!)

A board position is represented as a single integer, 9 bits for X and 9 bits for O.

Here is the search portion of the program, it's recursive and works by passing a copy of the board recursively. It returns a score and the moves (as well as a principal variation in the pv array.

Sorry it's poorly remarked:

Code: Select all

int  srch(int ttt, int alpha, int beta, int ctm, int *pv)
{
  int  solved[8] = { 0007, 0070, 0700, 0111, 0222, 0444, 0124, 0421 };
  int  fp;
  int  subpv;
  int  shift = 0;
  int  sc = 0;
  int  bsc = -2;
  int  mv;
  int  lmc = 0;

  *pv = -1;    // -1 = no move
  
  if (ctm & 1) shift = 16;
  
  for &#40;mv=0; mv<9; mv++) &#123;

    // legal move?
    if ( (&#40;0x10001 << mv&#41; & ttt&#41; == 0 ) &#123;

      lmc++;

      int  np = ttt | &#40;1 << &#40;mv + shift&#41;);
      
      int  j;
      for &#40;j=0; j<8; j++) &#123;
        if ( &#40;np & &#40;solved&#91;j&#93; << shift&#41;) == &#40;solved&#91;j&#93; << shift&#41; ) &#123;
          *pv = mv;
          return&#40;1&#41;;
        &#125;
      &#125;

      sc = -srch&#40; np, -beta, -alpha, ctm+1, &subpv );

      if &#40;sc > bsc&#41; &#123;
        bsc = sc;
        if &#40;sc >= beta&#41; return&#40;sc&#41;;
        if &#40;bsc > alpha&#41; &#123;
          *pv = mv;
          alpha = bsc;
        &#125;
      &#125;
    &#125;

  &#125;

  if &#40;lmc == 0&#41; return&#40;0&#41;; 
  return&#40;bsc&#41;;
&#125;

Right now, I'm taking an Artificial Intelligence class, and we're doing a program with either the alpha-beta or minimax algorithm. I'm the only person modifying the alpha-beta code that came from the book, and everyone else is using the minimax algorithm.

I've run into a little snag. We're just trying to modify the source from the book to play 5x5 tic-tac-toe with a max depth of greater than or equal to 4. I've gotten the 5x5 portion to work. My professor wanted us to use his heuristic number of wins minus the number of losses. Either my program picks along the bottom row, and blocks wins (by taking forever) or plays in various spots and lets me win.

I can't figure out how to fix that.

Here's the code. It was originally in C, but I'm more fluent in C++ so I'm having it compile in MSVS as a C++ program. Right now it lets you win if you pick 12, 22, 17, 7, and 2 in that order.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHILD_NODES 25
#define MAX_PLIES 4

#define EMPTY 0
#define X_PLAYER 1
#define O_PLAYER 2

#define MAX_INFINITY 100
#define DRAW 0
#define MIN_INFINITY -100

int boards_checked;
int evalshortcut(int player, unsigned long long board);
int checkpossiblewins(int player, unsigned long long board);
int checkpossiblelosses(int player, unsigned long long board);

int getCell( int cell, unsigned long long board )
{
return ((board >> (cell*2)) & 0x3);
}

void putCell( int player, int cell, unsigned long long *board )
{
*board |= (( (unsigned long long) player << (cell*2)));
return;
}


char convert( int contents )
{
if (contents == X_PLAYER) return 'X';
else if (contents == O_PLAYER) return 'O';

return ' ';
}


void emitBoard( unsigned long long board )
{
/* Emit the current board */
printf("\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(24,board)),
convert(getCell(23,board)),
convert(getCell(22,board)),
convert(getCell(21,board)),
convert(getCell(20,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(19,board)),
convert(getCell(18,board)),
convert(getCell(17,board)),
convert(getCell(16,board)),
convert(getCell(15,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(14,board)),
convert(getCell(13,board)),
convert(getCell(12,board)),
convert(getCell(11,board)),
convert(getCell(10,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n",
convert(getCell(9,board)),
convert(getCell(8,board)),
convert(getCell(7,board)),
convert(getCell(6,board)),
convert(getCell(5,board)) );
printf("------------------\n");
printf(" %c | %c | %c | %c | %c \n\n",
convert(getCell(4,board)),
convert(getCell(3,board)),
convert(getCell(2,board)),
convert(getCell(1,board)),
convert(getCell(0,board)) );

return;
}


void getHumanMove( unsigned long long *board )
{
int selection;

/* Get human move */
while (1) {
printf("Select a move (24=upper-left, 0=lower-right): ");
scanf("%d", &selection);
printf("\n");
if (selection < MAX_CHILD_NODES) {
if (getCell(selection, *board) == EMPTY) break;
printf("cell taken -- choose again.\n");
}
}

putCell( X_PLAYER, selection, board );

return;
}


#define MAX_TESTS 12

typedef struct {
unsigned char test[5];
} test_t;

const test_t tests[MAX_TESTS]={
{{ 24, 23, 22, 21, 20 }},
{{ 19, 18, 17, 16, 15 }},
{{ 14, 13, 12, 11, 10 }},
{{ 9, 8, 7, 6, 5 }},
{{ 4, 3, 2, 1, 0 }},

{{ 24, 19, 14, 9, 4 }},
{{ 23, 18, 13, 8, 3 }},
{{ 22, 17, 12, 7, 2 }},
{{ 21, 16, 11, 6, 1 }},
{{ 20, 15, 10, 5, 0 }},

{{ 24, 18, 12, 6, 0 }},
{{ 20, 16, 12, 8, 4 }} };


int checkPlayerWin(int player, unsigned long long cur_board)
{
int i;

for (i = 0 ; i < MAX_TESTS ; i++) {

if ((getCell(tests.test[0], cur_board) == player) &&
(getCell(tests.test[1], cur_board) == player) &&
(getCell(tests.test[2], cur_board) == player) &&
(getCell(tests.test[3], cur_board) == player) &&
(getCell(tests.test[4], cur_board) == player)) return 1;
}

return 0;
}


short evaluateHumanMove( unsigned long long board, int depth,
int alpha, int beta )
{
int i, value;
unsigned long long new_board;
short min = MAX_INFINITY+1;

short evaluateComputerMove( unsigned long long, int, int, int );

boards_checked++;

/* The computer (max) just made a move, so we evaluate that move here */
if (checkPlayerWin(O_PLAYER, board)) return MAX_INFINITY;

for (i = 0 ; i < MAX_CHILD_NODES ; i++) {

if (getCell(i, board) == EMPTY) {

new_board = board;
putCell( X_PLAYER, i, &new_board );

value = evaluateComputerMove( new_board, depth+1, alpha, beta );

if (value < min) {
min = value;
}

if (value < beta) beta = value;

/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return beta;

}

}

/* No move is possible -- draw */
if (min == MAX_INFINITY+1) {
return DRAW;
}

return min;
}


int computer_move;
int moves = 0;

short evaluateComputerMove( unsigned long long board, int depth, int alpha, int beta )
{
int i, value;
unsigned long long new_board;
short max = MIN_INFINITY-1;

boards_checked++;

/* The human (min) just made a move, so we evaluate that move here */
if (checkPlayerWin(X_PLAYER, board)) return MIN_INFINITY;

for (i = 0 ; i < MAX_CHILD_NODES ; i++)
{
if (getCell(i, board) == EMPTY) {

new_board = board;
putCell( O_PLAYER, i, &new_board );

if(depth > MAX_PLIES)
{
value = evalshortcut(O_PLAYER, new_board);
if (value > max)
{
max = value;
if (depth == 0) computer_move = i;
}
if (value > alpha) alpha = value;
/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return alpha;

computer_move = i;
}
else
{
value = evaluateHumanMove( new_board, depth+1, alpha, beta );
}
if (value > max)
{
max = value;
if (depth == 0) computer_move = i;
}

if (value > alpha) alpha = value;
/* Prune this subtree by not checking any further successors */
if (alpha >= beta) return alpha;
}
}
/* No move is possible -- draw */
if (max == MIN_INFINITY-1)
{
return DRAW;
}

return max;
}


void getComputerMove( unsigned long long *board )
{
boards_checked = 0;

evaluateComputerMove( *board, 0, MIN_INFINITY-1, MAX_INFINITY+1 );

printf("move is %d (boards checked %d)\n", computer_move, boards_checked);

putCell( O_PLAYER, computer_move, board );
moves++;

return;
}

int evalshortcut(int player, unsigned long long board)
{
int possiblewins = checkpossiblewins(player, board);
int possiblelosses = checkpossiblelosses(player, board);

return (possiblewins - possiblelosses);
}

int checkpossiblewins(int player, unsigned long long board)
{
int wins = 0;

for (int i = 0; i < MAX_TESTS; i++)
{
if (((getCell(tests.test[0], board) == O_PLAYER) ||
(getCell(tests.test[0], board) == EMPTY)) &&
((getCell(tests.test[1], board) == O_PLAYER) ||
(getCell(tests.test[1], board) == EMPTY)) &&
((getCell(tests.test[2], board) == O_PLAYER) ||
(getCell(tests[i].test[2], board) == EMPTY)) &&
((getCell(tests[i].test[3], board) == O_PLAYER) ||
(getCell(tests[i].test[3], board) == EMPTY))&&
((getCell(tests[i].test[4], board) == O_PLAYER) ||
(getCell(tests[i].test[4], board) == EMPTY)))
{
wins++;
}
}

return wins;
}

int checkpossiblelosses(int player, unsigned long long board)
{
int losses = 0;

for (int i = 0 ; i < MAX_TESTS ; i++)
{
if (((getCell(tests[i].test[0], board) == X_PLAYER) ||
(getCell(tests[i].test[0], board) == EMPTY)) &&
((getCell(tests[i].test[1], board) == X_PLAYER) ||
(getCell(tests[i].test[1], board) == EMPTY)) &&
((getCell(tests[i].test[2], board) == X_PLAYER) ||
(getCell(tests[i].test[2], board) == EMPTY)) &&
((getCell(tests[i].test[3], board) == X_PLAYER) ||
(getCell(tests[i].test[3], board) == EMPTY)) &&
((getCell(tests[i].test[4], board) == X_PLAYER) ||
(getCell(tests[i].test[4], board) == EMPTY)))
{
losses++;
}
}

return losses;
}

int main()
{
unsigned long long cur_board = 0;
int won = 0;

while (!won) {

emitBoard( cur_board );

getHumanMove( &cur_board );

emitBoard( cur_board );

won = checkPlayerWin( X_PLAYER, cur_board );
moves++;

if ((!won) && (moves == MAX_CHILD_NODES)) {
printf("draw\n");
break;
}

if (!won) {

/* Build the game tree */
getComputerMove( &cur_board );

won = checkPlayerWin( O_PLAYER, cur_board );

if (won) {
printf("\nYou lose!\n");
}

} else {

printf("\nYou win!\n");

}

}

emitBoard( cur_board );

return 0;
}

Any insights would be much appreciated.

[Don]

Many years ago I wrote a tic-tac-toe program and I still have the source code. I think you could learn much from it although it's not written for clarity. But it's so simple that any C expert would quickly be able to figure out what it's doing.

It is fully alpha/beta. No null move pruning or LMR (that's a joke!)

A board position is represented as a single integer, 9 bits for X and 9 bits for O.

Here is the search portion of the program, it's recursive and works by passing a copy of the board recursively. It returns a score and the moves (as well as a principal variation in the pv array.

Sorry it's poorly remarked:

Code: Select all

int  srch(int ttt, int alpha, int beta, int ctm, int *pv)
{
  int  solved[8] = { 0007, 0070, 0700, 0111, 0222, 0444, 0124, 0421 };
  int  fp;
  int  subpv;
  int  shift = 0;
  int  sc = 0;
  int  bsc = -2;
  int  mv;
  int  lmc = 0;

  *pv = -1;    // -1 = no move
  
  if (ctm & 1) shift = 16;
  
  for &#40;mv=0; mv<9; mv++) &#123;

    // legal move?
    if ( (&#40;0x10001 << mv&#41; & ttt&#41; == 0 ) &#123;

      lmc++;

      int  np = ttt | &#40;1 << &#40;mv + shift&#41;);
      
      int  j;
      for &#40;j=0; j<8; j++) &#123;
        if ( &#40;np & &#40;solved&#91;j&#93; << shift&#41;) == &#40;solved&#91;j&#93; << shift&#41; ) &#123;
          *pv = mv;
          return&#40;1&#41;;
        &#125;
      &#125;

      sc = -srch&#40; np, -beta, -alpha, ctm+1, &subpv );

      if &#40;sc > bsc&#41; &#123;
        bsc = sc;
        if &#40;sc >= beta&#41; return&#40;sc&#41;;
        if &#40;bsc > alpha&#41; &#123;
          *pv = mv;
          alpha = bsc;
        &#125;
      &#125;
    &#125;

  &#125;

  if &#40;lmc == 0&#41; return&#40;0&#41;; 
  return&#40;bsc&#41;;
&#125;

I just noticed that the principal variation it returns is one move only, which is all that is needed to get a move from the routine. But it would very simple to pass an array of integers and propagate them with a simple array copy. It's slightly tricky if you've never done it before, but I can make a version that does this if you are interested, I think it would add only 1 or 2 lines of code.

[Don]

By the way, HG Muller could probably write this in one line of code

Many years ago I wrote a tic-tac-toe program and I still have the source code. I think you could learn much from it although it's not written for clarity. But it's so simple that any C expert would quickly be able to figure out what it's doing.

It is fully alpha/beta. No null move pruning or LMR (that's a joke!)

A board position is represented as a single integer, 9 bits for X and 9 bits for O.

Here is the search portion of the program, it's recursive and works by passing a copy of the board recursively. It returns a score and the moves (as well as a principal variation in the pv array.

Sorry it's poorly remarked:

Code: Select all

int  srch(int ttt, int alpha, int beta, int ctm, int *pv)
{
  int  solved[8] = { 0007, 0070, 0700, 0111, 0222, 0444, 0124, 0421 };
  int  fp;
  int  subpv;
  int  shift = 0;
  int  sc = 0;
  int  bsc = -2;
  int  mv;
  int  lmc = 0;

  *pv = -1;    // -1 = no move
  
  if (ctm & 1) shift = 16;
  
  for &#40;mv=0; mv<9; mv++) &#123;

    // legal move?
    if ( (&#40;0x10001 << mv&#41; & ttt&#41; == 0 ) &#123;

      lmc++;

      int  np = ttt | &#40;1 << &#40;mv + shift&#41;);
      
      int  j;
      for &#40;j=0; j<8; j++) &#123;
        if ( &#40;np & &#40;solved&#91;j&#93; << shift&#41;) == &#40;solved&#91;j&#93; << shift&#41; ) &#123;
          *pv = mv;
          return&#40;1&#41;;
        &#125;
      &#125;

      sc = -srch&#40; np, -beta, -alpha, ctm+1, &subpv );

      if &#40;sc > bsc&#41; &#123;
        bsc = sc;
        if &#40;sc >= beta&#41; return&#40;sc&#41;;
        if &#40;bsc > alpha&#41; &#123;
          *pv = mv;
          alpha = bsc;
        &#125;
      &#125;
    &#125;

  &#125;

  if &#40;lmc == 0&#41; return&#40;0&#41;; 
  return&#40;bsc&#41;;
&#125;

I just noticed that the principal variation it returns is one move only, which is all that is needed to get a move from the routine. But it would very simple to pass an array of integers and propagate them with a simple array copy. It's slightly tricky if you've never done it before, but I can make a version that does this if you are interested, I think it would add only 1 or 2 lines of code.

[JuLieN]

By the way, HG Muller could probably write this in one line of code

A line of 212 chars, including 182 brackets