Jan 7, 2007

[Other] Fun with null-moves

I have implemented null-moves in Mediocre. I am not exactly sure if it is bug free, or if it is optimized. What I do know is Mediocre is searching about 1-2 plies deeper in any given poisition using the same time (sometimes faster) without any noticeable decrease in tactical strength (which can be the result of cutting off lines too early).

That is just an awesome improvement! :)

As mentioned earlier null-moves is an 'unsound' pruning of the search tree, atleast in the form I am using it. It is 'unsound' because the engine only estimates some lines and decides if we should search them or not. By doing this we can sometimes miss important lines since they appear to be bad at first. But judging from the results it does not seem very unsound. :)

Here is a match between Mediocre v0.1b and Mediocre Dev (development version with null-moves). The null-moves did pretty darn well.
   Engine         Score   Results
1: Mediocre Dev 15,0/20 =011111==10110111=11
2: Mediocre v0.1b 5,0/20 =100000==01001000=00
The times used was; if the search takes more than 2 seconds, finish the depth currently on and return the result. Mediocre v0.1b could sometimes do a 4 ply search in 1.8 seconds and then take 15-20 more seconds for the 5th ply. This never occurred in Mediocre Dev, usually the last ply took about 3-4 seconds, at most 7-8.

So even though Mediocre Dev searched deeper it ended up using a lot less time total.

Keep in mind both versions are using exactly the same simple evaluation code, the only difference is the null-moves. As you can see an extra ply here and there works miracles.

Also since so many lines are cutoff I am hoping the extended evaluation I intend to write will not slow down the engine as much as it did before.

In my next post I will explain the theory of null-moves, and after some more testing I will present the new code.

No comments: