# This is a shell archive. Remove anything before this line, # then unpack it by saving it in a file and typing "sh file". # # Wrapped by David Boll on Wed Sep 14 15:42:20 1994 # # This archive contains: # gameplayer.c gameplayer.h Makefile README # template.c attaxx.c attaxx.dat hexapawn.c # hexapawn.dat othello.c othello.dat hex.c # hex.dat # LANG=""; export LANG PATH=/bin:/usr/bin:$PATH; export PATH echo x - gameplayer.c cat >gameplayer.c <<'@EOF' #include #include #include #include /******************************************************************* * GamePlayer 1.2 * * Dave Boll 2/94 * * * * This program is intended as a general tool for generating game * * playing programs. The idea is that you supply the movement and * * scoring routines, and the included code below takes care of the * * alpha beta tree search. You can set many parameters to change * * how this search is carried out, these parameters can be found * * in the #define section, and the getsetup subroutine. * * * * The purpose of this program is not to make an excellent * * computer player for your game of choice - it's probably better * * as a way of tuning your evaluation function. * * * * See the game.dat file for information on how to change some of * * the processing of this program. * * * * See the README file for changes between this and the prv. * * version. * * * * This program is freely distributable. * *******************************************************************/ #define PATCHLEVEL 3 /* version number */ #define WHITE 1 /* used to identify the white player */ #define BLACK -1 /* used to identify the black player */ #define WLO 1 /* WHO & WHI define the numeric range for white */ #define WHI 9 /* pieces */ #define BLO -9 #define BHI -1 #define HUMAN 1 #define COMPUTER -1 #define COMPUTER2 -2 #define EMPTYSQUARE 0 #define BOUNDARY 100 /* used to mark boundary squares */ #define DEBUG 0 /* set to nonzero to get printf's at subroutine */ /* entry points. */ #define MAXMOVES 100 /* The most number of moves possible from a given */ /* game position. */ #define BIGSCORE 99999 /* this # must be bigger than any possible one */ /* returned from the scoring function. */ #define NOMOVES -10 /* invalid move from square to indicate no moves */ #include "gameplayer.h" /* Global variables: */ int bsize; /* size of board */ int pmax; /* max depth to search */ int bstart,bend; /* the start & end indices of the 'active' part of */ /* the board. A boundary 2 squares thick is placed around */ /* the playing area, messing up our indices */ int verbose; /* 0,1,2, controls how much calculation info is printed. */ int killer; /* 0=no killer moves, 1=save killer moves */ /* currently unused, maybe next time... */ int km[10][2][10][6]; /* killer move array */ /* Note: Killer moves, as currently implemented, are not the traditional */ /* implementation. It's more like a histogram of good moves at a par- */ /* ticular ply. */ int totalpos,alphacuts,betacuts,firstcuts,nthcuts; /* These are all statistics calculated by the alphabeta subroutine. */ /* totalpos: total # of positions looked at alphacuts: number of odd ply cuts betacuts: number of even ply cuts firstcuts: # of times the best move was 1st in move list nthcuts: # of times the best move was not 1st in move list These last two should change dramatically upon flipping the killer move flag, once it's implemented */ int FirstMove; /* who moves first, white or black? */ int WhitePlayer; /* is WhitePlayer human or computer? */ int BlackPlayer; /* is Blackplayer human or computer? */ int NoMoves; /* what do we do if one side has no moves available? 0 - they lose 1 - tie, game over 2 - they win 3 - they pass & it is the other players' turn */ int tournament; /* =0: default mode */ /* =1: play score1 vs score2 */ int sflag; /* active only if computer vs computer */ /* 1: always use score1 as the scoring function */ /* 2: switch between score1 and score2 depending on move */ int board[15][15],list1[MAXMOVES][4],nl,b1[15][15]; int tgames, randmove; int BoardShape; /* 0: square board 1: hex board */ char Wpieces[10],Bpieces[10]; /* these arrays hold the character to represent */ /* this type of piece on the board */ int Pruning; /* 0: no pruning N: keep only the first N moves */ int MoveSort; /* 0: no sorting 1: sort by scoring function */ int FromSquare; /* 1: moves in this game consist of both FROM and TO squares */ /*ARGSUSED*/ main(argc, argv) int argc; char **argv; { int who,i; int temp; int move[4],score; int whowon; int t1wgames, t1bgames, t2wgames, t2bgames; process_parameters(argv[0]); /* read in parms in progname.dat */ initkm(); srand(time(NULL)); boardinit(board); if (tournament == 0) bprint(board); who = FirstMove; if (tournament == 0) { playgame(who,&whowon); if (((whowon==BLACK) && (BlackPlayer==COMPUTER)) || ((whowon==WHITE) && (WhitePlayer==COMPUTER))) printf("I win. A pretty weak effort on your part, I'd say. \n"); else if ((whowon==WHITE) || (whowon==BLACK)) { printf("You got lucky and won. You must have set my search \n"); printf("depth to zero!!!!! \n"); } else { printf("Tie game! What ARE the odds!? \n"); } } else { /**************************************************************** * the following is the tournament portion of main() - * ****************************************************************/ t1wgames = 0; t1bgames = 0; t2wgames = 0; t2bgames = 0; for (i=0; i * * moves for each side. * * Notes: no provision is made for the game ending during this * * routine * **************************************************************/ { int i,j,move[4],list1[MAXMOVES][4],nl1,who; who = -1; if (DEBUG) printf("randboardinit \n"); for (i=0; i<2*randmove; i++) { who = 0 - who; mmlist(board,who,list1,&nl1); j = rand() % nl1; move[0] = list1[j][0]; move[1] = list1[j][1]; move[2] = list1[j][2]; move[3] = list1[j][3]; boardcopy(board,b1); process(b1,move,who,board); } /* next i */ } killermoves(mlist,depth,who,nm) int mlist[][4],depth,who,nm; /************************************************************** * (called only when killer=1) This routine checks out the * * killer move list and puts the most frequent killer in the * * first position * **************************************************************/ { } checkkillermovelist(mlist,depth,who,j,k) /************************************************************** * (called only when killer=1) This routine checks out the * * killer move array for occurence of a particular move * **************************************************************/ int mlist[],depth,who,*j,*k; { } registerkillermove(tm,depth,who) int tm[],depth,who; /************************************************************** * (called only when killer=1) This routine updates the km * * array with all good moves found at all plys. If the move is * * currently in the list, increment the count, else add it to * * the list. * **************************************************************/ { } alphabeta(score,depth,cutoff,who,board,move,stalemate) int *score,depth,cutoff,who,stalemate; int board[][15],move[]; /************************************************************** * Performs the minimax algorithm with alphabeta pruning. The * * search is performed to the specified depth. * **************************************************************/ { int i,j,nm,s; int bestscore,besti; int mlist[MAXMOVES][4]; int bestmove[4]; int b1[15][15],tempmove[4]; int g; if (DEBUG) printf("alphabeta \n"); boardcopy(board,b1); bestscore=(BIGSCORE+depth)*(0-who); mmlist(board,who,mlist,&nm); /* get move list */ if (MoveSort == 1) sortem(board,who,mlist,nm); if ((Pruning) && (Pruning1)) nm=1; while (i0)) printf("move that gets this score is %d %d %d %d \n",tempmove[0]-bstart+1,tempmove[1]-bstart+1,tempmove[2]-bstart+1,tempmove[3]-bstart+1); } if (who == WHITE) { if (s > bestscore) { bestscore=s; besti=i; bestmove[0]=mlist[i][0]; bestmove[1]=mlist[i][1]; bestmove[2]=mlist[i][2]; bestmove[3]=mlist[i][3]; } if (s >= cutoff) { *score = s; i = nm; alphacuts++; if (verbose==2) printf("Alpha Cut! \n"); } } else { if (s < bestscore) { bestscore=s; besti=i; bestmove[0]=mlist[i][0]; bestmove[1]=mlist[i][1]; bestmove[2]=mlist[i][2]; bestmove[3]=mlist[i][3]; } if (s <= cutoff) { *score = s; i = nm; betacuts++; if (verbose==2) printf("Beta Cut! \n"); } } i++; } /* end while */ } /* end else if nm == 0 */ move[0]=bestmove[0]; move[1]=bestmove[1]; move[2]=bestmove[2]; move[3]=bestmove[3]; *score=bestscore; if (besti==0) firstcuts++; else nthcuts++; } sortem(board,who,mlist,nm) int board[][15],who,mlist[][4],nm; { int b1[15][15],move[4],i,j; int mscores[MAXMOVES]; int mlist1[MAXMOVES][4],nm1,LOGN; int n,m,k,nn,l,temp; int s; boardcopy(board,b1); /* now, make each move on this board and score each one */ for (i=0; i 255) LOGN = 8; else if (nm > 127) LOGN = 7; else if (nm > 63) LOGN = 6; else if (nm > 31) LOGN = 5; else if (nm > 15) LOGN = 4; else if (nm > 7) LOGN = 3; else if (nm > 3) LOGN = 2; else if (nm > 1) LOGN = 1; m=nm; for (nn=0; nn mscores[i]) { /* swap the scores and the move */ temp = mscores[i]; mscores[i] = mscores[l]; mscores[l] = temp; temp = mlist[i][0]; mlist[i][0]=mlist[l][0]; mlist[l][0]=temp; temp = mlist[i][1]; mlist[i][1]=mlist[l][1]; mlist[l][1]=temp; temp = mlist[i][2]; mlist[i][2]=mlist[l][2]; mlist[l][2]=temp; temp = mlist[i][3]; mlist[i][3]=mlist[l][3]; mlist[l][3]=temp; i = i-m; if (i >= 0) goto stupidlabel; } } /* next j */ } /* next nn */ /* printf("after sorting: \n"); for (i=0; i=bstart) && (i<=bend) && (j>=bstart) && (j<=bend)) board[i][j] = EMPTYSQUARE; else board[i][j] = BOUNDARY; }} initpieceplacement(board); /************************************************************* * this section is attaxx specific; allows you to block off * * certain squares from the board since all the commercial * * versions of this game that I've seen block off some squares* *************************************************************/ /* i=1; printf("enter next square to block, 0 0 to quit \n"); scanf("%d %d",&i,&j); while (i != 0) { board[i+bstart-1][j+bstart-1] = BOUNDARY; printf("enter next square to block, 0 0 to quit \n"); scanf("%d %d",&i,&j); } */ } initkm() /**************************************************************** * initialize the killer moves array * ****************************************************************/ { int i,j,k,l; if (DEBUG) printf("initkm \n"); for (i=0; i<=pmax+1; i++) for (j=0; j<2; j++) for (k=0; k<10; k++) for (l=0; l<6; l++) km[i][j][k][l] = 0; } bprint(board) /****************************************************************** * print out board Pause for input * ******************************************************************/ int board[][15]; { int i,j,k; if (DEBUG) printf("bprint \n"); printf(" "); for (k=0; k=WLO) && (board[i][j] <=WHI)) printf("%c ",Wpieces[ board[i][j] ]); else if ((board[i][j]>=BLO) && (board[i][j] <= BHI)) printf("%c ",Bpieces[ 0-board[i][j] ]); else if (board[i][j]==BOUNDARY) printf("* "); else printf("- "); } /* next j */ printf("\n"); } /* next i */ printf("\n"); } process_parameters(progname) /******************************************************************* * Read in parameter file, progname.dat. There is NO ERROR CHECKING * * performed on this file, so it better be right. * *******************************************************************/ char *progname; { char filename[100],line[100]; FILE *stream; if (DEBUG) printf("process_parameters \n"); sprintf(filename, "%s.dat", progname); if ((stream = fopen( filename,"r" )) != NULL) { fgets(line,100,stream); FirstMove = atoi(line); fgets(line,100,stream); WhitePlayer = atoi(line); fgets(line,100,stream); BlackPlayer = atoi(line); fgets(line,100,stream); bsize = atoi(line); fgets(line,100,stream); pmax = atoi(line); fgets(line,100,stream); verbose = atoi(line); fgets(line,100,stream); killer = atoi(line); fgets(line,100,stream); NoMoves = atoi(line); /****************************************************** * someday I'll clean this up; we don't really need * * both sflag AND tournament * ******************************************************/ fgets(line,100,stream); sflag = atoi(line); fgets(line,100,stream); tournament = atoi(line); fgets(line,100,stream); tgames = atoi(line); fgets(line,100,stream); randmove = atoi(line); fgets(line,100,stream); BoardShape = atoi(line); fgets(line,100,stream); Pruning = atoi(line); fgets(line,100,stream); MoveSort = atoi(line); fgets(line,100,stream); FromSquare = atoi(line); } else { printf("Invalid parameter file \n"); } } @EOF chmod 644 gameplayer.c echo x - gameplayer.h cat >gameplayer.h <<'@EOF' /* global #defines used: */ #define WHITE 1 /* used to identify the white player */ #define BLACK -1 /* used to identify the black player */ #define WLO 1 /* WHO & WHI define the numeric range for white */ #define WHI 9 /* pieces */ #define BLO -9 #define BHI -1 #define HUMAN 1 #define COMPUTER -1 #define COMPUTER2 -2 #define EMPTYSQUARE 0 #define BOUNDARY 100 #define DEBUG 0 /* set to nonzero to get printf's at subroutine */ /* entry points. */ #define MAXMOVES 100 /* The most number of moves possible from a given */ /* game position. */ #define BIGSCORE 99999 /* this # must be bigger than any possible one */ /* returned from the scoring function. */ #define NOMOVES -10 /* flag to indivate move is null */ /* Global variables: */ extern int bsize; /* size of board */ extern int pmax; /* max depth to search */ extern int bstart,bend; /* the start & end indices of the 'active' part of */ /* the board. A boundary 2 squares thick is placed around */ /* the playing area, messing up our indices */ extern int verbose; /* 0,1,2, controls how much calculation info is printed. */ extern int killer; /* 0=no killer moves, 1=save killer moves */ /* currently unused, maybe next time... */ extern int km[10][2][10][6]; /* killer move array */ /* Note: Killer moves, as currently implemented, are not the traditional */ /* implementation. It's more like a histogram of good moves at a par- */ /* ticular ply. */ extern int totalpos,alphacuts,betacuts,firstcuts,nthcuts; /* These are all statistics calculated by the alphabeta subroutine. */ /* totalpos: total # of positions looked at alphacuts: number of odd ply cuts betacuts: number of even ply cuts firstcuts: # of times the best move was 1st in move list nthcuts: # of times the best move was not 1st in move list These last two should change dramatically upon flipping the killer move flag, once it's implemented */ extern int FirstMove; /* who moves first, white or black? */ extern int WhitePlayer; /* is WhitePlayer human or computer? */ extern int BlackPlayer; /* is Blackplayer human or computer? */ extern int NoMoves; /* what do we do if one side has no moves available? 0 - they lose 1 - tie, game over 2 - they win 3 - they pass & it is the other players' turn */ extern int tournament; /* =0: default mode */ /* =1: play score1 vs score2 */ extern int sflag; /* active only if computer vs computer */ /* 1: always use score1 as the scoring function */ /* 2: switch between score1 and score2 depending on move */ extern int board[15][15],list1[MAXMOVES][4],nl,b1[15][15]; extern int tgames, randmove; extern char Wpieces[10],Bpieces[10]; extern int Pruning; extern int BoardShape; extern int MoveSort; extern int NoFromSquare; @EOF chmod 644 gameplayer.h echo x - Makefile sed 's/^@//' >Makefile <<'@EOF' BINARIES = attaxx hexapawn othello hex CFLAGS = -g LIBS = -lm CC = cc @.KEEP_STATE: all: $(BINARIES) attaxx: attaxx.o gameplayer.o $(CC) -o attaxx $(CFLAGS) attaxx.o gameplayer.o $(LIBS) hexapawn: hexapawn.o gameplayer.o $(CC) -o hexapawn $(CFLAGS) hexapawn.o gameplayer.o $(LIBS) othello: othello.o gameplayer.o $(CC) -o othello $(CFLAGS) othello.o gameplayer.o $(LIBS) hex: hex.o gameplayer.o $(CC) -o hex $(CFLAGS) hex.o gameplayer.o $(LIBS) attaxx.o: attaxx.c othello.o: othello.c hex.o: hex.c hexapawn.o: hexapawn.c @EOF chmod 644 Makefile echo x - README cat >README <<'@EOF' README file for GamePlayer What is it?: Gameplayer is a set of programs that plays 2 person strategy games. It can be used as an opponant, or as a tool for improving your own program to play the game. The domain of Gameplayer is 2 person games on square grids (or rhomboid hex lattices), ex. games like chess, checkers, othello, hex, etc., although some (most!) of these haven't been written by anyone yet. Why would I want to use it? For fun, for practice on a particular game, or to fine tune a scoring function. If you enter computer tournaments with it, my guess is you'll lose to specialized programs written specifically for that game. What games are currently supported? See the list at the end of this file. How do I make my own program that plays a new game, not on the list? You basically need to write all the routines shown in template.c for your particular game. The comments in template.c tell you what the routines should do - looking at existing ones wouldn't hurt, either. If you're feeling kind, email me your program when you're done, and I'll put in in the master list. If you've put a lot of work in your scoring function and would rather not share it, substitute a lame but functional one. Once you're done with this, add your game to the makefile - just edit it and copy/change the obvious lines. You'll also need a .dat file for your particular game - look at an existing one to see how it's done. What if I want to make an existing game better? It's your lucky day - you don't have to write all the routines shown in template.c. Assuming you're happy with the 'other' routines, all you need to work on is the scoring function for your game. How does gameplayer work? Gameplayer does an alpha-beta search with minimax pruning. If you're unfamilar with the alpha-beta algorithm, you might want to read up on it - check out, for example, Computer Gamesmanship, by David Levy. How do I build the program? 2 simple steps: cc gameplayer.c -O -lm -c make Changes from last time: Added some new parameters to the .dat file: FromSquare: =1 if moves in this game consist of both a move FROM and a move TO square. =0 if moves are just move TO's (Othello,hex,go) Removed the pause from the board printing routine Fixed the problem where (in verboose=2 mode) board would always print in hex format. Added source for Othello, from Rick Burridge List of current games: Attaxx: Source: I saw it first as a video game. Numerous public domain versions of the game now exist - it's pretty easy to write a good program for this, the scoring routine with GamePlayer just uses piececount, and if I set it to 3 or 4 ply, I certainly can't beat it. Rules: The game is played on a 7x7 board. Play starts with 2 pieces of each color at the corners, diagonal to each other. Valid moves for a player are FROM any square occupied by their piece TO any unoccupied square 1 or 2 steps (1 step = 1 move of a king in chess) away. All neighbors of the move TO square (up to 8 of 'em) are changed to the player's color if currently occupied. If the move involved 2 steps, the move FROM square is vacated, otherwise it remains occupied by the player. If you have no moves, you lose your turn. Winner is player with the most pieces at the end of the game. Hexapawn: Source: The only written doc I have for the game is from one of Gardner's books. This is a good game to examine the source for if you're unsure of how to write some of the modules; Hexapawn is about the simplest game to program that there is. Rules: Played on an NxN board; each player has N pieces that move exactly like chess pawns. Winning is by wipeout, or by putting a piece on the enemy back row. I'm not sure about the stalemate condition. Othello: Source: Othello is the commercial name of the game called reversi, invented in England in the 19th century. This version of the program, uses a simplistic scoring function, but it still should give most people a fairly good game. Rules: Othello is played on an 8 x 8 board, with pieces which are black on one side and white on the other. A legal move consists of placing a piece of one's own color on the board so as to "sandwich" a row (orthogonal or diagonal) of pieces of the opposite color between the piece just placed and another piece of the same color. All pieces so sandwiched are flipped over to reveal the color of the other side. The object of the game, is to have more pieces than the opponent at the end of the game (ie. when the board is full or neither side has a legal move). If you have no legal move, you simply miss a turn. @EOF chmod 644 README echo x - template.c cat >template.c <<'@EOF' /********************************************************** * Game specific routines. Each of these routines needs to * * be changed for a new game. * * * * One routine you may have to change in the above section * * is bprint (and bprint1; they're the same except bprint * * pauses after printing the board). These routines are * * currently set to print boards for games that use only * * one type of piece. * **********************************************************/ initpieceplacement(board) /********************************************************** * initpieceplacement: Set up the board for the starting * * position. The board should be indexed in the range * * bstart to bend. If your board size is larger than 11x11 * * you'll have to change the dimensions on the 'board' * * array (which appears in many places in this program) * * * * Returns the board array initialized for the start of a * * game. You can use different integers to represent diff. * * types of pieces (eg. chess), just make sure that White * * is always positive, Black is always negative, and WLOW, * * WHIGH, BLOW, BHI (#defines at the top of the program) * * are accurate. * **********************************************************/ int board[][15]; { if (DEBUG) printf("initpieceplacement \n"); } mmlist(board,who,list1,nl1) int board[][15],who,list1[][4],*nl1; /************************************************************** * Given a board position, calculate a move list * * (User provided) * * Note: if there is an easy way for you to order this list so * * that good moves are at the beginning, do it! it will save * * all kinds of time. One easy-for-you way to do this is to * * sort by the scoring function; there's a flag for this in * * the .dat file. This is hardly an optimal way, so if you * * can do it yourself, more power to you. * * * * board: 2d array describing the current board position. * * who: whose turn is it to move? 1: white -1: black * * list1: Returned as a list of valid moves. * * list1[i][0], list1[i][1]: 'from' square of move * * list1[i][2], list1[i][3]: 'to' square of move * * nl1: returned as the number of valid entries in list1 * * * * Many games don't have a 'from' square at all (ex: hex, go) * * For games of this type, just put the move into the 'to' * * square and write your move processing routine correctly. * **************************************************************/ { if (DEBUG) printf("mmlist \n"); } madd(i1,j1,i2,j2,listn,n) /************************************************************ * madd: add a new move to the list. * * Take a look at this routine for an existing game; you'll * * be able to copy it verbatim, or it's possible you won't * * need it at all. * ************************************************************/ int i1,j1,i2,j2,listn[][4],*n; { if (DEBUG) printf("madd \n"); } process(board,move,who,b1) int board[][15],b1[][15],move[],who; /************************************************************** * Given a board position and a move, calculate the resulting * * board position. * * board: 2d array holding current position * * b1: 2d array returned as new board position. The copy of the* * existing board is done for you * * move[]: A 4-element array containing: * * move[0], move[1] 'from' square * * move[2], move[3] 'to' square * * who: 1: it's a white move -1: it's a black move * * Note: for games that move pieces around, this routine is as * * simple as: * * 1) Copy the board * * 2) b1[i2][j2]=b1[i1][j1] * * 3) b1[i1][j1]=0 * **************************************************************/ { int i,j; if (DEBUG) printf("process %d %d %d %d\n",move[0],move[1],move[2],move[3]); for (i=bstart; i<=bend; i++) /* Copy the board over. We don't need to */ for (j=bstart; j<=bend; j++) /* do boundaries, they're already done. */ b1[i][j] = board[i][j]; } gameovercheck(b,who,g) /************************************************************** * Returns in "g" the current status of the game. * * g = 0: game not over * * g = 1: game over; white wins * * g = -1: game over; black wins * * g = 3: game over, tie * * * * b: 2d array holding current board position * * who: 1: it's a white move -1: it's a black move * **************************************************************/ int b[][15],who,*g; { if (DEBUG) printf("gameovercheck \n"); } score1(b,s,who) int b[][15],who,*s; /************************************************************** * Primary scoring function * * (User provided) * * b: 2d array holding current board position * * who: 1: it's a white move -1: it's a black move * * s: returned as the numerical score of a position. * * The better the position is for White, the higher (more * * positive) s should be. * * * * Make sure the #define constant BIGSCORE is significantly * * larger than any possible value that this routine could * * return. * * Also, alphabeta will return a score of zero to indicate a * * tie game. Make sure this is compatible with your scoring fn.* **************************************************************/ { if (DEBUG) printf("score1 \n"); } score2(b,s,who) int b[][15],who,*s; /************************************************************** * Alternate scoring function for use during tournament play * * (User provided) * * If you want to play two scoring routines against each other,* * here's where to put the second one. * **************************************************************/ { if (DEBUG) printf("score2 \n"); } @EOF chmod 644 template.c echo x - attaxx.c cat >attaxx.c <<'@EOF' #include "gameplayer.h" #include "math.h" /********************************************************** * Game specific routines. Everything below this line will * * change for a new game. * * * * One routine you may have to change in the above section * * is bprint (and bprint1; they're the same except bprint * * pauses after printing the board). These routines are * * currently set to print boards for games that use only * * one type of piece. * **********************************************************/ initpieceplacement(board) /********************************************************** * initpieceplacement: Set up the board for the starting * * position. The board should be indexed in the range * * bstart to bend. If your board size is larger than 11x11 * * you'll have to change the dimensions on the 'board' * * array (which appears in many places in this program) * * * * Returns the board array initialized for the start of a * * game. You can use different integers to represent diff. * * types of pieces (eg. chess), just make sure that White * * is always positive, Black is always negative, and WLOW, * * WHIGH, BLOW, BHI (#defines at the top of the program) * * are accurate. * **********************************************************/ int board[][15]; { if (DEBUG) printf("initpieceplacement \n"); board[bstart][bstart] = 1; board[bend][bend] = 1; board[bstart][bend] = -1; board[bend][bstart] = -1; Wpieces[1] = 'W'; /* init the characters used to print the board */ Bpieces[1] = 'B'; } mmlist(board,who,list1,nl1) int board[][15],who,list1[][4],*nl1; /************************************************************** * Given a board position, calculate a move list * * (User provided) * * Note: if there is an easy way for you to order this list so * * that good moves are at the beginning, do it! it will save * * all kinds of time. * * * * board: 2d array describing the current board position. * * who: whose turn is it to move? 1: white -1: black * * list1: Returned as a list of valid moves. * * list1[i][0], list1[i][1]: 'from' square of move * * list1[i][2], list1[i][3]: 'to' square of move * * nl1: returned as the number of valid entries in list1 * * * * Many games don't have a 'from' square at all (ex: hex, go) * * For games of this type, just put the move into the 'to' * * square and write your move processing routine correctly. * **************************************************************/ { int i,j,i1,j1,nl2; int list2[MAXMOVES][4]; *nl1 = 0; nl2 = 0; if (DEBUG) printf("mmlist \n"); for (i=bstart; i<=bend; i++) { for (j=bstart; j<=bend; j++) { if (board[i][j]==EMPTYSQUARE) { /****************************************************** * in Attaxx, for moves that are not jumps, we record * * the start square as an invalid square: 1,1. This is * * because there are potentially eight different places* * a non jump move could come from, and we need to * * be able to check all eight (for input of users' * * moves. The process routine checks for this. * ******************************************************/ if (board[i-1][j-1] == who) madd(1,1,i,j,list1,nl1); else if (board[i-1][j] == who) madd(1,1,i,j,list1,nl1); else if (board[i-1][j+1] == who) madd(1,1,i,j,list1,nl1); else if (board[i][j-1] == who) madd(1,1,i,j,list1,nl1); else if (board[i][j+1] == who) madd(1,1,i,j,list1,nl1); else if (board[i+1][j-1] == who) madd(1,1,i,j,list1,nl1); else if (board[i+1][j] == who) madd(1,1,i,j,list1,nl1); else if (board[i+1][j+1] == who) madd(1,1,i,j,list1,nl1); if (board[i-2][j-2] == who) madd(i-2,j-2,i,j,list2,&nl2); if (board[i-2][j-1] == who) madd(i-2,j-1,i,j,list2,&nl2); if (board[i-2][j] == who) madd(i-2,j,i,j,list2,&nl2); if (board[i-2][j+1] == who) madd(i-2,j+1,i,j,list2,&nl2); if (board[i-2][j+2] == who) madd(i-2,j+2,i,j,list2,&nl2); if (board[i+2][j-2] == who) madd(i+2,j-2,i,j,list2,&nl2); if (board[i+2][j-1] == who) madd(i+2,j-1,i,j,list2,&nl2); if (board[i+2][j] == who) madd(i+2,j,i,j,list2,&nl2); if (board[i+2][j+1] == who) madd(i+2,j+1,i,j,list2,&nl2); if (board[i+2][j+2] == who) madd(i+2,j+2,i,j,list2,&nl2); if (board[i+1][j+2] == who) madd(i+1,j+2,i,j,list2,&nl2); if (board[i][j+2] == who) madd(i,j+2,i,j,list2,&nl2); if (board[i-1][j+2] == who) madd(i-1,j+2,i,j,list2,&nl2); if (board[i+1][j-2] == who) madd(i+1,j-2,i,j,list2,&nl2); if (board[i][j-2] == who) madd(i,j-2,i,j,list2,&nl2); if (board[i-1][j-2] == who) madd(i-1,j-2,i,j,list2,&nl2); }}} for (i=0; i1) b1[i1][j1]=EMPTYSQUARE; b1[i2][j2] = who; for (k1=i2-1; k1<=i2+1; k1++) { for (k2=j2-1; k2<=j2+1; k2++) { if (b1[k1][k2] == enemy) b1[k1][k2] = who; }} } gameovercheck(b,who,g) /************************************************************** * Returns in "g" the current status of the game. * * g = 0: game not over * * g = 1: game over; white wins * * g = -1: game over; black wins * * g = 3: game over, tie * * * * b: 2d array holding current board position * * who: 1: it's a white move -1: it's a black move * **************************************************************/ int b[][15],who,*g; { int i,j; int bpop,wpop,epop; if (DEBUG) printf("gameovercheck \n"); bpop = wpop = epop = 0; for (i=bstart; i<=bend; i++) { for (j=bstart; j<=bend; j++) { if (b[i][j] == EMPTYSQUARE) epop++; else if ((b[i][j] <= WHI) && (b[i][j] >= WLO)) wpop++; else if ((b[i][j] <= BHI) && (b[i][j] >= BLO)) bpop++; } } /* if there's empty squares and pieces of both colors, the game can't be over. */ if ((epop>0) && (wpop>0) && (bpop>0)) *g = 0; else { if (wpop>0) *g = WHITE; else *g = BLACK; if (wpop == bpop) *g = 3; } } score1(b,s,who) int b[][15],who,*s; /************************************************************** * Primary scoring function * * (User provided) * * b: 2d array holding current board position * * who: 1: it's a white move -1: it's a black move * * s: returned as the numerical score of a position. * * The better the position is for White, the higher (more * * positive) s should be. * * * * Make sure the #define constant BIGSCORE is larger than any * * possible value that this routine could return * * Also, alphabeta will return a score of zero to indicate a * * tie game. Make sure this is compatible with your scoring fn.* **************************************************************/ { int i,j,temp,k1,k2,f1,q,enemy; int score; if (DEBUG) printf("score1 \n"); *s = 0; f1 = 0; enemy = 0-who; score = 0; for (i=bstart; i<=bend; i++) { for (j=bstart; j<=bend; j++) { score += b[i][j]; /* count pieces */ } } *s = score; } score2(b,s,who) int b[][15],who,*s; /************************************************************** * Alternate scoring function for use during tournament play * * (User provided) * * Currently just calls score1 and adds a random number to the * * result; so if you do a tournament you should see score1 * * win more games than score2. * **************************************************************/ { int i,j,temp,k1,k2,f1,q,enemy; int score; if (DEBUG) printf("score2 \n"); score1(b,s,who); *s += (rand() % 30); } @EOF chmod 644 attaxx.c echo x - attaxx.dat cat >attaxx.dat <<'@EOF' 1 FirstMove: who moves first? 1:white -1:black -1 WhitePlayer: who is playing the white peices? 1:human -1:computer -1 BlackPlayer: who is playing the black peices? 1:human -1:computer 6 bsize: # of squares on side of board 3 pmax: search depth 0 verbose: set to 1 or 2 to see a lot more stuff printed out 0 killer: DON"T CHANGE THIS - currently inactive 3 NoMoves: 0-win 1:tie 2:lose 3:lose turn 1 sflag: 1:normal 2:play score1 vs score2 (iff both players=computer) 0 tournament:(if=1) play 2 scoring routines against each other 0 tgames: # of games to play in a tournament 0 randmove: # of random moves at the start of a tournament game 0 BoardShape: 0: square lattice 1: hexagonal lattice 0 Pruning: 0: don't N: keep only the first N moves (use w/MoveSort) 1 MoveSort: 0: don't 1: sort by scoring function 0 FromSquare: =0 if (no move FROM square for this game(ex hex)), else 1 @EOF chmod 644 attaxx.dat echo x - hexapawn.c cat >hexapawn.c <<'@EOF' #include "gameplayer.h" initpieceplacement(board) int board[][15]; { int i; for (i=bstart; i<=bend; i++) { board[bstart][i] = WHITE; board[bend][i] = BLACK; } Wpieces[1] = 'W'; Bpieces[1] = 'B'; } mmlist(board,who,list1,nl1) int board[][15],who,list1[][4],*nl1; /************************************************************** * Given a board position, calculate a move list * * (User provided) * * Note: if there is an easy way for you to order this list so * * that good moves are at the beginning, do it! it will save * * all kinds of time. * **************************************************************/ { int i,j,i1,j1; int list2[MAXMOVES][4], nl2; *nl1 = 0; nl2 = 0; if (who == WHITE) { for (i=bend; i>=bstart; i--) { for (j=bstart; j<=bend; j++) { if (board[i][j]==WHITE) { if (board[i+1][j] == EMPTYSQUARE) madd(i,j,i+1,j,list1,nl1); if (board[i+1][j] == BOUNDARY) madd(i,j,i+1,j,list1,nl1); if (board[i+1][j+1] == BLACK) madd(i,j,i+1,j+1,list1,nl1); if (board[i+1][j-1] == BLACK) madd(i,j,i+1,j-1,list1,nl1); }}} } else { for (i=bstart; i<=bend; i++) { for (j=bstart; j<=bend; j++) { if (board[i][j]==BLACK) { if (board[i-1][j] == EMPTYSQUARE) madd(i,j,i-1,j,list1,nl1); if (board[i-1][j] == BOUNDARY) madd(i,j,i-1,j,list1,nl1); if (board[i-1][j+1] == WHITE) madd(i,j,i-1,j+1,list1,nl1); if (board[i-1][j-1] == WHITE) madd(i,j,i-1,j-1,list1,nl1); }}} } } madd(i1,j1,i2,j2,listn,n) int i1,j1,i2,j2,listn[][4],*n; { listn[*n][0] = i1; listn[*n][1] = j1; listn[*n][2] = i2; listn[*n][3] = j2; *n += 1; } process(board,move,who,b1) int board[][15],b1[][15],move[],who; /************************************************************** * Given a board position and a move, calculate the resulting * * board position. * * (User provided) * **************************************************************/ { int enemy,i1,i2,j1,j2,i,j; int k1,k2; enemy = 0 - who; i1=move[0]; j1=move[1]; i2=move[2]; j2=move[3]; for (i=bstart; i<=bend; i++) for (j=bstart; j<=bend; j++) b1[i][j] = board[i][j]; if (b1[i2][j2] != BOUNDARY) b1[i2][j2] = b1[i1][j1]; b1[i1][j1] = EMPTYSQUARE; } gameovercheck(b,who,g) /************************************************************** * Returns in "g" the current status of the game. * * g = 0: game not over * * g = 1: game over; white wins * * g = -1: game over; black wins * * g = 3: game over, tie * * (User provided) * **************************************************************/ int b[][15],who,*g; { int i,j; int list1[MAXMOVES][4], nl1; int bpop,wpop,epop; *g = 0; bpop = wpop = epop = 0; for (i=bstart; i<=bend; i++) { if (b[bend][i] == WHITE) *g = 1; if (b[bstart][i] == BLACK) *g = -1; } if (*g == 0) { mmlist(b,who,list1,&nl1); if (nl1 == 0) mmlist(b,0-who,list1,&nl1); if (nl1 == 0) *g = 3; } } score1(b,s,who) int b[][15],who,*s; /**************************************************************/ { int i,j,temp,k1,k2,f1,q,enemy; *s = 0; f1 = 0; enemy = 0-who; for (i=bstart; i<=bend; i++) { for (j=bstart; j<=bend; j++) { if (b[i][j] == WHITE) *s += 2 + (i-bstart)*(i-bstart); else *s += -2*(bend-i)*(bend-i) - 2; } } } score2(b,s,who) int b[][15],who,*s; /************************************************************** * Alternate scoring function for use during tournament play * * (User provided) * **************************************************************/ { score1(b,s,who); *s = *s + (rand() % 100); } @EOF chmod 644 hexapawn.c echo x - hexapawn.dat cat >hexapawn.dat <<'@EOF' 1 FirstMove: who moves first? 1:white -1:black -1 WhitePlayer: who is playing the white peices? 1:human -1:computer -1 BlackPlayer: who is playing the black peices? 1:human -1:computer 8 bsize: # of squares on side of board 5 pmax: search depth 0 verbose: set to 1 or 2 to see a lot more stuff printed out 0 killer: DON"T CHANGE THIS - currently inactive 3 NoMoves: 0-win 1:tie 2:lose 3:lose turn 1 sflag: 1:normal 2:play score1 vs score2 (iff both players=computer) 0 tournament:(if=1) play 2 scoring routines against each other 0 tgames: # of games to play in a tournament 0 randmove: # of random moves at the start of a tournament game 0 BoardShape: 0: square 1: hex rhombus (affects board printing only) 0 Pruning: 0: don't N: keep only the first N moves (use w/MoveSort) 1 MoveSort: 0: don't 1: sort by scoring function @EOF chmod 644 hexapawn.dat echo x - othello.c cat >othello.c <<'@EOF' /* Othello game specific routines. Each of these routines needs to * be changed for a new game. */ #include "gameplayer.h" #define OPPONENT(p) p * -1 #define VINVUL 50 #define VCORN 100 /* Corner */ #define VORTH -30 /* Orthogonally next to corner */ #define VDIAG -50 /* Diagonally " " " */ #define VEDGE 20 /* On edge */ #define VNEXT -7 /* Next to edge */ #define VNORM 1 /* Elsewhere */ static int model[64] = { VCORN, VORTH, VEDGE, VEDGE, VEDGE, VEDGE, VORTH, VCORN, VORTH, VDIAG, VNEXT, VNEXT, VNEXT, VNEXT, VDIAG, VORTH, VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE, VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE, VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE, VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE, VORTH, VDIAG, VNEXT, VNEXT, VNEXT, VNEXT, VDIAG, VORTH, VCORN, VORTH, VEDGE, VEDGE, VEDGE, VEDGE, VORTH, VCORN } ; static int Incn[8] = { -9, -8, -7, -1, 1, 7, 8, 9 } ; int count(pos, who) int pos[64], who ; { int i, n ; n = 0 ; for (i = 0; i < 64; i++) if (pos[i] == who) n++ ; return(n) ; } /* This function finds invulnerable pieces, and scores them appropriately; it * does not find ALL invulnerable pieces - in fact, only concave blocks * including a corner - but nevertheless should provide a good approximation. */ find_invulnerable(pos, scores) int pos[64], scores[64] ; { int corner, hwm, i, j, value ; if ((corner = pos[0]) != 0) { value = corner * VINVUL ; hwm = 7 ; for (i = 0; i < 56; i += 8) { if (pos[i] != corner) break ; scores[i] = value ; for (j = 1; j < hwm; j++) { if (pos[i+j] != corner) { hwm = j ; break ; } scores[i+j] = value ; } } scores[0] = corner * VCORN ; } if ((corner = pos[7]) != 0) { value = corner * VINVUL ; hwm = 0 ; for (i = 0; i < 56; i+= 8) { if (pos[i+7] != corner) break ; scores[i+7] = value ; for (j = 6; j > hwm; j--) { if (pos[i+j] != corner) { hwm = j ; break ; } scores[i+j] = value ; } } scores[7] = corner * VCORN ; } if ((corner = pos[56]) != 0) { value = corner * VINVUL ; hwm = 7 ; for (i = 56; i > 0; i -= 8) { if (pos[i] != corner) break ; scores[i] = value ; for (j = 1; j < hwm; j++) { if (pos[i+j] != corner) { hwm = j ; break ; } scores[i+j] = value ; } } scores[56] = corner * VCORN ; } if ((corner = pos[63]) != 0) { value = corner * VINVUL ; hwm = 0 ; for (i = 56; i > 0; i -= 8) { if (pos[i+7] != corner) break ; scores[i+7] = value ; for (j = 6; j > hwm; j--) { if (pos[i+j] != corner) { hwm = j ; break ; } scores[i+j] = value ; } } scores[63] = corner * VCORN ; } } int ismove(pos, who) int pos[64], who ; { int flip, i, j ; flip = 0 ; for (i = 0; i < 64; i++) if (pos[i] != WHITE && pos[i] != BLACK) for (j = 0; j < 8; j++) if (sandwich(i, who, pos, flip, Incn[j])) return(1) ; return(0) ; } int sandwich(move, who, pos, flip, inc) int move, who, pos[64], flip, inc ; { int coff, count, off, piece, roff, square ; int col = move % 8 ; int row = move / 8 ; if ((move+inc) < 0 || (move+inc) > 63) return(0) ; if (pos[move+inc] != OPPONENT(who)) return(0) ; roff = (inc < -1 ? row : /* inc -1: -9, -8, -7 */ inc > 1 ? 7 - row : 8) ; /* inc 1: 7, 8, 9 */ coff = (inc & 4 ? col : /* inc -1: -9, -1, 7 */ inc & 1 ? 7 - col : 8) ; /* inc 1: -7, 1, 9 */ off = (roff > coff ? coff : roff) ; if (off <= 2) return(0) ; count = 1 ; square = move + inc ; while (--off) { if (!(piece = pos[square += inc])) return(0) ; if (piece == who) break ; else count++ ; } if (!off) return(0) ; if (flip) while (count--) pos[square -= inc] = who ; return(1) ; } scrunch_board(old, new) int old[][15], new[64] ; { int col, i, row ; i = 0 ; for (row = bstart; row <= bend; row++) for (col = bstart; col <= bend; col++) new[i++] = old[row][col] ; } /* initpieceplacement: Set up the board for the starting * position. The board should be indexed in the range * bstart to bend. If your board size is larger than 11x11 * you'll have to change the dimensions on the 'board' * array (which appears in many places in this program) * * Returns the board array initialized for the start of a * game. You can use different integers to represent diff. * types of pieces (eg. chess), just make sure that White * is always positive, Black is always negative, and WLOW, * WHIGH, BLOW, BHI (#defines at the top of the program) * are accurate. */ initpieceplacement(board) int board[][15]; { board[bstart+3][bstart+3] = WHITE ; board[bstart+4][bstart+3] = BLACK ; board[bstart+3][bstart+4] = BLACK ; board[bstart+4][bstart+4] = WHITE ; Wpieces[1] = 'W' ; Bpieces[1] = 'B' ; } /* Given a board position, calculate a move list * (User provided) * Note: if there is an easy way for you to order this list so * that good moves are at the beginning, do it! it will save * all kinds of time. * * board: 2d array describing the current board position. * who: whose turn is it to move? 1: white -1: black * list1: Returned as a list of valid moves. * list1[i][0], list1[i][1]: 'from' square of move * list1[i][2], list1[i][3]: 'to' square of move * nl1: returned as the number of valid entries in list1 * * Many games don't have a 'from' square at all (ex: hex, go) * For games of this type, just put the move into the 'to' * square and write your move processing routine correctly. */ mmlist(board, who, list1, nl1) int board[][15], who, list1[][4], *nl1 ; { int flip, i, j, pos[64] ; scrunch_board(board, pos) ; *nl1 = 0 ; flip = 0 ; for (i = 0; i < 64; i++) if (pos[i] != WHITE && pos[i] != BLACK) for (j = 0; j < 8; j++) if (sandwich(i, who, pos, flip, Incn[j])) { madd(0, 0, (i / 8) + bstart, (i % 8) + bstart, list1, nl1) ; break ; } } /* madd: add a new move to the list. */ madd(i1, j1, i2, j2, listn, n) int i1, j1, i2, j2, listn[][4], *n ; { listn[*n][0] = i1 ; listn[*n][1] = j1 ; listn[*n][2] = i2 ; listn[*n][3] = j2 ; *n += 1 ; } /* Given a board position and a move, calculate the resulting * board position. * board: 2d array holding current position * b1: 2d array returned as new board position * move[]: A 4-element array containing: * move[0], move[1] 'from' square * move[2], move[3] 'to' square * who: 1: it's a white move -1: it's a black move */ process(board, move, who, b1) int board[][15], b1[][15], move[], who ; { int flip, i, newmove, pos[64] ; scrunch_board(board, pos) ; newmove = ((move[2]-bstart) * 8) + (move[3] - bstart) ; pos[newmove] = who ; flip = 1 ; for (i = 0; i < 8; i++) sandwich(newmove, who, pos, flip, Incn[i]) ; for (i = 0; i < 64; i++) b1[(i / 8) + bstart][(i % 8) + bstart] = pos[i] ; } /* Returns in "g" the current status of the game. * g = 0: game not over * g = 1: game over; white wins * g = -1: game over; black wins * g = 3: game over, tie * * b: 2d array holding current board position * who: 1: it's a white move -1: it's a black move */ gameovercheck(b, who, g) int b[][15], who, *g ; { int bcount, pos[64], wcount ; scrunch_board(b, pos) ; bcount = count(pos, BLACK) ; wcount = count(pos, WHITE) ; if (ismove(pos, who)) *g = 0 ; else if (ismove(pos, OPPONENT(who))) *g = 0 ; else if (wcount > bcount) *g = 1 ; else if (wcount == bcount) *g = 3 ; else *g = 2 ; } /* Primary scoring function * (User provided) * b: 2d array holding current board position * who: 1: it's a white move -1: it's a black move * s: returned as the numerical score of a position. * The better the position is for White, the higher (more * positive) s should be. * * Make sure the #define constant BIGSCORE is larger than any * possible value that this routine could return * Also, alphabeta will return a score of zero to indicate a * tie game. Make sure this is compatible with your scoring fn. */ score1(board, s, who) int board[][15], who, *s ; { int i, pos[64], scores[64] ; *s = 0 ; scrunch_board(board, pos) ; for (i = 0; i < 64; i++) scores[i] = 0 ; find_invulnerable(pos, scores) ; /* Scores now contains VINVUL (or -VINVUL) for each invulnerable piece, and * 0 elsewhere; now fill in other evaluations (special cases: next to corner * [bad!], on edge[good!], next to edge[poor], anywhere else[boring]) */ for (i = 0; i < 64; i++) *s += (scores[i] ? scores[i] : model[i] * pos[i]) ; } /* Alternate scoring function for use during tournament play * (User provided) * Currently just calls score1 and adds a random number to the * result; so if you do a tournament you should see score1 * win more games than score2. */ score2(board, s, who) int board[][15], who, *s ; { score1(board, s, who) ; *s += (rand() % 30) ; } @EOF chmod 644 othello.c echo x - othello.dat cat >othello.dat <<'@EOF' 1 FirstMove: who moves first? 1:white -1:black 1 WhitePlayer: who is playing the white pieces? 1:human -1:computer -1 BlackPlayer: who is playing the black pieces? 1:human -1:computer 8 bsize: # of squares on side of board 4 pmax: search depth 0 verbose: set to 1 or 2 to see a lot more stuff printed out 0 killer: DON"T CHANGE THIS - currently inactive 3 NoMoves: 0-win 1:tie 2:lose 3:lose turn 1 sflag: 1:normal 2:play score1 vs score2 (iff both players=computer) 0 tournament:(if=1) play 2 scoring routines against each other 0 tgames: # of games to play in a tournament 0 randmove: # of random moves at the start of a tournament game 0 BoardShape: 0: square 1: hex rhombus (affects board printing only) 0 Pruning: 0: don't N: keep only the first N moves (use w/MoveSort) 1 MoveSort: 0: don't 1: sort by scoring function 0 FromSquare: =0 if (no move FROM square for this game(ex hex)), else 1 @EOF chmod 644 othello.dat echo x - hex.c cat >hex.c <<'@EOF' #include "gameplayer.h" initpieceplacement(board) int board[][15]; { if (DEBUG) printf("initpieceplacement \n"); Wpieces[1] = 'H'; Bpieces[1] = 'V'; } mmlist(board,who,list1,nl1) int board[][15],who,list1[][4],*nl1; /************************************************************** * Given a board position, calculate a move list * * (User provided) * * Note: if there is an easy way for you to order this list so * * that good moves are at the beginning, do it! it will save * * all kinds of time. * **************************************************************/ { int i,j; if (DEBUG) printf("mmlist \n"); *nl1 = 0; for (i=bstart; i<=bend; i++) for (j=bstart; j<=bend; j++) if (board[i][j] == EMPTYSQUARE) madd(i,j,list1,nl1); } madd(i2,j2,listn,n) int i2,j2,listn[][4],*n; { listn[*n][0] = 0; listn[*n][1] = 0; listn[*n][2] = i2; listn[*n][3] = j2; *n += 1; } process(board,move,who,b1) int board[][15],b1[][15],move[],who; /************************************************************** * Given a board position and a move, calculate the resulting * * board position. * * (User provided) * **************************************************************/ { int enemy,i2,j2,i,j; if (DEBUG) printf("process \n"); enemy = 0 - who; i2=move[2]; j2=move[3]; for (i=bstart; i<=bend; i++) for (j=bstart; j<=bend; j++) b1[i][j] = board[i][j]; b1[i2][j2] = who; } gameovercheck(b,who,g) /************************************************************** * Returns in "g" the current status of the game. * * g = 0: game not over * * g = 1: game over; white wins * * g = -1: game over; black wins * * g = 3: game over, tie * * (User provided) * **************************************************************/ int b[][15],who,*g; { if (DEBUG) printf("gameovercheck \n"); *g = 0; if (who == WHITE) connhor(b,g); else connvert(b,g); } score1(b,s,who) int b[][15],who,*s; /**************************************************************/ { int k1,k2; if (DEBUG) printf("score1 \n"); Realconnhor(b,&k1,WHITE); /* temp is returned as min of opposite side */ Realconnvert(b,&k2,BLACK); /* get min for opponant */ *s = k2-k1; /* minimize our min (k1) and maximize opponants (k2) */ } score2(b,s,who) int b[][15],who,*s; /************************************************************** * Alternate scoring function for use during tournament play * * (User provided) * **************************************************************/ { if (DEBUG) printf("score2 \n"); score1(b,s,who); *s = *s + (rand() % 100); } connvert(b,res) int b[][15],*res; { int i,j,flag,i1,j1; int conn[15][15]; int clist[500][2],nclist,cclist,current; if (DEBUG) printf("connvert \n"); /* do quick check first - do we have a piece in every row? */ flag = 0; for (i=bstart; i<=bend; i++) { j = bstart; while ((b[i][j] != WHITE) && (b[i][j] != BOUNDARY)) j++; if (b[i][j] == BOUNDARY) { flag=1; i=bend+1; } } if (flag == 1) { /* we don't have a piece in every row */ *res=0; } /* maybe a good second level check would be to see if the hexes */ /* in a row are touching a hex in a neighboring row */ else { /* we have a piece in every row - check further */ nclist = 0; cclist = 0; for (i=0; i<15; i++) for (j=0; j<15; j++) conn[i][j] = 30; for (i=bstart; i<=bend; i++) { /* mark pieces in first row */ if (b[bstart][i] == BLACK) { clist[nclist][0] = i; clist[nclist][1] = bstart; nclist++; } for (j=bstart; j<=bend; j++) conn[i][j] = i-bstart; } while (cclist < nclist) { i1 = clist[cclist][0]; /* make all touching pieces the same value as */ j1 = clist[cclist][1]; /* this one */ current = conn[i1][j1]; dohex(b,conn,i1,j1,clist,&nclist,current,WHITE); cclist++; } /* end while */ *res = 0; for (i=bstart; i<=bend; i++) /* did the connection reach the far side? */ if (conn[bend][i] == 0) *res = -1; } /* end else if */ } connhor(b,res) int b[][15],*res; { int i,j,flag,i1,j1; int conn[15][15]; int clist[500][2],nclist,cclist,current; if (DEBUG) printf("connhor \n"); /* do quick check first - do we have a piece in every column? */ flag = 0; for (i=bstart; i<=bend; i++) { j = bstart; while ((b[j][i] != WHITE) && (b[j][i] != BOUNDARY)) j++; if (b[j][i] == BOUNDARY) { flag=1; i=bend+1; } } if (flag == 1) { /* we don't have a piece in every column */ *res=0; } /* maybe a good second level check would be to see if the hexes */ /* in a column are touching a hex in a neighboring column */ else { /* we have a piece in every column - check further */ nclist = 0; cclist = 0; for (i=0; i<15; i++) for (j=0; j<15; j++) conn[i][j] = 30; for (i=bstart; i<=bend; i++) { /* mark pieces in first column */ if (b[i][bstart] == WHITE) { clist[nclist][0] = i; clist[nclist][1] = bstart; nclist++; } for (j=bstart; j<=bend; j++) conn[i][j] = j-bstart; } while (cclist < nclist) { i1 = clist[cclist][0]; /* make all touching pieces the same value as */ j1 = clist[cclist][1]; /* this one */ current = conn[i1][j1]; dohex(b,conn,i1,j1,clist,&nclist,current,WHITE); cclist++; } /* end while */ *res = 0; for (i=bstart; i<=bend; i++) /* did the connection reach the far side? */ if (conn[i][bend] == 0) *res = 1; } /* end else if */ } dohex(b,conn,i1,j1,clist,nclist,current,who) int b[][15],conn[][15],i1,j1,clist[][2],*nclist,current; { if (DEBUG) printf("dohex \n"); if ((b[i1+1][j1] == who) && (conn[i1+1][j1] > current)) update(conn,i1+1,j1,clist,nclist,current); if ((b[i1-1][j1] == who) && (conn[i1-1][j1] > current)) update(conn,i1-1,j1,clist,nclist,current); if ((b[i1][j1-1] == who) && (conn[i1][j1-1] > current)) update(conn,i1,j1-1,clist,nclist,current); if ((b[i1][j1+1] == who) && (conn[i1][j1+1] > current)) update(conn,i1,j1+1,clist,nclist,current); if ((b[i1-1][j1+1] == who) && (conn[i1-1][j1+1] > current)) update(conn,i1-1,j1+1,clist,nclist,current); if ((b[i1+1][j1-1] == who) && (conn[i1+1][j1-1] > current)) update(conn,i1+1,j1-1,clist,nclist,current); } update(conn,i1,j1,clist,nclist,current) int conn[][15],i1,j1,clist[][2],*nclist,current; { if ((i1>=bstart) && (i1<=bend) && (j1>=bstart) && (j1<=bend)) { conn[i1][j1] = current; clist[*nclist][0] = i1; clist[*nclist][1] = j1; *nclist += 1; } } initconnhor(board,conn,clist,nclist) int board[][15],conn[][15],clist[][2],*nclist; { int i,j,res; if (DEBUG) printf("initconnhor \n"); for (i=0; i<15; i++) for (j=0; j<15; j++) conn[i][j] = 30; *nclist=0; for (i=bstart; i<=bend; i++) { if (board[i][bstart] != BLACK) update(conn,i,bstart,clist,nclist,0); if (board[i][bstart+1] != BLACK) { Link2Left(board,i,bstart+1,&res,BLACK); if (res == 1) update(conn,i,bstart+1,clist,nclist,0); } if ((i>(bstart+1)) && (board[i][bstart+2] == WHITE)) { Link3Left(board,i,bstart+2,&res,BLACK); if (res == 1) update(conn,i,bstart+2,clist,nclist,0); } if ((i>(bstart+3)) && (i<(bend-1)) && (board[i][bstart+3] == WHITE)) { Link4Left(board,i,bstart+3,&res,BLACK); if (res == 1) update(conn,i,bstart+3,clist,nclist,0); } } /* next i */ } initconnvert(board,conn,clist,nclist) int board[][15],conn[][15],clist[][2],*nclist; { int i,j,res; if (DEBUG) printf("initconnvert \n"); for (i=0; i<15; i++) for (j=0; j<15; j++) conn[i][j] = 30; *nclist=0; for (i=bstart; i<=bend; i++) { if (board[bstart][i] != WHITE) update(conn,i,bstart,clist,nclist,0); if (board[bstart+1][i] != WHITE) { Link2North(board,bstart+1,i,&res,WHITE); if (res == 1) update(conn,bstart+1,i,clist,nclist,0); } if ((i>(bstart+1)) && (board[bstart+2][i] != WHITE)) { Link3North(board,bstart+2,i,&res,WHITE); if (res == 1) update(conn,bstart+2,i,clist,nclist,0); } if ((i>(bstart+3)) && (i<(bend-1)) && (board[bstart+3][i] != WHITE)) { Link4North(board,bstart+3,i,&res,BLACK); if (res == 1) update(conn,bstart+3,i,clist,nclist,0); } } /* next i */ } Realconnvert(board,res,who) int *res,board[][15],who; { int i,flag; int smallcon; int i1,j1,current; int conn[15][15]; int clist[300][2]; int cclist,nclist; if (DEBUG) printf("Realconnvert \n"); nclist = 0; cclist = 0; initconnvert(board,conn,clist,&nclist); while (cclist < nclist) { i1 = clist[cclist][0]; /* make all touching pieces the same value as */ j1 = clist[cclist][1]; /* this one */ current = conn[i1][j1]; if (board[i1][j1] == 1) dohexfar(board,conn,clist,&nclist,i1,j1,current,current+1,BLACK); else if (board[i1][j1] == 0) dohexfar(board,conn,clist,&nclist,i1,j1,current+1,current+1,BLACK); cclist++; } /* end while */ smallcon=conn[bend][bstart]; for (i=bstart+1; i<=bend; i++) if (conn[bend][i] < smallcon) smallcon = conn[bend][i]; /* smallcon is now the best link on the edge = check more distant ones */ for (i=bstart; i<=bend-1; i++) { if (conn[bend-1][i] < smallcon) { Link2South(board,bend-1,i,&flag,0-who); if (flag == 1) smallcon = conn[bend-1][i]; }} for (i=bstart; i<=bend-2; i++) { if (conn[bend-2][i] < smallcon) { Link3South(board,bend-2,i,&flag,0-who); if (flag == 1) smallcon = conn[bend-2][i]; }} for (i=bstart+1; i<=bend-4; i++) { if (conn[bend-3][i] < smallcon) { Link4South(board,bend-3,i,&flag,0-who); if (flag == 1) smallcon = conn[bend-3][i]; }} *res = smallcon; } Realconnhor(board,res,who) int *res,board[][15],who; { int i,flag,j; int smallcon; int i1,j1,current; int conn[15][15]; int clist[300][2]; int cclist,nclist; if (DEBUG) printf("Realconnhor \n"); nclist = 0; cclist = 0; initconnhor(board,conn,clist,&nclist); while (cclist < nclist) { i1 = clist[cclist][0]; /* make all touching pieces the same value as */ j1 = clist[cclist][1]; /* this one */ current = conn[i1][j1]; if (board[i1][j1] == 1) dohexfar(board,conn,clist,&nclist,i1,j1,current,current+1,WHITE); else if (board[i1][j1] == 0) dohexfar(board,conn,clist,&nclist,i1,j1,current+1,current+1,WHITE); cclist++; } /* end while */ smallcon = conn[bstart][bend]; for (i=bstart+1; i<=bend; i++) if (conn[i][bend] < smallcon) smallcon = conn[i][bend]; /* smallcon is now the best link on the edge = check more distant ones */ for (i=bstart; i<=bend-1; i++) { if (conn[i][bend-1] < smallcon) { Link2Right(board,i,bend-1,&flag,0-who); if (flag == 1) smallcon = conn[i][bend-1]; }} for (i=bstart; i<=bend-2; i++) { if ((conn[i][bend-2] < smallcon) && (board[i][bend-2] == WHITE)) { Link3Right(board,i,bend-2,&flag,0-who); if (flag == 1) smallcon = conn[i][bend-2]; }} for (i=bstart+1; i<=bend-4; i++) { if ((conn[i][bend-3] < smallcon) && (board[i][bend-3] == WHITE)) { Link4Right(board,i,bend-3,&flag,0-who); if (flag == 1) smallcon = conn[i][bend-3]; }} *res = smallcon; /* printf(" \n"); for (i=bstart; i<=bend; i++) { for (j=0; j<(bend-i); j++) printf(" "); for (j=bstart; j<=bend; j++) { printf("%3d",conn[i][j]); } printf(" \n"); } */ } dohexfar(board,conn,clist,nclist,i1,j1,nHex,nBlank,who) int board[][15],conn[][15],clist[][2],*nclist,i1,j1,nHex,nBlank,who; { int i; int i2,j2; static int a[]={1,1,0,-1,-1,0,1}; /* offsets for surrounding hexes */ static int bb[]={0,1,1,0,-1,-1,0}; /* first one is repeated to avoid bounds */ /* checking for 2-links */ static int fa[]={2,1,-1,-2,-1,1}; /* offsets for 2-link hexes */ static int fb[]={1,2,1,-1,-2,-1}; if (DEBUG) printf("dohexfar from:%d %d hex: %d blank: %d\n",i1,j1,nHex,nBlank); /* do the 1-link hexes */ for (i=0; i<6; i++) { i2=i1+a[i]; j2=j1+bb[i]; if ((conn[i2][j2]>nHex) && (board[i2][j2]==who)) { update(conn,i2,j2,clist,nclist,nHex); } else if ((conn[i2][j2]>nBlank) && (board[i2][j2]==0)) { update(conn,i2,j2,clist,nclist,nBlank); } } /* next i */ /* now do the 2-link hexes */ for (i=0; i<6; i++) { if (board[i1+a[i]][j1+bb[i]] == EMPTYSQUARE) { /* check that the */ if (board[i1+a[i+1]][j1+bb[i+1]] == EMPTYSQUARE) { /* 1-links r clear */ i2=i1+fa[i]; /* the 2-link hex */ j2=j1+fb[i]; if ((board[i2][j2] == who) && (conn[i2][j2] > nHex)) { update(conn,i2,j2,clist,nclist,nHex); } else if ((board[i2][j2] == 0) && (conn[i2][j2] > nBlank)) { update(conn,i2,j2,clist,nclist,nBlank); } } } } return 0; } /* return 1 if things are cool, 0 if they're not */ strip(b,i,j,inci,incj,res,ValToAvoid) int i,j,inci,incj,*res,ValToAvoid; int b[][15]; { int i1,j1; i1=i; j1=j; while ((b[i1][j1] != ValToAvoid) && (b[i1][j1] != BOUNDARY)) { i1 += inci; j1 += incj; } *res=0; if (b[i1][j1] == BOUNDARY) *res=1; } Link4Left(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; strip(b,i-1,j,-1,-1,res,ValToAvoid); if (res) strip(b,i,j,-1,-1,res,ValToAvoid); if (res) strip(b,i+1,j,-1,-1,res,ValToAvoid); if (res) Link3Left(b,i+1,j-1,res,ValToAvoid); if (*res) { strip(b,i-3,j,-1,-1,&res1,ValToAvoid); if (res1 == 0) { strip(b,i+2,j-1,0,-1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link4Right(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; strip(b,i+1,j,1,1,res,ValToAvoid); if (res) strip(b,i,j,1,1,res,ValToAvoid); if (res) strip(b,i-1,j,1,1,res,ValToAvoid); if (res) Link3Right(b,i-1,j+1,res,ValToAvoid); if (*res) { strip(b,i+3,j,1,1,&res1,ValToAvoid); if (res1 == 0) { strip(b,i-2,j+1,0,1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link4North(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; strip(b,i,j+1,-1,0,res,ValToAvoid); if (res) strip(b,i,j,-1,0,res,ValToAvoid); if (res) strip(b,i,j-1,-1,0,res,ValToAvoid); if (res) Link3North(b,i-1,j-2,res,ValToAvoid); if (*res) { strip(b,i-1,j+2,-1,0,&res1,ValToAvoid); if (res1 == 0) { strip(b,i-1,j-3,-1,-1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link4South(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; strip(b,i,j-1,1,0,res,ValToAvoid); if (res) strip(b,i,j,1,0,res,ValToAvoid); if (res) strip(b,i,j+1,1,0,res,ValToAvoid); if (res) Link3North(b,i+1,j+2,res,ValToAvoid); if (*res) { strip(b,i+1,j-2,1,0,&res1,ValToAvoid); if (res1 == 0) { strip(b,i+1,j+3,1,1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link3Left(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; Link2Left(b,i-1,j-1,res,ValToAvoid); if (*res) strip(b,i,j,0,-1,res,ValToAvoid); if (*res) { strip(b,i-1,j,-1,-1,&res1,ValToAvoid); if (res1 == 0) { strip(b,i+1,j,0,-1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link3Right(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; Link2Right(b,i+1,j+1,res,ValToAvoid); if (*res) strip(b,i,j,0,1,res,ValToAvoid); if (*res) { strip(b,i+1,j,1,1,&res1,ValToAvoid); if (res1 == 0) { strip(b,i-1,j,0,1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link3North(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; Link2North(b,i-1,j-1,res,ValToAvoid); if (*res) strip(b,i,j,-1,0,res,ValToAvoid); if (*res) { strip(b,i,j+1,-1,0,&res1,ValToAvoid); if (res1 == 0) { strip(b,i,j-1,-1,-1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link3South(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { int res1; Link2South(b,i+1,j+1,res,ValToAvoid); if (*res) strip(b,i,j,1,0,res,ValToAvoid); if (*res) { strip(b,i,j-1,1,0,&res1,ValToAvoid); if (res1 == 0) { strip(b,i,j+1,1,1,&res1,ValToAvoid); if (res1 == 0) *res=0; } } } Link2Left(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { *res=0; if ( (b[i][j] != ValToAvoid) && (b[i][j] != BOUNDARY) && (b[i][j-1] != ValToAvoid) && (b[i][j-1] != BOUNDARY) && (b[i-1][j-1] != ValToAvoid) && (b[i-1][j-1] != BOUNDARY)) *res=1; } Link2Right(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { *res=0; if ( (b[i][j] != ValToAvoid) && (b[i][j] != BOUNDARY) && (b[i][j+1] != ValToAvoid) && (b[i][j+1] != BOUNDARY) && (b[i+1][j+1] != ValToAvoid) && (b[i+1][j+1] != BOUNDARY)) *res=1; } Link2North(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { *res=0; if ( (b[i][j] != ValToAvoid) && (b[i][j] != BOUNDARY) && (b[i-1][j] != ValToAvoid) && (b[i-1][j] != BOUNDARY) && (b[i-1][j-1] != ValToAvoid) && (b[i-1][j-1] != BOUNDARY)) *res=1; } Link2South(b,i,j,res,ValToAvoid) int i,j,*res,ValToAvoid; int b[][15]; { *res=0; if ( (b[i][j] != ValToAvoid) && (b[i][j] != BOUNDARY) && (b[i-1][j] != ValToAvoid) && (b[i-1][j] != BOUNDARY) && (b[i-1][j-1] != ValToAvoid) && (b[i-1][j-1] != BOUNDARY)) *res=1; } @EOF chmod 644 hex.c echo x - hex.dat cat >hex.dat <<'@EOF' 1 FirstMove: who moves first? 1:white -1:black -1 WhitePlayer: who is playing the white peices? 1:human -1:computer 1 BlackPlayer: who is playing the black peices? 1:human -1:computer 3 bsize: # of squares on side of board 1 pmax: search depth 0 verbose: set to 1 or 2 to see a lot more stuff printed out 0 killer: DON"T CHANGE THIS - currently inactive 3 NoMoves: 0-win 1:tie 2:lose 3:lose turn 1 sflag: 1:normal 2:play score1 vs score2 (iff both players=computer) 0 tournament:(if=1) play 2 scoring routines against each other 0 tgames: # of games to play in a tournament 0 randmove: # of random moves at the start of a tournament game 1 BoardShape: 0: square 1: hex rhombus (affects board printing only) 0 Pruning: 0: don't N: keep only the first N moves (use w/MoveSort) 0 MoveSort: 0: don't 1: sort by scoring function 0 FromSquare: =0 if (no move FROM square for this game(ex hex)), else 1 @EOF chmod 644 hex.dat exit 0