How costly is taking moves back ?

[OneTrickPony]

So I am completely new to chess programming and just trying to wrap my head around why basic things are done in the way they are done.

Take backtracking for example. There are two ways:
a)use one board representation struct/object and when visiting a node make a move on it but when going back take the move back to reuse for sibling node;

b)allocate new board representation struct/object for every new node visited; it isn't memory expensive because every time we go back stack pointer takes care of deallocating boards we created (we use N boards instead of 1 where N is length of the path from root to leaf)
(we allocate new memory once and then memcpy from original for every child visited);

Cost of a) is taking moves back. Cost of b) is cost of allocating stuff on stack + memcpy of arrays.
My question is if anybody tried b). Is it obviously slower ?

I tried it for N queens problem for fun and it was a fail (finding all solutions for 15x15 board took 20045ms for standard backtracking and 34061ms for one with allocating new boards) but in N queens problems taking moves backs is trivial while it's not so trivial in chess.

Thoughts ?

(EDIT: after compiling with /Ox the times were 9658ms and 25282ms so even worse)

[syzygy]

Cost of a) is taking moves back. Cost of b) is cost of allocating stuff on stack + memcpy of arrays.
My question is if anybody tried b). Is it obviously slower ?

There are long threads on copy/make, which is your option b).

http://talkchess.com/forum/viewtopic.php?t=39938
http://talkchess.com/forum/viewtopic.php?t=29770
http://talkchess.com/forum/viewtopic.php?t=29798

And I think there are more.

[OneTrickPony]

Thanks much, I suck at searching this forum

[jdart]

Re a) there are two ways to reuse: have code "undo" a move (reverse of "move") or just save essential state before the move and copy it back into the board structure to "undo". Unless you have a very simple board structure, the latter is probably faster.

Re b) I don't see why you would ever want allocate on the heap instead of the stack for such a frequently used structure. malloc has a non-trivial cost. With C++ and a custom allocator you can minimize the cost but it is still there.

--Jon

[OneTrickPony]

Hi, I didn't mention malloc. I mention memcpy for copying arrays (and if you have many arrays to express game state and only some of them change when making a move you can just copy pointers to ones unchanged).

or just save essential state before the move and copy it back into the board structure to "undo".

To save it somewhere I need to allocate memory anyway (on the stack) and then memcpy to it and then memcpy back when backtracking. Isn't it exactly the same performance wise as cloning the game state (or even worse)?

[hgm]

In the time when it was still competitive to build your own hardware, I once considered building a memory card using 'video RAM'. These RAMs contained a shift register, and you could transfer an entire memory page (row of the memory matrix) to or from the shift register in a single memory cycle. The idea was that this would make copy/make very cheap, by copying a page to the shift register, and the next cycle transfer it back to another page, so that I would be able to copy entire move lists and attack maps, and then incrementally update them without worrying about the undo.

I never got to do it, though. The VRAM chips are still sitting in a drawer in my attic.

[Evert]

To save it somewhere I need to allocate memory anyway (on the stack) and then memcpy to it and then memcpy back when backtracking. Isn't it exactly the same performance wise as cloning the game state (or even worse)?

You can do it like that, but it's certainly not the best way to do it.
In Jazz, I allocate a list of boards (type board_t) at the beginning and I set up a pointer (board) that points to the first entry. When I make a move I memcpy(board+1, board, sizeof *board) followed by board++. Then I make the move on the (now current) board.

My unmake move is basically just board--;

It's just a waste of time to copy things twice.

[OneTrickPony]

My unmake move is basically just board--;

So what you do is imitate function call stack memory with global stack. In my first post I described doing the same thing (I believe!) just using function call stack to store game states (so when the function returns your board-- is the same as call stack going back).
Intuitively your way is faster (because in my way every function call allocates memory for new state while in your way the memory is reused and in the same place all the time) but my intuition is too weak to tell without tests and it's quite some time till I start working on game representation/move generation.

[OneTrickPony]

In Jazz, I allocate a list of boards (type board_t) at the beginning and I set up a pointer (board) that points to the first entry.

Ok I really like this. One more question: where do you keep this stack ? Do you allocate it on the call stack and pass the pointer around (or make a global pointer?) or do you malloc it (or maybe declare as global variable?) ?

[syzygy]

My unmake move is basically just board--;

So what you do is imitate function call stack memory with global stack. In my first post I described doing the same thing (I believe!) just using function call stack to store game states (so when the function returns your board-- is the same as call stack going back).
Intuitively your way is faster (because in my way every function call allocates memory for new state while in your way the memory is reused and in the same place all the time) but my intuition is too weak to tell without tests and it's quite some time till I start working on game representation/move generation.

Your "allocation" is not costing anything, because it's only a matter of reserving place on the stack. (While strictly speaking I can't object to the term "allocate", I think using this term easily leads to confusion in this discussion.)

Both the global stack and the call stack consist of memory that is continuously being reused as the search tree is traversed, so I don't think there is a clear winner in terms of speed. (With a global stack it might be easier to align on cache line boundaries, but I don't know if that is a decisive advantage.)

I use make/unmake for the part of the board representation that is not affected by every move (e.g. the board[64] array and bitboards for piece types) and copy/make using a global stack for the part that is affected by every move.

Using a global stack instead of the call stack seems easier to me, because it decouples the call stack from the tree traversal. I like to be able to make or take back a series of moves without having to use recursion.

A global stack also helped for the way I implemented a multithreaded search.