Natural TB

[mcostalba]

Ah, this seems so simple to implement. But the problem is that the normal search has many exit points and at all those points you would need to check against the TB score. That's a lot of ugly code.

Failing hard does this without ugly code.

Suppose that when TB probing, the result of the TB is stored on a stack variable ss->tbScore.

During search(), after trying one move:

Code: Select all

pos.do_move(move);
v = -search(pos, -beta, -alpha);
pos.undo_move(move);

You could simply check (ss+1)->tbScore and if, for instance it is a TB loss then you can safely return a win, without continuing searching, so although you didn't TB probe at the beginning of the search(), it does not take a lot, in case of a winning position, to early cut-off the search, thanks to the TB score stored in the stack of the inner nodes.

Does this scheme seems reasonable?

Well, this is what Natural TB does, but instead of the stack hack, it simply returns alpha after TB probing at child node that yields to a fail-high cut-off at the previous node and the previous node skips all the remaining search.

[syzygy]

This might explain why Marco is seeing some improvements in behaviour by using fail hard. It seems to be the logical choice is some scenarios.

I don't think we know which scenario exactly shows improvement and improvement in what sense...

Improvement if DTZ is not available and the position is a TB win would not be very surprising.

[mcostalba]

Of course current SF with DTZ would play such endings perfectly. I don't know what the times you report should mean.

The test was aimed at measuring overhead, not quality of best move.

It is a fixed depth search to 10 plies on 300 endgame positions. It does not check the best move found. In case the position is in TB, syzygy SF simply disables TB probing so it falls back on vanilla SF, this could explain why is not faster than Natural, that instead does not change its logic depending if root position is in TB or not.

What we can infer from the test is limited, just that the supposed overhead of Natural TB is not that huge anyhow. But only real games will tell us the real picture.

[syzygy]

You could simply check (ss+1)->tbScore and if, for instance it is a TB loss then you can safely return a win, without continuing searching, so although you didn't TB probe at the beginning of the search(), it does not take a lot, in case of a winning position, to early cut-off the search, thanks to the TB score stored in the stack of the inner nodes.

Does this scheme seems reasonable?

You would have to be lucky to play the winning move first.
If instead you probed immediately, you would have known the position is won and you can return immediately (if beta < TB win). This avoids having to probe (and search etc.) ony ply below (and one ply further below, etc.).

Hint: if probing the current position does not give a TB result, then probing the ply below will not give a TB result either. Unless you play a capture that brings you in the TBs.

If the current position can be resolved by a TB probe (which is the case if +/- TB win is outside (alpha, beta)), it is not reasonable to instead recursively search and probe.

Only if you want to know more than win/draw/loss, so only if beta > TBwin (or alpha < -TBwin) does it make sense to search on. Even then, it makes a lot of sense to probe first, because maybe you are looking for a win but the position is drawn or lost. (And I think that in this case one would like to "correct" the result returned to the parent in case the subtree search does not return a value bigger than TB win.)

Of course instead of TB win you could return VALUE_KNOWN_WIN. But not correcting for distance to root might result in the search not making progress. Maybe this danger is very small for SF, I don't know.

[Michel]

I don't think we know which scenario exactly shows improvement and improvement in what sense...

In my post I gave two specific scenarios where failing hard (instead of returning +- TBWIN) seems dictated by a-b search.

If my reasoning is correct then this should indeed improve behaviour....

In other situations you should fall soft. Otherwise you throw away valuable information.

Everything follows from thinking of (non draw) TB scores not as hard scores but as bounds. Then one can simply follow the principles of a-b search.

[syzygy]

I don't think we know which scenario exactly shows improvement and improvement in what sense...

In my post I gave two specific scenarios where failing hard (instead of returning +- TBWIN) is the logical choice from the point of view of a-b search.

By scenario I mean primarily: what kind of root position are we searching, and what criteria determine whether some behaviour is better than other behaviour?

If the root position is a TB win, then I'd say better is one of report a mate quicker or convert the TB win into a mate quicker. (And still more importantly: actually make sure you can always convert the win, but that is only possible using DTZ. DTZ filtering at the root is pretty easy and does not take time unless the laptop HDD has to spin up first.)

If the root position is a non-TB position and no forced TB win is in sight, then better is a finding a better move in less time.

If the root position is a non-TB position and a forced TB win is in sight, then better might be finding a mate or a more advantageous conversion into a TB win. (But first of all make sure the position gets converted.)

[syzygy]

Everything follows from thinking of (non draw) TB scores not as hard scores but as bounds. Then one can simply follow the principles of a-b search.

The principles of a-b search don't deal with the choice between taking the TB cutoff (treating the TB node as a terminal node) and not (yet) taking it.

[mcostalba]

You could simply check (ss+1)->tbScore and if, for instance it is a TB loss then you can safely return a win, without continuing searching, so although you didn't TB probe at the beginning of the search(), it does not take a lot, in case of a winning position, to early cut-off the search, thanks to the TB score stored in the stack of the inner nodes.

Does this scheme seems reasonable?

You would have to be lucky to play the winning move first.

If you are in a winning position you don't have to be lucky, any move will do.

[syzygy]

You could simply check (ss+1)->tbScore and if, for instance it is a TB loss then you can safely return a win, without continuing searching, so although you didn't TB probe at the beginning of the search(), it does not take a lot, in case of a winning position, to early cut-off the search, thanks to the TB score stored in the stack of the inner nodes.

Does this scheme seems reasonable?

You would have to be lucky to play the winning move first.

If you are in a winning position you don't have to be lucky, any move will do.

Think again.

[mcostalba]

You could simply check (ss+1)->tbScore and if, for instance it is a TB loss then you can safely return a win, without continuing searching, so although you didn't TB probe at the beginning of the search(), it does not take a lot, in case of a winning position, to early cut-off the search, thanks to the TB score stored in the stack of the inner nodes.

Does this scheme seems reasonable?

You would have to be lucky to play the winning move first.

If you are in a winning position you don't have to be lucky, any move will do.

Think again.

Not in general case, but in many cases yes, for instance in KRvK any move will do.

And also in other cases, engine is usually good in finding the best moves early on already by itself.