[Plan] Fixing the unmake move

After timing the move generation method, I concluded the takeback in my planned setup (as posted below) was by far too time consuming.

For every created move the method had to generate a FEN-string to put into the Move-object to remember its takeback-position. While one FEN-string generation takes a fraction of a millisecond to calculate you have to count with the engine generating millions of moves.

Below is an overview of the number of times we need to call the generate move method at each ply (a ply is one move made by one side). The average position has about 30 available moves for each side.

Ply  Possible lines     Total generation calls
1                30             1
2    30*30  =   900            31
3    900*30 = 27000         27931
4    .       810000        837931
5    .     24300000      25137931
6    .    729000000     754137931
     etc.

As you can see the numbers grow extremely fast. At ply 6 one extra millisecond in the move generation algorithm would result in 8.7 days(!) extra calculation time.

Now even in the worst possible scenarios we would not get near 8.7 days calculation time. Firstly one millisecond is a very high number and you would have to really mess it up to get it (one full move generation currently takes about 0.04 milliseconds on my hardware). Secondly our search algorithm will narrow the number of positions down to a fraction.

But you get the idea what one ineffective part of the chain can cause if we are not careful. At higher plies I would estimite my move generation with FEN-strings could cause minutes of extra calculation time.

I had hoped the easy unmake-method would help evening out the extra time, but after some thinking I realized it was slower than alternative methods as well. Since it requires a call to the inputFEN()-method which is quite slow.

So instead of a FEN-string in the Move-object we need to hold a few parameters that needs to be remembered about the previous position, these are:

• Captured piece - To know what piece to put back on the board. The boardArray holds no information about passed pieces.


• En passant square - Since the en passant square in the previous position arose one move further back, there is no way to calculate what it might have been, unless the move we are taking back is an en passant move.


• White/black castling rights - Even though we could calculate what changes the move caused to castling rights, we know nothing about passed castling rights. Just because the move we take back puts the white king back on its original square, it does not mean we could give white full castling rights again since it might have changed earlier in the game.


• Half-moves (for 50 moves rule) - In most cases it would be possible to calculate this while unmaking the move. But if the half-moves count was 0 before the takeback, we would have no idea what the count might have been before.

Captured piece is already implemented in the Move-class so we do not need to worry about that.

So we need to create a way to remember the other three parameters.

Total full moves can be calculated at the time we unmake the move.