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)
How costly is taking moves back ?
Moderators: hgm, Rebel, chrisw
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: How costly is taking moves back ?
There are long threads on copy/make, which is your option b).OneTrickPony wrote: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 ?
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.
-
- Posts: 157
- Joined: Tue Apr 30, 2013 1:29 am
Re: How costly is taking moves back ?
Thanks much, I suck at searching this forum
-
- Posts: 4367
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: How costly is taking moves back ?
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
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
-
- Posts: 157
- Joined: Tue Apr 30, 2013 1:29 am
Re: How costly is taking moves back ?
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).
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)?or just save essential state before the move and copy it back into the board structure to "undo".
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How costly is taking moves back ?
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.
I never got to do it, though. The VRAM chips are still sitting in a drawer in my attic.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: How costly is taking moves back ?
You can do it like that, but it's certainly not the best way to do it.OneTrickPony wrote: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)?
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.
-
- Posts: 157
- Joined: Tue Apr 30, 2013 1:29 am
Re: How costly is taking moves back ?
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).My unmake move is basically just board--;
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.
-
- Posts: 157
- Joined: Tue Apr 30, 2013 1:29 am
Re: How costly is taking moves back ?
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?) ?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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: How costly is taking moves back ?
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.)OneTrickPony wrote: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).My unmake move is basically just board--;
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.
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.