New version of HaChu released

[hgm]

Yet another version (0.13) at the same link. New features:

*) Null move (+160 Elo in 320 games)
*) Check extension (+75 Elo in 187 games)

Now I am running in a problem, however. I implemented LMR, which should start reducing the depth of late moves by 1 in nodes where the requested depth was 5 or higher. (So that it is searched at 4-ply, leaving 3 for the reply, which is then eaten by the null move plus its 2-ply reduction, to check if the move can do any damage in QS).

At the TC I am testing (40 moves/min), it usually does not reach more than 5 ply, however. So only the late moves in the root could be reduced, in the final iteration, if I am lucky. That shouldn't really cause much strength increase (although it could save some time). So it is kind of difficult to evaluate this feature...

[Henk]

The first problem I encountered with the hash table was that I did not know what to do when Hash gives back an upper bound and you search a position with an artificial lower bound greater than that upper bound from hash.

That is the good case, right? If the hashed result is an upper bound below the node's current alpha, you know for sure the real score must be below alpha, hence a fail low. So you cut off using the score if the depth was sufficient.

For me it's about whether these 'artificial' bounds are valid.

For instance in a null move check I use the upper bound to check if a null move is already good enough. So the 'artificial' lower bound is -upper bound where upper bound is upper bound from that "parent" position(=node) where null move is tested.

If null move check fails low with that -upper bound as a lower bound I doubt if I can store that value -upper bound as a valid upper bound for that child position in the hash table.

[Henk]

The first problem I encountered with the hash table was that I did not know what to do when Hash gives back an upper bound and you search a position with an artificial lower bound greater than that upper bound from hash.

That is the good case, right? If the hashed result is an upper bound below the node's current alpha, you know for sure the real score must be below alpha, hence a fail low. So you cut off using the score if the depth was sufficient.

For me it's about whether these 'artificial' bounds are valid.

For instance in a null move check I use the upper bound to check if a null move is already good enough. So the 'artificial' lower bound is -upper bound where upper bound is upper bound from that "parent" position(=node) where null move is tested.

If null move check fails low with that -upper bound as a lower bound I doubt if I can store that value -upper bound as a valid upper bound for that child position in the hash table.

Maybe it's only the mate pruning that caused the problem. This famous technical topic has already been discussed.

I did not use the -nReply correction. Maybe that's all.

[hgm]

If null move check fails low with that -upper bound as a lower bound I doubt if I can store that value -upper bound as a valid upper bound for that child position in the hash table.

Not sure what situation exactly you are describing. When the null-move search with window {beta-1, beta} fails low, the daughter node (which has window {-beta, 1-beta} must have failed high. That means its score must have been a lower bound, not an upper bound, and >= 1-beta (so that in the parent it shows up as <= beta-1).

So in the hash entry for the daughter you store that score >= 1-beta as a lower bound. That 1-beta was 'artificial'', and really should heve been -alpha > 1-beta if you would have searched the null move with open window, does not alter that. It just means that the lower bound you store might not be the highest lower bound that is possible, and that if you would have let the search work harder, it might have produced a sharper bound. This is exactly why you raise alpha to beta-1 in the null-move search: you don't want the search to work harder, that is just wasted time. You might be lucky, and the lower-bound that produced the cutoff in the daughter might be above -alpha anyway. Or it might not be possible to get a lower-bound above -alpha, because the true score is below it (but still above 1-beta), in which case nothing is lost anyway. If you later get a hish on this hash entry (which remains to be seen...), and the lower bound is not good enough to service the window of that node, you would redo the search with the new window.

[Henk]

If null move check fails low with that -upper bound as a lower bound I doubt if I can store that value -upper bound as a valid upper bound for that child position in the hash table.

Not sure what situation exactly you are describing..

I meant if null move check fails low in the child position. But that doesn't change much.

.. It just means that the lower bound you store might not be the highest lower bound that is possible ..

So it still could be that the program might store too many hash entries with unsharp bounds which might slow down the search.

Maybe I'll introduce hash table again in my program but then the mate check pruning puzzle should also be solved. I think this hash table complicates the search too much and I might have more bugs or use wrong bounds. I used alfa beta for [alfa, beta] instead of <alfa, beta> and it's not easy for me to get used to it. Also got windows 8 and used ASP.NET MVC instead of Windows Forms. So now I also got troubles in the user interface of my chess program.

[hgm]

So it still could be that the program might store too many hash entries with unsharp bounds which might slow down the search.

It should be obvious that storing anything could never slow down the search. The worst it could do is fail to speed it up. Doing the extra work in advance, just in case you might benefit from it later, is a losing proposition.

If you buy a new bicycle, and the salesman offers you an insurance that would replace the bicycle the first time it got damaged, for a fee equal to the price of the bicycle, would youtake that insurance?

This might also interest you: I am re-testing the very simple LMR implementation I made in HaChu again, but this time in combination with a chage in the time management to compensate for the effect that LMR decreased the average time per move (because the late moves in the root are searched much faster). Without that it started to distribute its time very unevenly, with 40 moves per session it would play the first 20 of each session in a quarter of the time, and take ther remaining 3/4 for the nex 20. The version with LMR is leading 73-49 now (60%, or +70 Elo).

It simply reduces all non-captures beyond the killers by 1 ply (And it does not even group promotions with the captures. Perhaps I should at least exempt promotions from LMR. But I guess in practice they would fail high anyway, so maybe that would not make a difference at all.)

[Henk]

So it still could be that the program might store too many hash entries with unsharp bounds which might slow down the search.

It should be obvious that storing anything could never slow down the search. The worst it could do is fail to speed it up. Doing the extra work in advance, just in case you might benefit from it later, is a losing proposition.

If you buy a new bicycle, and the salesman offers you an insurance that would replace the bicycle the first time it got damaged, for a fee equal to the price of the bicycle, would youtake that insurance?

This might also interest you: I am re-testing the very simple LMR implementation I made in HaChu again, but this time in combination with a chage in the time management to compensate for the effect that LMR decreased the average time per move (because the late moves in the root are searched much faster). Without that it started to distribute its time very unevenly, with 40 moves per session it would play the first 20 of each session in a quarter of the time, and take ther remaining 3/4 for the nex 20. The version with LMR is leading 73-49 now (60%, or +70 Elo).

It simply reduces all non-captures beyond the killers by 1 ply (And it does not even group promotions with the captures. Perhaps I should at least exempt promotions from LMR. But I guess in practice they would fail high anyway, so maybe that would not make a difference at all.)

I just found out that there was a bug with En Passant moves in my chess program. That might also have caused errors in my hash table. I repaired the bug by using the last move played. Before that I used a 64 bit integer.

At the last days of the week I always get the worst bugs.

[hgm]

For the time being this (i.e. HaChu 0.14) will be he last release of HaChu, and unless major problems crop up the version I will participate with at the ICGA Olympiad. As I now have to devote my attention to mini-Shogi (where I participate with Shokidoki).

HaChu 0.14 has LMR, but in my 40 moves/min testing that did not bring a clear strength improvement. (I expect it to make the scaling better, however, so that it would help at long TC.)

More interesting is that I added two engine options to act as rule modifiers (as the rules used in Japan seem to be somewhat different from those used in Europe):

*) Promotion can be limited to when the piece enters the promotion zone (in stead of on any move that touches it except the first after deferral).
*) Repetitions can be considered not strictly illegal, but scored as losses (or wins in case you were checked or reciprocating a turn pass).

[hgm]

I now prepared a package that bundles the new HaChu with an improved version of WinBoard Alien Edition. The improvement is that it now uses the square highlighting that the engine indicates when you pick up a piece not only to determine if the move you enter is legal, but also whether it should pop up a promotion dialog (if you move to a purple square), or if it should allow you to enter a second leg of the move (when you move to a cyan square). HaChu's highlighting is adapted to use these colors.

http://hgm.nubati.net/WinBoard-Chu.zip