copy/make vs make/unmake

[bob]

This discussion comes up from time to time. As most know, I've done both over the years, but fairly early on, I moved from copy/make (which is certainly simpler) to make/unmake, for the speed advantage...

This weekend I went back and again converted Crafty to copy/make, to see if the newer PCs with much larger cache would make it worthwhile. After a few hours of testing to get a version that matched the make/unmake version exactly in node tests, I ran speed comparisons.

First point of notice, copy/make STILL slows me down by almost 10%, which is more than measurable in cluster testing. Second point, for comparison, the "copy/make" data that had to be copied was something like 212 bytes total. Note that this was not a half-assed conversion, but that it was not THAT hard to do having had past experience with going from copy/make to make/unmake already.

My ultimate take from this is that copy/make is still not as efficient as make/unmake, IF you do a really optimized make/unmake implementation. There's something to be said for the inherent simplicity of eliminating the Unmake() code, but the speed is, IMHO, certainly worth the effort. Needless to say, the copy/make version was dropped in the toilet.

[mar]

Interesting, this is what I do:

I have something I call undo buffer, which is a fraction of full board representation. In doMove I store what's needed and set flags in undo buffer.
Undo is done by unrolled implementation that simply takes flags and copies what's needed.

This is most likely slower than make/unmake but I'm lazy - so let's say it's just another possibility without wasting full board size on undo information
I will probably switch to make/unmake at some point in the future - but it's obvious that you always have to save 50 rule counter and castling rights anyway.
EDIT: and of course one has to remember piece that has been captured - I don't have this information stored in my move type.

[hgm]

When I have to deal with a very complex UnMake(), e.g. in engines that keep an incrementally updated attack map, I found it often very competitive to store everything that was changed as a (location, oldData) pair on an 'undo stack', and during UnMake() simply run through the stack to put everything back. For 'location' I preferably use offsets / array indices rather than pointers, to save space.

[Aaron Becker]

Weird coincidence, I've been slowly revamping my engine and ran a similar do/undo vs copy experiment last week. My result was similar--about a 5% advantage to explicit undo (with a somewhat smaller board state to copy).

[Evert]

Guess it depends on the program.

One of the previous times the discussion came up I converted Jazz from copy/make to make/unmake and there was hardly any difference in speed or strength. I forgot the details but I think the make/unmake was actually slightly slower.

There are always some things that need to be stored because you can't reconstruct it using unmake though and it's possible that the way I did this was a bit clumsy. Jazz' board struct is only 96 bytes though, making it larger does hurt and slow things down.

[lucasart]

I use a hybrid approach in DiscoCheck:
* some things take much space but are easy to recalculate on undo(). these can be recalculated, in the hope that the lesser cache pressure will make up for it.
* some things don't take much space but are costly to recalc: those belong on an undo stack.

I started with a plain and simply make/unmake, where I was recalculating everything from scratch. Then I introduced the undo stack as an optimization, and started profiling and fine tuning until my raw perft reached ridiculously speeds... Eventually I realized that none of this matters in a fully fledged engine.

Actually, the first thing that comes up on my profiling is the search(). And by a decent margin. It is not the eval, and certainly not the make/unmake stuff.

I don't think we can answer the question of make/unmake vs make/copy in general. Every engine is different.

[tpetzke]

Code: Select all

Actually, the first thing that comes up on my profiling is the search(). And by a decent margin. It is not the eval, and certainly not the make/unmake stuff. 

This surprise me a bit. What is search doing beyond few comparisons and then calling itself ?

Last time I profiled iCE the single most expensive function was calculateMobility<EColor> which is only a subfunction of eval().

But I agee to see makeMove and unMakeMove I must scroll down a bit.

[Daniel Shawul]

I don't think we can answer the question of make/unmake vs make/copy in general. Every engine is different.

Exactly, "Piece-list engines" like mine would prefere make/unmake or a combo by a huge margin. However I used copy/make for an engine I wrote for the GPU using bitboards.

This is yet another optimization that an eninge author should figure by himself.

[mar]

Actually, the first thing that comes up on my profiling is the search(). And by a decent margin. It is not the eval, and certainly not the make/unmake stuff.

I get the same impression, last time I profiled eval was only 25% of total in my case, vast majority spent in search.