Computer Chess Club Archives




Subject: Move Make/Unmake Questions

Author: Dan Homan

Date: 07:28:24 07/15/99

I've decided to make some free time for myself this summer to work on
my chess program.  I've decided to do a complete re-write of EXchess
from the ground up, using 0x88.

My plan in writting previous versions of EXchess has always been to
make everything as easy to understand as possible.  I want to keep that
in the new version, but I would also like to go faster!

I have some ideas on making/unmaking moves during the search.  In
previous versions of EXchess, I have just done position copies for
each new ply and had no need for an unmake routine.  Several people told
me it was faster to make/unmake but my experiments didn't show much
improvement.  I want to do unmake in the new version of my program, and
I would like to make it as efficient as possible.

One idea I had was just doing a bit-shift to undo moves.  The idea
is that a square on my board would be an int (or perhaps int64), but only
the first 4 bits would store piece/color information.  Then I could
store 8 (or 16) "states" for a given square - all in order of how they
occurred in the tree.  My unmake move would just be a bit-shift on the
appropriate squares.

I have one concern with this - How many times can the state of a given
square change in the tree?  My feeling is that there will be situations
where the state of a square will change more than 8 (or even 16) times.
(I score any repeated position as a draw, so that may make these situations
relatively rare, but just one such situation could be a big problem in
a game.) I could have a scheme for storing the "lost" information in
these rare cases, but I wonder if the speed-up from this idea is
significant enough to warrant the added complexity?

I would welcome any other ideas people have for making a fast "unmake"

 - Dan

This page took 0.04 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.