Is Unmake Move truly necessary?

[SethCS]

Hello,

I'm new to this forum and have a question about unmake move. Currently my move generator achieves perft 6 from the starting position with a speed of about 20M nodes/second (single threaded). However, I would like to improve this. Granted, I'm using horrible hardware (an old laptop from 2006 - no joke) but I still feel like my move generator is extremely slower than some other top chess engines.

I wanted to focus on unmake move. It seems to me like there is a lot of overhead storing the information, and all of the checks involved whenever you unmake a move. Instead all of my moves are stored in an array, with the root initialized at index 0. My current state is simply a pointer to this array. When I want to make a move, I use std::memmove (I should probably note I'm using c++), to the next index. When I want to unmake a move, I simply move my pointer back one index.

While this is definitely less code, do you guys think I'm losing a lot of speed with this method? Do you think it's absolutely necessary to have a traditional unmake function?

[H.G.Muller]

Whether copy-make or make-unmake is faster depends on the complexity of your game-state representation. In particular which fraction of it typically changes. E.g. if you have a mailbox board of 64 memory cells, and only 2 cells change during a move, changing 2 cells back on unmake is probably faster than copying the 64 cells (even if they are bytes and your memcopy can copy them 8 by 8) and making the move on the copy. It all depends on how much is copied unchanged, compared to how much changes.

Also note that you don't have to use the same method for all parts of the game state. E.g. for castling rights and the hash key you could use copy-make by passing them as a parameter in the recursive call to Search(), while for the board you use make-unmake.

[delphi_coder]

Despite the fact that, this topic not matters most in engine performance in comparison to having good implemented search algorithm or having optimistic evaluation function just in case I believe, at-least in 8086 architecture (currently the most widely used computers) using a simple code

Code: Select all

move rdi,dest
move rsi,src
move cx,size
cld
rep movsb

in assembly level could be faster than calling a routine and throwing the program to bunch of conditional jumps. It means resetting CPU instruction cache again and again which could result lowering the performance for just unmaking a move. C,C++ and also pascal compilers of these days generating good optimized code. Anyways these are just theory or paper based things, the best is implementing and testing it precisely to see which one has better result.

[chrisjly]

Hello,
The first version of my chess program written in C did not unmake the moves because the chess board structure was stored on the stack.
It was just necessary to do a memcpy of the structure at every node. I had to use a small structure so I choosed to use a 8x8 board.
In the beginning of the 2000's I switched to a mixed data structure, one on the stack and one on global memory (unmaking necessary). I didn't noticed a slowdown in the node/s. As said above, the today's microprocessors are very fast in calculations so the benefit of pulling the stack for unmaking moves is not evident.