/*
 * Othello playing program.
 * 
 * Written in 1993 by Bennett Todd, with some help by John White, who
 * designed the finite state automaton for edge strategy.
 *
 * Hacked by Evan Harris in 1994-1998, to enable a more general user
 * interface.
 */

/*

    Plays othello using alpha-beta search.

    Switches:
    -f  gofirst (default=no)
    -bn allocate n boards: default=64, grows as branching factor*depth
    -dn look ahead n moves: default is variable, must be greater than 0
    -rn reverse the initial board in various ways:

        -r1 reverse initial board setup; 'o' still goes first
        -r2 reverse initial board setup; 'x' goes first
        -r3  normal initial board setup; 'x' goes first

*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <getopt.h>

#include "othello.h"

#define DEBUG_LEVEL 1

/*
    About the following defines:
    BEST and WORST are upper and lower bounds, respectively, on the
        worth of a board.
    MAXSONS is the maximum number of possible moves from any given board,
        used to size the sons array in a board node.
    EMPTY, MINE, and HIS are values for the possible states of a square
        on an othello board. In the original code, they were used as an
        enumerated type, after the fashion of PASCAL. However, during
        the process of optimizing the program, It was observed that
        in the code
            <expression>!=EMPTY
        !=EMPTY doesn't change the logical value of the expression, and
            <expression>==EMPTY is equivalent to !<expression>
        Thus the contents of board cells are sometimes used as boolean
        variables.
        What's worse, many nested if expressions and switch statements
        were removed by using values of board cells as subscripts into
        arrays, a process which altogether exceeded any reasonable bounds
        in the finite state machine found in the function worth.
*/

#define TRUE 1
#define FALSE 0
#define WORST -1000
#define BEST   1000
#define MAXSONS 30
#define EMPTY '\0'
#define MINE  '\1'
#define HIS   '\2'

typedef struct boardtype
{
    struct boardtype *sons[MAXSONS];    /* pointers to descendants  */
    int val;                            /* worth of board position  */
    char *array[8];                     /* the board itself         */
}
BOARD;

BOARD *freeboards; /* pointer to head of linked list of free boards */

int maxdepth[60]=   /* maxdepth[movenumber] is the depth that alphabeta */
    {               /* will search on the movenumber'th move            */
        1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
        3, 3, 3, 3, 3, 3, 4, 7, 6, 5, 4, 3, 2, 1, 1
    },
    maxboards=64,   /* default number of boards to allocate     */
    reversed=FALSE, /* switch to reverse initial board position */
    movenumber=0,   /* counter for what move we are on          */
    time_out[3]=    /* timeout points, to hurry up if we are in */
    {               /* danger of overshooting 30 seconds        */
        2000,2500,2800
    },
    start_dive=52,  /* the movenumber on which to switch worths */
    gofirst=FALSE,  /* by default, the opponent goes first      */
    max,            /* who is playing at any given instant      */
    (*worth)(),     /* pointer to the current worth function    */
    i_tran[64]=     /* i subscript generator                    */
    {
        0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1,
        2, 2, 2, 2, 2, 2, 2, 2,
        3, 3, 3, 3, 3, 3, 3, 3,
        4, 4, 4, 4, 4, 4, 4, 4,
        5, 5, 5, 5, 5, 5, 5, 5,
        6, 6, 6, 6, 6, 6, 6, 6,
        7, 7, 7, 7, 7, 7, 7, 7
    },
    j_tran[64]=     /* j subscript generator                    */
    {
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7
    };

long lasttime;          /* time tick holder, for stopwatch  */

/*
    The array moves, declared below, is an array of pointers to arrays
    of pointers to arrays of subscripts, ranging from 0 to 63.
    A board is declared in the structure declaration above to be represented
    by an array of 8 pointers to arrays of chars (8 per array). In my
    initialization of the board structures, I explicitly allocate the row
    arrays consecutively; therefore, board->array[0] can be taken as a
    pointer to an array 64 long of chars, containing the cells of the board.
    board->array[0][moves[i][j][k]] is the k-th step in th j-th direction
    from the i-th cell in board. Moves is 64 long; moves[i] is variable
    length (one for each direction in which a move is possible) delimited
    with NULLs, and move[i][j] is variable length, delimited by i. In
    other words, to walk as far as possible in the j-th direction from
    cell i, you could use
        for(k=0;i!=moves[i][j][k];k++)
    though I didn't, since I use pointers to walk through the array.

*/

char **moves[64];


void initmoves(), initfree(), sort();
void move(), reclaim(), score(), putboard();
int getmove(), allsons(), alphabeta(), worth_1(), worth_2();


static struct option long_options[] = {
    { "computer-starts", 0, NULL, 'c' },
    { "search-depth", 1, NULL, 'd' },
    { "reverse-colours", 0, NULL, 'r' },
    { "reverse-colors", 0, NULL, 'r' },
    { "help", 0, NULL, 'H' }
};


int
main(argc,argv)
int argc;
char **argv;
{
    int temp, end = 0, endmove = 0, reversecolors = 0, oldmove;

    BOARD *root,            /* the root of the current tree, changed by     */
          *firstboard();    /* both move() and getmove()                    */

    int c, depth, err = 0;
    int option_index;
    
    while ((c = getopt_long(argc, argv, "cd:rH",
			    long_options, &option_index)) != -1) {
	switch (c) {
	  case 'c':
	    gofirst = TRUE;
	    break;
	  case 'd':
	    depth = atoi(optarg);
	    if (depth >= 1 && depth <= 9) {
		maxdepth[0] = depth;
		start_dive = 60 - depth;
		for(temp = 0; temp < 59; temp++)
		    maxdepth[temp+1] = maxdepth[temp];
	    } else {
		err++;
	    }
	    break;
	  case 'r':
	    reversecolors = TRUE;
	    break;
	  case 'H':
	  case '?':
	    err++;
	    break;
	}
    }
    if (err) {
	fprintf(stderr, "Usage: %s [-c] [-d N] [-r] [-H]\n", argv[0]);
	fprintf(stderr, "  -c     --computer-starts   computer plays first\n");
	fprintf(stderr, "  -d N   --search-depth=N    set search depth to N (1-9),\n");
        fprintf(stderr, "                             default: 3 (higher in endgame)\n");
	fprintf(stderr, "  -r     --reverse-colours   reverse chip colours\n");
	fprintf(stderr, "  -H     --help              print this help message\n");
	exit(EXIT_FAILURE);
    }
    
    /* call various initialization routines         */
    worth=worth_1;  /* the main heuristic function  */

    initmoves();    /* initialize the array moves   */

    initfree();         /* set up free boards list  */

    InitDisplay(reversecolors);
    
    while (!end) {
	root=firstboard();	/* set up to play the game  */

	lasttime=clock();	/* and mark time            */

	if(gofirst)
	    move(&root);
	else
	    putboard(root);

	oldmove=(-1);		/* dummy out endgame flag, it's only starting now! */

	/* main game loop */
	while(movenumber<60 && movenumber!=oldmove) /* game lasts 60 moves, */
	{			/* unless no one can move   */
	    if(movenumber>start_dive) /* change to h*, the "true" h function */
	    {
		time_out[0]=time_out[1];
		worth=worth_2;	/* only computable by looking to the end*/
	    }
	    oldmove=movenumber;	/* set to recognize if no one can move  */
	    endmove = getmove(&root);	/* get a move from the user */
	    if (endmove < 0) {
		movenumber = 60;
	    } else {
		move(&root);	/* make a move              */
	    }
	}
	if (endmove >= 0) {
	    score(root);	/* report the result */
	}

	while (endmove >= 0)
	    endmove = GetMove();
	switch (endmove) {
	  case NEWGAME:
	    NewGame();
	    worth=worth_1;  /* the main heuristic function  */
	    time_out[0]=2000;
	    movenumber = 0;
	    break;
	  case QUIT:
	    end = 1;
	    break;
	  default:
	    break;
	}
    }

    EndDisplay();

    return 0;
}

/*
    move makes a move on the (called-by-reference) board. It first
    expands all possible moves with a call to allsons, with max set to
    true (moves is trying to maximize the evaluation function), then uses
    alphabeta to evaluate each possibility, picking the best.
    Move is different from alphabeta mostly in that
        a)  it always and only plays as max
        b)  it must keep track of the actual boards, and not just
            their values (alphabeta always reclaims as soon as possible)
        c)  it is in charge of initializing everything for the search
        d)  rather than returning a backed up value, it simply outputs the
            move (and some other junk) and resets the root to point to the
            new move.
*/

void
move(board)
BOARD **board;
{
    BOARD *tempboard;

    int i,
        n,
        rush=0,         /* used to panic stop short of 30 seconds           */
        temp,
        alpha=WORST,    /* the root is max, and therefore has an alpha value*/
        best=WORST-1,   /* must be worst than the worst possible value, so  */
                        /* that a move will be picked even if they are all  */
                        /* the worst.                                       */
        bestboard;      /* subscript of the best board seen so far          */

    char *t1,           /* a couple of temporary pointers used to           */
         *t2;           /* figure out exactly where I moved.                */

    max=TRUE;   /* let us get this straight, once and for all... */

    /* read the following as "if( <number of sons found> == 0)" */
    if(!(n=allsons(*board)))    /* "==0" is equivalent to "!"   */
    {
	/* computer cannot move - warning ? */

        return;
    }

    ThinkingOn();

    /* for every son */
    for(i=0;i<n;i++)
    {

        max=FALSE;  /* think as my opponent would think */

        /* if this is better than the best we have seen so far */
        if(best<(temp=alphabeta((*board)->sons[i],maxdepth[movenumber],
                                alpha,BEST)))
        {
            best=alpha=temp;
            bestboard=i;
        }

	Poll();

        /* make sure we do not under any circumstances exceed 30 seconds */
        if((clock()-lasttime) * 100 / CLOCKS_PER_SECOND > time_out[rush])
        {
            if(rush==2)
                goto outta_here;

            rush++;
            maxdepth[movenumber]--;
        }
    }

outta_here:
    t1=(*board)->array[0]-1;                    /* set up pointers  */
    t2=(*board)->sons[bestboard]->array[0]-1;   /* for comparison   */
loop:
    while(*++t1==(*++t2));  /* find different squares           */
    if(*t1) /* then this square was flipped, not actually moved */
        goto loop;  /* so keep trying                           */

    /* temp gets the 0-63 subscript of the move */
    temp=t1-(*board)->array[0];

    ThinkingOff();

    ShowTime(((double)(clock()-lasttime))/CLOCKS_PER_SECOND);
    
    putboard((*board)->sons[bestboard]);

    /* now reclaim unneeded boards, reset the root, and count this move */
    for(i=0;i<n;i++)
        if(i!=bestboard)
            reclaim((*board)->sons[i]);
    tempboard=(*board)->sons[bestboard];
    reclaim(*board);
    *board=tempboard;
    movenumber++;
}

/*
    alphabeta takes four parameters: the board to evaluate,
    the depth to search, and the current alpha and beta values.
    It returns the worth of the board, obtained by backing up
    the values seen at the bottom of the search.
    It plays maximizing or minimizing, based on the global
    boolean variable max.
*/
    
int alphabeta(current,depth,alpha,beta)
BOARD *current;
int depth,
    alpha,
    beta;
{
    int i,
        n,
        temp,
        best,
        curmax;     /* contains the current value of the global "max",  */
                    /* negated (to minimize the number of negations)    */

    BOARD *curson;  /* contains the son being examined currently        */

    /* if no sons can be found */
    if(!(n=allsons(current)))
    {
        max=!max;                       /* then try as the other guy    */
        if(!(n=allsons(current)))       /* and if he can't move         */
            return(worth_2(current));   /* return the final value       */
    }

    best=max?WORST:BEST;    /* start off assuming the worst     */
    depth--;                /* keep track of depth              */
    curmax=!max;            /* and max through recursive calls  */

    /* for every son */
    for(i=0;i<n;i++)
    {
        max=curmax;
        curson=current->sons[i];

	Poll();

        /*
            This statement does it all. Recurse, propogating correct alpha
            and beta values (only one of which can change at any given node)
            unless of course the recursion has terminated, in which case we
            use the value of the node, as evaluated by worth when allsons
            created the node. Put the value thus obtained into temp, and
            compare it with the best value seen so far. The sense of
            comparison is reversed if curmax is true (bitwise xor is all
            right if both booleans are "pure"--0 or 1).
        */
        if(curmax^best<(temp=depth?
                                (curmax?
                                    alphabeta(curson,depth,alpha,best)
                                    :alphabeta(curson,depth,best,beta))
                                :curson->val))
        {
            /* check for an alphabeta "prune" of the tree */
            if(curmax?(temp<=alpha):(temp>=beta))
            {
                while(i<n)                      /* clean up         */
                    reclaim(current->sons[i++]);
                return(temp);                   /* and pack it in   */
            }
            else
                best=temp;  /* remember the best value seen so far  */
        }
        reclaim(curson);
    }
    return(best);
}

/*
    Simple-minded free space management. Keep a bunch of boards on a linked
    list. When one is needed, take it off the top. When no longer needed,
    insert it at the top. Optionally, check for out-of-boards (The converse,
    attempting to check for freeing of space not taken from the freeboard
    list, seemed to be too difficult. Perhaps I could have kept around high-
    water and low-water mark pointers to the space of legal board pointers.),
    and accumulate statistics.
*/

BOARD *newboard()
{
    BOARD *temp;

#if DEBUG_LEVEL > 0
    if(!freeboards)
        initfree();
#endif

    temp=freeboards;
    freeboards=freeboards->sons[0];
    temp->sons[0]=NULL;
    return(temp);
}

void
reclaim(board)
BOARD *board;
{
    board->sons[0]=freeboards;
    freeboards=board;
}

/*
    Shell sort taken from K&R, sorts the n boards in the array into ascending
    or descending order based on the global boolean max, sorting on the
    values contained in the value member of each board structure. This sort
    focuses the alphabeta search significantly, increasing the pruning enough
    to cut depth 4 search time by approximately 65 percent.
*/

void
sort(boards,n)
BOARD **boards;
int n;
{
    int i,
        j,
        gap,
        jpg; /* temporary storage hold j+gap */

    BOARD *tempboard;

    for(gap=n/2;gap>0;gap/=2)
        for(i=gap;i<n;i++)
            for(j=i-gap;j>=0 &&
                    (max?(boards[j]->val<boards[jpg=j+gap]->val):
                    (boards[j]->val>boards[jpg=j+gap]->val));j-=gap)
            {
                tempboard=boards[j];
                boards[j]=boards[jpg];
                boards[jpg]=tempboard;
            }
}

/*
    Initialize a linked list of free boards. Each board has an array of
    8 pointers to rows of 8 bytes each. Allocate space for the rows, and
    initialize the pointer arrays to point to the rows. The rows in a board
    are explicitly allocated contiguously, so it is possible (and turns out
    to enhance efficiency at the expense of comprehensability) to treat
    a board as a single array of 64 bytes, pointed to by the pointer to
    the first row. Optionally, produce statistics on allocation of memory.
*/

void
initfree()
{
    int i,j;

    char *boardspace;

    freeboards=((BOARD *) calloc(maxboards,sizeof(BOARD)));
    if(!freeboards)
    {
        fprintf(stderr, "Error: board structure allocation failed.\n");
        exit(1);
    }
    boardspace=calloc(maxboards,sizeof(char [64]));
    if(!boardspace)
    {
        fprintf(stderr, "Error: board freespace allocation failed.\n");
        exit(1);
    }

    /* thread linked list and arrange the row pointer arrays */
    for(i=0;i<maxboards;i++)
    {
	if (i>0)
	{
	    freeboards[i-1].sons[0]=freeboards+i;
	}
        for(j=0;j<8;j++)
	{
	    freeboards[i].array[j]=boardspace+64*i+8*j;
	}
    }
    freeboards[maxboards-1].sons[0]=NULL;

    /* We might be called again, if he needs more boards */
    maxboards=10;
}

/*
    The array moves contains information about the shape of a board, in
    a fashion which simplifies the checking of loop conditions in the
    code which is examining a board for a move, and flipping the resulting
    pieces. Specifically, moves (which is a byte array because it needs
    no large numbers) is used as follows:
        moves[i][j][k] refers to the subscript of the
            k-th square, in the
            j-th direction, from the
            i-th square on the board.
    Moves is 64 long; moves[i] is variable length delimited by NULL; and
    moves[i][j] is variable length delimited by the value of i.
*/

void
initmoves()
{
    int i,
        j,
        k,
        l,
        m,
        n;

    char **pointers,
         *bytes;

    /* 484 and 2016 are computed by rote */
    pointers=((char **) calloc(484,sizeof(char **)));
    if(pointers==NULL)
    {
        fprintf(stderr, "Error in initmoves: cannot allocate pointers.\n");
        exit(1);
    }
    bytes=calloc(2016,sizeof(char));
    if(bytes==NULL)
    {
        fprintf(stderr, "Error in initmoves: cannot allocate bytes.\n");
        exit(1);
    }

    /* for each square on the board */
    for(i=0;i<8;i++) for(j=0;j<8;j++)
    {

        /* set the corresponding entry of moves to some free pointers */
        moves[i*8+j]=pointers;

        /* for each direction */
        for(k=(-1);k<2;k++) for(l=(-1);l<2;l++)
            if(k || l)  /* if neither k or l we aren't going anywhere */
            {
                *pointers=bytes; /* point to some free bytes */
                /* let m and n walk to the edge of the board */
                for(m=i+k,n=j+l;m>=0 && m<8 && n>=0 && n<8;m+=k,n+=l)
                    (*bytes++)=m*8+n;
                if(m!=i+k || n!=j+l)
                /* then we managed to walk somewhere */
                {
                    (*bytes++)=i*8+j;   /* terminate bytes list             */
                    pointers++;         /* get pointer for next direction   */
                }
            }
        (*pointers++)=NULL; /* terminate pointers list */
    }
}

/*
    allsons finds all sons for the board which is its parameter, sets the
    array of pointers to sons to point to new boards containing the resulting
    boards, sets the val member of each son board structure to the value as
    evaluated by worth, and sorts the sons in order, to focus the alphabeta
    search. It returns the number of sons it found.
*/

int allsons(pos)
BOARD *pos;
{
    int cur=0, /* son next to allocate */
        i;

    char mine,          /* mine, from the point of the current player   */
         hisn,          /* likewise                                     */
         whose,         /* temporary variable--keep from recomputing    */
         *board,        /* pointer into the board array                 */
         ***move_ptr,   /* pointer into the moves array                 */
         **dir_ptr,     /* pointer into moves[i] arrays of directions   */
         *sub_ptr;      /* pointer into moves[i][j] arrays of subscrtips*/

    BOARD *resultof(),  /* create a board resulting from making a move  */
          *curson;      /* point to current son                         */

    mine=max?MINE:HIS;
    hisn=max?HIS:MINE;
    board=pos->array[0];

    /* for(i=0;i<64;i++) with move_ptr=moves[i] */
    for(i=0,move_ptr=moves;i<64;i++,move_ptr++)
    {
        /* if(board[i]==EMPTY) */
        if(!board[i])
            /* for(j=0;moves[i][j]!=NULL;j++) with sub_ptr=moves[i][j] */
            for(dir_ptr=(*move_ptr);sub_ptr=(*dir_ptr++);)
                /* if he owns the cell in the j-th direction */
                if(board[*sub_ptr++]==hisn)
                {
                    /* scan until edge of board or end of list */
                    /*
                        NOTE: moves[i][j] is delimited by i, so the edge of
                        the board looks like a cell containing the same thing
                        as board[i], which must be empty if I got into this
                        code; therefore, hitting edge of board looks just
                        like seeing a space at the end of the string of
                        opponents pieces, which means I cannot capture them.
                    */
                    while((whose=board[*sub_ptr++])==hisn);
                    if(whose==mine) /* then we have a possible capture */
                    {
                        curson=pos->sons[cur++]=resultof(pos,i);
                        curson->val=(*worth)(curson);
                        goto endit; /* don't look in other directions */
                    }
                }
endit:  ;
    }

#if DEBUG_LEVEL > 0
    if(cur>MAXSONS)
    {
        fprintf(stderr,"allsons: I needed %d sons for",cur+1);
        putboard(pos);
        fprintf(stderr,"allsons: but I only am alotted %d.\n",MAXSONS);
        printf("Sorry, boss.\n");
        exit(0);
    }
#endif

    sort(pos->sons,cur);
    pos->sons[cur]=0;
    return(cur);
}

/*
    Resultof makes a copy of the board (using _move(), a fast block
    move routine that comes with Mark DeSmet's Cware C compiler, if
    the code is being generated for an IBM-PC) and flips all squares
    thet need to be flipped based on making a move at position x
    (where x ranges for 0 to 63), takes the square at x, and returns
    a pointer to the resulting board. It calls newboard(), the free
    board server.
*/

BOARD *resultof(father,x)
BOARD *father;
int x;
{
    int mine,   /* mine, from the point of view of the current player   */
        hisn;   /* likewise                                             */

    char *board,    /* pointer into the board array                     */
		 *tmpptr,	/* pointers for copying the board in portble C		*/
		 *tmplim,
         **dir, /* pointer for moves[x][j], a direction                 */
         *sub;  /* pointer to a subscript, moves[i][j][k]               */

    BOARD *newboard(),
          *temp;

    mine=max?MINE:HIS;
    hisn=max?HIS:MINE;
    temp=newboard();

    /* Copy the board. Use a block move on the PC   */
    board=temp->array[0];
    tmpptr=father->array[0];
    tmplim=board+64;
    while(board<tmplim)
        (*board++)=(*tmpptr++);

    board=temp->array[0];

    /* for(j=0;moves[x][j]!=NULL;j++) */
    for(dir=moves[x];*dir;dir++)
        /* if the cell in the j-th direction is his  */
        if(board[**dir]==hisn)
        {
            sub=(*dir);

            /* scan as long as the pieces are his   */
            /* (Please see discussion in allsons    */
            while(board[*++sub]==hisn);

            /* if the search was terminated by a piece of mine */
            if(board[*sub]==mine)
            {
                /* do the same scan, flipping pieces as you go */
                sub=(*dir);
                while(board[*sub]==hisn)
                    board[*(sub++)]=mine;
            }
        }

    /* put a piece where we actually moved */
    board[x]=mine;
    return(temp);
}

/*
    firstboard() returns a pointer to a board set up in the initial position.
    It is the only routine that actually zeros out a board array, and sets
    things up in it. The remainder of the boards are made by copying and
    then changing, by resultof(). The initial position is reversed if we
    are going first (because what is stored is not x's and o's, but MINE
    and HIS) and can be reversed again by a reverse switch.
*/

BOARD *firstboard()
{
    BOARD *temp,
          *newboard();

    int i,
        j;

    temp=newboard();

    /* zero out the array */
    for(i=0;i<8;i++)
        for(j=0;j<8;j++)
            temp->array[i][j]=EMPTY;
    /* put the start position into the cells */
    /* either gofirst or reversed can switch the initialization */
    temp->array[3][3]=temp->array[4][4]=(!(gofirst^reversed))?MINE:HIS;
    temp->array[3][4]=temp->array[4][3]=(!(gofirst^reversed))?HIS:MINE;

    return(temp);
}

/*
    Getmove gets a move from the user. 
*/

int
getmove(board)
BOARD **board;
{
    int i,
        j,
        k,
        n;
    int move;

    BOARD *resultof(),
          *temp;

    max=FALSE;

    /* if(<the number of sons found>==0) */
    if(!(n=allsons(*board)))
    {
	/* player cannot move - warning ? */

        lasttime=clock();
        return 0;
    }

    movenumber++;
#ifdef EVAN0
    if(n==1)
    {
        printf("You have only one move. Press return to continue: ");

        while(getchar()!='\n');

        lasttime=clock();
        temp=(*board)->sons[0];

        reclaim(*board);
        (*board)=temp;
        return;
    }
#endif

    /* get and validity check move */
retry:
    move = GetMove();
    if (move == NEWGAME || move == QUIT) {
	return move;
    }
    lasttime = clock();

    i = move % 8;
    j = move / 8;

    /* if(<position is out of range> || board[i][j]!=EMPTY) */
    if(i<0 || i>7 || j<0 || j>7 || (*board)->array[i][j])
    {
        goto retry;
    }
    /* scan the sons list, looking for a son with this cell occupied    */
    for(k=0;!((*board)->sons[k]->array[i][j]);)
        /* if we have reached the end of the list without finding one   */
        if(++k==n)
        {
            goto retry;
        }

    /* clean up stray sons */
    for(i=0;i<n;i++)
        if(i!=k)
            reclaim((*board)->sons[i]);
    temp=(*board)->sons[k];

    reclaim(*board);
    *board=temp;

    putboard(*board);

    return 0;
}

/*
    Score simply adds up the number of cells owned by each player,
    reports the results, and leaves.
*/

void
score(board)
BOARD *board;
{
    char i,
         sums[3]={0,0,0},
         *ptr;

    ptr=board->array[0];
    for(i=0;i<64;i++)
        sums[(int)*ptr++]++;
    if (sums[MINE] == sums[HIS]) {
	ShowDraw(sums[MINE]);
    } else if (sums[MINE] > sums[HIS]) {
	ShowWin(MINE, sums[MINE], sums[HIS]);
    } else {
	ShowWin(HIS, sums[HIS], sums[MINE]);
    }
}

/*
    Putboard can be used for one or two boards. For one board, make the
    second parameter NULL. It calls a function fast_puts to put the string
    out. This is to allow quick board drawing on a PC.
    Optionally, error checking code can be compiled in, to check for the
    (common) C bug of wandering of into randomn memory locations.
    Throughout the function, realize the "if(new)" is functionally identical
    to "if(new!=NULL)".
*/

void
putboard(new)
BOARD *new;
{
    int i, j;

    PutBoardStart();

    /* for every row */
    for(i=0;i<8;i++)
    {
        /* for every column */
        for(j=0;j<8;j++)
        {
	    PutSquare(j, i, new->array[i][j]);
        }
    }

    PutBoardEnd();
}

/*
    Worth_1 is the worth function containing all the subtle strategic
    heuristic information in the game. It is used until we can start
    looking all the way to the end of the game, at which point the
    optimum heuristic function, h* becomes available. That is called
    worth_2, and is much simpler.
*/

int
worth_1(board)
BOARD *board;
{
    int valsum[3]; /* buckets in which to accumulate the sums       */

    char *ptr,  /* temporary pointers for walking through the array */
         *t;

    static char
        val1[3]={30,0,0},   /* value of (1,1) if (0,0)=0,1,2 */
        val2[3]={ 4,0,0},   /* value of (1,2) if (0,2)=0,1,2 */
        val3[3]={ 5,0,0};   /* value of (1,3) if (0,3)=0,1,2 */

#define ev0 50  /* value of pos 00 (corner)     */
#define ev1 4   /* value of pos 01              */
#define ev2 16  /* value of pos 02              */
#define ev3 12  /* value of pos 03              */
#define sv  20  /* value of a split on the edge */

/*
     50,  4, 16, 12, 12, 16,  4, 50,
      4,-30, -4, -5, -5, -4,-30,  4,
     16, -4,  1,  0,  0,  1, -4, 16,        This is what the board cell
     12, -5,  0,  0,  0,  0, -5, 12,        worth function looks like,
     12, -5,  0,  0,  0,  0, -5, 12,        discounting all dynamic
     16, -4,  1,  0,  0,  1, -4, 16,        dependancies.
      4,-30, -4, -5, -5, -4,-30,  4,
     50,  4, 16, 12, 12, 16,  4, 50
*/

/*
    f[] is a finite state automaton used for edge strategy
    It recognizes two related phenomena, which we call "splits";
    positions where two pieces owned by one player on an edge are

        a) separated by exactly 1 blank, or
        b) separated by 1 or more of the opponent's

    Invented by John White, it is structured as follows:

    f[105] can be viewed as 5 tiers of 7 states, each of which requires
    3 cells for the three possible input values.
    Starting at one corner, you scan along an edge.
    Keep always in mind that the values of board cells are

                        0       EMPTY
                        1       MINE
                        2       HIS

    The states are numbered as follows:

      state         decription                      board
      ----- ----------------------------------      ------

        0   currently scanning through blanks       ... 0
        1   just seen a square of mine              ... 1
        2   just seen a square if his               ... 2
        3   a blank following a square of mine      ... 10
        4   a blank following a square of his       ... 20
        5   one of his following one of mine        ... 12
        6   one of mine following one of his        ... 21

    The following table identifies the transitions between states.
    The numbers down the left, labelling the rows, are the input
    cell values. The numbers across the top are state numbers.
    The contents of a cell in this matrix is the number of the
    state the will be result from the input at the left from the
    state above.

            0       1       2       3       4       5       6
        ---------------------------------------------------------
    0   |   0   |   3   |   4   |   0   |   0   |   4   |   3   |
        ---------------------------------------------------------
    1   |   1   |   1   |   6   |   1 - |   1   |   6 - |   6   |
        ---------------------------------------------------------
    2   |   2   |   5   |   2   |   2   |   2 + |   5   |   5 + |
        ---------------------------------------------------------

    The cells containing postfix "+" or "-" symbols represent
    situations in which we have found one of the key patterns,
    at which point we go to the state indicated in the immediately
    higher or lower tier, respectively. The final value is
    simply the number of the tier we are on at the end, multiplied
    by sv, the split value. Note that each state takes three array elements,
    so the actual contents of the array are three times the state
    numbers shown above, repeated 5 times, offset by the tier start
    subscripts, with special offsets applied to the cells which
    jump tiers. The array v[] is used for the last lookup, since
    we are uninterested in the exact state, but just the tier, and
    since the tier number must be multiplied by sv, we put the resulting
    products in v[]. Finally, the tiers are organized as follows:

              offset    meaning             value
              ------ ----------------       -----
        
                 0       neutral               0
                21        good                sv
                42        bad                -sv
                63      very good            2*sv
                84      very bad            -2*sv

    With this organization, if the state of the machine at time t0 is
    S0 and the input is I0, the state at time t1 is f[S0+I0], and therefore
    the state at time t2 is f[f[S0+I0]+I1] and so forth.
    So, without further ado:
*/

    static char f[105]=
                {
/*----------------------------------------------------------------------------
|state    0         1          2         3         4          5          6   |
|input 0  1  2   0  1  2   0   1  2   0  1  2   0  1  2   0   1  2   0   1  2|
----------------------------------------------------------------------------*/
       0, 3, 6,  9, 3,15, 12, 18, 6,  0,45, 6,  0, 3,27, 12, 60,15,  9, 18,36,
      21,24,27, 30,24,36, 33, 39,27, 21, 3,27, 21,24,69, 33, 18,36, 30, 39,78,
      42,45,48, 51,45,57, 54, 60,48, 42,87,48, 42,45, 6, 54,102,57, 51, 60,15,
      63,66,69, 72,66,78, 75, 81,69, 63,24,69, 63,66,69, 75, 39,78, 72, 81,78,
      84,87,90, 93,87,99, 96,102,90, 84,87,90, 84,87,48, 96,102,99, 93,102,57
                };

/* v is the final pass of f, and is board value instead of next state */

    static int v[105]=
               {
        0,0,0,0,0,0,0,0,0,0,-sv,0,0,0,sv,0,-sv,0,0,0,sv,
        sv,sv,sv,sv,sv,sv,sv,sv,sv,sv,0,sv,sv,sv,2*sv,sv,0,sv,sv,sv,2*sv,
        -sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-2*sv,-sv,-sv,-sv,0,-sv,
                -2*sv,-sv,-sv,-sv,0,
        2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,sv,2*sv,2*sv,
                2*sv,2*sv,2*sv,sv,2*sv,2*sv,2*sv,2*sv,
        -2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,
                -2*sv,-2*sv,-2*sv,-sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-sv
               };

#if DEBUG_LEVEL > 1
    worth_called++;
#endif

    *valsum=valsum[2]=0;    /* clean out buckets    */
    ptr=t=board->array[0];  /* set up pointers      */

    /* and let the finite state automoton roll--one edge in each term */
    valsum[1]=
      v[f[f[f[f[f[f[f[  *t ]+t[ 1]]+t[ 2]]+t[ 3]]+t[ 4]]+t[ 5]]+t[ 6]]+t[ 7]]
     +v[f[f[f[f[f[f[f[  *t ]+t[ 8]]+t[16]]+t[24]]+t[32]]+t[40]]+t[48]]+t[56]]
     +v[f[f[f[f[f[f[f[t[ 7]]+t[15]]+t[23]]+t[31]]+t[39]]+t[47]]+t[55]]+t[63]]
     +v[f[f[f[f[f[f[f[t[56]]+t[57]]+t[58]]+t[59]]+t[60]]+t[61]]+t[62]]+t[63]];

    /*
        if the worth array shown in the comment above actually existed, the
        next 60 or so lines might have been written

            for(i=0;i<64;i++)
                valsum[board[i]]+=worth[i];

        but it doesn't, except in the defined constants ev0 through ev3.
        Besides, it's quicker to execute 60 statements than to go through
        a loop 60 times (no loop control and branching) and this function
        is at the bottom of the recursion, and needs to be fast.
    */

    valsum[(int)*ptr++]+=ev0;
    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr++]+=ev0;

    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr++]-=val1[(int)*t];
    valsum[(int)*ptr++]-=val2[(int)t[2]];
    valsum[(int)*ptr++]-=val3[(int)t[3]];
    valsum[(int)*ptr++]-=val3[(int)t[4]];
    valsum[(int)*ptr++]-=val2[(int)t[5]];
    valsum[(int)*ptr++]-=val1[(int)t[7]];
    valsum[(int)*ptr++]+=ev1;

    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]-=val2[(int)t[16]];
    valsum[(int)*ptr]++;
    ptr+=3;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]-=val2[(int)t[23]];
    valsum[(int)*ptr++]+=ev2;

    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr]-=val3[(int)t[24]];
    ptr+=5;
    valsum[(int)*ptr++]-=val3[(int)t[31]];
    valsum[(int)*ptr++]+=ev3;

    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr]-=val3[(int)t[32]];
    ptr+=5;
    valsum[(int)*ptr++]-=val3[(int)t[39]];
    valsum[(int)*ptr++]+=ev3;

    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]-=val2[(int)t[40]];
    valsum[(int)*ptr]++;
    ptr+=3;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]-=val2[(int)t[47]];
    valsum[(int)*ptr++]+=ev2;

    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr++]-=val1[(int)t[56]];
    valsum[(int)*ptr++]-=val2[(int)t[58]];
    valsum[(int)*ptr++]-=val3[(int)t[59]];
    valsum[(int)*ptr++]-=val3[(int)t[60]];
    valsum[(int)*ptr++]-=val2[(int)t[61]];
    valsum[(int)*ptr++]-=val1[(int)t[63]];
    valsum[(int)*ptr++]+=ev1;

    valsum[(int)*ptr++]+=ev0;
    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr++]+=ev3;
    valsum[(int)*ptr++]+=ev2;
    valsum[(int)*ptr++]+=ev1;
    valsum[(int)*ptr]+=ev0;

    return(valsum[1]-valsum[2]);
}

/*
    If worth_2 is being called, we are looking all the way to the end of
    the game, and we can use the final board as an evaluator: the worth
    of the board is the number of squares more I have than he. This number
    is shifted left 2 to attempt to make the range of values returned
    approximately comparable to worth_1, so that worth_2 can be used
    by alphabeta when we find an early game ending.
*/

int
worth_2(board)
BOARD *board;
{

    int valsum[3]={0,0,0};

    char *ptr;

    ptr=board->array[0];
    /*
        The following 64 lines could have been replaced with
            for(i=0;i<64;i++)
                valsum[board[i]]++;

        but it would have been slower.
    */
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr++]++;
    valsum[(int)*ptr]++;

    /* return((<number I have> - <number he has>) * 2); */
    return((valsum[1]-valsum[2])<<2);
}