undo move vs. Position Cloning

[BoldReceiver]

I started a hobby engine last month, my first programming project since college 12 years ago. Before I had written an "undo Move" function, I was lazy and simply cloned a position before making any alterations to it. So search looked like this:

for ( all moves) {
clone position to newPosition
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
…
discard newPosition}

instead of

for ( all moves) {
make move;
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
…
undo move}

Last night I added an array of 512 64bit Ints to track the game history (up to 256 full moves) to detect draws per the 3 move rule. Thinking that cloning and discarding millions of Position Objects during search was an increasingly bad idea now that the position Object was over 4k in size I wrote an “undo move” function, which seems to be the norm. To my surprise Running perft 6 moves deep revealed the the cloning method to be marginally quicker.
I am using Java and have no idea how memory is malloced or how the garbage collection works, but simply given that the piece array and position history stack (really the Zorbist key history) were being copied, it seems way off to have this be faster than undo move. Has anyone else tried anything like this? Anyone venture a guess as to what's going on? I'm a hardware guy and have never written code longer than a few hundred lines so I could be way off on this. If so, enlighten me. I have included stats and some code snippets below.


Perft from initial position with undo move function (time in ms):
Search time: 0
Nodes 20, Captues 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 14
Nodes 400, Captues 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 113
Nodes 8902, Captues 34, EnPassant 0, Castles 0, Promotions 0, Checks 12, Mates 0
Search time: 2099
Nodes 197281, Captues 1576, EnPassant 0, Castles 0, Promotions 0, Checks 469, Mates 0
Search time: 47758
Nodes 4865609, Captues 82719, EnPassant 258, Castles 0, Promotions 0, Checks 27351, Mates 0
Search time: 1193596
Nodes 119060324, Captues 2812008, EnPassant 5248, Castles 0, Promotions 0, Checks 809099, Mates 0

Perft with Cloning function.
Search time: 1
Nodes 20, Captues 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 14
Nodes 400, Captues 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 108
Nodes 8902, Captues 34, EnPassant 0, Castles 0, Promotions 0, Checks 12, Mates 0
Search time: 1920
Nodes 197281, Captues 1576, EnPassant 0, Castles 0, Promotions 0, Checks 469, Mates 0
Search time: 45269
Nodes 4865609, Captues 82719, EnPassant 258, Castles 0, Promotions 0, Checks 27351, Mates 0
Search time: 1134039
Nodes 119060324, Captues 2812008, EnPassant 5248, Castles 0, Promotions 0, Checks 809099, Mates 0

///Position Object

Code: Select all

class Position implements Cloneable{
	int board[]=new int [128]; //0x88 Board representation
	long moveHistoryStack[] = new long [512]; //Position Zorbist key History
	int moveHistoryPointer; 
	int whiteKingSq;
	int blackKingSq;
	int moveNumber;
	int hundredHalfMoveCounter; // This is for the 50 move rule
	int enPassant; //  If en passant capture is legal it's for this column. A column of 8 means no En Passant is possible
	long hashKey=0;
	int materialSum;
	boolean castleKingSideBlack; //castle king side still legal
	boolean castleQueenSideBlack; // dito queen side
	boolean castleKingSideWhite; //castle king side still legal
	boolean castleQueenSideWhite; // dito queen side
	boolean whitesMove; //White to move (else black)
	boolean whiteCheck; //In check flag
	boolean blackCheck; //In check flag
	boolean draw;       //Draw flag
	
    void undoMove(UnMove unMove){
		this.enPassant = unMove.enPassant;
		this.materialSum = unMove.materialSum;
		this.hundredHalfMoveCounter = unMove.hundredHalfMoveCounter;
		this.castleKingSideBlack = unMove.castleKingSideBlack;
		this.castleQueenSideBlack = unMove.castleQueenSideBlack;
		this.castleKingSideWhite = unMove.castleKingSideWhite;
		this.castleQueenSideWhite = unMove.castleQueenSideWhite;
		this.blackCheck = unMove.blackCheck;
		this.whiteCheck = unMove.whiteCheck;
		if (unMove.wasCastles){
			switch(unMove.to){ 
			case (2):{ //White castles Q
				this.board[0]=W_ROOK;
				this.board[4]=W_KING;
				this.board[2]=EMPTY;
				this.board[3]=EMPTY;
				this.whiteKingSq=4;
			}
			case (6):{ //White castles K
				this.board[7]=W_ROOK;
				this.board[4]=W_KING;
				this.board[5]=EMPTY;
				this.board[6]=EMPTY;
				this.whiteKingSq=4;
			}
			case (114):{ //Black castles Q
				this.board[112]=B_ROOK;
				this.board[116]=B_KING;
				this.board[114]=EMPTY;
				this.board[115]=EMPTY;
				this.blackKingSq=116;
			}
			case (118):{ //Black castles Q
				this.board[119]=B_ROOK;
				this.board[116]=B_KING;
				this.board[117]=EMPTY;
				this.board[118]=EMPTY;
				this.blackKingSq=116;
			}
			}
			undoMoveCleanUp();
			return;
		}
		if (unMove.wasEnPassant){
			this.board[unMove.to]=EMPTY;
			if (this.whitesMove){//side to move has not been undone, so this is blacks move
				this.board[unMove.from] = B_PAWN;
				this.board[unMove.to+16]=W_PAWN;
			}
			else{
				this.board[unMove.from] = W_PAWN;
				this.board[unMove.to-16]=B_PAWN;
			}
			undoMoveCleanUp();
			return;
		}
		this.board[unMove.from]=this.board[unMove.to];
		this.board[unMove.to]=unMove.piece;
		if (this.board[unMove.from]==W_KING) this.whiteKingSq=unMove.from;
		if (this.board[unMove.from]==B_KING) this.blackKingSq=unMove.from;
		if (unMove.wasPromotion) {
			if (this.whitesMove)//side to move has not been updated, so this is blacks move
				this.board[unMove.from]=B_PAWN;
			if (this.whitesMove) this.board[unMove.from]=W_PAWN;
		}
    	undoMoveCleanUp();
    	return;
    	
    }

    void undoMoveCleanUp(){
    	this.whitesMove=!this.whitesMove;
    	this.moveHistoryPointer--;
    	this.hashKey=this.moveHistoryStack[moveHistoryPointer];
    	this.moveNumber--;
    }

[mcostalba]

To my surprise Running perft 6 moves deep revealed the the cloning method to be marginally quicker.

Of course is faster and not only marginally.

The traditional way of doing this is copy in makemove the current state in a backup storage, then update the state then in undo move to copy back from the backup storage to the position state.

This last step is totally uneeded and I still don't understand why nobody uses the opposite way that makes undo move way faster.

When I have implemented this new scheme in Stockfish I was very surprised that nobody uses it.

In Stockfish do_move() and undo_move() work like this:

In do_move() the subset of the position state that is updated incrementally, for instance position key, is copied in the new position state and then the new state is updated as usual. The fundamental point is that the original state is not lost but is still kept in memory and there is a pointer that points to it.

In undo_move() we simply redirect the pointer to the old one.

While in do_move() we don't have any gain (but also no slowdown) in undo_move() we have a big speedup because we can remove the copy operations almost entirely and just change a pointer.

I am still wondering why nobody uses this scheme...

[BoldReceiver]

Thanks Marco. If all info is stored then yes a pointer switch is much better than unnecessarily copying back in all the info to a position. But I don't need to store it all, only the information that might be destroyed (castling rights, 50 move rule info etc.) or is easier to store than undo (material count, king in check etc.) . The board is not copied just modified slightly for undo and the zorbist key history is not modified, just the pointer into the stack is decremented. So the question becomes why is

do/undo method{
do: store about 32 bytes.
undo:recall about 32 bytes,
execute about 20 lines of code.}

slower than

{
do: copy 4.5K of info
undo: switch pointers
}

It made sense back when my position structure was only about 600 bytes, but now it's a lot bigger due to the zorbist history. At some point it becomes cheaper to store just some info and undo it. Have you tried an Undo move (not copy all) in Stockfish? Again, I am not a software engineer, and this is now not all that chess related, but I REALLY do appriciate the answers.

Maybe it's best to have just one position history (I have a single thread) always passed by reference and use the clone method for the rest of the board info. I'll see if it's quicker to execute the paltry undo code on the board or simply store and retrieve it.

[mcostalba]

Maybe it's best to have just one position history (I have a single thread) always passed by reference and use the clone method for the rest of the board info.

Yes, that's the way it is implemented in Stockfish. We only copy a very small subset of the position: the data that is updated incrementally and this data is stored in a State record, separated from the position itself and to which the positions keeps a pointer.

Probably my description it is not very clear, but if you have a little bit of time you can download SF sources and check it yourself in position.cpp, functions are do_move() and undo_move().

[BoldReceiver]

Thanks Marco.

Everyone else:
Putting aside the foolish way I was storing the key history with each position (it's game data too, not position data and didn't belong there in the first place), the question remains: Do most engines clone positions before making a child, or store information to remake a position from one of it's children? Tests suggest it's a wash for me given my current "position object" now that repetition detection has been relegated elsewhere.
Terry O'
Undo:
Search time: 1
Nodes 20, Captures 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 12
Nodes 400, Captures 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 49
Nodes 8902, Captures 34, EnPassant 0, Castles 0, Promotions 0, Checks 12, Mates 0
Search time: 735
Nodes 197281, Captures 1576, EnPassant 0, Castles 0, Promotions 0, Checks 469, Mates 0
Search time: 16825
Nodes 4865609, Captures 82719, EnPassant 258, Castles 0, Promotions 0, Checks 27351, Mates 0

Clone:
Search time: 0
Nodes 20, Captures 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 12
Nodes 400, Captures 0, EnPassant 0, Castles 0, Promotions 0, Checks 0, Mates 0
Search time: 47
Nodes 8902, Captures 34, EnPassant 0, Castles 0, Promotions 0, Checks 12, Mates 0
Search time: 746
Nodes 197281, Captures 1576, EnPassant 0, Castles 0, Promotions 0, Checks 469, Mates 0
Search time: 17088
Nodes 4865609, Captures 82719, EnPassant 258, Castles 0, Promotions 0, Checks 27351, Mates 0

[Gian-Carlo Pascutto]

This thread got a bit confused because the both of you are talking about different things.

The fastest is to undo the changes to large data structures, and clone the small ones. You need to think about the trade off in effort between undoing a change and copying it back.

Undoing moves should be faster than copying 4.5K of memory. If it's not, something is wrong.

What Marco describes is a small optimization for the case where you copy a datastructure (to have only 1 copy instead of 2).

[Evert]

I have an array of positions and a pointer into that array for the correct position. When I make a move, the current position gets copied into the next slot in the table and the "current position" pointer gets incremented.
When reversing a move, the pointer simply gets decreased.

I thought about what I wanted to do before implementing this, ultimately I decided that I didn't want to do all the extra book keeping and write what comes down to a second "make move" function. The price is that I have to copy around extra memory for the current board. The advantage is that both my "make move" and "undo move" functions are a bit simpler (and the "undo move" function is essentially free since all it does is decrement a pointer).

I don't think this makes much of a difference in terms of speed (my initial fear was that this might be slower), but it makes the code a lot simpler, which in the end was my main motivation for doing it this way.

The reason "undo move" type functions are more common is that they are closer to how we as humans might think about or analyse chess positions.

[Gian-Carlo Pascutto]

The reason "undo move" type functions are more common is that they are closer to how we as humans might think about or analyse chess positions.

Not really. If your position has enough state then the copying gets too expensive quickly. I don't think anyone starts out thinking he wants to unmove instead of just copying

[gingell]

Here's what I do in Chesley:

Code: Select all

child_position = parent_position;  // Copy the parent
child_position.apply_move (move);  // Apply a move to the child.
search (child_position)            // Search the child

And then child_position is thrown away.

In Chesley a position is 168 bytes. The implementation is C++ and I've verified the compiler generates a memcpy as you'd expect. Experimenting with dummy fields to pad that out to 256 or 512 bytes makes very little difference in number of nodes per second I see.

The fact that virtually every other program I've looked at does move/undo worries me a little, since it's rather more likely I'm missing something everyone else sees than the other way round! But it's still hard for me to see a solution cheaper than doing that copy.

[mjlef]

I just clone now, and the size of my board structure is about 500 bytes. Note you do no need a move stack for each board structure. You need a move stack for each processor, and it needs not be copied at all unless you are spiltting the search (just allocated at program startup).

Before I decided to clone I did some timing tests and found way under 1% of processor time was being spent copying the board over, so I decided an undo would be a waste of time.