Natural TB

[Joerg Oster]

First they seriously deteriorate the 5-men play at the root: on randomly occurring in games 5-men wins Natural fails to convert about 5% of them. On 5-men draws, it loses about 0.4% of them. On MES1258 varied endgame testsuite I got a SPRT stop for (-4,1):

BTW did you know that current syzygy when root is in TB completely disables the probing in inner nodes?

So what you have tested is vanilla SF (with DTZ filtering at root) vs natural.

I have done some important improvments to Natural TB, so interested people please pull again from github the updated version.

Thanks.

Done. Test match will start soon.

[syzygy]

First they seriously deteriorate the 5-men play at the root: on randomly occurring in games 5-men wins Natural fails to convert about 5% of them. On 5-men draws, it loses about 0.4% of them. On MES1258 varied endgame testsuite I got a SPRT stop for (-4,1):

BTW did you know that current syzygy when root is in TB completely disables the probing in inner nodes?

So what you have tested is vanilla SF (with DTZ filtering at root) vs natural.

I have done some important improvments to Natural TB, so interested people please pull again from github the updated version.

Thanks.

Done. Test match will start soon.

So...

Marco first decided that probing should be postponed to AFTER searching the subtree. This is done recursively, so the net effect is an enormous explosion of probes. Indeed, SF now gets about 1/3rd the nps on my machine in endgame positions.

To counter the now massive probing overhead, Marco has somewhat randomly decided that TBs are only probed if the root color is to move and has added a TB cache.

There is obviously (2+2=4, Pythagoras' theorem, etc. - no testing needed here) no way this could ever benefit playing strength.

[syzygy]

Practically we do not need to probe if we are certain about the result and probing some KQRR vs KN when you are sure that the stronger side wins is a waste of time and it is better to return high score without probing.

As I said: if you don't think the cost of the probe outweighs its benefits, then don't probe and don't probe anywhere in the subtree.

Suppose that you are uncertain about the result without probing in some interior node.

You have 3 options:
1)To probe.
2)To search and maybe you get in the search position when you are certain about the result so you do not need to probe.
3)To search without probing even if you are uncertain about the result.

Well, I can imagine only a single reasonable strategy for delaying a probe:
- if there is reason to think probing of a TB node (the node immediately after a capture into the TBs) might not be necessary, search its subtree (and do not probe there);
- on the basis of information obtained during that subtree search, you could perhaps decide there is now reason to probe the TB node anyway.

In all cases, a single probe within the subtree in principle has the same cost as the probe in the TB node but the information it returns is less useful. So if for whatever reason there would be a need to probe within the subtree, then the engine should NOT do that but instead probe the TB node.

(Again, depending on hardware configuration it may make sense to probe 6-piece positions less aggressively than 5-piece positions.)

Basically, Marco is experimenting with delaying the TT probe in a node until after the search of the node's subtree, reasoning that it might not become necessary to probe the TT in that node.

[mcostalba]

Marco has somewhat randomly decided that TBs are only probed if the root color is to move and has added a TB cache.

Thanks for reading my code!

I have also extended probing to PV nodes, this gave an unexpected big jump in speed (more than the color trick).

Now a fixed search on 300 endgame position it takes 3760ms vs 5820ms of vanilla SF (measured on second run, when WDL are already mapped in memory, I think this scenario more resembles real game conditions where the same WDL is used many times).

Thanks Joerg for testing it


P.S: I don't have a SSD, this is all from hard-disk

P.P.S: In case you are curious on the color trick, I have somewhat randomly decided that once you probe that position is win, there is no need for the opponent color to redo the same probe at the next move: it will be always lost whatever move he does. Instead you have to re-probe at grand child because perhaps your second follow up move is a bad one (chose a draw continuation, hang a piece, etc..)

[mcostalba]

Now a fixed search on 300 endgame position it takes 3760ms vs 5820ms of vanilla SF

Sorry I meant SF withouth TB, my mistake.

the correct table is the following:

Code: Select all

SF no TB:  5820ms
SF with TB: 4774 ms (warm cache run)
Natural TB: 3760ms

[syzygy]

P.P.S: In case you are curious on the color trick, I have somewhat randomly decided that once you probe that position is win, there is no need for the opponent color to redo the same probe at the next move: it will be always lost whatever move he does. Instead you have to re-probe at grand child because perhaps your second follow up move is a bad one (chose a draw continuation, hang a piece, etc..)

That's OK if the root position is a TB win. It may also be OK if the search has already determined that a TB win can be forced. As I wrote here:

What wat one could do instead, if the root position is in the WDL TBs and winning and DTZ is not available, is call probe_wdl() everywhere but not return immediately but only use the result to filter out non-winning moves. But I did not think it worth the effort to deal too extensively with the case that DTZ is not available.

The "WDL-only and TB win at root" case can indeed be improved at the cost of extra code in search(). And if this code is there anyway, it may as well be used if DTZ is available and the root position is a TB win. (Eliminating the DTZ filtering at the root if DTZ is available is completely unnecessary, though.)

In the normal case, where a forced win is not yet in sight, it makes no sense to search deeper once the search reaches a TB position. You can return a TB win value or you can return beta, that does not make much difference as long as beta < TB win.

Once a TB win can be forced, it also seems wise to build in a guarantee that the search will actually seek to convert the position into the TB win unless something better is found (and ideally to pick that TB win that gives it the easiest win).

So in my view:
- if current node is in the TB, then probe;
- if winning and beta > TB_win, search the subtree in the normal way (*);
- (if losing or drawing, then obviously take the TB cutoff except for the case alpha < -TB_win);
- return the max of the TB probe result and the search result.

(*) Before, I wrote that the subtree should now be searched with TB probing disabled. However, if you don't take an immediate TB cutoff anyway if beta > TB_win, then I guess there is no need to disable probing.

[syzygy]

I have somewhat randomly decided that once you probe that position is win, there is no need for the opponent color to redo the same probe at the next move: it will be always lost whatever move he does.

But that is not what you actually do, as far as I can tell. You probe at the child before you probe at the parent, so at the child you don't know whether the parent was winning.

Your approach seems designed for the case that the root position is a TB win. That's not the usual situation.

I don't know what endgame positions you are testing on, but if they are 5-piece winning endings, then I guess you might well find an improvement. They are probably long wins that short searches might not be able to solve. Probing WDL everywhere won't help in KBNvK or KQvKR (since everything is won anyway), but it would help immensely in KBNvKN (only some positions are winning, and DTZ can be very high).

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

[syzygy]

Also the idea to first search the subtree of a TB position and probe there and only then probe the position itself?

No, if you clicked the link you would have seen what I have done....

Why are you comparing alpha and beta with bestValue (== -VALUE_INFINITE)? Probably not what you intended.

[syzygy]

So in my view:
- if current node is in the TB, then probe;
- if winning and beta > TB_win, search the subtree in the normal way (*);
- (if losing or drawing, then obviously take the TB cutoff except for the case alpha < -TB_win);
- return the max of the TB probe result and the search result.

(*) Before, I wrote that the subtree should now be searched with TB probing disabled. However, if you don't take an immediate TB cutoff anyway if beta > TB_win, then I guess there is no need to disable probing.

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.

So what you would like is call search() recursively on the same position, and now skip the TB probe in that position. That also needs some sort of hack, but it seems a simple flag in the Position structure could do the trick...

This is what I meant by "complicated surgery" here. It seems certainly doable, though.

[Michel]

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.

I haven't looked at SF's code but I am sort of surprised by this.

You would normally not exit if you are below alpha (so the case beta>TBWIN should not be a problem) and there should be a single place where you can take a beta cutoff and in that case I guess you would adjust the score in the alpha<-TBWIN base.

It's an interesting question what to return in the latter case if bestValue>-TBWIN since now the TB and the search are in contradiction.

You want to return a lowerbound but -TBWIN is only an upperbound. So it seems safest to make the most conservative decision and to return beta.

EDIT: There is a similar issue with failing low at the end of search in the beta>TBWIN case if bestValue<TBWIN. I guess you should return alpha in that case.

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.