Jan 30, 2007

[Other] A good night's sleep is all it takes

Yesterday I was just about to start writing the transposition table guide, after having sorted out a few more bugs and it all seemed to work nicely. So I started a tournament between v0.12b and Mediocre with transposition tables in the background, and started typing.

And in the first game, just after I had typed the first paragraph in my guide, ANOTHER bug appeared out of nowhere.

It was in the following position:

Mediocre v0.12b is white, to move, and Mediocre with transposition tables black, and after:
a3   Nxe4
Bxe4 Nf6
Bd3 Nd7
axb4 f5
Mediocre with transposition tables crashed. And also Nd7 looks like weird move since it just hangs the pawn on b4.

So back to bug hunting again. :(

After a while I realized the crash originated from my method of extracting the principal variation from the transposition tables.

After the move 'Bd3' Mediocre with transposition tables calculated with Nd7 followed by Bxe4 which of course is not possible in the position (there is no black piece on e4 after the moves).

Calculating with transposition tables turned off did not have the problem, so the Bxe4 had to come from the transposition table. Then the pv extraction method played it on the board (to find the next move in the line) and when unmaking the move a black knight appeared on e4 out of nowhere (since the unmake-method puts back whatever piece that was captured, and Bxe4 apparently had a black knight in its capture field).

And then after a couple of moves v0.12b plays Bxf5, so Mediocre with transposition tables crashes since in its internal board there is a knight on e4, making Bxf5 illegal.

Now I tried a bunch of different ways to get around the problem, thinking it was just an update problem of some sort that did not interfere with the actual calculation. But nothing worked.

I then woke up this morning and before I turned on the computer I realized what the problem was, and exactly where I had to make a change in the code. :)

The problem is in the Zobrist keys (even though I did extended testing on those).

The following two positions should not return the same Zobrist key:

And they did not if inserted separately with fen-strings. But if the first position was inserted with a fen-string and then the sequence:
Bxe4 Nf6
Bd3 Nd7
was played (which ends up in the second position) the Zobrist keys magically matched. Which they should not!

The problem is, in my make and unmake move methods I only update the zobrist with the piece moving if it is a capture. Just like I update the board array.

A piece on d3 capturing a piece on e4 is in the board array done with setting 'd3' to empty and 'e4' to the piece moving. Setting 'e4' to the piece moving automatically replaces whatever piece was there before and we do not have to worry about it.

But a Zobrist key does not work that way, you have to 'remove' the captured piece as well by updating the Zobrist key with its position just like you would remove the moving piece from 'd3'.

Hopefully there are no more bugs now, and I can go on to writing my guide and releasing Mediocre v0.2b.

Hopefully... :)


Genorb said...

Haaa, we will have soon a new version of Mediocre, very nice!! I am looking forward to test it!! Do you think that you will release it today?

Jonatan Pettersson said...

If no other bug pops up it will be released later today.

I want to clean up the comments a bit and such, but I think I release v0.2b first, and then make a few adjustments and release v0.21b in a day or two.

Genorb said...

Ok thanks!