OpenChess

Hello, I have a question concerning "saving" info about your board representation before making a move. I am wondering what is a good way to do this? Right now I have an array of structs of type Save_t, and when the make move function is called it adds a new "save" to the top of the save stack. My Save_t data structure saves information such as the e.p. square, the piece (if any) that was captured, castling rights, etc. The unmake function simply pops the top of the save stack and uses the info to undo the move on the board. However, it seems that my save/unmake functions are very slow. I am using bitboards and an array in unison to represent my board. What is a good (preferably fast) way to save enough info about the board state such that a move can be unmade?

CDaley11 wrote:Hello, I have a question concerning "saving" info about your board representation before making a move. I am wondering what is a good way to do this? Right now I have an array of structs of type Save_t, and when the make move function is called it adds a new "save" to the top of the save stack. My Save_t data structure saves information such as the e.p. square, the piece (if any) that was captured, castling rights, etc. The unmake function simply pops the top of the save stack and uses the info to undo the move on the board. However, it seems that my save/unmake functions are very slow. I am using bitboards and an array in unison to represent my board. What is a good (preferably fast) way to save enough info about the board state such that a move can be unmade?

There are two ways that are well-known.

The first is a simple global chess board, where you Make/Unmake moves to walk around in the tree.

The second is commonly called copy/Make, where you copy the board structure to a new block, then update that with Make. Now you don't need to do the unmake, you just back up to the previous block of memory and you are instantly back to that position. Downside is the copy operation, upside is the lack of unmake. Seems to be a wash nowadays. A long while back it was better to use make/unmake because the copy was pretty expensive with older memory systems on the PC.

hyatt wrote:

CDaley11 wrote:Hello, I have a question concerning "saving" info about your board representation before making a move. I am wondering what is a good way to do this? Right now I have an array of structs of type Save_t, and when the make move function is called it adds a new "save" to the top of the save stack. My Save_t data structure saves information such as the e.p. square, the piece (if any) that was captured, castling rights, etc. The unmake function simply pops the top of the save stack and uses the info to undo the move on the board. However, it seems that my save/unmake functions are very slow. I am using bitboards and an array in unison to represent my board. What is a good (preferably fast) way to save enough info about the board state such that a move can be unmade?

There are two ways that are well-known.

The first is a simple global chess board, where you Make/Unmake moves to walk around in the tree.

The second is commonly called copy/Make, where you copy the board structure to a new block, then update that with Make. Now you don't need to do the unmake, you just back up to the previous block of memory and you are instantly back to that position. Downside is the copy operation, upside is the lack of unmake. Seems to be a wash nowadays. A long while back it was better to use make/unmake because the copy was pretty expensive with older memory systems on the PC.

Thanks for your suggestion! The size of my Board_t structure is just 192 bytes, and I tried out simply making a copy of the whole board, rather than unmaking the move, and my program now runs noticeably faster.

hyatt wrote: There are two ways that are well-known.

The first is a simple global chess board, where you Make/Unmake moves to walk around in the tree.

The second is commonly called copy/Make, where you copy the board structure to a new block, then update that with Make. Now you don't need to do the unmake, you just back up to the previous block of memory and you are instantly back to that position. Downside is the copy operation, upside is the lack of unmake. Seems to be a wash nowadays. A long while back it was better to use make/unmake because the copy was pretty expensive with older memory systems on the PC.

Interesting. I never thought about this too much. I first learnt computer chess programming by loking at the GNU Chess 5 and Crafty (don't remember which version) sources quite a few years ago (around 2003 or so). From that time I always thought that make/unmake was the normal way. And that's what I did in all my programs. But after doing some serious perft profiling I ended up creating a "stack" structure where I put lots of stuff to save the undo() having to recompute it. In the end, what I have in DiscoCheck is a hybrid approach, that is leaning more towards the copy than the pure make/unmake actually. If I was to rewrite this one day (can't be bothered) I would use a plain and simple copy.

Another approach that I've used is to store the board state information (castling, e.p., etc.) in the move object. When a move is made, all of the necessary state information is copied from the board the move; when the move is later "unmade", the state information is copied from the move back to the board. This may not be hugely innovative or efficient, but is very easy to code and debug.

Cheers!
Humble Programmer
,,,^..^,,,