diff options
Diffstat (limited to 'games/backgammon')
| -rw-r--r-- | games/backgammon/backgammon/Makefile | 4 | ||||
| -rw-r--r-- | games/backgammon/backgammon/backgammon.6 | 11 | ||||
| -rw-r--r-- | games/backgammon/backgammon/backlocal.h | 7 | ||||
| -rw-r--r-- | games/backgammon/backgammon/move.c | 192 | ||||
| -rw-r--r-- | games/backgammon/backgammon/pubeval.c | 147 |
5 files changed, 175 insertions, 186 deletions
diff --git a/games/backgammon/backgammon/Makefile b/games/backgammon/backgammon/Makefile index 88b7038685d..874077dfea0 100644 --- a/games/backgammon/backgammon/Makefile +++ b/games/backgammon/backgammon/Makefile @@ -1,10 +1,10 @@ -# $OpenBSD: Makefile,v 1.8 2002/05/23 18:43:00 deraadt Exp $ +# $OpenBSD: Makefile,v 1.9 2002/07/30 18:11:52 pjanzen Exp $ # @(#)Makefile 8.1 (Berkeley) 5/31/93 PROG= backgammon CFLAGS+=-I${.CURDIR}/../common_source SRCS= allow.c board.c check.c extra.c fancy.c init.c main.c move.c \ - odds.c one.c save.c subs.c table.c text.c + odds.c pubeval.c one.c save.c subs.c table.c text.c MAN= backgammon.6 DPADD= ${LIBCURSES} LDADD= -lcurses diff --git a/games/backgammon/backgammon/backgammon.6 b/games/backgammon/backgammon/backgammon.6 index 2cd860b41fc..7390e6e94e7 100644 --- a/games/backgammon/backgammon/backgammon.6 +++ b/games/backgammon/backgammon/backgammon.6 @@ -1,4 +1,4 @@ -.\" $OpenBSD: backgammon.6,v 1.9 2001/11/17 05:27:09 pjanzen Exp $ +.\" $OpenBSD: backgammon.6,v 1.10 2002/07/30 18:11:52 pjanzen Exp $ .\" .\" Copyright (c) 1980, 1993 .\" The Regents of the University of California. All rights reserved. @@ -126,7 +126,7 @@ the roll .Ic r separated by commas or spaces and ending with a newline. Available abbreviations are -.Bl -tag -width indent +.Bl -tag -width XXXXXXX .It Ic s-f1-f2 means .Ic s-f1,f1-f2 @@ -144,10 +144,13 @@ for home, or 0 or 25 as appropriate. .Sh AUTHORS Alan Char +.Pp +The strategy is the +.Dq pubeval +algorithm of Gerry Tesauro, +with minimal doubling logic added. .Sh FILES .Bl -tag -width /usr/games/teachgammon -compact .It Pa /usr/games/teachgammon rules and tutorial .El -.Sh BUGS -The program's strategy needs much work. diff --git a/games/backgammon/backgammon/backlocal.h b/games/backgammon/backgammon/backlocal.h index 5d7f8eb8ae6..f6070dc383d 100644 --- a/games/backgammon/backgammon/backlocal.h +++ b/games/backgammon/backgammon/backlocal.h @@ -1,4 +1,4 @@ -/* $OpenBSD: backlocal.h,v 1.3 2002/02/16 21:27:08 millert Exp $ */ +/* $OpenBSD: backlocal.h,v 1.4 2002/07/30 18:11:52 pjanzen Exp $ */ /*- * Copyright (c) 1997 The NetBSD Foundation, Inc. @@ -40,9 +40,8 @@ void dble(void); int dblgood(void); int eval(void); int freemen(int); -void movcmp(void); void domove(int); -int movegood(void); -void pickmove(void); int trapped(int, int); void trymove(int, int); +float pubeval(int); +void setx(void); diff --git a/games/backgammon/backgammon/move.c b/games/backgammon/backgammon/move.c index 4f0af367325..beb9d944f91 100644 --- a/games/backgammon/backgammon/move.c +++ b/games/backgammon/backgammon/move.c @@ -1,4 +1,4 @@ -/* $OpenBSD: move.c,v 1.5 2002/02/16 21:27:08 millert Exp $ */ +/* $OpenBSD: move.c,v 1.6 2002/07/30 18:11:52 pjanzen Exp $ */ /* * Copyright (c) 1980, 1993 @@ -37,17 +37,13 @@ #if 0 static char sccsid[] = "@(#)move.c 8.1 (Berkeley) 5/31/93"; #else -static char rcsid[] = "$OpenBSD: move.c,v 1.5 2002/02/16 21:27:08 millert Exp $"; +static char rcsid[] = "$OpenBSD: move.c,v 1.6 2002/07/30 18:11:52 pjanzen Exp $"; #endif #endif /* not lint */ #include "back.h" #include "backlocal.h" -#ifdef DEBUG -static char tests[20]; -#endif - struct BOARD { /* structure of game position */ int b_board[26]; /* board position */ int b_in[2]; /* men in */ @@ -60,38 +56,21 @@ struct BOARD { /* structure of game position */ struct BOARD *freeq = 0; struct BOARD *checkq = 0; -/* these variables are values for the candidate move */ -static int ch; /* chance of being hit */ -static int op; /* computer's open men */ -static int pt; /* comp's protected points */ -static int em; /* farthest man back */ -static int frc; /* chance to free comp's men */ -static int frp; /* chance to free pl's men */ - -/* these values are the values for the move chosen (so far) */ -static int chance; /* chance of being hit */ -static int openmen; /* computer's open men */ -static int points; /* comp's protected points */ -static int endman; /* farthest man back */ -static int barmen; /* men on bar */ -static int menin; /* men in inner table */ -static int menoff; /* men off board */ -static int oldfrc; /* chance to free comp's men */ -static int oldfrp; /* chance to free pl's men */ - static int cp[5]; /* candidate start position */ static int cg[5]; /* candidate finish position */ static int race; /* game reduced to a race */ - +static float bestmove; static int bcomp(struct BOARD *, struct BOARD *); static struct BOARD *bsave(void); static void binsert(struct BOARD *); static void boardcopy(struct BOARD *); static void makefree(struct BOARD *); +static void movcmp(void); static void mvcheck(struct BOARD *, struct BOARD *); static struct BOARD *nextfree(void); +static void pickmove(void); void @@ -101,6 +80,7 @@ domove(okay) int i; /* index */ int l = 0; /* last man */ + bestmove = -9999999.; if (okay) { /* see if comp should double */ if (gvalue < 64 && dlast != cturn && dblgood()) { addstr(*Colorptr); @@ -135,6 +115,7 @@ domove(okay) nexturn(); return; } + /* initialize */ for (i = 0; i < 4; i++) cp[i] = cg[i] = 0; @@ -322,7 +303,7 @@ mvcheck(incumbent, candidate) } } -void +static void makefree(dead) struct BOARD *dead; /* dead position */ { @@ -350,7 +331,7 @@ nextfree() return(new); } -void +static void pickmove() { /* current game position */ @@ -392,160 +373,19 @@ boardcopy(s) } } -void +static void movcmp() { - int i; - -#ifdef DEBUG - if (trace == NULL) - trace = fopen("bgtrace", "w"); -#endif + int i; + float f; - odds(0, 0, 0); - if (!race) { - ch = op = pt = 0; - for (i = 1; i < 25; i++) { - if (board[i] == cturn) - ch = canhit(i, 1); - op += abs(bar - i); - } - for (i = bar + cturn; i != home; i += cturn) - if (board[i] * cturn > 1) - pt += abs(bar - i); - frc = freemen(bar) + trapped(bar, cturn); - frp = freemen(home) + trapped(home, -cturn); - } - for (em = bar; em != home; em += cturn) - if (board[em] * cturn > 0) - break; - em = abs(home - em); -#ifdef DEBUG - fputs("Board: ", trace); - for (i = 0; i < 26; i++) - fprintf(trace, " %d", board[i]); - if (race) - fprintf(trace, "\n\tem = %d\n", em); - else - fprintf(trace, - "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n", - ch, pt, em, frc, frp); - fputs("\tMove: ", trace); - for (i = 0; i < mvlim; i++) - fprintf(trace, " %d-%d", p[i], g[i]); - fputs("\n", trace); - fflush(trace); - strcpy(tests, ""); -#endif - if ((cp[0] == 0 && cg[0] == 0) || movegood()) { -#ifdef DEBUG - fprintf(trace, "\t[%s] ... wins.\n", tests); - fflush(trace); -#endif + setx(); + f = pubeval(race); + if (f > bestmove) { + bestmove = f; for (i = 0; i < mvlim; i++) { cp[i] = p[i]; cg[i] = g[i]; } - if (!race) { - chance = ch; - openmen = op; - points = pt; - endman = em; - barmen = abs(board[home]); - oldfrc = frc; - oldfrp = frp; - } - menin = *inptr; - menoff = *offptr; - } -#ifdef DEBUG - else { - fprintf(trace, "\t[%s] ... loses.\n", tests); - fflush(trace); - } -#endif -} - -int -movegood() -{ - int n; - - if (*offptr == 15) - return(1); - if (menoff == 15) - return(0); - if (race) { -#ifdef DEBUG - strcat(tests, "o"); -#endif - if (*offptr - menoff) - return(*offptr > menoff); -#ifdef DEBUG - strcat(tests, "e"); -#endif - if (endman - em) - return(endman > em); -#ifdef DEBUG - strcat(tests, "i"); -#endif - if (menin == 15) - return(0); - if (*inptr == 15) - return(1); -#ifdef DEBUG - strcat(tests, "i"); -#endif - if (*inptr - menin) - return(*inptr > menin); - return(rnum(2)); - } else { - n = barmen - abs(board[home]); -#ifdef DEBUG - strcat(tests, "c"); -#endif - if (abs(chance - ch) + 25 * n > rnum(150)) - return(n ? (n < 0) : (ch < chance)); -#ifdef DEBUG - strcat(tests,"o"); -#endif - if (*offptr - menoff) - return(*offptr > menoff); -#ifdef DEBUG - strcat(tests, "o"); -#endif - if (abs(openmen - op) > 7 + rnum(12)) - return(openmen > op); -#ifdef DEBUG - strcat(tests, "b"); -#endif - if (n) - return(n < 0); -#ifdef DEBUG - strcat(tests, "e"); -#endif - if (abs(endman - em) > rnum(2)) - return(endman > em); -#ifdef DEBUG - strcat(tests, "f"); -#endif - if (abs(frc - oldfrc) > rnum(2)) - return(frc < oldfrc); -#ifdef DEBUG - strcat(tests, "p"); -#endif - if (abs(n = pt - points) > rnum(4)) - return(n > 0); -#ifdef DEBUG - strcat(tests, "i"); -#endif - if (*inptr - menin) - return(*inptr > menin); -#ifdef DEBUG - strcat(tests, "f"); -#endif - if (abs(frp - oldfrp) > rnum(2)) - return(frp > oldfrp); - return(rnum(2)); } } diff --git a/games/backgammon/backgammon/pubeval.c b/games/backgammon/backgammon/pubeval.c new file mode 100644 index 00000000000..9feedb14a7c --- /dev/null +++ b/games/backgammon/backgammon/pubeval.c @@ -0,0 +1,147 @@ +/* $OpenBSD: pubeval.c,v 1.1 2002/07/30 18:11:52 pjanzen Exp $ */ +/* Public domain, Gerry Tesauro. */ + +#ifndef lint +static const char rcsid[] = "$OpenBSD: pubeval.c,v 1.1 2002/07/30 18:11:52 pjanzen Exp $"; +#endif + +/* Backgammon move-selection evaluation function for benchmark comparisons. + * Computes a linear evaluation function: Score = W * X, where X is an + * input vector encoding the board state (using a raw encoding of the number + * of men at each location), and W is a weight vector. Separate weight + * vectors are used for racing positions and contact positions. Makes lots + * of obvious mistakes, but provides a decent level of play for benchmarking + * purposes. + */ + +/* Provided as a public service to the backgammon programming community by + * Gerry Tesauro, IBM Research. (e-mail: tesauro@watson.ibm.com) + */ + +/* The following inputs are needed for this routine: + * + * race is an integer variable which should be set based on the INITIAL + * position BEFORE the move. Set race=1 if the position is a race (i.e. no + * contact) and 0 if the position is a contact position. + * + * pos[] is an integer array of dimension 28 which should represent a legal + * final board state after the move. Elements 1-24 correspond to board + * locations 1-24 from computer's point of view, i.e. computer's men move in + * the negative direction from 24 to 1, and opponent's men move in the + * positive direction from 1 to 24. Computer's men are represented by + * positive integers, and opponent's men are represented by negative + * integers. Element 25 represents computer's men on the bar (positive + * integer), and element 0 represents opponent's men on the bar (negative + * integer). Element 26 represents computer's men off the board (positive + * integer), and element 27 represents opponent's men off the board + * (negative integer). + */ + +#include "back.h" +#include "backlocal.h" + +static float x[122]; +static int pos[28]; + +static const float wc[122] = { + 0.25696, -0.66937, -1.66135, -2.02487, -2.53398, -0.16092, -1.11725, -1.06654, +-0.92830, -1.99558, -1.10388, -0.80802, 0.09856, -0.62086, -1.27999, -0.59220, +-0.73667, 0.89032, -0.38933, -1.59847, -1.50197, -0.60966, 1.56166, -0.47389, +-1.80390, -0.83425, -0.97741, -1.41371, 0.24500, 0.10970, -1.36476, -1.05572, + 1.15420, 0.11069, -0.38319, -0.74816, -0.59244, 0.81116, -0.39511, 0.11424, +-0.73169, -0.56074, 1.09792, 0.15977, 0.13786, -1.18435, -0.43363, 1.06169, +-0.21329, 0.04798, -0.94373, -0.22982, 1.22737, -0.13099, -0.06295, -0.75882, +-0.13658, 1.78389, 0.30416, 0.36797, -0.69851, 0.13003, 1.23070, 0.40868, +-0.21081, -0.64073, 0.31061, 1.59554, 0.65718, 0.25429, -0.80789, 0.08240, + 1.78964, 0.54304, 0.41174, -1.06161, 0.07851, 2.01451, 0.49786, 0.91936, +-0.90750, 0.05941, 1.83120, 0.58722, 1.28777, -0.83711, -0.33248, 2.64983, + 0.52698, 0.82132, -0.58897, -1.18223, 3.35809, 0.62017, 0.57353, -0.07276, +-0.36214, 4.37655, 0.45481, 0.21746, 0.10504, -0.61977, 3.54001, 0.04612, +-0.18108, 0.63211, -0.87046, 2.47673, -0.48016, -1.27157, 0.86505, -1.11342, + 1.24612, -0.82385, -2.77082, 1.23606, -1.59529, 0.10438, -1.30206, -4.11520, + 5.62596, -2.75800 +}; + +static const float wr[122] = { + 0.00000, -0.17160, 0.27010, 0.29906, -0.08471, 0.00000, -1.40375, -1.05121, + 0.07217, -0.01351, 0.00000, -1.29506, -2.16183, 0.13246, -1.03508, 0.00000, +-2.29847, -2.34631, 0.17253, 0.08302, 0.00000, -1.27266, -2.87401, -0.07456, +-0.34240, 0.00000, -1.34640, -2.46556, -0.13022, -0.01591, 0.00000, 0.27448, + 0.60015, 0.48302, 0.25236, 0.00000, 0.39521, 0.68178, 0.05281, 0.09266, + 0.00000, 0.24855, -0.06844, -0.37646, 0.05685, 0.00000, 0.17405, 0.00430, + 0.74427, 0.00576, 0.00000, 0.12392, 0.31202, -0.91035, -0.16270, 0.00000, + 0.01418, -0.10839, -0.02781, -0.88035, 0.00000, 1.07274, 2.00366, 1.16242, + 0.22520, 0.00000, 0.85631, 1.06349, 1.49549, 0.18966, 0.00000, 0.37183, +-0.50352, -0.14818, 0.12039, 0.00000, 0.13681, 0.13978, 1.11245, -0.12707, + 0.00000, -0.22082, 0.20178, -0.06285, -0.52728, 0.00000, -0.13597, -0.19412, +-0.09308, -1.26062, 0.00000, 3.05454, 5.16874, 1.50680, 5.35000, 0.00000, + 2.19605, 3.85390, 0.88296, 2.30052, 0.00000, 0.92321, 1.08744, -0.11696, +-0.78560, 0.00000, -0.09795, -0.83050, -1.09167, -4.94251, 0.00000, -1.00316, +-3.66465, -2.56906, -9.67677, 0.00000, -2.77982, -7.26713, -3.40177,-12.32252, + 0.00000, 3.42040 +}; + + +float +pubeval(int race) +{ + int i; + float score; + + if (pos[26] == 15) + return (99999999.); + /* all men off, best possible move */ + + setx(); /* sets input array x[] */ + score = 0.0; + if (race) { /* use race weights */ + for (i = 0; i < 122; ++i) + score += wr[i] * x[i]; + } else { /* use contact weights */ + for (i = 0; i < 122; ++i) + score += wc[i] * x[i]; + } + return (score); +} + +/* sets input vector x[] given board position pos[] */ +void +setx() +{ + int i, j, jm1, n; + + /* initialize */ + for (j = 0; j < 122; ++j) + x[j] = 0.0; + if (cturn > 0) { /* we are red, going from 1->24 */ + for (i = 0; i < 26; i++) + pos[25 - i] = board[i]; + } else { /* we are white, going from 24 -> 1 */ + for (i = 0; i < 26; i++) + pos[i] = -board[i]; + } + pos[26] = *offptr; + pos[27] = -(*offopp); + + /* first encode board locations 24-1 */ + for (j = 1; j <= 24; ++j) { + jm1 = j - 1; + n = pos[25 - j]; + if (n != 0) { + if (n == -1) + x[5 * jm1 + 0] = 1.0; + else if (n == 1) + x[5 * jm1 + 1] = 1.0; + else if (n == 3) + x[5 * jm1 + 3] = 1.0; + if (n >= 4) + x[5 * jm1 + 4] = (float) (n - 3) / 2.0; + if (n >= 2) + x[5 * jm1 + 2] = 1.0; + } + } + /* encode opponent barmen */ + x[120] = -(float) (pos[0]) / 2.0; + /* encode computer's menoff */ + x[121] = (float) (pos[26]) / 15.0; +} |