Copy-make vs Make/Unmake ?

[MahmoudUthman]

So far on all "most of" the threads I stumbled upon discussing this topic claim a "somewhat" clear advantage for making/unmaking or that it'll never be slower than copy make , but when I switched from a copy-make to make/unmake both perft and search functions became noticeably slower when tested on my PC a Core I7 5820k with 32GB of Memory , but when tested on my old laptop I5 2410 there was almost no difference , does this mean that recent hardware favor copy-make ?

my position representation =168 bytes :
16 bitboards ,
2x U64 Castle Rights
1x U64 HalfMoveClock
1x U64 key
1x int32 PSQ
1x U32 Enpassant

by the way I don't use a pure copy-make , instead of decrementing ply I copy the above position representation each to it's backup array[maxply] and in unmake I copy the content of the backup arrays back, for some reason this is faster for me than using a pointer to the current location in the backup array !

[ZirconiumX]

Ultimately, I think copy-make vs make-unmake is a matter of taste. Komodo used (still uses? Maybe it was changed in BeeKay) copy-make due to its elegance. Dorpsgek uses copy-make, but that would be because incrementally updating the attack tables would drive performance through the floor. But my bitboard engine uses make-unmake, so I really don't think it matters. You will probably spend much more time computing things like SEE and eval, so focus on those.

[Evert]

I think it's largely a matter of taste. Unless you're Stockfish, it's not going to be the limiting factor in playing strength anyway.

The board representation in Jazz uses 96 bytes (94+2 dummy bytes for alignment). Performing a move is memcpy/pointer increment/make-move. reversing a move is simply a pointer decrement.

[hgm]

In CrazyWa the board is 242 byte (22 x 11 mailbox). In addition I keep a semi-piece list that keeps for 2x32 piece types where to find a piece of that type. (This is in fact only important for tracking the Kings.) At most 4 bytes change in the board proper (on castling, two from-squares, two to-squares), and perhaps one counter (located in the off-board part) for pieces in hand. This is still pretty easy to UnMake().

Code: Select all

void
UnMake (StackFrame *f)
{
    board[f->rookSqr] = f->rook;      // restore either pawnCount or (after castling) Rook from-square
    board[f->toSqr]   = f->savePiece; // put back the regularly captured piece (for castling that captured by Rook)
    board[f->captSqr] = f->victim;    // differs from toSqr on e.p. (Pawn to-square) and castling, (King to-square) and should be cleared then
    board[f->fromSqr] = f->fromPiece; //          and the mover
    board[handSlot[f->victim]]++;
    promoGain[(f->toPiece & COLOR)+30] = f->bulk;
    location[f->fromPiece] = f->fromSqr;
}

MakeMove() identifies the relevant squares from the move, and stores the old info that was on them. On normal moves toSqr and captSqr are the same, and there is no need to remember savePiece. Only for e.p. captures and castlings, where they are different, the old contents of both squares is remembered. (Of course on castlings and e.p. captures the toSqr has to be empty, but I am a bit paranoic about invalid hash moves, and want to make sure they do no permanent damage to the board rather than verifying them. During UnMake() it makes practically no difference whether you store the remembered value there or a hard-coded zero. During MakeMove() it only matters during the making of e.p. captures and castlings, which are so rare that speed is no issue there.)

The restoring of the castling Rook is overhead, but put to good use for restoring Pawn-per-file counters, which I also hide in the invalid part of the board. Only for for castling these would not be restored, but castling only can occur in Crazyhouse, and there the 'update' of the Pawns-per-file counter always is a zero 'increment' anyway. Only in Shogi the Pawns are given a non-zero 'bulk' that would lead to an actual change in the Pawn-per-file counters when a Pawn is captured or promotes.

On a drop move the from-square is the location of the relevant piece counter, and the from-'piece' is the old counter value.

[lucasart]

I've done both, and from experience I can tell you that you can achieve top level performance with either copy-make, or make/unmake.

But copy-make is superior because of simplicity and maintainability:
- you don't need unmake: half as much complicated code is always welcome!
- you avoid a lot of bugs, and hours of debugging. this is because lots of bugs you have with make/unmake leaving things in a broken state simply cannot exist with copy-make.

The worst kind of bugs you can have, when debugging your movegen and benchmarking against perft numbers are path-dependant bugs. Those bugs can only exist with make/unmake. Imagine your perft(4) is wrong. You look at perft(3) after each move at root, and one of them is wrong. So you load the position after that move, and now the perft(3) is correct. Or maybe it's wrong, but shows a different number. What's the @#!% ? How's that possible ? Welcome to path-dependant bugs paradise. Have a nice day

So I would recommend copy-make, especially for beginners.

[lucasart]

Imagine your perft(4) is wrong. You look at perft(3) after each move at root, and one of them is wrong. So you load the position after that move, and now the perft(3) is correct. Or maybe it's wrong, but shows a different number.

This is only a simple example. Real life path-dependant bugs get even worse than that. The point is that your state is the result of all the moves that have been made/unmade in the tree before reaching a position. It is not a pure function of the position. And that is why make/unmake is an atrocity: a violation of every good programming principle out there.

[Rein Halbersma]

Imagine your perft(4) is wrong. You look at perft(3) after each move at root, and one of them is wrong. So you load the position after that move, and now the perft(3) is correct. Or maybe it's wrong, but shows a different number.

This is only a simple example. Real life path-dependant bugs get even worse than that. The point is that your state is the result of all the moves that have been made/unmade in the tree before reaching a position. It is not a pure function of the position. And that is why make/unmake is an atrocity: a violation of every good programming principle out there.

I agree that copy-make is much easier to reason about (and I use it in all my engines), but make-undo is a legitimate approach as well. It all depends on the ratio of state size vs the amount of bits changed per move. For checkers / chess the ratio is small, with total state size a few cache lines. But for Go, and people doing robotics simulations or molecular conformation optimization, the state size can be several kilobytes, with only a few bits changing per "move", so state space search in these problems has a different tradeof. Of course, the make-undo will make doing multithreading more difficult, but again that's an engineering tradeof, not an absolute truth.

[hgm]

Indeed, it all depends on the overhead you incur by copying all the unchanged data. I'd rather copy 4 bytes to a save location before changing them, to write them back on unmake, than copy the 238 unchanged bytes. In copy-make you would likely copy all 242 bytes, and then overwrite the four that change in the copy, because figuring out which bytes do not have to be copied is not worth the overhead. So we are talking 242 reads + 246 writes for copy-make vs 12 reads + 12 writes for make/unmake. (There are 4 extra reads during unmake for knowing where to copy the saved changes back.)

BTW, I pass the e.p. square and castling rights as parameters to Search(), which effectively is a form of copy-make. This is data that always potentially changes, and figuring out whether it changed is more effort than applying a null-change when it doesn't, and treat it as changed.

My MakeMove() code is now this:

Code: Select all

int
MakeMove (StackFrame *f, int move)
{
    int to, stm;
    f->fromSqr = move >> 8 & 255;
    to = move & 255;
    f->wholeMove = move;
    f->toSqr = f->captSqr = toDecode[to];                               // real to-square for to-encoded special moves
    f->fromPiece = board[f->fromSqr];                                   // occupant or (for drops) complemented holdings count
    if(f->checker != CK_NONE && NonEvade(f)) return 0;                  // abort if move did not evade existing check
    f->mutation = (f->fromPiece >> 7) | f->fromPiece;                   // occupant or (for drops) -1
    f->toPiece = f->mutation + dropType[f->fromSqr] | promoInc[to];     // (possibly promoted) occupant or (for drops) piece to drop
    f->victim = board[f->captSqr];					// for now this is the replacement victim
    f->newEval = f->pstEval; f->newKey  = f->hashKey;			// start building new key and eval
    f->epSqr = 255;
    f->rookSqr = sqr2file[f->toSqr] + (pawnCount - board);              // normally (i.e. when not castling) use for pawnCount
    f->rook = board[f->rookSqr];					// save and update Pawn occupancy
    board[f->rookSqr] = f->rook + pawnBulk[f->toPiece] - pawnBulk[f->mutation] - pawnBulk[f->victim]; // assumes all on same file!
    if(to >= specials) { // treat special moves for Chess
        if(sqr2file[to] > 11) {                                         // e.p. capture, shift capture square
            f->captSqr = toDecode[to-11];				// use to-codes from double pushes, which happen to be what we need
            f->victim  = board[f->captSqr];
            f->savePiece = board[f->toSqr];
            board[f->captSqr] = 0;					// e.p. is only case with toSqr != captSqr where we have to clear captSqr
        &#125; else if&#40;sqr2file&#91;to&#93; < 8&#41; &#123;					// double push
            int xpawn = f->toPiece ^ COLOR;				// enemy Pawn
            if&#40;board&#91;f->toSqr + 1&#93; == xpawn ||				// if land next to one
               board&#91;f->toSqr - 1&#93; == xpawn ) &#123;
        	f->epSqr = &#40;f->fromSqr + f->toSqr&#41; >> 1;		// set e.p. rights
            &#125;
            f->victim = 0;						// for key and pst update
        &#125; else &#123; // castling. at this point we are set up to 'promote' a King to Rook &#40;so the check tests sees the Rook, and UnMake restores location&#91;K&#93;)
            f->rookSqr = zoneTab&#91;to&#93;;					// Rook from-square
            f->rook = board&#91;f->rookSqr&#93;;                                // arrange Rook to be put back on UnMake &#40;pawnCount is never modified in chess&#41;
            board&#91;f->rookSqr&#93; = 0;					// and remove it
            f->newEval -= PST&#91;f->rook&#93;&#91;f->rookSqr&#93;;
            f->newKey  -= KEY&#40;f->rook, f->rookSqr&#41;;
            f->captSqr = dropType&#91;to&#93;;					// this tabulates to-square of the King
            f->savePiece = f->victim;					// now toSqr and captSqr are different, make sure the piece that was on toSqr goes back there in UnMake
            f->victim = board&#91;f->captSqr&#93;;				// should be 0, but who knows?
            f->toPiece = f->rook;					// make sure Rook &#40;or whatever was in corner&#41; will be placed on toSqr
            board&#91;f->captSqr&#93; = f->mutation;				// place the King
            f->newEval += PST&#91;f->mutation&#93;&#91;f->captSqr&#93; + 50;		// add 50 cP castling bonus
            f->newKey  += KEY&#40;f->mutation, f->captSqr&#41;;
            location&#91;f->mutation&#93; = f->captSqr;				// be sure King location stays known
        &#125;
    &#125;
    board&#91;f->fromSqr&#93; = f->fromPiece - f->mutation;                     // 0 or &#40;for drops&#41; decremented count
    board&#91;f->toSqr&#93;   = f->toPiece;
    board&#91;handSlot&#91;f->victim&#93;&#93;--; // put victim in holdings
    f->newEval += promoGain&#91;f->toPiece&#93; - promoGain&#91;f->mutation&#93;                                        + handVal&#91;f->victim&#93; +
		  PST&#91;f->toPiece&#93;&#91;f->toSqr&#93; - PST&#91;f->mutation&#93;&#91;f->fromSqr&#93; + PST&#91;f->victim&#93;&#91;f->captSqr&#93;;
    f->newKey  += KEY&#40;f->toPiece, f->toSqr&#41; - KEY&#40;f->mutation, f->fromSqr&#41; - KEY&#40;f->victim, f->captSqr&#41; + handKey&#91;f->victim&#93;;
    stm = f->toPiece & COLOR;
    f->bulk = promoGain&#91;stm+30&#93;; promoGain&#91;stm+30&#93; += handBulk&#91;f->victim&#93; - dropBulk&#91;f->fromSqr&#93;;
    location&#91;f->toPiece&#93; = f->toSqr;

    return 1;
&#125;

(A small complication here is that this is not just MakeMove, but also calls a test if moves in in-check positions are indeed evading the check. Something I postponed to the point where it was sure you would want to make the move.)