I noticed chess engines have quite different approaches saving the game history.
Some use a very small StateInfo structure, storing only castlingrights, epsquare and drawcounter.
Most of these store inside the Position structure a fixed array of StateInfo (with a length of 2048 or something like that).
Some engines - I believe Stockfish does so - have (correct me if I am wrong) some external big stack with a larger StateInfo.
(checkers, pins, hashkeys etc.)
This makes it faster to undo moves without having to recalculate stuff.
The only thing I do not like about this last approach is the "external pointer injection" into Position.
It makes Position more tricky and not a self-contained structure.
I guess there are hybrid approaches as well. Maybe some engines use a growable (heap managed) StateInfo list?
What do people think about the how and what of these approaches.
What is good, what is bad, what is fast etc.
The way engines store history
Moderator: Ras
-
Aleks Peshkov
- Posts: 903
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
- Full name: Aleks Peshkov
Re: The way engines store history
I use class Node that extended from Position for easier access.
Object of class Node have pointer to parent and grandparent Nodes. Some methods are easier to make as parent inside current node, some methods are easier to make as child node inside current.
For example: parent->killerMove = child->currentMove
Object of class Node have pointer to parent and grandparent Nodes. Some methods are easier to make as parent inside current node, some methods are easier to make as child node inside current.
For example: parent->killerMove = child->currentMove
-
hgm
- Posts: 28363
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: The way engines store history
With 'history' you mean the information that is stored in order to take back moves during search?
There are two basic approaches to this: copy-make and make-unmake. With copy-make you don't have to explicitly store anything; to take back a move you simply discard the modified copy. For make-unmake you have to store values that are irreversibly overwritten during make.
My engines typically use a mixed approach. For data that can be copied very cheaply, such as castling rights, I use copy-make. For data that would be hard to copy (such as a board array) and is hardly modified, I use make-unmake.
If modifications are irreversible, make-unmake requires copying those, so that the difference between copy-make and make-unmake boils down to whether you apply the move to the original or the copy. Which should not make much difference in efficiency. But for make-unmake you would then have to copy the stored information back, which is extra work. So make-unmake is only attractive if it the modified data is part of a larger structure, (such as the from- and to-square in a mailbox board), and cannot be used in isolation.
For reversibly altered info, such as the ply counter, you often don't have to store anything; you just increment it on make, and decrement it on unmake.
In the 'Mailbox Trials' copy-make turned out to be more efficient for the attack map. Even though this was a pretty large array, a typical move modified it in so many places that make-unmake was no longer competitive.
There are two basic approaches to this: copy-make and make-unmake. With copy-make you don't have to explicitly store anything; to take back a move you simply discard the modified copy. For make-unmake you have to store values that are irreversibly overwritten during make.
My engines typically use a mixed approach. For data that can be copied very cheaply, such as castling rights, I use copy-make. For data that would be hard to copy (such as a board array) and is hardly modified, I use make-unmake.
If modifications are irreversible, make-unmake requires copying those, so that the difference between copy-make and make-unmake boils down to whether you apply the move to the original or the copy. Which should not make much difference in efficiency. But for make-unmake you would then have to copy the stored information back, which is extra work. So make-unmake is only attractive if it the modified data is part of a larger structure, (such as the from- and to-square in a mailbox board), and cannot be used in isolation.
For reversibly altered info, such as the ply counter, you often don't have to store anything; you just increment it on make, and decrement it on unmake.
In the 'Mailbox Trials' copy-make turned out to be more efficient for the attack map. Even though this was a pretty large array, a typical move modified it in so many places that make-unmake was no longer competitive.