How costly is taking moves back ?

[hgm]

Well, for simple variables copy/make is the obvious method, and most of the time not even recognzable as such, as there isn't really any copy. Some of my engines pass the incremental eval as a parameter to search:

Code: Select all

 score = -Search(-beta, -alpha, -incrementalEval - materialGain, depth-1);

In a sense all these parameters are modified copies. And even if they live in global variables, an expression like hash ^= zobrist; does not cause machine code that is more complicated than hash = savedHash ^zobrist; It just stores the result in a different place.

When I think of copy/make I usually think of larger data-structures, of which you only want to change a part (so that there actually is something left to copy). Like boards, piece lists or attack maps. The larger they are, the more you usually benefit from make/unmake. Even on 8x8 boards the ratio of changed vs constant part is already quite unfavorable.

The decision copy/make vs make/unmake must be considered for every data structure separately. There is no reason at all why doing make/unmake on board and piece list should force you to do the same on the hash key or search depth.

[Don]

Well, for simple variables copy/make is the obvious method, and most of the time not even recognzable as such, as there isn't really any copy. Some of my engines pass the incremental eval as a parameter to search:

Code: Select all

 score = -Search(-beta, -alpha, -incrementalEval - materialGain, depth-1);

In a sense all these parameters are modified copies. And even if they live in global variables, an expression like hash ^= zobrist; does not cause machine code that is more complicated than hash = savedHash ^zobrist; It just stores the result in a different place.

When I think of copy/make I usually think of larger data-structures, of which you only want to change a part (so that there actually is something left to copy). Like boards, piece lists or attack maps. The larger they are, the more you usually benefit from make/unmake. Even on 8x8 boards the ratio of changed vs constant part is already quite unfavorable.

The decision copy/make vs make/unmake must be considered for every data structure separately. There is no reason at all why doing make/unmake on board and piece list should force you to do the same on the hash key or search depth.

Yes, it can almost become a matter of semantics what you consider part of the board state. In fact I have some things in the state that really are part of the search state but I need to reference. A big part of the reason I use copy/make is that I like the KISS principle of code simplicity and I cannot detect a cost.

I do not have a single thing against make/unmake and it may in fact be slightly more efficient if it could be measured. Maybe in a lean program it is measurable, but in a heavy program with a fat evaluation like Komodo I have been unable to measure it.

With MP you have to do the equivalent of copying the entire state and that becomes yet another "one-off" special case thing you must do. None of this is really a big deal though.

[Rein Halbersma]

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.

In draughts copy-make is even cheaper than in chess since you have only 2 types of pieces (men and kings). And I know of at least one very strong draughts program that doesn't even have a make_move() function: it simply generates the successor board state in its move generator, and uses a non-Zobrist / non-incremental approach to hashing. It saves a ton of logic for apparently very little speed loss.