Author: jonathan Baxter
Date: 13:25:19 11/12/98
Go up one level in this thread
On November 12, 1998 at 14:34:16, Robert Hyatt wrote:
>On November 12, 1998 at 12:13:26, Larry Coon wrote:
>
>>(Long question follows -- sorry.)
>>
>>I know I saw SEE talked about recently, but I couldn't
>>locate the discussion here, on rgcc or anybody's web
>>page (I don't remember where I saw it). Can somebody
>>tell me if I'm thinking about this the right way?
>
SEE is nothing more than negamax (or minimax) where at each node in the tree
you have two options: make the next capture or sit (with an eval equal to the
current material balance). I found that once I thought of it that way, the code
was easy to write. Note that the resulting tree looks like:
+
| \
| \
+ +
| \
| \
+ +
| \
| \
+ +
with a depth equal to the number of captures in the exchange.
Here's my "swap.c" (note that "topieces" for each square is a 32 bit mask
indicating which pieces are attacking that square. It is ordered so that
the next bit is always the next highest value piece. "ff_one" finds the first
set bit in its argument, fl_one finds the last set bit).
/* swap routines. */
#include "includes.h"
#include "tdchess.h"
static int debug = 0;
extern struct state *state;
/* does a crude static search to determine the material gain of
move. It is mainly used for move ordering. */
etype swap(Position *b, Move *m)
{
etype swap_score[32], next, gain;
int pi, tomove, i;
uint32 topieces, discovered, used;
uint32 mask;
Square from=m->from, to=m->to;
gain = mat_value(ABS(b->board[to]));
/* start with the piece on the "to" sqaure */
swap_score[0] = gain;
/* the first capture is from the "from" square. */
next = -mat_value(ABS(b->board[from]));
used = 1<<b->pboard[from];
topieces = b->topieces[to] & ~used;
if (debug)
lprintf(0, "from: %s gain: %d\n", posstr(from), gain);
/* moving this piece might expose a new capture possibility by
another sliding piece. */
discovered = b->topieces[from] & b->sliding_mask & ~used;
while (discovered) {
pi = ff_one(discovered);
discovered &= ~(1<<pi);
if (same_line(b->pieces[pi].pos, from, to)) {
topieces |= (1<<pi);
if (debug)
lprintf(0, "discovered: %s\n",
posstr(b->pieces[pi].pos));
break;
}
}
/* now we go through and work out the rest of the scores. */
tomove = 1;
mask = ~player_mask(b);
i = 1;
while (topieces & mask) {
gain += next;
swap_score[i++] = gain;
pi = fl_one(topieces & mask);
from = b->pieces[pi].pos;
if (debug)
lprintf(0, "from: %s gain: %d\n", posstr(from), gain);
topieces &= ~(1<<pi);
used |= (1<<pi);
discovered = b->topieces[from] & b->sliding_mask & ~used;
while (discovered) {
pi = ff_one(discovered);
discovered &= ~(1<<pi);
if (same_line(b->pieces[pi].pos, from, to)) {
topieces |= (1<<pi);
if (debug)
lprintf(0, "discovered: %s\n",
posstr(b->pieces[pi].pos));
break;
}
}
next = tomove*mat_value(ABS(b->board[from]));
tomove = -tomove;
mask = ~mask;
}
/* now "minimax" the swap scores to determine the optimal
point to stop. */
--i;
while (i) {
if (tomove < 0) {
if (swap_score[i] < swap_score[i-1])
swap_score[i-1] = swap_score[i];
} else {
if (swap_score[i] > swap_score[i-1])
swap_score[i-1] = swap_score[i];
}
--i;
tomove = -tomove;
}
return swap_score[0];
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.