markp@valid.UUCP (Mark P.) (11/30/86)
--
This is another Othello (reversi) program. It works, is documented, and
is extremely portable. What more could you ask? Now of course it ain't
pretty, has a primitive user interface (row-column as two-digit number,
88 means start automatic play and 99 means suggest a move), and employs
a recursive alpha-beta search algorithm, but to each his own :-). I wrote
it about 4 years ago, when my C programming ability was in its infancy, so
that's my only excuse. Do enjoy, and keep me informed by e-mail of any
deficiencies or enhancements.
Mark Papamarcos
Valid Logic Systems
hplabs!ridge!valid!markp
------------------------------ cut here ------------------------------
: This is a shar archive.
: Remove everything above this line.
: Run the file through sh, not csh.
: (type `sh this_file')
echo extracting - README
sed 's/^X//' > README << 'SHAR_EOF'
XSince there seems to be an interest in Othello programs, I thought I might
Xcontribute one I wrote as a project for an AI course a few years back. It
Xhas a somewhat primitive human interface, but is quite good and has an
Xeasily tunable board evaluator. Here I include some information on the
Xinner workings of the program, to ease hacking.
X
XNote that, at the time I wrote this program, I didn't know enough about C
Xto do anything non-standard, and it has compiled and run first-time on two
Xdifferent 4.2 Unix machines since. Since it uses nothing outside of the
Xscope of K&R, there should be no portability problems (although I believe
Xit is possible that the current weighting scheme may depend on 'int' being
Xmore than 16 bits, for what it's worth).
X
XOccasionally, the program makes an apparently stupid move. However, it
Xsucceeds in wasting me enough of the remaining games so as to be plenty
Xchallenging. At 5 plies (half-moves of lookahead with alpha-beta pruning),
Xit takes 20-30 seconds worst-case to move on a VAX 780. A Sun-3 or
Xsimilar beast should do somewhat better, and you might want to keep it
Xto 4 plies on lesser machines. The quality of play is very similar.
X
XMany of my ideas on improving the program's performance stem from the
Xbook, "How to win at Othello" by Goro Hasegawa and Maxine Brady. This
Xincludes the particular partitioning of the board into various values,
Xthe "dependency" factors, which reward squares adjacent to corners when
Xthe corner is owned, and the changing of relative weights as the game
Xprogresses.
X[First Harvest/Harcourt Brace Jovanovich, 1977, ISBN 0-15-642215-8]
X
XBefore I delve into implementation details, I would like to apologize
Xin advance for the truly deplorable quality of the actual code-- it hasn't
Xchanged significantly since the initial coding, and there are a few things
X(like the mechanics of data handling by the recursive procedure ply(...))
Xwhich are particularly messy. Sorry. Anyway....
X
XThe board is defined as
X
X CORNER ADJCOR EDGE2 EDGE1 EDGE1 EDGE2 ADJCOR CORNER
X ADJCOR INCOR ADJEDGE ADJEDGE ADJEDGE ADJEDGE INCOR ADJCOR
X EDGE2 ADJEDGE CENT3 CENT2 CENT2 CENT3 ADJEDGE EDGE2
X EDGE1 ADJEDGE CENT2 CENT1 CENT1 CENT2 ADJEDGE EDGE1
X EDGE1 ADJEDGE CENT2 CENT1 CENT1 CENT2 ADJEDGE EDGE1
X EDGE2 ADJEDGE CENT3 CENT2 CENT2 CENT3 ADJEDGE EDGE2
X ADJCOR INCOR ADJEDGE ADJEDGE ADJEDGE ADJEDGE INCOR ADJCOR
X CORNER ADJCOR EDGE2 EDGE1 EDGE1 EDGE2 ADJCOR CORNER
X
X(in some cases ADJ->A,IN->I, but I'm sure you can figure that out)
X
XEach square begins with a weight equal to V_____, and every STAGE moves, it
Xchanges by DV_____. In addition, since squares next to the corners should be
Xworth considerably more when the corner is taken (they become valuable instead
Xof dangerous), DEPEDGE is the additional value that ADJCOR spaces acquire with
Xthe occupation of the adjacent corner, and DEPCOR is the additional value that
Xthe INCOR position gets. These are all plainly declared as constants and
Xthen included in the weighting arrays. If you want to play with the program
Xitself, you are welcome to do so. I believe that it is commented copiously
Xenough to be reasonable.
X
XThe problem that I have been having is that while most of the time it plays
Xa very strong game, occasionally it gives away corners near the end of the
Xgame (>40 moves) when it clearly has safe and legal moves. I think that
Xthis may be fixable by adjusting the relative values of the corners, the
Xadjacent 3 squares, and the dependency factors, but I don't have the time
Xright now to play with it. Please let me know if you manage to find a
Xgood balance of V's and DV's.
X
XAnd, of course, I make no guarantees that this program as it stands will ever
Xplay a brilliant game. In fact, the evaluators should probably not change
Xlinearly throughout the game as they do now, but I was not particularly in the
Xmood to juggle 5 or 6 matrices when 2 are bad enough. So anyway, have fun
Xwith it. Oh, as for speed, expect 20-30 seconds absolute worst case for
X5-ply. I usually play 4-ply games, a level at which it should be able to
Xkill as long as the static board evaluator is reasonable.
X
XI did spend quite a bit of time tuning this baby back in the dark ages,
Xso we are rather attached :-). As such, I would greatly appreciate any
Ximprovements that you make.
X
X Mark Papamarcos
X Valid Logic Systems
X hplabs!ridge!valid!markp
SHAR_EOF
echo extracting - othello.c
sed 's/^X//' > othello.c << 'SHAR_EOF'
X/*
XMark Papamarcos
XEE348 Final Project (for graduate credit)
X
XThis program plays the game of Othello. It employs an N-ply minimax
Xsearch with alpha-beta pruning. It was decided to use C rather than
XLISP due to its much more powerful array manipulation capabilities.
XAt each leaf node a static board evaluator is called, which roughly
Xsums one player's pieces times a relative value assigned to each
Xsquare and subtracts the value obtained for the other player's pieces.
XThere are also dependencies between certain squares- if a square is
Xoccupied by either player, the weight of some other square might be
Xaffected. Finally, the weights of squares are dynamic- changing by
Xa fixed increment in each stage of the game.
X
XInvocation:
X othello {pPLY} {f} {a}
X
XWhere 'pPLY' sets the maximum search depth to PLY (default=3).
X'f' forces the computer to move first (default=human first).
X'a' sets automatic play mode.
X
XCopyright (c) 1982, 1986 Mark Papamarcos (hplabs!ridge!valid!markp)
XPermission is granted to do with this program whatever you damn well
Xplease, although I expect you would have the decency to let me in on
Xany profits from commercial ventures :-).
X*/
X
X#include <stdio.h>
X
X#define NO 0 /* logical values */
X#define YES 1
X
X#define PLY 3 /* default ply level */
X
X#define HIS -1 /* board assignments to mark pieces */
X#define OPEN 0
X#define MINE 1
X
X#define HISDUDE 'O' /* what each position prints as */
X#define NODUDE '.'
X#define MYDUDE '*'
X
X#define MAX 1 /* maximizing or minimizing flag */
X#define MIN -1
X
X /* Weights */
X#define VCORNER 400 /* Corner squares are studdly */
X#define VADJCOR -16 /* avoid adjacent ones in general */
X#define VINCOR -80 /* But adjacent ones are to be avoided */
X#define VCENT1 12 /* Very middle is mediocre */
X#define VCENT2 20 /* center border is better */
X#define VCENT3 40 /* center corner is very nice initially */
X#define VEDGE1 28 /* Edges are nice */
X#define VEDGE2 60 /* edge spaces 2 from corners really nice */
X#define VADJEDGE 12 /* Next to edges are okay */
X
X#define STAGE 5 /* weights change every 5 moves */
X
X#define DVCOR -30 /* corners greatly decrease in value */
X#define DVACOR 5 /* next to corners become more important */
X#define DVICOR 5 /* same here */
X#define DVEDGE1 0 /* middle edges stay same */
X#define DVEDGE2 -4 /* good edges lose their advantage */
X#define DVAEDGE 1 /* next to edges little better */
X#define DVCENT1 0 /* middle stays same */
X#define DVCENT2 0 /* center border stays same */
X#define DVCENT3 -3 /* center corners lose their prominence */
X
X#define LARGE 5000 /* a very large weight */
X
X#define DEPEDGE 80 /* if corner taken, adjacent edges better */
X#define DEPCOR 40 /* inside corner worth a little more */
X
Xstatic int di[8]= { 1, 1, 0,-1,-1,-1, 0, 1}; /* direction deltas */
Xstatic int dj[8]= { 0, 1, 1, 1, 0,-1,-1,-1};
X
X/* weights defined for one quarter of the board */
Xstatic int wtab[4][4]= {{VCORNER,VADJCOR ,VEDGE2 ,VEDGE1 },
X {VADJCOR,VINCOR ,VADJEDGE,VADJEDGE},
X {VEDGE2 ,VADJEDGE,VCENT3 ,VCENT2 },
X {VEDGE1 ,VADJEDGE,VCENT2 ,VCENT1 }};
X
X/* amount by which weights change every STAGE moves */
Xstatic int dwtab[4][4]={{DVCOR ,DVACOR ,DVEDGE2 ,DVEDGE1 },
X {DVACOR ,DVICOR ,DVAEDGE ,DVAEDGE },
X {DVEDGE2,DVAEDGE ,DVCENT3 ,DVCENT2 },
X {DVEDGE1,DVAEDGE ,DVCENT2 ,DVCENT1 }};
X
Xint weight[8][8]; /* actual weights for 8x8 */
Xint dweight[8][8]; /* weight increments */
X
X/* dependency factors defined for one quarter of the board */
Xstatic int dtab[4][4]= {{0 ,DEPEDGE ,0 ,0 },
X {DEPEDGE,DEPCOR ,0 ,0 },
X {0 ,0 ,0 ,0 },
X {0 ,0 ,0 ,0 }};
X
Xint dependx[8][8]; /* dependency factor */
Xint dependi[8][8]; /* square that additional weight depends on */
Xint dependj[8][8];
X
Xint pcc[3]; /* piece counts */
X /* [0]=human, [1]=empty, [2]=computer */
X
Xint totalmoves; /* moves considered */
X
Xint maxply; /* search level */
Xint mptemp; /* search level towards end */
X
Xint autoplay; /* automatic play flag */
X
Xmain(argc,argv)
Xint argc;
Xchar *argv[];
X{
X int arg; /* argument count */
X int b[8][8]; /* current position */
X int i,j; /* counters */
X int ti,tj; /* temporaries */
X int mvi,mvj; /* move */
X int endg; /* endgame flag */
X int movefirst; /* computer move first flag */
X int hecanmove; /* human can move */
X int icanmove; /* computer can move */
X
X maxply= PLY; /* set default search level */
X
X movefirst= NO;
X autoplay= NO;
X
X /* Take care of arguments to set game parameters */
X arg= 0;
X while(++arg<argc)
X {
X switch(*argv[arg])
X {
X case 'p':
X sscanf(++argv[arg],"%d",&maxply);
X if(maxply<1 || maxply>5)
X {
X printf("Ply must be between 1 and 5.\n");
X return;
X }
X break;
X case 'f':
X movefirst= YES;
X break;
X case 'a':
X autoplay= YES;
X break;
X default:
X printf("Usage: othello pn f a\n");
X return;
X }
X }
X
X mptemp= maxply;
X for(i=0;i<8;i++) /* initialize board, weights */
X for(j=0;j<8;j++)
X {
X b[i][j]=OPEN;
X ti= (i>3) ? 7-i : i;
X tj= (j>3) ? 7-j : j;
X weight[i][j]= wtab[ti][tj];
X dweight[i][j]= dwtab[ti][tj];
X dependx[i][j]= dtab[ti][tj];
X if(dependx[i][j]==0)
X {
X dependi[i][j]= 0;
X dependj[i][j]= 0;
X }
X else
X {
X dependi[i][j]= (i<4) ? 0 : 7;
X dependj[i][j]= (j<4) ? 0 : 7;
X }
X }
X
X
X b[3][3]= HIS; /* starting configuration */
X b[4][4]= HIS;
X b[3][4]= MINE;
X b[4][3]= MINE;
X
X bookkeep(b);
X
X printf("\nWelcome to Othello V1.0 (MSP)\n");
X printf("You are playing O. I am playing *.\n\n");
X if(autoplay)
X printf("Automatic play begins.\n");
X
X endg= NO;
X while(!endg)
X {
X hecanmove= NO;
X icanmove= NO;
X board(b);
X if(!movefirst)
X {
X if(!genmove(b,HIS))
X printf("You have no legal moves.\n");
X else
X {
X hecanmove= YES;
X if(!autoplay)
X {
X getmove(b,&mvi,&mvj);
X }
X else
X {
X ply(b,HIS,MAX,LARGE,&mvi,&mvj,mptemp,HIS);
X printf("You take %d%d.\n",mvi,mvj);
X flip(b,mvi,mvj,HIS,b);
X }
X bookkeep(b);
X board(b);
X }
X }
X else
X {
X movefirst= NO;
X bookkeep(b);
X }
X if(!genmove(b,MINE))
X printf("I have no legal moves.\n");
X else
X {
X icanmove= YES;
X totalmoves= 0;
X ply(b,MINE,MAX,LARGE,&mvi,&mvj,mptemp,MINE);
X printf("I take %d%d. (moves= %d)\n",mvi,mvj,totalmoves);
X flip(b,mvi,mvj,MINE,b);
X bookkeep(b);
X }
X endg= !(pcc[0] && pcc[1] && pcc[2]) || !(hecanmove || icanmove);
X }
X printf("Final Position:\n");
X board(b);
X if(pcc[0]>pcc[2])
X printf("You have won %d to %d.\n",pcc[0],pcc[2]);
X if(pcc[0]==pcc[2])
X printf("We have tied %d to %d.\n",pcc[0],pcc[2]);
X if(pcc[0]<pcc[2])
X printf("I have won %d to %d.\n",pcc[2],pcc[0]);
X}
X
X/* bookkeep updates board weights, piece counts, ply level */
Xbookkeep(bp)
Xint bp[8][8];
X{
X int i,j;
X
X pcc[0]= 0; pcc[1]= 0; pcc[2]= 0;
X for(i=0;i<8;i++)
X for(j=0;j<8;j++)
X pcc[bp[i][j]+1]++;
X if( (((pcc[0]+pcc[2]-4) % STAGE) ==0) && (pcc[0]+pcc[2] !=4))
X for(i=0;i<8;i++)
X for(j=0;j<8;j++)
X weight[i][j]+= dweight[i][j];
X if(pcc[1]<maxply) /* near end of game, don't search too far */
X mptemp= pcc[1];
X}
X
X/* getmove inputs a move for a board bp, returns 10*row+column */
X/* 88 move starts automatic play, 99 suggests a move */
Xgetmove(bp,reti,retj)
Xint bp[8][8];
Xint *reti,*retj;
X{
X int m,i,j; /* input move, decomposed row and column */
X int ok; /* ok flag */
X
X ok= NO;
X while(!ok)
X {
X printf("\nMove > ");
X scanf("%d",&m);
X switch(m)
X {
X case 88:
X printf("Automatic play initiated on next move.\n");
X autoplay= YES;
X break;
X case 99:
X ply(bp,HIS,MAX,LARGE,&i,&j,mptemp,HIS);
X printf("Try %d%d.\n",i,j);
X break;
X default:
X i= m/10;
X j= m%10;
X if (valid(i,j) && bp[i][j]==OPEN && flip(bp,i,j,HIS,bp))
X ok= YES;
X else
X printf("Illegal move");
X }
X }
X *reti=i;
X *retj=j;
X}
X
X/* flip checks if move i,j legal for bp, returns YES or NO. */
X/* Result of flip returned in bp2 */
Xflip(bp,i,j,self,bp2)
Xint bp[8][8];
Xint i,j,self;
Xint bp2[8][8];
X{
X int ok; /* okay flag */
X int dc,pc,nix; /* counters, abort flag */
X int it,jt,pct; /* temporaries */
X int ix,jx; /* more temporary counters */
X int enemy; /* value of enemy */
X
X enemy= -self;
X ok= NO;
X for(dc=0;dc<8;dc++) /* for each possible direction */
X {
X pct= 0;
X nix= NO; /* don't discount this direction yet */
X it=i;jt=j; /* start searching from move location */
X while(pct++,!nix && valid(it+= di[dc],jt+= dj[dc]))
X {
X if (bp[it][jt]!=enemy)
X nix= YES;
X if ((bp[it][jt]==self)&&(pct>1))
X {
X if(!ok) /* automatically initialize result board */
X {
X ok= YES;
X for(ix=0;ix<8;ix++)
X for(jx=0;jx<8;jx++)
X bp2[ix][jx]= bp[ix][jx];
X }
X for(pc=0;pc<pct;pc++) /* do the flip */
X bp2[i+pc*di[dc]][j+pc*dj[dc]]= self;
X }
X }
X }
X return(ok);
X}
X
X/* genmove checks if a legal move exists for self from bp */
Xgenmove(bp,self)
Xint bp[8][8];
Xint self;
X{
X int i,j; /* counters */
X int tbp[8][8]; /* temporary board */
X
X for(i=0;i<8;i++)
X for(j=0;j<8;j++)
X if(bp[i][j]==OPEN && flip(bp,i,j,self,tbp))
X return(YES);
X return(NO);
X}
X
X/* ply is the workhorse function. It evaluates all possible moves */
X/* on bp for self, given a previous max/min of bound. It returns */
X/* the value of the best move and points to it in pmvi and pmvj. */
X/* doer is the one who will execute this move. */
Xply(bp,self,maxmin,bound,pmvi,pmvj,depth,doer)
Xint bp[8][8];
Xint self,maxmin,bound;
Xint *pmvi,*pmvj;
Xint depth;
Xint doer;
X{
X int i,j; /* counters */
X int nbp[8][8]; /* new position after move */
X int best; /* extreme min or max found so far */
X int prune; /* prune flag */
X int valmove; /* what move under consideration is worth */
X int besti,bestj; /* best move found here */
X
X totalmoves++; /* keep statistics of this */
X if(depth==0) /* leaf node- return board evaluation */
X return(sbe(bp,doer));
X best= (maxmin==MAX) ? -LARGE : LARGE; /* best move= nil */
X prune= NO;
X for(i=0;!prune && i<8;i++)
X for(j=0;!prune && j<8;j++)
X {
X if(bp[i][j]==OPEN && flip(bp,i,j,self,nbp)) /* legal */
X {
X valmove= ply(nbp,-self,-maxmin,best,pmvi,pmvj,depth-1,doer);
X if(maxmin==MAX)
X {
X if(valmove > best) /* best so far, maximizing */
X {
X besti= i;
X bestj= j;
X best= valmove;
X prune= (best>bound) ? YES : NO; /* alpha/beta */
X }
X }
X else
X if(valmove < best) /* best so far, minimizing */
X {
X besti= i;
X bestj= j;
X best= valmove;
X prune= (best < bound) ? YES : NO; /* alpha/beta */
X }
X }
X }
X *pmvi= besti; /* return best move */
X *pmvj= bestj;
X if(( (best>=0) ? best : -best)==LARGE) /* none found */
X return(bound);
X else
X return(best);
X}
X
X/* valid determines whether i,j is on the board */
Xvalid(i,j)
Xint i,j;
X{
X return((i>=0 && i<=7 && j>=0 && j<=7) ? YES : NO);
X}
X
X/* sbe is the static board evaluator, returning bp's value for self */
Xsbe(bp,self)
Xint bp[8][8];
Xint self;
X{
X int i,j; /* counters */
X int goodness; /* running total */
X
X goodness= 0;
X for(i=0;i<8;i++)
X for(j=0;j<8;j++)
X goodness+= weight[i][j]*bp[i][j] +
X dependx[i][j]*abs(bp[dependi[i][j]][dependj[i][j]]);
X goodness*= self;
X return(goodness);
X}
X
X/* board prints the board bp */
Xboard(bp)
Xint bp[8][8];
X{
X int i,j;
X char equiv[3];
X equiv[0]= HISDUDE;
X equiv[1]= NODUDE;
X equiv[2]= MYDUDE;
X printf("\n ");
X for(j=0;j<8;j++)
X printf(" %d",j);
X printf("\n ----------------\n");
X for(i=0;i<8;i++)
X {
X printf("%d|",i);
X for(j=0;j<8;j++)
X printf(" %c",equiv[bp[i][j]+1]);
X printf("\n");
X }
X}
X
SHAR_EOF