richb@sunaus.oz (Rich Burridge) (05/04/90)
[I've sent a copy of this to the moderator of comp.sources.games for
archiving].
As many of you will have realised I screwed up with patches 1&2.
It seems the changes to the file makemove.c never got into patch #1.
This patch really is a release of the current version of makemove.c,
with patchlevel.h and CHANGES adjusted accordingly.
Rich Burridge - Aus.Sun.COM
------CUT HERE------CUT HERE------
#! /bin/sh
# this is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh to create the files:
# patch.3
# makemove.c
# This archive created: Thu May 3 10:37:34 EST 1990
#
#
export PATH; PATH=/bin:$PATH
#
if [ -f patch.3 ]
then
echo shar: will not over-write existing file patch.3
else
echo shar: extracting 'patch.3', 830 characters
cat > patch.3 <<'Funky_Stuff'
------- patchlevel.h -------
*** /tmp/da06251 Thu May 3 10:36:29 1990
--- patchlevel.h Thu May 3 10:32:18 1990
***************
*** 19,22 ****
* to me, then an attempt will be made to fix them.
*/
! #define PATCHLEVEL 2
--- 19,22 ----
* to me, then an attempt will be made to fix them.
*/
! #define PATCHLEVEL 3
------- CHANGES -------
*** /tmp/da06254 Thu May 3 10:36:30 1990
--- CHANGES Thu May 3 10:34:16 1990
***************
*** 86,88 ****
--- 86,93 ----
It would be nice if (at least on the tty version) the text
"black" was replaced with "X" or "black (X)" and likewise for
white.
+
+ v1.3 - patchlevel 3. 3rd May 1990.
+
+ * Release of the current version of makemove.c, because the changes
+ to this file at patch level #1 never made it out.
Funky_Stuff
len=`wc -c < patch.3`
if [ $len != 830 ] ; then
echo error: patch.3 was $len bytes long, should have been 830
fi
fi # end of overwriting check
if [ -f makemove.c ]
then
echo shar: will not over-write existing file makemove.c
else
echo shar: extracting 'makemove.c', 12624 characters
cat > makemove.c <<'Funky_Stuff'
/*LINTLIBRARY*/
/* %Z%%M% %I% %E%
*
* Best computer strategy routines used by the othello program.
*
* Copyright: Chris Miller, 1979, 1981, 1984.
*
* Included with this othello game by
* Rich Burridge, Sun Microsystems, Australia.
*
* Permission is given to distribute these sources, as long as the
* introductory messages are not removed, and no monies are exchanged.
*
* No responsibility is taken for any errors on inaccuracies inherent
* either to the comments or the code of this program, but if reported
* to me, then an attempt will be made to fix them.
*/
#include "othello.h"
#include "extern.h"
makemove(board, player, depth)
BOARD *board ;
int depth, player ;
{
int d,value ;
int mv = NOMOVE ;
if (!depth)
{
if ((mv = nextmove(board, NOMOVE, (BOARD *) 0, player)) == NOMOVE)
return(-1) ;
else return(mv) ;
}
if ((mv = nextmove(board, NOMOVE, (BOARD *) 0, player)) == NOMOVE)
{
if (remark) message(REMARK_MES, "I'm not dead, just resting") ;
return(-1) ;
}
ab_count = se_count = 0 ;
if (nextmove(board, mv, (BOARD *) 0, player) == NOMOVE)
{
value = static_eval(board) ;
if (remark) make_remark(player,value) ;
return(mv) ;
}
/* Exhaustive for last 3*depth ply (at most 10!). */
if ((board->moves_left <= 10) && (board->moves_left <= 3*depth))
d = board->moves_left ;
else d = depth ;
set_aspiration(board) ;
value = alfabeta(board, d, player*INFINITY, player, &mv) ;
if (remark) make_remark(player,value) ;
return(mv) ;
}
nextmove(pos, mv, nextpos, player)
BOARD *pos,*nextpos ;
int mv, player ;
{
/* On first entry for a given position, move is set to NOMOVE,
* i.e. -1. Moves are generated in a rough plausibility order
* given by the list structure move_table, whose head is
* move_table[-1], and whose tail-pointer is set to NOMOVE.
* The order is purely heuristic, and corresponds roughly to
* the values associated by static_eval with different squares.
*/
static int m_table[65] =
{
0, 7, 6, 5, 4, 24, 16, 8, 56, 15,
14, 13, 12, 25, 17, 49, 48, 23, 22, 21,
20, 26, 42, 41, 40, 31, 30, 29, 28, 35,
34, 33, 32, 39, 38, 37, 36, 10, 43, 51,
59, 47, 46, 45, 44, 27, 19, 50, 58, 55,
54, 53, 52, 1, 11, -1, 57, 63, 62, 61,
60, 18, 3, 9, 2
} ;
static int *move_table = &(m_table[1]) ;
while ((mv = move_table[mv]) != NOMOVE)
if (legal(mv,player,pos))
{
if (nextpos) domove(pos,mv,nextpos,player) ;
/* Next position generated only if pointer is non-zero */
return(mv) ;
}
return(NOMOVE) ; /* No more legal moves */
}
domove(pos, mv, nextpos, player)
BOARD *pos, *nextpos ;
int mv, player ;
{
register int i ;
if (pos != nextpos) FOR_BOARD(i) nextpos->square[i] = pos->square[i] ;
s_move = mv ;
s_row = mv >> 3 ;
s_col = mv & 7 ;
s_player = player ;
s_opponent = -player ;
s_flip = TRUE ;
s_pos = nextpos ;
nextpos->square[s_move] = player ;
(void) sandwich(-9) ;
(void) sandwich(-8) ;
(void) sandwich(-7) ;
(void) sandwich(-1) ;
(void) sandwich(1) ;
(void) sandwich(7) ;
(void) sandwich(8) ;
(void) sandwich(9) ;
nextpos->moves_left = (pos->moves_left) - 1 ;
}
legal(mv, player, pos)
BOARD *pos ;
int mv, player ;
{
if (pos->square[mv]) return(FALSE) ; /* Already occupied */
s_move = mv ;
s_row = mv >> 3 ;
s_col = mv & 7 ;
s_player = player ;
s_opponent = -player ;
s_flip = FALSE ;
s_pos = pos ;
return(sandwich(-9) || sandwich(-8) || sandwich(-7) || sandwich(-1) ||
sandwich(1) || sandwich(7) || sandwich(8) || sandwich(9)) ;
}
/* Test whether the square move sandwiches a line
* of enemy pieces in the direction [row_inc, col_inc];
* If (s_flip) then update position by capturing such pieces
*/
sandwich(increment)
register int increment ;
{
register int square,offset ;
int row_offset,col_offset,piece,piece_count ;
if (s_pos->square[s_move+increment] != s_opponent) return(FALSE) ;
/* Quick test to catch most failures -
* note that the tested square may not even
* be on the board, but the condition is a
* sufficient one for failure.
*/
row_offset = (increment < -1 ? s_row : /* inc -1: -9, -8, -7 */
increment > 1 ? 7-s_row : 8) ; /* inc 1: 7, 8, 9 */
col_offset = (increment & 4 ? s_col : /* inc -1: -9, -1, 7 */
increment & 1 ? 7-s_col : 8) ; /* inc 1: -7, 1, 9 */
offset = (row_offset > col_offset ? col_offset : row_offset) ;
/* offset = shortest distance to an edge in the direction of search */
if (2 > offset) return(FALSE) ;
piece_count = 1 ;
square = s_move+increment ;
while (--offset)
{
if (!(piece = s_pos->square[square += increment]))
return(FALSE) ; /* If empty square, give up */
if (piece == s_player) break ;
else piece_count++ ; /* Count opponent's pieces encountered */
}
if (!offset) return(FALSE) ;
if (s_flip)
while (piece_count--)
s_pos->square[square -= increment] = s_player ;
return (TRUE) ;
}
/* Alpha-beta pruning algorithm.
*
* If sign = 1, then try to MAXIMISE score, else MINIMISE.
* Parent node wants to MINIMISE/MAXIMISE, so as soon as
* we exceed parent_opt, give up and return INFINITY.
* Return best move in parent_best.
*
* Externals used:
* static_eval(position)
* ISMOVE(position,player) [does player have a legal move?]
* game_ended(pos)
* typedef BOARD
* aspiration(player,depth,position)
* [return the aspiration limit for next level of search]
* nextmove(position,mv,nextposition,player)
* [give the next legal move for player in position;
* put the resulting position in nextposition]
*/
alfabeta(pos, depth, parent_opt, sign, parent_best)
BOARD *pos ;
int depth, parent_opt, sign, *parent_best ;
{
BOARD nextpos ;
int value,this_opt,this_best = NOMOVE,mv = NOMOVE,asp = 0 ;
if ((depth==0) || game_ended(pos))
{
value = static_eval(pos) ;
*parent_best = NOMOVE ;
if ((sign*value) > (sign*parent_opt)) return(sign*INFINITY) ;
else return (value) ;
}
ab_count++ ; /* Record boards dynamically evaluated */
this_opt = (sign == 1 ? -INFINITY : INFINITY) ;
if (!ISMOVE(pos,sign)) /* No legal move */
{
value = alfabeta(pos,depth,this_opt,-sign,&this_best) ;
goto valfound ;
}
asp = sign * aspiration(sign,depth) ;
while ((mv = nextmove(pos,mv,&nextpos,sign)) != NOMOVE)
{
value = alfabeta(&nextpos,depth-1,this_opt,-sign,&this_best) ;
valfound:
if ((sign*value) >= (sign*parent_opt)) return(sign*INFINITY) ;
if ((sign*value) > asp)
{
*parent_best = mv ;
return(value) ;
}
if ((sign*value) > (sign*this_opt))
{
this_opt = value ;
*parent_best = mv ;
}
/* If two moves have same evaluation, choose
* uniformly randomly between them (of course,
* where several moves have same value, this
* is biased towards the later ones
*/
if ((value == this_opt) && (rand() & 020)) *parent_best = mv ;
}
return(this_opt) ;
}
/* Aspirations are as follows:
* Aspiration-level Aspiration
* 1 The worse of 0, static value
* 2 The static value
* 3 10% better than the static value
* 4 25% better than the static value
* 5 Any winning move
* 6 The move winning by the greatest margin
*
* It is assumed that the opponent has
* the same level of aspiration as the program.
*/
set_aspiration(position)
BOARD *position ;
{
if (aspire == MAXASPIRE)
{
expected = 0 ;
margin = INFINITY ;
return ;
}
if (aspire == (MAXASPIRE-1))
{
expected = 0 ;
margin = INFINITY-64 ;
return ;
}
expected = static_eval(position) ;
switch (aspire)
{
case 1 : expected /= 2 ;
margin = -abs(expected) ;
return ;
case 2 : margin = 0 ;
return ;
case 3 : margin = abs(expected/10) ;
return ;
case 4 : margin = abs(expected/4) ;
return ;
}
}
aspiration(player, depth)
int player,depth ;
{
if (aspire == MAXASPIRE) return(player*INFINITY) ;
if (depth < 3 && aspire > 1) return(player*(INFINITY-64)) ;
return(expected+player*margin) ;
}
#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 */
/* Square values (only valid when a "vulnerable" piece occupies the
* square in question)
*/
static_eval(pos)
BOARD *pos ;
{
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
} ;
register int i ;
register int value = 0 ;
int scores[64] ;
se_count++ ; /* Record number of static evaluations */
if (game_ended(pos))
{
FOR_BOARD(i) value += pos->square[i] ;
return (value > 0 ? INFINITY+value-64 :
value < 0 ? -INFINITY+value+64 : 0) ;
}
FOR_BOARD(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_BOARD(i) value += (scores[i] ? scores[i] : model[i]*pos->square[i]) ;
return (value) ;
}
game_ended(pos)
BOARD *pos ;
{
if (!(pos->moves_left)) return(TRUE) ;
return((!ISMOVE(pos,WHITE)) && !(ISMOVE(pos,BLACK))) ;
}
/* 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(board, scores)
BOARD *board ;
int scores[64] ;
{
int hwm,corner,value,i,j ;
if ((corner = board->square[0]) != 0)
{
value = corner*VINVUL ;
hwm = 7 ;
for (i = 0; i < 56; i += 8)
{
if (board->square[i] != corner) break ;
scores[i] = value ;
for (j = 1; j < hwm; j++)
{
if (board->square[i+j] != corner)
{
hwm = j ;
break ;
}
scores[i+j] = value ;
}
}
scores[0] = corner*VCORN ;
}
if ((corner = board->square[7]) != 0)
{
value = corner*VINVUL ;
hwm = 0 ;
for (i = 0; i < 56; i+= 8)
{
if (board->square[i+7] != corner) break ;
scores[i+7] = value ;
for (j = 6; j > hwm; j--)
{
if (board->square[i+j] != corner)
{
hwm = j ;
break ;
}
scores[i+j] = value ;
}
}
scores[7] = corner*VCORN;
}
if ((corner = board->square[56]) != 0)
{
value = corner*VINVUL ;
hwm = 7 ;
for (i = 56; i > 0; i -= 8)
{
if (board->square[i] != corner) break ;
scores[i] = value ;
for (j = 1; j < hwm; j++)
{
if (board->square[i+j] != corner)
{
hwm = j ;
break ;
}
scores[i+j] = value ;
}
}
scores[56] = corner*VCORN ;
}
if ((corner=board->square[63]) != 0)
{
value = corner*VINVUL ;
hwm = 0 ;
for (i = 56; i > 0; i -= 8)
{
if (board->square[i+7] != corner) break ;
scores[i+7] = value ;
for (j = 6; j > hwm; j--)
{
if (board->square[i+j] != corner)
{
hwm = j ;
break ;
}
scores[i+j] = value ;
}
}
scores[63] = corner*VCORN ;
}
}
Funky_Stuff
len=`wc -c < makemove.c`
if [ $len != 12624 ] ; then
echo error: makemove.c was $len bytes long, should have been 12624
fi
fi # end of overwriting check