⟦5e41be73b⟧

TextFile


/*  makemove.c
 *
 *  Best computer strategy routines.
 *
 *  Copyright: Chris Miller, 1979, 1981, 1984.
 *
 *  Included with this othello game by
 *  Rich Burridge, Sun Microsystems, Australia - December 1986.
 */

#include "othello.h"

/*  Globals for passing arguments to "sandwich";
 *  this is to save time putting arguments on and off the
 *  stack in a very heavily used piece of code
 */

int s_move,s_row,s_col,s_player,s_opponent,s_flip ;
BOARD *s_pos ;

extern int aspire ;	      /* Computers level of aspiration. */
extern int cretin_flag ;
extern int remark ;	      /* Indicates if remarks to be displayed. */
extern Panel_item remark_mes ;

int expected,margin ;
long ab_count,se_count ;	 /* Calls of alfabeta and static_eval. */


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) remark_msg("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)) ;
}


sandwich(increment)
register int increment ;

/*  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
 */

{
  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:      /* inc  1:  7,  8,  9 */
		8) ;
  col_offset = (increment & 4 ? s_col   :      /* inc -1: -9, -1,  7 */
		increment & 1 ? 7-s_col :      /* inc  1: -7,  1,  9 */
		8) ;
 
  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) ;
}


alfabeta(pos,depth,parent_opt,sign,parent_best)
BOARD *pos ;
int depth,parent_opt,sign,*parent_best ;

/*  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]
 */
 
{
  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) ;
}


set_aspiration(position)
BOARD *position ;

/*  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.
 */
 
{
  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) ;
}


static_eval(pos)
BOARD *pos ;

/*  Square values (only valid when a "vulnerable" piece occupies the
 *  square in question)
 */

#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
	 } ;
 
  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))) ;
}


find_invulnerable(board,scores)
BOARD *board ;
int scores[64] ;

/*  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.
 */

{
  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 ;
    }
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦5e41be73b⟧ TextFile

Derivation

TextFile
