copy/make vs make/unmake

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
bob
Posts: 20697
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

copy/make vs make/unmake

Post by bob » Tue Jan 07, 2014 5:32 am

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
Posts: 2054
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: copy/make vs make/unmake

Post by mar » Tue Jan 07, 2014 6:13 am

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.

User avatar
hgm
Posts: 23950
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: copy/make vs make/unmake

Post by hgm » Tue Jan 07, 2014 8:37 am

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
Posts: 292
Joined: Tue Jul 07, 2009 2:56 am

Re: copy/make vs make/unmake

Post by Aaron Becker » Tue Jan 07, 2014 9:13 am

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).

User avatar
Evert
Posts: 2924
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: copy/make vs make/unmake

Post by Evert » Tue Jan 07, 2014 12:09 pm

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.

User avatar
lucasart
Posts: 3074
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: copy/make vs make/unmake

Post by lucasart » Tue Jan 07, 2014 12:51 pm

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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: copy/make vs make/unmake

Post by tpetzke » Tue Jan 07, 2014 1:14 pm

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.
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

Daniel Shawul
Posts: 3818
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: copy/make vs make/unmake

Post by Daniel Shawul » Tue Jan 07, 2014 1:40 pm

lucasart wrote: 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
Posts: 2054
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: copy/make vs make/unmake

Post by mar » Tue Jan 07, 2014 3:00 pm

lucasart wrote: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.

Post Reply