UnMakeMove
Orhan Öztürk
Recently I have checked some chess programs,especially crafty,i have
noticed that the UnMakeMove routine is exactly reverse of MakeMove(As
should be,no suprise).The MakeMove routine includes hundreds of lines
including update of piece bitboards,castle flags,en passant
flags,removing captured pieces,updating material counts...etc.And
UnMakeMake does these costly things again but in reverse manner.
I have a question about this.
Why dont we get a copy of position before we enter MakeMove() so that
later we can restore the original position back?This requires a simple
memcpy function and a stack for holding positions at each ply.When the
previous position is needed to be restored the only thing to do is
decrementing the stack pointer,that is all.
For generating moves, move generator only needs the current position's
starting adress,which is stack pointer's current place.
Copying a position requires moving sizeof(position) bytes of data.This
should not cost high.
What is wrong with this idea ? Are there any programs using this
technique ?
Regards
Severi Salminen
> later we can restore the original position back?This requires a simple
> memcpy function and a stack for holding positions at each ply.When the
> previous position is needed to be restored the only thing to do is
> decrementing the stack pointer,that is all.
When your bitboard structure is small, this is a good approach, but when it
gets really large, like in Crafty, memcopying all might be slower than only
updating those bitboards necessary. Having, say, 24 bitboards is having
192bytes of data. That is 48 MOV instructions in assembly. With 48
instructions you can do many individual updates, and usually only a few
bitboards need to be updated.
Severi.
Jean-François GAZET
I don't use bitboards.
"Orhan Öztürk" <ooz...@porttakal.com> a écrit dans le message news:
532069cf.02120...@posting.google.com...
B. Ross
If we examine more than 3 or 4 plys in an opening or middle game
position, we need to store millions of moves (or positions,
respectively). Thus, the size of what we store _does_ matter.
Perhaps your concept might work in the 'quiescence search', where
the number od nodes in the search tree is comparatively small.
Regards
B. Ross
>
> > Hi All,
> >
> > Recently I have checked some chess programs,especially crafty,i have
> > noticed that the UnMakeMove routine is exactly reverse of MakeMove(As
> > should be,no suprise).The MakeMove routine includes hundreds of lines
> > including update of piece bitboards,castle flags,en passant
> > flags,removing captured pieces,updating material counts...etc.And
> > UnMakeMake does these costly things again but in reverse manner.
> >
> > I have a question about this.
> >
> > Why dont we get a copy of position before we enter MakeMove() so that
> > later we can restore the original position back?This requires a simple
> > memcpy function and a stack for holding positions at each ply.When the
> > previous position is needed to be restored the only thing to do is
> > decrementing the stack pointer,that is all.
> >
> > For generating moves, move generator only needs the current position's
> > starting adress,which is stack pointer's current place.
> >
> > Copying a position requires moving sizeof(position) bytes of data.This
> > should not cost high.
> >
> > What is wrong with this idea ? Are there any programs using this
> > technique ?
> >
> > Regards
>
"B. Ross" wrote <nonsense>
Meanwhile, I believe I misunderstood your proposal. I apologize for that.
Please ignore my answer.
Regards
Robert Hyatt
> Hi All,
> Recently I have checked some chess programs,especially crafty,i have
> noticed that the UnMakeMove routine is exactly reverse of MakeMove(As
> should be,no suprise).The MakeMove routine includes hundreds of lines
> including update of piece bitboards,castle flags,en passant
> flags,removing captured pieces,updating material counts...etc.And
> UnMakeMake does these costly things again but in reverse manner.
> I have a question about this.
> Why dont we get a copy of position before we enter MakeMove() so that
> later we can restore the original position back?This requires a simple
> memcpy function and a stack for holding positions at each ply.When the
> previous position is needed to be restored the only thing to do is
> decrementing the stack pointer,that is all.
The answer becomes apparent when you test your idea, which is known as
"copy-make" by the way. The problem is the "copy" operation. The PC
doesn't have a lot of memory bandwidth and that taxes it beyond its
ability to keep up. You will find it is slower to copy-make than to
make-unmake... with make-unmake everything stays in cache, not so with
copy-make.
> For generating moves, move generator only needs the current position's
> starting adress,which is stack pointer's current place.
> Copying a position requires moving sizeof(position) bytes of data.This
> should not cost high.
> What is wrong with this idea ? Are there any programs using this
> technique ?
> Regards
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
B. Ross
Robert Hyatt wrote:
> Orhan Öztürk <ooz...@porttakal.com> wrote:
<...>
> > Why dont we get a copy of position before we enter MakeMove() so that
> > later we can restore the original position back?This requires a simple
> > memcpy function and a stack for holding positions at each ply.When the
> > previous position is needed to be restored the only thing to do is
> > decrementing the stack pointer,that is all.
>
> The answer becomes apparent when you test your idea, which is known as
> "copy-make" by the way. The problem is the "copy" operation. The PC
> doesn't have a lot of memory bandwidth and that taxes it beyond its
> ability to keep up. You will find it is slower to copy-make than to
> make-unmake... with make-unmake everything stays in cache, not so with
> copy-make.
Dear Dr. Hyatt,
would you mind explaining your answer in more detail? I'm a bit puzzled
about it. The access to a stack with copies of boards would be local, not
random.
At least at the terminal levels of a search (where we spend most time), the
top
entries of the stack will be cached after the first access. 'Penalties' for
cache
misses will only occur when we traverse the search tree back to some (much)
higher level. However, compared to the number of nodes at the terminal
levels,
they will be rare. Where am I wrong?
Robert Hyatt
> Robert Hyatt wrote:
>> Orhan Öztürk <ooz...@porttakal.com> wrote:
> <...>
>> > Why dont we get a copy of position before we enter MakeMove() so that
>> > later we can restore the original position back?This requires a simple
>> > memcpy function and a stack for holding positions at each ply.When the
>> > previous position is needed to be restored the only thing to do is
>> > decrementing the stack pointer,that is all.
>>
>> The answer becomes apparent when you test your idea, which is known as
>> "copy-make" by the way. The problem is the "copy" operation. The PC
>> doesn't have a lot of memory bandwidth and that taxes it beyond its
>> ability to keep up. You will find it is slower to copy-make than to
>> make-unmake... with make-unmake everything stays in cache, not so with
>> copy-make.
> Dear Dr. Hyatt,
> would you mind explaining your answer in more detail? I'm a bit puzzled
> about it. The access to a stack with copies of boards would be local, not
> random.
The problem is that if you do copy/make, where the thing you are copying
has any significant size to it, you smoke the memory bus since this is
done once per node searched. In the case of Crafty on fast hardware, this
is 2M+ times a second...
> At least at the terminal levels of a search (where we spend most time), the
> top
> entries of the stack will be cached after the first access. 'Penalties' for
> cache
> misses will only occur when we traverse the search tree back to some (much)
> higher level. However, compared to the number of nodes at the terminal
> levels,
> they will be rare. Where am I wrong?
The problem is that the stuff has to really be copied from one place in memory
to another. If you get a cache hit, eventually you get a cache miss to the
same line causing it to first be flushed back to memory.
Early versions of Crafty did copy/make, but I later discovered that while this
worked just fine on a Cray, it was terrible on a PC...
B. Ross
I believe I understand now. Thank you very much!
Best Regards
!-!erc
many people trained on computers falter in
competition.
Luckily www.chess3.com is not so forgiving.
Herc
Severi Salminen
A joke? Unmake, in this thread, meant unmaking moves in search tree: it just
means updating the internal data structures to search different moves.
Nothing to do with unmaking moves in the real game.
Severi
Orhan Öztürk
> Orhan Öztürk <ooz...@porttakal.com> wrote:
> > Hi All,
>
> > Recently I have checked some chess programs,especially crafty,i have
> > noticed that the UnMakeMove routine is exactly reverse of MakeMove(As
> > should be,no suprise).The MakeMove routine includes hundreds of lines
> > including update of piece bitboards,castle flags,en passant
> > flags,removing captured pieces,updating material counts...etc.And
> > UnMakeMake does these costly things again but in reverse manner.
>
> > I have a question about this.
>
> > Why dont we get a copy of position before we enter MakeMove() so that
> > later we can restore the original position back?This requires a simple
> > memcpy function and a stack for holding positions at each ply.When the
> > previous position is needed to be restored the only thing to do is
> > decrementing the stack pointer,that is all.
>
> The answer becomes apparent when you test your idea, which is known as
> "copy-make" by the way. The problem is the "copy" operation. The PC
> doesn't have a lot of memory bandwidth and that taxes it beyond its
> ability to keep up. You will find it is slower to copy-make than to
> make-unmake... with make-unmake everything stays in cache, not so with
> copy-make.
Thank you Bob, i got the idea.