📄 stone.c
字号:
char *optchars = "ab";
#else
char *optchars = "";
#endif
/* 1. Get command line arguments: */
#if TRACE
ab = db = 0;
#endif
errflag = 0;
while ((c = getopt(argc, argv, optchars)) != EOF) {
switch (c) {
default :
fprintf(stderr, "stone(main): error in getopt()");
exit(1);
case '?' : /* getopt() found illegal option letter */
errflag = TRUE;
break; /* has already complained */
#if TRACE
case 'a' :
ab = TRUE;
break;
case 'd' :
ab = db = TRUE;
break;
#endif
}
}
if (errflag || optind < argc) { /* error or arguments */
#if TRACE
fprintf(stderr, "usage: stone [-ad]\n");
#else
fprintf(stderr, "usage: stone\n");
#endif
exit(1);
}
initscr();
/* 2. Keep playing as long as user wants to: */
do {
/* 3. Display an empty board: */
initb(board);
printb(board);
/* 4. Get game parameters: */
get_game_parameters();
initb(board);
if (!pbegins) goto first;
/* 5. Main move loop: */
while (!done(board)) {
/* 6. Get player's move */
do {
pmove = get_players_move(board);
if (pmove == -1) { /* user entered 'q' */
goto quit;
}
} while (!dmove(board, pmove) && !done(board));
/* 7. Get computer's move: */
first:
{
int first = 0, y, x;
move(20, 0); addstr("I'm thinking..."); clrtoeol();
while (!done(board)) {
cmove = comp(board);
if (first == 0) {
move(19, 0); printw("Computer moves: %d", cmove-(NR_PITS+1));
clrtoeol();
getyx(stdscr, y, x);
first++;
} else {
move(y, x);
printw(", %d", cmove-(NR_PITS+1));
getyx(stdscr, y, x);
}
if (dmove(board, cmove)) {
move(20, 0); clrtoeol(); /* Not thinking anymore */
break;
}
}
}
} /* end of main move loop */
/* 8. Game is over. Sum up the results: */
com = board[C_KALAH];
hum = board[P_KALAH];
for (i = 1; i <= NR_PITS; i++) {
hum += board[i];
com += board[NR_PITS+1+i];
}
move(22, 0); printw("Score: me %d you %d . . . ", com, hum);
if (com > hum) {
addstr("I win\n");
}
else if (com == hum) {
addstr("game is a draw\n");
} else {
addstr("you win\n");
}
quit:
move(23, 0); addstr("New game (y or n): "); clrtoeol();
refresh();
getstr(string);
} while (toupper(string[0]) == 'Y');
endwin();
return 0;
}
/*----------------------------------------------------------------------
Routine: mmove
Description: Perform the move 'move' on the 'old' board, and
put the new board in 'new'.
Return FALSE only if the move ended in a kalah.
This indicates that the mover may move again.
Return TRUE otherwise.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int mmove(old, new, mov)
char *old;
char *new;
int mov;
{
int i;
int who;
/* 1. Check that 'move' is legal on 'old': */
if ( (mov < P_FIRST) || (mov == P_KALAH) ||
(mov >= BOARD_SIZE) ||
old[mov] == 0) {
printf("Bad arg to mmove: %d",mov);
}
/* 2. Do some setting up: */
total++; /* Total number of moves made during tree search */
for (i = 0; i < BOARD_SIZE; ++i) {
new[i] = old[i];
}
who = (mov < P_KALAH ? 1 : 0); /* 1 == player, 0 == computer */
/* 3. Make move: */
i = old[mov]; /* 'i' is the stones 'in hand' */
new[mov] = 0;
while (i--) {
mov = mod(mov, who);
++new[mov];
}
/* 3. Did we make a capture? */
if (new[mov] == 1 && who == (mov < 7 ? 1 : 0) && mov && mov != 7) {
new[who*P_KALAH] += new[14-mov];
new[14-mov] = 0;
}
/* 4. Did the move end in a kalah? */
return (!(mov == C_KALAH || mov == P_KALAH));
}
/*----------------------------------------------------------------------
Routine: mod
Description: Return the number of the pit after 'i'.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int mod(i, player)
int i,player;
{
/* 1. Get next pit number: */
++i;
/* 2. Only player may use player's own kalah: */
if (i == P_KALAH) return( player ? P_KALAH : P_KALAH+1);
if (i >= BOARD_SIZE) return ( player ? P_FIRST : C_KALAH);
return(i);
}
/*----------------------------------------------------------------------
Routine: initb
Description: Initialize the board to starting position
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static void initb(board)
t_board board;
{
int i;
for (i=0; i<BOARD_SIZE; i++) {
board[i] = NUM;
}
board[P_KALAH] = board[C_KALAH] = 0;
printb(board);
}
/*----------------------------------------------------------------------
Routine: printb
Description: Display the kalah board on the screen.
The board is displayed in lines 0-16,
columns 0-77.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static char screen[17][78+1] = { /* Remember trailing \0! */
"+----------------------------------------------------------------------------+",
"| |",
"| ME 6 5 4 3 2 1 |",
"| +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ |",
"| | | | | | | | | | | | | |",
"| | | | | | | | | | | | | |",
"| | | | | | | | | | | | | |",
"| +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ |",
"| |",
"| +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ |",
"| | | | | | | | | | | | | |",
"| | | | | | | | | | | | | |",
"| | | | | | | | | | | | | |",
"| +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ |",
"| 1 2 3 4 5 6 YOU |",
"| |",
"+----------------------------------------------------------------------------+"
};
/* 'centres' of the 0-13 pits */
static int ypos[14] = { 5, 11, 11, 11, 11, 11, 11, 11, 5, 5, 5, 5, 5, 5};
static int xpos[14] = { 8, 17, 25, 33, 41, 49, 57, 65, 57, 49, 41, 33, 25, 17};
static void printb(board)
t_board board;
{
int i;
/* 1. Print empty board layout: */
for (i=0; i<17; i++) {
move(i,0);
addstr(screen[i]);
}
/* 2. Fill in pit contents: */
for (i=0; i<BOARD_SIZE; i++) {
move(ypos[i], xpos[i]);
printw("%3d", board[i]);
}
/* 3. Update board: */
refresh();
}
/*----------------------------------------------------------------------
Routine: comp
Description: given the board 'board', calulate the best
next move and return it as result.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int comp(board)
char *board;
{
int score;
int bestscore,best;
char temp[14];
int i;
unsigned nodes;
DEPTH = MAXDEPTH = CALLS = TOTDEPTH = WIDTH = TERM = 0;
total = 0;
/* 1. Only one possible move? Then select that: */
if ((i = countnodes(board, C_FIRST)) == 1) {
for (best = C_FIRST; best < C_FIRST+NR_PITS-1; ++best) {
if (board[best]) {
return(best);
}
}
}
#if 0 /* DEBUG only */
if (i < 1) {
printw("ABORT! comp entered when no moves possible!");
exit(1);
}
#endif
/* 2. Try each move that is left. Select the best one: */
nodes = COUNT/i;
bestscore = -10000; /* should be MIN_INT */
for (i = 13; i > P_KALAH; --i) {
if (board[i]) {
score = mmove(board,temp,i);
#if !TRACE
score = comp1(temp, score, nodes, bestscore, 10000);
#else
score = comp1(temp, score, nodes, db? -10000 : bestscore, 10000);
if (db > 0) {
printf("MOVE: %2d SCORE: %5d",
i-P_KALAH,
(score>=1000)?(score-1000):
((score<= -1000)?(score+1000):score));
if (score > 1000 || score < -1000) {
printf(" for SURE");
}
printf("\n");
}
#endif
if (score > bestscore) {
bestscore = score;
best = i;
}
}
}
/* - -
Indicate if we think we're winning or losing.
Comment by A. Thulin:
The program is sometimes wrong, altough it often is difficult to refute it,
especially with many stones. The best strategy for the player to win a game
that the program thinks it has won, seems to be to play a 'waiting' game.
The fact that the program *is* wrong indicates an error somewhere, but it
does not appear to be an obvious one...
- -*/
move(18, 0);
if (bestscore > 1000) {
addstr("(I think I've got you!)");
} else if (bestscore < -1000) {
addstr("(I think you've got me...)");
} else {
clrtoeol();
}
#if TRACE
if (db) {
printf("\nCount: %u\n",total);
printf("Maximum depth: %d\nAverage depth: %u\n", MAXDEPTH,TOTDEPTH/CALLS);
printf("Terminal Evaluations: %u\nPlayed out: %u\n",WIDTH,TERM);
}
#endif
return(best);
}
/*----------------------------------------------------------------------
Routine: comp1
Description: The real alpha-beta minmax evaluator
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int comp1(board, who, count, alpha, beta)
char *board; /* current board */
int who; /* who is to move */
unsigned count; /* max nr of positions to examine */
int alpha, /* ... */
beta; /* ... */
{
int i;
int turn,new;
char temp[14];
unsigned nodes;
++DEPTH;
MAXDEPTH = MAX(MAXDEPTH,DEPTH);
/* 1. If no nodes left, evaluate position statically: */
if (count < 1) { /* No remaining nodes ... */
++CALLS;
TOTDEPTH += DEPTH;
++WIDTH;
--DEPTH;
new = board[C_KALAH]-board[P_KALAH];
for (i = 1; i < P_KALAH; ++i) {
turn = MIN(P_KALAH-i,board[i]);
new -= 2*turn - board[i];
}
for (i = P_KALAH+1; i < 14; ++i) {
turn = MAX(14-i,board[i]);
new += 2*turn - board[i];
}
if (board[C_KALAH] > 6*NUM) {
return new+1000;
}
if (board[P_KALAH] > 6*NUM) {
return new-1000;
}
return(new);
}
/* 2. No more moves to be examined? */
if (done(board)) {
++CALLS;
TOTDEPTH += DEPTH;
++TERM;
--DEPTH;
new = board[0]+board[8]+board[9]+board[10]+board[11]+board[12]+board[13]
-board[1]-board[2]-board[3]-board[4]-board[5]-board[6]-board[7];
if (new < 0) new -= 1000;
if (new > 0) new += 1000;
return(new);
}
/* 3. Check moves further down in tree: */
#if 0 /* DEBUG printout only */
if (countnodes(board, 8-who*7) == 0) {
printf("BREAKOFF: EMPTY BOARD! who = %d\n", who);
printf("done(board) = %d\n", done(board));
for (i=0; i<BOARD_SIZE; i++) {
printf("%4d", board[i]);
}
exit(1);
}
#endif
nodes = count/countnodes(board,8-who*7);
for (i = 7*(1-who)+6; i > 7*(1-who); --i)
if (board[i]) {
turn = mmove(board,temp,i);
new = comp1(temp,(turn ? 1-who : who),nodes,alpha,beta);
#if TRACE
if (ab) printf("DEPTH: %2d MOVE: %2d NEW: %4d ALPHA: %6d BETA: %6d\n",DEPTH,i,new,alpha,beta);
#endif
if (who) {
beta = MIN(new,beta);
if (beta <= alpha) {
DEPTH--;
return(beta);
}
}
else {
alpha = MAX(new,alpha);
if (alpha >= beta) {
DEPTH--;
return(alpha);
}
}
}
--DEPTH;
return(who ? beta : alpha);
}
/*----------------------------------------------------------------------
Routine: countnodes
Description: How many moves are possible?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
static int countnodes(board, start)
int start;
char *board;
{
int i, num;
num = 0;
for (i=start; i < start + NR_PITS; i++)
num += (board[i] > 0 ? 1 : 0);
return(num);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -