Natural TB

[mcostalba]

I will properly address your post later.

I'd like just to quickly present my point of view.

TB in normal games are useful for 2 reasons: to show the engine the winning path and to prune useless subtrees. My view is that the latter is what gives the biggest advantage, the first one is not so important with today engines at long TC.


Return immediately on draw or lose position is a kind of pruning, reduce search in case of winning is a kind of very aggressive LMR. I do this to avoid strange sacrifices because not altering the score fixes that behaviour at its roots.

I can miss detecting winning positions as such, but my bet is that in normal games (not in studies) this is very small thing and the engine will do without its ELO is affected.

Again, my hypothesis is that in normal games biggest advantage of TB is pruning useless sidelines. Only at endgame time TB can have a visible effect but at that point my take is that game is already decided.

[syzygy]

Just before to submit this post I found that most of this idea was already presented by Ronald de Man:

Code: Select all

Ideally, once the engine has determined that it can have at least a TB win, it should start searching beyond the TB probe without doing further TB probes, but in such a way that if that search beyond the TB probe does not return a MATE, the search at the TB position still returns the TB win value.

And my implementation was posted here.

[syzygy]

TB in normal games are useful for 2 reasons: to show the engine the winning path and to prune useless subtrees. My view is that the latter is what gives the biggest advantage, the first one is not so important with today engines at long TC.

But you got the first one wrong in an important way.
The first advantage is not showing the winning path, but having accurate evaluations of the TB positions.

The second advantage is not the ability to prune "useless" subtrees, but the ability to completely prune very useful subtrees. This is possible, because the TB probe done at the root of the subtree returns 100% accurate information. Without this 100% accurate information, the engine would have to search the subtree in the normal way (or lose in quality).

What you are now proposing is not using that very valuable information to prune the the subtree. Instead, you throw the valuable information away and search the subtree. But instead of doing a normal search (already bad enough), you are reducing that search. How can you possibly think that is a good idea?

If it is a good idea to reduce those subtrees, why not reduce them even if TBs are not available at all?

Again, my hypothesis is that in normal games biggest advantage of TB is pruning useless sidelines.

Again, they are not useless sidelines. The only reason TBs allow you to prune them is because the TB probe gives perfect information that is equal to what a search with infinite depth would have returned. But you can't prune if you throw away the perfect information...

Do you not understand what I write, or do you think elementary principles of logic somehow can be circumvented ?

[syzygy]

As has been pointed out many times by many people already this particular problem can be fully solved within the context A/B search by regarding TB scores win/loss scores as bounds (like TT upperbound and lowerbound scores).

The point is if you return from a TB probe immediately (no matter with what score) you will never find a mate line.

If you are in a MATE in 5 position, a TB probe returns "win", if you just return failing high and you keep failing high on that node, you will never find the winning line. To find the winning line you have to continue searching, there is no other way.

This was already stated somewhere in this thread's old posts, but admittedly this thread was very noisy and confusing.

But Michel is right. The "clean" solution to the problem has been pointed out many times in this thread. The simple idea of the solution is that you don't take the TB cutoff if the TB win or loss value is inside the (alpha, beta) window.

Note that to find a mate you need to continue but with TB probe disabled in the sub-tree, otherwise at the child node probing will return a losing score for the opponent that will not continue the search.

With the clean solution there is no need to disable probing: the next probe in the subtree will simply again not lead to a TB cutoff (unless it should lead to a TB cutoff because the move being searched was not a winning move but a drawing or losing move).

[hgm]

Indeed, an EGT is equivalent to a hash table with score bounds for the wins and losses of infinite draft, and produces cutoffs in a similar way. (For draws the score is exact.) If it doesn't cut on a win or loss because the bound is in-window, it can be used to narrow the window. With fail hard this will then cause the EGT score bound to be returned, even if all searched move would not find something better (for a win).

If you combine this with a different score as TB-win for each EGT, depending on its desirability (e.g. a KQRKR win is better than a KQKR win but worse than a KQRK win) then the continued search will also allow you to find better conversions at the expense of faster conversions, even if it cannot search all the way to the mate. It will refrain from sacrificing the surplus Rook in KQRKR if it sees it can trade it, and refrain from trading it if it sees it can gain it.

In this case you cannot even do any harm by reducing the search. Except of course that it reduces the probability that you will indeed find a more favorable conversion, and goes to the quick sacrifice alluded to in the EGT.

[syzygy]

If you combine this with a different score as TB-win for each EGT, depending on its desirability (e.g. a KQRKR win is better than a KQKR win but worse than a KQRK win) then the continued search will also allow you to find better conversions at the expense of faster conversions, even if it cannot search all the way to the mate. It will refrain from sacrificing the surplus Rook in KQRKR if it sees it can trade it, and refrain from trading it if it sees it can gain it.

Having different TB win values depending on material balance will indeed make the search prefer TB wins with better material, but it does not solve the perceived problem of the engine unnecessarily sacking its queen to reach a winning TB ending, unless these TB win values are set to values within the normal range of evaluation scores.

If you set the TB win values to values in the normal range, you lose the possibility to keep track of the distance to the TB win (I am aware that you have proposed adjusting all non-zero evaluation scores by the distance from the root to the leaf, but that would have wider implications). So there is a danger that the engine would be able to find the TB win, but would need the 50-move rule to actually reach the winning TB position (or would not find it in time if the TT table messed up 50-move draw detection). Whether this danger is more than theoretical is something I don't really know.

Another effect of setting the TB win values to values in the normal range is that the user is no longer informed that the position he or she is analysing is a win or a loss. A value of +10 is a very likely win, but it is not the same as seeing +123.45 and knowing that this means TB win.

If the aim is to remove "unnatural behaviour", then I guess the underlying aim is to improve SF for end users. What do end users want? Do they want to be informed that the position they are analysing is a TB win? Or do they prefer to be kept in the dark about whether the engine has already solved the position with the help of TBs?

Do users prefer to be kept in the dark? Marco seems to think so.

I suspect serious users prefer to get full information. Ideally, the GUI would say TB win instead of showing a strange score, but this is a GUI/UCI issue.

I do not contest that users would like to see Stockfish find easy mates that it will currently not find with TBs enabled because the mate is "hidden" behind a TB win. But his can be achieved in a proper way without effectively disabling TBs as Marco is doing now.

[hgm]

Completely agreed. Entering the EGT will always be a dilemma. Will you go for a certain mate that takes long, but which you can see because it is tabulated, or prefer a heuristically better position where you cannot prove mate, and just hope for a faster one? As the heuristics are not perfect, the latter will lead to an occasional blunder. (E.g. most engines have trouble recognizing a rabid Rook as a draw, and could prefer the opponent to have one if they have overwhelming material compensation.)

There can also be disagreement over what 'natural' means. When I was still playing Chess myself, I always tried to convert as rapidly as possible to a position that my opponent would recognize as a theoretical win. Often much to the dismay of my team members. ("Why are you sacrificing that Pawn? You could have forced its promotion! Now it will take much longer to win!" Of course the win then was instant, because the opponent invariably resigned on his next turn.)

As for what the user wants, why not let him decide that himself, through an engine option? By allowing the user to set the TB-win score for various end-games, and have the various material compoistions at different defaults (e.g. some TB-win score plus the material imbalance according to Q=9, R=5...), the user will immediately be able to see from the root score which kind of win the engine plans to force. If he is not happy with that plan, he can reduce the score of the corresponding EGT to the heuristic range, and redo the analysis, to see if a better win can be found.

[Houdini]

There can also be disagreement over what 'natural' means. When I was still playing Chess myself, I always tried to convert as rapidly as possible to a position that my opponent would recognize as a theoretical win. Often much to the dismay of my team members. ("Why are you sacrificing that Pawn? You could have forced its promotion! Now it will take much longer to win!" Of course the win then was instant, because the opponent invariably resigned on his next turn.)

Exactly.
This whole "natural" thing is a non-issue, it's a relic of the previous century when human players were still relevant for chess .
For an engine, simplifying to a TB position is always the best solution, it instantly ends the game.

[zullil]

There can also be disagreement over what 'natural' means. When I was still playing Chess myself, I always tried to convert as rapidly as possible to a position that my opponent would recognize as a theoretical win. Often much to the dismay of my team members. ("Why are you sacrificing that Pawn? You could have forced its promotion! Now it will take much longer to win!" Of course the win then was instant, because the opponent invariably resigned on his next turn.)

Exactly.
This whole "natural" thing is a non-issue, it's a relic of the previous century when human players were still relevant for chess .
For an engine, simplifying to a TB position is always the best solution, it instantly ends the game.

Nicely said. I agree completely.

[Nordlandia]

Hi Robert.

When probing nalimov egtb. Occasionally H5 crashes.

I hope this can be looked upon and fixed in next Houdini release