Alpha-beta fail soft cut-off issue

[hgm]

I was thinking of a sorting algorithm that sorts the best x moves, and leaves all the other scores as soon as there is a score gap unsorted, and the deeper we go in the variations, the fewer moves we want to maintain. (Thinking like a human, not like an algorithm)

That won't work. In almost all positions you will have some 20 moves with a score that is the same or just a few cP below that of the best, even if the best is the only move that avoids the loss of a piece. Because alpha-beta pruning will make the search very lazy, not willing to do any more work than necessary. So it stops searching for better refutations to your non-best moves as soon as it has found one that pushes the score only marginally below that of your best one.

If you want to detect a score gap (i.e. an 'easy move' situation) you would have to do the searches of the later moves with artificially lowerd alpha. i.e., if your best move scores, say, 30cP, you normally raise alpha to 30 cP, but now you should set it to (say) -70 cP instead). Then the score of really poor moves will all be pushed to below -70cP (creating the score gap you want), and moves for which this isn't possible you will get an exact score between -70 and +30.

I do this in Shokidoki on early iterations. As soon as I finish an iteration that has a second move in the gap, I conclude it is not an easy move, and do the remaining iterations without gap. But while the gap lasts I keep it in the next iteration. And while the gap lastst, it already moves when 10% of the normal thinking time has elapsed.

[ydebilloez]

If you want to detect a score gap (i.e. an 'easy move' situation) you would have to do the searches of the later moves with artificially lowerd alpha. i.e., if your best move scores, say, 30cP, you normally raise alpha to 30 cP, but now you should set it to (say) -70 cP instead). Then the score of really poor moves will all be pushed to below -70cP (creating the score gap you want), and moves for which this isn't possible you will get an exact score between -70 and +30.

I do this in Shokidoki on early iterations. As soon as I finish an iteration that has a second move in the gap, I conclude it is not an easy move, and do the remaining iterations without gap. But while the gap lasts I keep it in the next iteration. And while the gap lastst, it already moves when 10% of the normal thinking time has elapsed.

This is a very good idea. Will try to play with it. Thanks for the suggestion.

[ydebilloez]

Meanwhile, I created a version of my program that has the selection in between 3 different algorithms:

1) AB without Beta cut-off
2) AB with Fail-Soft
3) AB with Fail-Hard

The rest of the code is the same, same evaluation, same everything...

When playing tournaments on different time-controls (bullet, blitz, 5s/move) to allow search tree optimisations to act differently, only the Fail-Soft variation is performing well. In my opinion, the Fail hard (returning beta or beta-1) in case of a cut-off is not helping a lot.

The reason I see for this is: I do iterative deepening. At the end of each depth, the moves come out sorted with the best move first.
In case of almost returning beta on cut-off, it happens that a very bad move is ranked second in the movelist instead at the end.
Ranking best moves first seems to have a positive impact on engine performance.

Please note that I do not yet use hashtables to sort moves in deeper levels according to the ability to refute a move.

The engine does the following:
Initial ordering of moves.
Search depth 1 - with QS extension to 8+ - sorted moves as outcome
Search depth n+1 - with QS extension - sorted moves as outcome
Search depth n+x .... until we got a time-based abort
return first move on the list

* on search depth -1 and below, moves are only pre-sorted according to static rules