How costly is taking moves back ?

[Don]

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)

I'm a big advocate of copy/make without need undo. But there are good arguments for either method. copy state is very fast. With undo, you STILL have to maintain "undo" state as well as additional logic for the make and of course unmake becomes another routine that takes time to execute so it's certainly not as clean and simple. Is it faster either way? I don't really know for sure, but in Komodo I once measured that making a move barely registers on the profile. I assume that making and then unmaking the moves would also be very cheap if I were doing it that way.

One never knows for sure because everything impacts everything else in some way. So the speed of any given routine does not tell the entire story and neither does a profile tool.

Bottom line, I prefer the simplicity of copy/make. By the way, I did an experiment once where I artificially increased the size of the board state to see how it impacted things and I had to make the state a LOT bigger for it to have a noticeable slowdown effect on the program. Still, probably due to superstition more than anything else, I am careful to keep it relatively small.

Don

[OneTrickPony]

It's also natural way to me so if it's not significantly slower I will choose it once I am ready to code some chess.
I started thinking about it after writing a toy backtracking solver in Haskell. In Haskell you don't have mutable state so "copy/make" is forced. The compiler however is smart enough to only copy pointers of record fields which aren't modified during "make" (as state is not mutable, those are guaranteed to stay constant during execution). I thought it would be good idea to try the same thing in chess.
I was very surprised to find out it's raging debate here

[Don]

It's also natural way to me so if it's not significantly slower I will choose it once I am ready to code some chess.
I started thinking about it after writing a toy backtracking solver in Haskell. In Haskell you don't have mutable state so "copy/make" is forced. The compiler however is smart enough to only copy pointers of record fields which aren't modified during "make" (as state is not mutable, those are guaranteed to stay constant during execution). I thought it would be good idea to try the same thing in chess.
I was very surprised to find out it's raging debate here

I didn't know it was a raging debate, but there has been some discussion on it. I have concluded that it's not very expensive and it make a clearly simpler program and is a good fit for eventual MP work too where you must maintain separate state anyway.

I have planned at some point to test make/unmake but based on profile data I would not get anything out of it. Of course I might discover than that the reduced memory is a benefit. Each state is stored in the stack frame, I don't malloc a new state of course but just declare the new state at the top of the search routine which is recursive. So that makes the stack bigger.

My make routine expect 2 state pointers and a move:

make( *old_state, *new_state, move );

Don

[hgm]

I always use make/unmake. With mailbox boards this is much faster as copying the entire board, as typically the unmake only has to put the piece and the victim back. Even aliasing the ranks of the board to 8-byte quantities would require 8 load-store pairs to copy the board. The same holds for the piece list; also there only the location of piece and victim change, and will have to be restored. (Special moves, which require more than just moving a single piece, are too rare in the tree to affect the decision; I have special make and unmake functions for those.)

The problem gets worse as the data structure gets larger. On a 25x25 board that uses int in stead of char variables because there are more than 256 pieces, copying would become very costly, while the conventional make/unmake isn't anymore expensive than on 8x8. Even with 8x8 you can get such a situation when dealing with a quite large data structure, such as an incrementally update attack map. In such cases I could greatly limit the UnMake overhead by not implementing it a reverse MakeMove, but by letting MakeMove build an 'undoStack', storing a pointer (or index) plus value pair on it for every item in the attack map that it changes. Usually this only requires storing of values it was already working on, and extra store instructions hardly take time, as the store unit is usually idle. The takeback then only has to loop over the undoStack, and put everything back, without any complex logic decisions.

[Don]

I always use make/unmake. With mailbox boards this is much faster as copying the entire board, as typically the unmake only has to put the piece and the victim back. Even aliasing the ranks of the board to 8-byte quantities would require 8 load-store pairs to copy the board. The same holds for the piece list; also there only the location of piece and victim change, and will have to be restored. (Special moves, which require more than just moving a single piece, are too rare in the tree to affect the decision; I have special make and unmake functions for those.)

The problem gets worse as the data structure gets larger. On a 25x25 board that uses int in stead of char variables because there are more than 256 pieces, copying would become very costly, while the conventional make/unmake isn't anymore expensive than on 8x8. Even with 8x8 you can get such a situation when dealing with a quite large data structure, such as an incrementally update attack map. In such cases I could greatly limit the UnMake overhead by not implementing it a reverse MakeMove, but by letting MakeMove build an 'undoStack', storing a pointer (or index) plus value pair on it for every item in the attack map that it changes. Usually this only requires storing of values it was already working on, and extra store instructions hardly take time, as the store unit is usually idle. The takeback then only has to loop over the undoStack, and put everything back, without any complex logic decisions.

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I'm not arguing that make/unmake is slower or that copy/move is better and faster, I don't know the answer to that, I just know the difference is trivial. But you make it sound like undue is just 2 simple operations with almost no logic to it (just move the piece and restore the captured piece) and we know that is not the case for a real program that does a lot of things incrementally for efficiency.

On a 25x25 board the cost ratio would change of course so it may be the way to go for you or people working on other games, but I'm only discussing chess. If we were discussing home security systems and what is best, then you bring the possibility of a military bombardment into the picture, then of course the context completely changes. I don't have an argument for or against how you build a move generator for a completely different game.

[syzygy]

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I suppose most if not all implementations of make/unmake copy at least those position attributes. It makes no sense to throw away the old hash key value and then having to recalculate it during the unmake.

[Pio]

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I suppose most if not all implementations of make/unmake copy at least those position attributes. It makes no sense to throw away the old hash key value and then having to recalculate it during the unmake.

Hi Ronald!

If I am not wrong you will just have to make the same xor once more to get your Zobrist hash the move before so I do not think it will be a big problem.

Kind Regards
Pio

[Don]

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I suppose most if not all implementations of make/unmake copy at least those position attributes. It makes no sense to throw away the old hash key value and then having to recalculate it during the unmake.

Yes, that is exactly my point. But you can replace the stack with additional operations, but that starts to make the argument against copy/make less convincing.

This is one of those things that we tend to oversimplify in our minds. We say, "oh, that's easy, all you have to do is ...." and when pressed we have to admit, "oh yes, you also have to do this other thing" and probably qualify each additional thing we forgot about with, "but that is trivial" and so it goes.

One way or the other, you have to update the ply of the game, the hash key, whatever you do incrementally (which can be a lot in a really good chess program), castling rights, half move clock, and other stuff. You can do it with a stack, whether an explicit stack or part of the search stack, or you can get this information with additional calculation.

Komodo keeps 3 or 4 keys such as material signature, primary hash key, pawn structure hash key as well as the ply of game, castling rights, incremental score, pointer to previous state, stage of game, incheck flag and other stuff.

Not all of this is required for a toy program of course but I believe that the more sophisticated a program becomes the bigger gain from using copy/move. If I had make/unmake I probably would compute more things instead of putting them on a statck. But I like being able to know stuff such as what was the score 2 moves ago? Was the move 2 ply ago a check or out of check move or a capture? So I keep a pointer to previous board states. There are always creative ways to get information like that, you can pass it along as an extra parameter, or keep a separate stack for all these little details which then starts to look more and more like copy/make.

A hybrid approach is to have an extremely primitive make/unmake and on top of a state structure like komodo's that keeps everything EXCEPT the board itself. (The board could be in the state as a pointer to a global board.) And then when I make a move I still do copy/make except I have an additional unmake for modifying the board in place.

In this way I would not have to change hardly anything in Komodo except the addition of a unmake routine which only changes the board itself. That is an experiment that I want to try at some point just to see if the few extra bytes of state has some impact on memory caching. Since make is almost no measurable difference in terms of execution time there is no hope of getting an improvement based on saving time to copy state. Note that Komodo only needs 176 bytes per level for the board part of the representation itself, so if I were doing a 100 ply search it would consume only 17k which on modern processors is nothing. The total state size, which includes all sorts of things that one might keep around such as the things mentioned above is currently 272 bytes. As I said many of those things EVERY program has to maintain anyway. An additional benefit is that when a processor reads state everything gets cached and modern programming practices and languages are emphasizing immutable data structures and a position state in Komodo becomes immutable after it's created.

I think that make/unmake is a vestige from the old days of computer chess where you had no other option due to extremely limited memory resources and you often had to trade off memory for additional calculation. This is how you write tiny programs and of course any top playing program such as Komodo would not be a good candidate for a 4k program running on an embedded device with 1k of RAM but neither would any 64 bit program.

[Don]

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I suppose most if not all implementations of make/unmake copy at least those position attributes. It makes no sense to throw away the old hash key value and then having to recalculate it during the unmake.

Hi Ronald!

If I am not wrong you will just have to make the same xor once more to get your Zobrist hash the move before so I do not think it will be a big problem.

Kind Regards
Pio

That may not be so bad but it's hard to say. In either case no single aspect of making a move with either system is very expensive. I'm pretty sure that popping a value off the stack is a cheaper way to unmake a move, but that has to be measured against the additional cost of placing the key on a key stack when making the move.

That kind of thinking brought me to the point where I neatly side-stepped the issue completely. You can place all sorts of things on a stack or you can treat unmake as the complete inverse of make. Unfortunately, due to special moves and captures it's not quite as easy as reversing the from and to squares!

[syzygy]

When I have done mailbox I needed more than just to move a piece. I had to track which moves changed castling status, update a hash key and put it in a stack, keep an incremental score for the incremental part of the evaluation and other stuff like that. I don't see how you can get away with just a simple "put the piece and victim back."

I suppose most if not all implementations of make/unmake copy at least those position attributes. It makes no sense to throw away the old hash key value and then having to recalculate it during the unmake.

Hi Ronald!

If I am not wrong you will just have to make the same xor once more to get your Zobrist hash the move before so I do not think it will be a big problem.

Still a lot of work for nothing. It's not just a xor. You have to retrieve two or three Zobrist values from an array depending on whether it was a capture or not, then perform two or three xors.

You have the result available and you're going to need it again, so why throw it away? I would be surprised if any serious engine recalculated the hash key in an undo_move() routine.

In a make/unmake scheme you're going to have some state per position anyway, if only to allow you to undo the move. The sensible thing to do is to store the hashkey in that structure together with the 50-move counter, castling status and other stuff that can't be undone without storing additional information (to restore the 50-move counter or castling status you need more information than just the move that is to be unmade including the piece that was captured) or needs too much work to undo.

I think all programs are to some extent copy/make. Some programs are 100% copy/make and don't need an undo. Other programs are only partially copy/make and need an undo. I suppose practically all programs in the latter category do not copy the board array, but merely change the values of the from- and to- squares.