Is Unmake Move truly necessary?

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Is Unmake Move truly necessary?

Postby SethCS » 18 May 2017, 18:47

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?
SethCS
 
Posts: 1
Joined: 12 May 2017, 23:32

Re: Is Unmake Move truly necessary?

Postby H.G.Muller » 18 May 2017, 21:14

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.
User avatar
H.G.Muller
 
Posts: 3392
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Is Unmake Move truly necessary?

Postby delphi_coder » 05 Aug 2022, 09:33

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.
delphi_coder
 
Posts: 2
Joined: 21 Jul 2022, 08:32


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 6 guests