[Guide] Another unmake move scheme

I am currently hunting bugs in the new version of Mediocre. It is actually quite fun since while going through the old makeMove/unmakeMove and move generations methods I notice tons of things to optimize.

To not leave the blog idle like I did when struggling with the transposition tables I thought I would explain one of the new features I implemented, namely the new handling of unmaking moves.

Why a new unmake

To unmake a move we need a bunch of information. Things like what piece was moving from where to where, and what piece it captured (if any) we already have in the new move integer (explained earlier).

Previously I also stored information about the previous position's en passant square, castling rights and number of moves without pawn push or capture (for fifty move rule) in the Move-object itself.

But with my new move representation I could not fit the nescessary information about passed positions in the move itself (as mentioned earlier) so I had to come up with something else.

I got the following idea from Tom Kerrigan's TSCP.

The new scheme

Since we can not store the nescessary information in the move anymore we need to store it somewhere else.

The logical place is in the Board-object, but since we use one Board-object throughout the whole search, how should we store information about passed positions so we can keep track of what to 'remake' for a certain move?

If you think about it is not so easy. We could have variables like 'previousEnpassant', 'previousWhitecastling' and so on, but this will only keep track of the position one move back.

So if we make 10 moves, and then start unmaking them one by one, the 'previous'-variables will be reused several times before we come back to the original position and we would have no way of retrieving the original variables.

The solution is keeping an array of passed position variables.

At creation time the Board-object's 'history'-array will be empty.

If we make one move we add the values we need stored (en passant, castling and half-moves) to the history-array at index '0' and keep track of where we currently are (e.g. increment a 'historyIndex' integer with 1).

When we unmake the move we decrement the historyIndex with 1 and look at that index (in this case '0') and we find the values we wanted.

The benifit of this solution is we can make 10 moves in a row, which will result in 10 indexes being filled in the array, and every time we unmake a move we will find the right values in the array.

This also works if we make 10 moves, unmake one and make another. As long as we are only unmaking one move we will be alternating between index 8 and 9 here, which is of course what we want (we want the earlier values intact until we get to unmaking them).

How to store the information

I used the same scheme for storing information in the history-array as I did with the move integer.

That is use an integer and update the right bits in it with the particular information. This way we only need one array (and not one for each type of information) and we do not have to create some sort of history-object.

The code is very simple and looks like this:

In the Board-class:

public int[] history;
public int historyIndex;

In the makeMove()-method:

history[historyIndex] = 0;
if(enPassant != -1)
{
  history[historyIndex] =
  enPassant;
}  
  
history[historyIndex] = history[historyIndex] |
    (white_castle << 7)
  | (black_castle << 9)
  | (movesFifty << 16);

historyIndex++;

And in the unmakeMove()-method:

historyIndex--;

if(((history[historyIndex]) & 127) == 0)
{
  enPassant = -1;
}
else
{
  enPassant = ((history[historyIndex]) & 127);
}
white_castle = ((history[historyIndex] >> 7) & 3);
black_castle = ((history[historyIndex] >> 9) & 3);
movesFifty = ((history[historyIndex] >> 16) & 127);

Notice how my constant for 'no' enPassant (-1) is giving me trouble again. We can not store -1 in the integer since it would result in a weird value. I really have to do something about this soon.

But all in all it is very easy and works like a charm.

I also added a separate array for the zobrist keys that works the same way (but with 'long' type to fit the keys). This is not mandatory since we can reset the zobrist key 'manually' while unmaking the move. But it saves some time and makes the code in unmakeMove() clearer (thanks Patrice for pointing this out).

Well that was a short idea of how to make unmaking a bit easier. Now it is back to bug hunting for me. Wish me good luck. :)

Edit:
While writing this guide I noticed one of the bugs I was hunting. When making a move we need to set the history value at the current index to '0' before attempting to update it. If we do not we might be doing bit operations to an existing key which will result in weird results.