Author: Don Dailey
Date: 22:37:13 07/20/99
Go up one level in this thread
On July 21, 1999 at 00:09:10, Dan Homan wrote:
>On July 20, 1999 at 22:04:42, Don Dailey wrote:
>
>>
>>Occam uses the same state copy and update technique all the way through
>>the quies search. Occam is my new chess program which is doing over
>>400,000 nodes per second on a pentium 500 in middlegame positions.
>>State copy is simply not expensive. It makes the whole chess program
>>a whole lot cleaner too, so it should appeal to meticulous programmers.
>>
>
>400,000 nps - Wow! I do a state copy in my program, and I always
>assumed that was my major bottleneck. I've been recently thinking
>of some (in one case rather silly) ideas for replacing it with a fast
>make/unmake. Maybe I'll keep the state copy and look elsewhere for
>slowdowns. How large is your "state" structure which gets copied?
>
> - Dan
>
>
>>
>>- Don
I recommend that you profile your code and see exactly how much time
goes into the state copy. But subtract from that time the time you
save on unmakes (which is probably pretty small.) This of course
doesn't tell the whole story but will give you a rough idea. You
can always do the in place updating near end nodes, for instance in
the quies search. I can't see this being a win for me however.
I do try to minimize the position state. You probably actually
copy a lot more state that you think already though because every time
you make a move you keep some undo information, alpha and beta values
and likely various other things like move list pointers and such. But
the size of the state is not a big consideration for us, I just try not
to go wild with it. It makes for a nice clean program too.
Everything becomes somewhat simpler and there is less logic in your
routine that MAKES moves too. You are not concerned with writing
all the undo information and downdating any attack structures you
have. It takes only a small amount of logic to exceed the time of
doing a full state copy, which is done quickly.
Here is what my chess state looks like. SQUARES is a 32 bit int
right now and so is base_int. ev_type is floating point or int
depending on what experiments I'm doing with Occam. The board is
65 elements instead of 64 to enable some speedup tricks.
The his[] pointers are for repetition testing, you can't use the
hash table for this in a parallel program and must search backwards.
I keep information about the status of kings and rook for castling
on the squares themselves as a moved piece bit.
I will eventually add a piece list to this state. I know from past
experience I will get a good speedup when I add this to the
state. This program is currently extremely primitive and so I
expect the state to grow to inherit some more information, particularly
evaluation information. Material signature makes it quick to identify
specific endings.
typedef struct ptag
{
SQUARES bd[65]; /* the board */
base_int king_loc[2]; /* location of kings */
u64 hashkey; /* position key for hash table */
int32 mat_sig; /* signature of material situation */
struct ptag *his[2]; /* pointer to last 2 positions */
ev_type inc_score; /* incremental component of score */
base_int ply_of_game; /* even = white to move */
base_int ply_of_search; /* start at 0 */
base_int pv[PV_LEN]; /* best move from position */
base_int last_move; /* move that got us here */
base_int null_count; /* how many recursive null moves? */
base_int in_check; /* is ctm king in check? */
} position;
This page took 0.13 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.