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.