billr@saab.CNA.TEK.COM (Bill Randle) (05/04/90)
Submitted-by: Rich Burridge <rburridge@sun.COM>
Posting-number: Volume 9, Issue 45
Archive-name: othello2/Patch3
Patch-To: othello2: Volume 9, Issue 37-40
[from the author...]
[[I screwed up. It seems the changes to the file makemove.c never got
into patch #1. It's easier if I release a copy of the current version
of makemove.c, and a small patch to adjust the patchlevel and update
the CHANGES file.
Sorry for the confusion.
Rich Burridge - richb@Aus.Sun.COM]]
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: makemove.c patches03
# Wrapped by billr@saab on Thu May 3 14:43:09 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo shar: Extracting \"'makemove.c'\" \(12624 characters\)
sed "s/^X//" >'makemove.c' <<'END_OF_FILE'
X/*LINTLIBRARY*/
X
X/* %Z%%M% %I% %E%
X *
X * Best computer strategy routines used by the othello program.
X *
X * Copyright: Chris Miller, 1979, 1981, 1984.
X *
X * Included with this othello game by
X * Rich Burridge, Sun Microsystems, Australia.
X *
X * Permission is given to distribute these sources, as long as the
X * introductory messages are not removed, and no monies are exchanged.
X *
X * No responsibility is taken for any errors on inaccuracies inherent
X * either to the comments or the code of this program, but if reported
X * to me, then an attempt will be made to fix them.
X */
X
X#include "othello.h"
X#include "extern.h"
X
X
Xmakemove(board, player, depth)
XBOARD *board ;
Xint depth, player ;
X{
X int d,value ;
X int mv = NOMOVE ;
X
X if (!depth)
X {
X if ((mv = nextmove(board, NOMOVE, (BOARD *) 0, player)) == NOMOVE)
X return(-1) ;
X else return(mv) ;
X }
X
X if ((mv = nextmove(board, NOMOVE, (BOARD *) 0, player)) == NOMOVE)
X {
X if (remark) message(REMARK_MES, "I'm not dead, just resting") ;
X return(-1) ;
X }
X ab_count = se_count = 0 ;
X if (nextmove(board, mv, (BOARD *) 0, player) == NOMOVE)
X {
X value = static_eval(board) ;
X if (remark) make_remark(player,value) ;
X return(mv) ;
X }
X
X/* Exhaustive for last 3*depth ply (at most 10!). */
X
X if ((board->moves_left <= 10) && (board->moves_left <= 3*depth))
X d = board->moves_left ;
X else d = depth ;
X
X set_aspiration(board) ;
X value = alfabeta(board, d, player*INFINITY, player, &mv) ;
X if (remark) make_remark(player,value) ;
X return(mv) ;
X}
X
X
Xnextmove(pos, mv, nextpos, player)
XBOARD *pos,*nextpos ;
Xint mv, player ;
X{
X
X/* On first entry for a given position, move is set to NOMOVE,
X * i.e. -1. Moves are generated in a rough plausibility order
X * given by the list structure move_table, whose head is
X * move_table[-1], and whose tail-pointer is set to NOMOVE.
X * The order is purely heuristic, and corresponds roughly to
X * the values associated by static_eval with different squares.
X */
X
X static int m_table[65] =
X {
X 0, 7, 6, 5, 4, 24, 16, 8, 56, 15,
X 14, 13, 12, 25, 17, 49, 48, 23, 22, 21,
X 20, 26, 42, 41, 40, 31, 30, 29, 28, 35,
X 34, 33, 32, 39, 38, 37, 36, 10, 43, 51,
X 59, 47, 46, 45, 44, 27, 19, 50, 58, 55,
X 54, 53, 52, 1, 11, -1, 57, 63, 62, 61,
X 60, 18, 3, 9, 2
X } ;
X
X static int *move_table = &(m_table[1]) ;
X
X while ((mv = move_table[mv]) != NOMOVE)
X if (legal(mv,player,pos))
X {
X if (nextpos) domove(pos,mv,nextpos,player) ;
X
X/* Next position generated only if pointer is non-zero */
X return(mv) ;
X }
X return(NOMOVE) ; /* No more legal moves */
X}
X
X
Xdomove(pos, mv, nextpos, player)
XBOARD *pos, *nextpos ;
Xint mv, player ;
X{
X register int i ;
X if (pos != nextpos) FOR_BOARD(i) nextpos->square[i] = pos->square[i] ;
X
X s_move = mv ;
X s_row = mv >> 3 ;
X s_col = mv & 7 ;
X s_player = player ;
X s_opponent = -player ;
X s_flip = TRUE ;
X s_pos = nextpos ;
X
X nextpos->square[s_move] = player ;
X
X (void) sandwich(-9) ;
X (void) sandwich(-8) ;
X (void) sandwich(-7) ;
X (void) sandwich(-1) ;
X (void) sandwich(1) ;
X (void) sandwich(7) ;
X (void) sandwich(8) ;
X (void) sandwich(9) ;
X
X nextpos->moves_left = (pos->moves_left) - 1 ;
X}
X
X
Xlegal(mv, player, pos)
XBOARD *pos ;
Xint mv, player ;
X{
X if (pos->square[mv]) return(FALSE) ; /* Already occupied */
X
X s_move = mv ;
X s_row = mv >> 3 ;
X s_col = mv & 7 ;
X s_player = player ;
X s_opponent = -player ;
X s_flip = FALSE ;
X s_pos = pos ;
X
X return(sandwich(-9) || sandwich(-8) || sandwich(-7) || sandwich(-1) ||
X sandwich(1) || sandwich(7) || sandwich(8) || sandwich(9)) ;
X}
X
X
X/* Test whether the square move sandwiches a line
X * of enemy pieces in the direction [row_inc, col_inc];
X * If (s_flip) then update position by capturing such pieces
X */
X
Xsandwich(increment)
Xregister int increment ;
X{
X register int square,offset ;
X int row_offset,col_offset,piece,piece_count ;
X
X if (s_pos->square[s_move+increment] != s_opponent) return(FALSE) ;
X
X/* Quick test to catch most failures -
X * note that the tested square may not even
X * be on the board, but the condition is a
X * sufficient one for failure.
X */
X
X row_offset = (increment < -1 ? s_row : /* inc -1: -9, -8, -7 */
X increment > 1 ? 7-s_row : 8) ; /* inc 1: 7, 8, 9 */
X col_offset = (increment & 4 ? s_col : /* inc -1: -9, -1, 7 */
X increment & 1 ? 7-s_col : 8) ; /* inc 1: -7, 1, 9 */
X
X offset = (row_offset > col_offset ? col_offset : row_offset) ;
X
X/* offset = shortest distance to an edge in the direction of search */
X
X if (2 > offset) return(FALSE) ;
X
X piece_count = 1 ;
X square = s_move+increment ;
X
X while (--offset)
X {
X if (!(piece = s_pos->square[square += increment]))
X return(FALSE) ; /* If empty square, give up */
X
X if (piece == s_player) break ;
X else piece_count++ ; /* Count opponent's pieces encountered */
X }
X
X if (!offset) return(FALSE) ;
X
X if (s_flip)
X while (piece_count--)
X s_pos->square[square -= increment] = s_player ;
X
X return (TRUE) ;
X}
X
X
X/* Alpha-beta pruning algorithm.
X *
X * If sign = 1, then try to MAXIMISE score, else MINIMISE.
X * Parent node wants to MINIMISE/MAXIMISE, so as soon as
X * we exceed parent_opt, give up and return INFINITY.
X * Return best move in parent_best.
X *
X * Externals used:
X * static_eval(position)
X * ISMOVE(position,player) [does player have a legal move?]
X * game_ended(pos)
X * typedef BOARD
X * aspiration(player,depth,position)
X * [return the aspiration limit for next level of search]
X * nextmove(position,mv,nextposition,player)
X * [give the next legal move for player in position;
X * put the resulting position in nextposition]
X */
X
Xalfabeta(pos, depth, parent_opt, sign, parent_best)
XBOARD *pos ;
Xint depth, parent_opt, sign, *parent_best ;
X{
X BOARD nextpos ;
X int value,this_opt,this_best = NOMOVE,mv = NOMOVE,asp = 0 ;
X
X if ((depth==0) || game_ended(pos))
X {
X value = static_eval(pos) ;
X *parent_best = NOMOVE ;
X if ((sign*value) > (sign*parent_opt)) return(sign*INFINITY) ;
X else return (value) ;
X }
X
X ab_count++ ; /* Record boards dynamically evaluated */
X this_opt = (sign == 1 ? -INFINITY : INFINITY) ;
X
X if (!ISMOVE(pos,sign)) /* No legal move */
X {
X value = alfabeta(pos,depth,this_opt,-sign,&this_best) ;
X goto valfound ;
X }
X
X asp = sign * aspiration(sign,depth) ;
X
X while ((mv = nextmove(pos,mv,&nextpos,sign)) != NOMOVE)
X {
X value = alfabeta(&nextpos,depth-1,this_opt,-sign,&this_best) ;
X
Xvalfound:
X
X if ((sign*value) >= (sign*parent_opt)) return(sign*INFINITY) ;
X
X if ((sign*value) > asp)
X {
X *parent_best = mv ;
X return(value) ;
X }
X
X if ((sign*value) > (sign*this_opt))
X {
X this_opt = value ;
X *parent_best = mv ;
X }
X
X/* If two moves have same evaluation, choose
X * uniformly randomly between them (of course,
X * where several moves have same value, this
X * is biased towards the later ones
X */
X
X if ((value == this_opt) && (rand() & 020)) *parent_best = mv ;
X }
X return(this_opt) ;
X}
X
X
X/* Aspirations are as follows:
X * Aspiration-level Aspiration
X * 1 The worse of 0, static value
X * 2 The static value
X * 3 10% better than the static value
X * 4 25% better than the static value
X * 5 Any winning move
X * 6 The move winning by the greatest margin
X *
X * It is assumed that the opponent has
X * the same level of aspiration as the program.
X */
X
Xset_aspiration(position)
XBOARD *position ;
X{
X if (aspire == MAXASPIRE)
X {
X expected = 0 ;
X margin = INFINITY ;
X return ;
X }
X
X if (aspire == (MAXASPIRE-1))
X {
X expected = 0 ;
X margin = INFINITY-64 ;
X return ;
X }
X
X expected = static_eval(position) ;
X
X switch (aspire)
X {
X case 1 : expected /= 2 ;
X margin = -abs(expected) ;
X return ;
X case 2 : margin = 0 ;
X return ;
X case 3 : margin = abs(expected/10) ;
X return ;
X case 4 : margin = abs(expected/4) ;
X return ;
X }
X}
X
X
Xaspiration(player, depth)
Xint player,depth ;
X{
X if (aspire == MAXASPIRE) return(player*INFINITY) ;
X if (depth < 3 && aspire > 1) return(player*(INFINITY-64)) ;
X return(expected+player*margin) ;
X}
X
X
X#define VCORN 100 /* Corner */
X#define VORTH -30 /* Orthogonally next to corner */
X#define VDIAG -50 /* Diagonally " " " */
X#define VEDGE 20 /* On edge */
X#define VNEXT -7 /* Next to edge */
X#define VNORM 1 /* Elsewhere */
X
X/* Square values (only valid when a "vulnerable" piece occupies the
X * square in question)
X */
X
Xstatic_eval(pos)
XBOARD *pos ;
X{
X static int model[64] = {
X VCORN, VORTH, VEDGE, VEDGE, VEDGE, VEDGE, VORTH, VCORN,
X VORTH, VDIAG, VNEXT, VNEXT, VNEXT, VNEXT, VDIAG, VORTH,
X VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE,
X VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE,
X VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE,
X VEDGE, VNEXT, VNORM, VNORM, VNORM, VNORM, VNEXT, VEDGE,
X VORTH, VDIAG, VNEXT, VNEXT, VNEXT, VNEXT, VDIAG, VORTH,
X VCORN, VORTH, VEDGE, VEDGE, VEDGE, VEDGE, VORTH, VCORN
X } ;
X
X register int i ;
X register int value = 0 ;
X int scores[64] ;
X
X se_count++ ; /* Record number of static evaluations */
X if (game_ended(pos))
X {
X FOR_BOARD(i) value += pos->square[i] ;
X return (value > 0 ? INFINITY+value-64 :
X value < 0 ? -INFINITY+value+64 : 0) ;
X }
X
X FOR_BOARD(i) scores[i] = 0 ;
X
X find_invulnerable(pos,scores) ;
X
X/* Scores now contains VINVUL (or -VINVUL)
X * for each invulnerable piece, and 0 elsewhere;
X * now fill in other evaluations (special cases:
X * next to corner [bad!], on edge[good!], next to
X * edge[poor], anywhere else[boring])
X */
X
X FOR_BOARD(i) value += (scores[i] ? scores[i] : model[i]*pos->square[i]) ;
X return (value) ;
X}
X
X
Xgame_ended(pos)
XBOARD *pos ;
X{
X if (!(pos->moves_left)) return(TRUE) ;
X return((!ISMOVE(pos,WHITE)) && !(ISMOVE(pos,BLACK))) ;
X}
X
X
X/* This function finds invulnerable pieces, and scores them
X * appropriately; it does not find ALL invulnerable pieces -
X * in fact, only concave blocks including a corner - but
X * nevertheless should provide a good approximation.
X */
X
Xfind_invulnerable(board, scores)
XBOARD *board ;
Xint scores[64] ;
X{
X int hwm,corner,value,i,j ;
X
X if ((corner = board->square[0]) != 0)
X {
X value = corner*VINVUL ;
X hwm = 7 ;
X
X for (i = 0; i < 56; i += 8)
X {
X if (board->square[i] != corner) break ;
X scores[i] = value ;
X for (j = 1; j < hwm; j++)
X {
X if (board->square[i+j] != corner)
X {
X hwm = j ;
X break ;
X }
X scores[i+j] = value ;
X }
X }
X scores[0] = corner*VCORN ;
X }
X
X if ((corner = board->square[7]) != 0)
X {
X value = corner*VINVUL ;
X hwm = 0 ;
X
X for (i = 0; i < 56; i+= 8)
X {
X if (board->square[i+7] != corner) break ;
X scores[i+7] = value ;
X for (j = 6; j > hwm; j--)
X {
X if (board->square[i+j] != corner)
X {
X hwm = j ;
X break ;
X }
X scores[i+j] = value ;
X }
X }
X scores[7] = corner*VCORN;
X }
X
X if ((corner = board->square[56]) != 0)
X {
X value = corner*VINVUL ;
X hwm = 7 ;
X
X for (i = 56; i > 0; i -= 8)
X {
X if (board->square[i] != corner) break ;
X scores[i] = value ;
X for (j = 1; j < hwm; j++)
X {
X if (board->square[i+j] != corner)
X {
X hwm = j ;
X break ;
X }
X scores[i+j] = value ;
X }
X }
X scores[56] = corner*VCORN ;
X }
X
X if ((corner=board->square[63]) != 0)
X {
X value = corner*VINVUL ;
X hwm = 0 ;
X
X for (i = 56; i > 0; i -= 8)
X {
X if (board->square[i+7] != corner) break ;
X scores[i+7] = value ;
X for (j = 6; j > hwm; j--)
X {
X if (board->square[i+j] != corner)
X {
X hwm = j ;
X break ;
X }
X scores[i+j] = value ;
X }
X }
X scores[63] = corner*VCORN ;
X }
X}
END_OF_FILE
if test 12624 -ne `wc -c <'makemove.c'`; then
echo shar: \"'makemove.c'\" unpacked with wrong size!
fi
# end of 'makemove.c'
if test -f 'patches03' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'patches03'\"
else
echo shar: Extracting \"'patches03'\" \(830 characters\)
sed "s/^X//" >'patches03' <<'END_OF_FILE'
X
X------- patchlevel.h -------
X*** /tmp/da06251 Thu May 3 10:36:29 1990
X--- patchlevel.h Thu May 3 10:32:18 1990
X***************
X*** 19,22 ****
X * to me, then an attempt will be made to fix them.
X */
X
X! #define PATCHLEVEL 2
X--- 19,22 ----
X * to me, then an attempt will be made to fix them.
X */
X
X! #define PATCHLEVEL 3
X
X------- CHANGES -------
X*** /tmp/da06254 Thu May 3 10:36:30 1990
X--- CHANGES Thu May 3 10:34:16 1990
X***************
X*** 86,88 ****
X--- 86,93 ----
X It would be nice if (at least on the tty version) the text
X "black" was replaced with "X" or "black (X)" and likewise for
X white.
X+
X+ v1.3 - patchlevel 3. 3rd May 1990.
X+
X+ * Release of the current version of makemove.c, because the changes
X+ to this file at patch level #1 never made it out.
END_OF_FILE
if test 830 -ne `wc -c <'patches03'`; then
echo shar: \"'patches03'\" unpacked with wrong size!
fi
# end of 'patches03'
fi
echo shar: End of shell archive.
exit 0