Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move Make/Unmake Questions

Author: Dan Homan

Date: 04:14:39 07/16/99

Go up one level in this thread


On July 15, 1999 at 17:37:42, Will Singleton wrote:

>
>On July 15, 1999 at 10:28:24, Dan Homan wrote:
>
>>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"
>>routine.
>>
>> - Dan
>
>
>Sounds interesting, help me out on this.  Is this substantially diferent than
>storing each move into 64 arrays (each corresponding to a square), then indexing
>into each array for the current state?  The unmake would just be to subtract the
>index.  Then, you wouldn't have the limit problem.
>
>How about state info, like en passant and castle privileges?  Would you have to
>copy those from ply-to-ply if you wanted to simplify the unmake to a bit shift?
>
>Will

In principle it is not substantially different than your array idea.  The
only major difference is that rather than an array for each square; I just
have an int or and int64.  4 bits store the current state of a square and each
time the state changes I do a bit shift and an "AND" to give the new state.
To get the old state back, I would just bit shift in the other direction.
I have a fondness for neat ideas - even if they are not very practical.
This one is not very practical given that I would need a rather complicated
scheme for the rare cases where the state of a square changes more than
16 times in the search.

As you point out, I would still need to do a memory copy for ep and castling
rights.  Bruce is certainly correct that twiddling the squares during make
and unmake is simpler.  It is also probably just as fast (for practical
purposes anyway).  Also if I have only one state on each square (rather
than a bit-shifted collection of states), I can extract information about
the square more easily without having to do an "&15" to get the current
state of the square first. Oh well...

The simplest thing to do, of course, is just one gigantic copy of the
position, which is what I do currently (I have an array of positions and
just copy the current position to the future position prior to make - then I
have no need for an unmake routine at all).  I've been told that doing
this is considerably slower than a full make/unmake cycle.

 - Dan



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.