Natural TB

hgm · Post by **hgm** » Tue May 31, 2016 11:31 pm

I guess the problem on first entering the EGT can be solved by scoring a winning probe not as a mate score, but as the material evaluation of the EGT plus 2 Pawns. Then it would not sacrifice any pieces to enter the EGT. This involves a gamble, however. Namely that with the extra material you will be able to find a faster mate by playing on the heuristic eval than the tabulated win after the sac.

You would still sac a Pawn, but I guess this should be considered 'natural play'. Pawns do not really speed up the mating effort. (And you cannot easily force the opponnet to take it, like you can with a Queen, so you would just ignore threats against it.) Unless they promote. But if you would see they could promote, you would of course not sac them to reap the 200cP gain the EGT win gives you.

lucasart · Post by **lucasart** » Wed Jun 01, 2016 1:42 am

mcostalba wrote:
lucasart wrote: So, I really think your patch has merit. However, I think the best course of action is to first merge the syzygy branch into master: no functional change, great code cleanup/documentation. And then do more testing on this natural_tb, before eventually mergine (unless we find real problems that are not trivial to resolve).
Thanks for your quick test.

At the moment I have no urge to merge anything in SF. Indeed I think I will not merge any syzygy new version during my maintenance period.

I think we should instead systematically test and verify the "Natural TB": many real games end tests are needed to get a correct picture of this experiment.

And at one point a direct match with syzgy will be needed to measure any ELO loss from syzygy.

Note that DTZ is really necessary, at least in theory, to guarantee progress and win all winnable TB positions (or draw all drawable TB positions).

The point is that WDL only tells you if a win is cursed or not, based on the assumption that rule50=0 in the current position. If you find a win with DTZ=90, but rule50=20 already, then you have a cursed win with DTZ=110, and simply using DL you'll be thinking you have a real win.

At root, when you remove all the moves that don't preserve the win (or draw), you need to use DTZ to do it correctly, accounting for the 50 move rule.
* Even if the root position has rule50=0, you need DTZ, because after playing a non zeroging move, you have rule50=1, so you can't just probe WDL, but need also check DTZ to make sure you don't get a win with DTZ=100, which turns into DTZ=101 at root that is a cursed win!
* Even more so if rule50 at root is larger that that.

And, only probing WDL for rule50=0 means you may find situations where SF cannot make progress.

But, this is only a theoretical possibility, and I have yet to see any concrete example of this in real games. It's probably so rare, that it's well worth the code simplification + half download size, of throwing away DTZ.

Vinvin · Post by **Vinvin** » Wed Jun 01, 2016 2:47 am

With Stockfish reaching very high depth and the number of possible moves reduced to only good moves (+endgame knowledge +a lot of things stored in HT), I'm no more sure DTZ is needed.

Here are the longest checkmates to check (may some are draw by 50 moves rules : as this one q3Q3/8/5q2/8/8/8/3k4/1K5R w - - 0 1 )

http://kirill-kryukov.com/chess/longest ... ates.shtml

KBPKN 100 1n6/3P4/8/8/1K6/7B/8/k7 w - - 0 1
KBNKP 104 8/8/3K4/8/8/1p6/k7/5B1N w - - 0 1
KBNKN 107 8/8/8/8/8/8/1n5B/2K1N2k w - - 0 1

KRBKR 65 8/3B4/8/1R6/5r2/8/3K4/5k2 w - - 0 1

KNNKP 115 1N6/8/p7/8/8/8/2k1N3/K7 w - - 0 1 <- this one seems draw-50m too
KBNKP 104 8/8/3K4/8/8/1p6/k7/5B1N w - - 0 1
KBNKN 107 8/8/8/8/8/8/1n5B/2K1N2k w - - 0 1
KRKNP 67 2K4k/7p/8/8/8/8/3R4/n7 w - - 0 1

KQPKP 105 8/8/8/8/3P2Q1/8/1p6/K1k5 w - - 0 1
KQPKQ 124 4Q3/8/7q/8/8/8/k3P3/2K5 w - - 0 1

KQKNN 72 8/8/8/8/4n2Q/3k4/8/3K3n w - - 0 1
KQKBB 81 8/1Q6/8/8/2bb4/8/3k4/K7 w - - 0 1
KQKRB 70 8/4Q3/b7/r7/8/8/8/K5k1 w - - 0 1
KQKRN 69 8/5Q2/8/n7/8/4k3/8/3K2r1 w - - 0 1
KNNNKN 90 7N/N7/1k6/8/8/8/2K1n3/1N6 w - - 0 1
KNNNKB 96 6bN/8/8/8/8/1N6/2k5/K6N w - - 0 1
KQBPKQ 158 8/5B1Q/8/8/3k4/6qP/8/1K6 w - - 0 1
KQNKRR 174 3r2r1/8/k7/8/8/8/3K4/1Q4N1 w - - 0 1

Here are some KNNKP mate in 45 I found with Wilhem :

8/4p3/8/1K1N2k1/8/2N5/8/8 w - - dm 45;
1N1N4/6k1/3p4/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/2p3k1/2K5/8/8/8/8 w - - dm 45;
1N1N4/8/3p1k2/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/3p2k1/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K4k1/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/6k1/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/6k1/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/8/6k1/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/8/8/6k1 w - - dm 45;
1N1N4/8/3p4/2K3k1/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/3K4/8/8/8/6k1 w - - dm 45;
8/4p3/8/1K1N2k1/8/6N1/8/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/3N4/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/4N3/8 w - - dm 45;
1N1k2N1/8/2p5/8/1K6/8/8/8 w - - dm 45;
1N1k2N1/8/2p5/8/2K5/8/8/8 w - - dm 45;
1N1k2N1/8/2p5/8/3K4/8/8/8 w - - dm 45;
1N1k2N1/8/8/3p4/1K6/8/8/8 w - - dm 45;
1N1k2N1/8/8/3p4/8/1K6/8/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/5N2/8 w - - dm 45;
8/4p3/8/1K1N4/6k1/2N5/8/8 w - - dm 45;

Frank Quisinsky · Post by **Frank Quisinsky** » Wed Jun 01, 2016 3:14 am

Lound thinking ...
We can seach to each topic such a discussion if we like with the results that we have to search more and more the topics we like.

In my opinion all is good what we have.
Nothing should be changed.

Michel · Post by **Michel** » Wed Jun 01, 2016 7:49 am

petero2 wrote:
Michel wrote:
hgm wrote:In general it does not pay to treat it as lower bound as you would for hash hits, however.
Why not? IMHO using TB hits in this way would precisely have the effect that it would continue to search for a mate, when it makes sense to do so (i.e. when the window contains mate scores).

If this idea is correct (I am not completely sure) then no hacks would be required to resolve the issue of mate blindness.

And no performance sacrifices either since we only continue searching if the root window has already been enlarged so much that it contains mate scores. This will only happen (in aspiration search) if the position has already been determined to be a win.
This is in fact what Texel's tablebase implementation already does. It works fine and in some cases produces impressive results, such as finding the mate in 70/72 in the positions I mentioned here.

Great!! So at least the mate blindness appears to be completely trivial to solve within the context of PVS without any downsides neither with regard to correctness or performance.

Marco mentionned two more "artifacts"

(1) Unnatural scores. The case I am aware of where this was reported was a draw position which SF thought was lost. At that time Ronald's TB implementation returned the SF search score unfiltered (despite of course being aware of the draw). I guess it would be simple matter to return a draw score at root if the position is a TB draw.

(2) Sacrifices to reach a TB position This appears to be unfixable for positions where the search cannot yet detect a mate.

The current implementation I think would normally already postpone the sacrifice in a proven win position if the postponement does not invalidate the proof (Ronald?).

EDIT: When I wrote "unfixable" I meant unfixable without sacrificing correctness.

Evert · Post by **Evert** » Wed Jun 01, 2016 9:00 am

bob wrote: This fails in several ways. What about KNN vs KP? You can't drop the pawn as it is a draw. And what if, in the KNNQ vs KP you drop the queen and find it is a mate, what do you do? Search without using the tables to avoid tossing the queen? I'd bet one could construct a number of endgame positions where the trade wins by a long mate, but not trading leads to a forced draw.

When you have imperfect information, you make imperfect decisions. I don't see the point in trying for the most aesthetic win, any win will do. Humans generally don't find the shortest mate yet we don't see anyone complaining.

Well, it pre-supposes that you think dropping Q in KNNQKP to get an assured, but long and tedious mate, is something that you'd like to avoid. If one is perfectly content with that, then there is nothing to fix - even if dropping N for P seems like a better idea.

Of course you don't go and squander the point. You know you have an assured win, but you're interested in looking for a "better" one (again, probably only for analysis). If you can't find it, you're not going to toss the one you found.
I suppose you can also think of it as a type of multi-PV search.

syzygy · Post by **syzygy** » Wed Jun 01, 2016 9:22 am

Michel wrote:(1) Unnatural scores. The case I am aware of where this was reported was a draw position which SF thought was lost. At that time Ronald's TB implementation returned the SF search score unfiltered (despite of course being aware of the draw). I guess it would be simple matter to return a draw score at root if the position is a TB draw.

That is what current SF does.

I suppose what Marco considers "unnatural" is reporting a TB win score (+123 or so) where the engine in fact has found a TB win. Rationality has nothing to do with this thread.

(2) Sacrifices to reach a TB position This appears to be unfixable for positions where the search cannot yet detect a mate.

The current implementation I think would normally already postpone the sacrifice in a proven win position if the postponement does not invalidate the proof (Ronald?).

The current implementation treats all TB wins equal and goes for the quickest one. This is by far the simplest approach. It would be possible to differentiate between TB wins (e.g. on the basis of material balance), but you will also need to take into account the distance to the TB win or the search might never get to any.

So it's not that nothing can be done (although even DTM will sometimes cause the engine to sack its queen), but doing something right needs careful thought (so forget about that in the context of Stockfish) and careful implementation. And whether it is worth to add a lot of complexity just to be able to win in a slightly nicer way (where the current engine already is guaranteed to win anyway)...

hgm · Post by **hgm** » Wed Jun 01, 2016 9:56 am

Dropping anything is usually not a good idea. Surely in KQNNKP, when KNNKP would already be won, the mate should be very close, and the gain of a Pawn even closer. The point is that you should push the engine to search for it. With these rediculously high reductions everyone is using nowadays, awarding won KNNKP probes with a mate score will reduce the search in the KQNNKP to almost nothing.

So once you established you have a sure win through converting to KNNKP from a materially superior position, you should try to improve the search not by doggedly cranking up the nominal depth in the root (which could take forever before it hits a KQNNKP mate). You should improve it by preventing the KNNKP probes from masking heuristically good moves in the KQNNKP sector.

This can be easily achieved by redoing the search under rules that do not probe inferior EGTs. This hides the cumbersome KNNKP win, and forces the engine to find a better win (like conversion to KQNNK, or mate in KQNNKP). If it cannot find such a better win, you play the move that forced the win through KNNKP.

Note that it is easy to check whether a winning score is obtained by forcing conversion to an inferior end-game, by using different 'mate scores' for probes to such end-games (such as adding 100 to the DTM).

lucasart · Post by **lucasart** » Wed Jun 01, 2016 1:14 pm

Vinvin wrote:With Stockfish reaching very high depth and the number of possible moves reduced to only good moves (+endgame knowledge +a lot of things stored in HT), I'm no more sure DTZ is needed.

Agreed!

Vinvin wrote: Here are the longest checkmates to check (may some are draw by 50 moves rules : as this one q3Q3/8/5q2/8/8/8/3k4/1K5R w - - 0 1 )

http://kirill-kryukov.com/chess/longest ... ates.shtml

KBPKN 100 1n6/3P4/8/8/1K6/7B/8/k7 w - - 0 1
KBNKP 104 8/8/3K4/8/8/1p6/k7/5B1N w - - 0 1
KBNKN 107 8/8/8/8/8/8/1n5B/2K1N2k w - - 0 1

KRBKR 65 8/3B4/8/1R6/5r2/8/3K4/5k2 w - - 0 1

KNNKP 115 1N6/8/p7/8/8/8/2k1N3/K7 w - - 0 1 <- this one seems draw-50m too
KBNKP 104 8/8/3K4/8/8/1p6/k7/5B1N w - - 0 1
KBNKN 107 8/8/8/8/8/8/1n5B/2K1N2k w - - 0 1
KRKNP 67 2K4k/7p/8/8/8/8/3R4/n7 w - - 0 1

KQPKP 105 8/8/8/8/3P2Q1/8/1p6/K1k5 w - - 0 1
KQPKQ 124 4Q3/8/7q/8/8/8/k3P3/2K5 w - - 0 1

KQKNN 72 8/8/8/8/4n2Q/3k4/8/3K3n w - - 0 1
KQKBB 81 8/1Q6/8/8/2bb4/8/3k4/K7 w - - 0 1
KQKRB 70 8/4Q3/b7/r7/8/8/8/K5k1 w - - 0 1
KQKRN 69 8/5Q2/8/n7/8/4k3/8/3K2r1 w - - 0 1
KNNNKN 90 7N/N7/1k6/8/8/8/2K1n3/1N6 w - - 0 1
KNNNKB 96 6bN/8/8/8/8/1N6/2k5/K6N w - - 0 1
KQBPKQ 158 8/5B1Q/8/8/3k4/6qP/8/1K6 w - - 0 1
KQNKRR 174 3r2r1/8/k7/8/8/8/3K4/1Q4N1 w - - 0 1

Here are some KNNKP mate in 45 I found with Wilhem :

8/4p3/8/1K1N2k1/8/2N5/8/8 w - - dm 45;
1N1N4/6k1/3p4/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/2p3k1/2K5/8/8/8/8 w - - dm 45;
1N1N4/8/3p1k2/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/3p2k1/1K6/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K4k1/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/6k1/8/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/6k1/8/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/8/6k1/8 w - - dm 45;
1N1N4/8/3p4/1K6/8/8/8/6k1 w - - dm 45;
1N1N4/8/3p4/2K3k1/8/8/8/8 w - - dm 45;
1N1N4/8/3p4/3K4/8/8/8/6k1 w - - dm 45;
8/4p3/8/1K1N2k1/8/6N1/8/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/3N4/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/4N3/8 w - - dm 45;
1N1k2N1/8/2p5/8/1K6/8/8/8 w - - dm 45;
1N1k2N1/8/2p5/8/2K5/8/8/8 w - - dm 45;
1N1k2N1/8/2p5/8/3K4/8/8/8 w - - dm 45;
1N1k2N1/8/8/3p4/1K6/8/8/8 w - - dm 45;
1N1k2N1/8/8/3p4/8/1K6/8/8 w - - dm 45;
8/4p3/8/1K1N2k1/8/8/5N2/8 w - - dm 45;
8/4p3/8/1K1N4/6k1/2N5/8/8 w - - dm 45;

Please check your positions with DTZ. Many of them are draws (cursed wins).

Laskos · Post by **Laskos** » Wed Jun 01, 2016 1:54 pm

Vinvin wrote:With Stockfish reaching very high depth and the number of possible moves reduced to only good moves (+endgame knowledge +a lot of things stored in HT), I'm no more sure DTZ is needed.

I am getting curious results. The time control is short (100ms / move), so maybe somebody can test more seriously. I have 5-men Syzygy bases (WDL+DTZ) on a flash.

On hard 5-men root wins Natural is performing just a bit better than No TB at all, and Syzygy (perfect engine in this case) is well ahead of both:

Code: Select all

Games Completed = 600 of 600 &#40;Avg game length = 8.915 sec&#41;
Settings = RR/32MB/100ms per move/M 900cp for 1000 moves, D 150000 moves/EPD&#58;Hard5men.epd&#40;258&#41;
Time = 1394 sec elapsed, 0 sec remaining
 1.  Stockfish                	155.0/400	98-188-114  	&#40;L&#58; m=188 t=0 i=0 a=0&#41;	&#40;D&#58; r=10 i=62 f=42 s=0 a=0&#41;	

&#40;tpm=105.1 d=30.57 nps=2047822&#41;
 2.  Stockfish Nat TB         	171.5/400	115-172-113  	&#40;L&#58; m=172 t=0 i=0 a=0&#41;	&#40;D&#58; r=6 i=25 f=82 s=0 a=0&#41;	

&#40;tpm=103.9 d=32.55 nps=1912074&#41;
 3.  Stockfish Syz            	273.5/400	200-53-147  	&#40;L&#58; m=53 t=0 i=0 a=0&#41;	&#40;D&#58; r=10 i=37 f=100 s=0 a=0&#41;	

&#40;tpm=105.2 d=30.80 nps=1914023&#41;

But on 6-10 men a bit unbalanced opening positions (if they are too balanced, the draw rate is very high), I got a surprise:

Code: Select all

Games Completed = 1800 of 1800 &#40;Avg game length = 10.424 sec&#41;
Settings = RR/32MB/100ms per move/M 900cp for 1000 moves, D 150000 moves/EPD&#58;END_10_14.epd&#40;727&#41;
Time = 4865 sec elapsed, 0 sec remaining
 1.  Stockfish                	557.0/1200	236-322-642  	&#40;L&#58; m=322 t=0 i=0 a=0&#41;	&#40;D&#58; r=299 i=172 f=156 s=15 a=0&#41;	

&#40;tpm=107.6 d=24.74 nps=2020062&#41;
 2.  Stockfish Nat TB         	634.0/1200	324-256-620  	&#40;L&#58; m=256 t=0 i=0 a=0&#41;	&#40;D&#58; r=299 i=171 f=135 s=15 a=0&#41;	

&#40;tpm=106.5 d=27.41 nps=1819026&#41;
 3.  Stockfish Syz            	609.0/1200	303-285-612  	&#40;L&#58; m=285 t=0 i=0 a=0&#41;	&#40;D&#58; r=286 i=169 f=141 s=16 a=0&#41;	

&#40;tpm=107.4 d=25.60 nps=1854485&#41;

Natural is performing above Syzygy.

Natural TB

Re: Natural TB

Re: Natural TB

Re: Natural TB

Re: To MODERATORS: Please STOP moving programming selection!

Re: Natural TB

Re: Natural TB

Re: Natural TB

Re: Natural TB

Re: Natural TB

Re: Natural TB