implementation of undoMove()?

[cyberfish]

Hi,
I have read some engine's source code (mostly crafty and gnuchess) and it seems that they all have complicated undoMove() functions. I wrote my program before I read their sources, and the way I did it is simply make a stack of previous boards. That way, every time I need to undo a move I only need to do simple copies of ~20 bitboards (including all the auxillary boards I use). Can someone please enlighten me as to how the way crafty and gnuchess has done it is better than how I am doing it? It seems to me that copying should be faster as there is almost no branching at all, just copying 160 bytes or so (another 160 for storing).

Thank you

[Robert Pope]

In some cases, a copy may well be faster. You just have to try them both and see.

[bob]

Hi,
I have read some engine's source code (mostly crafty and gnuchess) and it seems that they all have complicated undoMove() functions. I wrote my program before I read their sources, and the way I did it is simply make a stack of previous boards. That way, every time I need to undo a move I only need to do simple copies of ~20 bitboards (including all the auxillary boards I use). Can someone please enlighten me as to how the way crafty and gnuchess has done it is better than how I am doing it? It seems to me that copying should be faster as there is almost no branching at all, just copying 160 bytes or so (another 160 for storing).

Thank you

that's too slow on the PC. Memory bandwidth is limited. The Copy/Make approach will be much slower than Make/Unmake. If you look at the comments in main.c in Crafty, you will notice that I made the same mistake early on in the development of Crafty, but I later rewrote it as a Make/Unmake program and speeded it up _significantly_. A factor of 2x or more if I remember correctly. Copy/Make is murderously expensive in the q-search...

[cyberfish]

that's too slow on the PC. Memory bandwidth is limited. The Copy/Make approach will be much slower than Make/Unmake. If you look at the comments in main.c in Crafty, you will notice that I made the same mistake early on in the development of Crafty, but I later rewrote it as a Make/Unmake program and speeded it up _significantly_. A factor of 2x or more if I remember correctly. Copy/Make is murderously expensive in the q-search...

Thank you for the explanation, that clears it up for me. I never thought copying data is that expensive =).

[wgarvin]

Accessing memory tends to be pretty slow on modern machines---reading from the L2 cache can take dozens of cycles, and reading from main memory can take hundreds. That's why it is often faster to do some small calculations, than to read a pre-calculated thing from a table. The only exception really, is if you have just accessed that memory shortly before and so you know it will be in the L1 cache.

You can fit all the state needed to undo a move into 32 bits without much trouble: source square, dest square, type of captured piece (if any), and either the previous halfMove counter, or the previous enpassant square (the two of those can fit together in 7 bits if necessary) .

[Stan Arts]

Hi,

something in between is possible too, and that way unmaking is very simple,

Because if you only copy and make,
Before making a move at some depth in the tree that's not the first in the movelist you have to restore/recopy the board every move. (not when it's the first move, because when it's the first the position is ok already because it directly follows a move from one depth higher in the tree (moving down), instead of moving back up in the tree. (assuming the root is high and the leafes down/low) )

However at any depth in the tree you can also store the board before making the first move like you already would with copy/make, but then instead of recopy before the next move, unmake each move on that depth by only recopying the contents of your from/to squares from the stored board, only having to deal with a few special cases like castling and enpassant etc. (depending on your datastructures checking for special cases probably won't take much, much less then copying the entire board anyway) And not have to also store captured piece to be able to unmake a capture, or promotion, etc. which normally makes unmaking complicated.

This probably gives a speedimprovement over copy/make every time at the last ply/termination of the tree, where it matters most.

I don't know if anyone else does this, but this is what I do. (Neurosis used to be purely copy/make, till I figured this out about a year ago. It was a speedup of a few %. (and it sounds like you are copying almost 3x as many bytes as I am at each copy) )

Regards,
Stan

Hi,
I have read some engine's source code (mostly crafty and gnuchess) and it seems that they all have complicated undoMove() functions. I wrote my program before I read their sources, and the way I did it is simply make a stack of previous boards. That way, every time I need to undo a move I only need to do simple copies of ~20 bitboards (including all the auxillary boards I use). Can someone please enlighten me as to how the way crafty and gnuchess has done it is better than how I am doing it? It seems to me that copying should be faster as there is almost no branching at all, just copying 160 bytes or so (another 160 for storing).

Thank you