generating algorithms

[cdani]

I was letting fly the imagination on tablebases, and I had the idea to try to, instead of generating a tablebase, generate the algorithms that validate a position as won/draw.

The idea is to generate automatically something like this for example for the endgame KBPK:

If (weak king in front of pawn)
draw;
if (distance between king and pawn < distance from pawn to 8th rank and ...)
draw;
...

To generate this I think one can iterate trough all the possible positions having tablebase access and find which "Ifs" are true always; first find one-condition if's that are always true; then find two condition if's that are always true; and so on until all the cases or most of them are covered. Of course the if's that cover most positions will be first in the resulting algorithm.

One can also use if's like (if distance between kings < 5), when the number 5 is generated and validated with a for 1..7.

Will be nice, and many people will use them in their engines those resulting algorithms

[velmarin]

This published Steve maughan, have it in your computer and favorite how,
The question if this gives knowledge, that insurance, or improving the engine which is more dubious.
He has his job, but it is something to keep in mind.

http://www.talkchess.com/forum/viewtopi ... w=&start=0

[Xann]

I was letting fly the imagination on tablebases, and I had the idea to try to, instead of generating a tablebase, generate the algorithms that validate a position as won/draw.

Hi Daniel,

I'm not sure what you have in mind (due to some contradictory wording), but please make sure not to reinvent machine learning (ML below). You might want to have a look at decision-tree and decision-rule learning, although they are usually designed for noisy data.

Ross Quinlan already did what you are suggesting in the 80's:
http://chessprogramming.wikispaces.com/Ross+Quinlan

Chess endgames are even part of standard ML benchmarks:
http://archive.ics.uci.edu/ml/datasets/ ... s.+King%29

Fabien.

[cdani]

Nice to know all this information!
But I don't see the supposed resulting algorithms implemented in any opensource engine, so either is impossible to work them, or nobody has tried, or there is some difficult thing I don't imagine for the moment.
I will try to play on this with some code...

[hgm]

To cover all cases, the decision trees get unmanageably large. To traverse them in every leaf would not be competitive to just probing a bitbase. On-the-fly generation of P-slices of EGTs reachable from the root would be a more effective method. You don't see that in any open-source engines either.

I guess the point is that perfect play in the late end-game is not very important. With todeay's deep searches an evaluation with only the most basic principles is enough to make the engines win 99% of the won end-games they reach. Worrying about the remaining 1% doesn't bring enough Elo for anyone to worry about it.

[cdani]

To cover all cases, the decision trees get unmanageably large. To traverse them in every leaf would not be competitive to just probing a bitbase. On-the-fly generation of P-slices of EGTs reachable from the root would be a more effective method. You don't see that in any open-source engines either.

I guess the point is that perfect play in the late end-game is not very important. With todeay's deep searches an evaluation with only the most basic principles is enough to make the engines win 99% of the won end-games they reach. Worrying about the remaining 1% doesn't bring enough Elo for anyone to worry about it.

"the decision trees get unmanageably large." I was not able to guess that. Sure is the key answer. Thanks!

"I guess the point is that perfect play in the late end-game is not very important." I know this, but I hoped to be able to

[cdani]

To cover all cases, the decision trees get unmanageably large.

But, if you see a fractal and do not know that it is born from a simple formula, one will guess exactly that, that the decision tree to make it is unmanageably large.
So maybe there is hope somewhere

[kbhearn]

One key to making the decision tree more manageable is to turn much of the tablebase into 'don't care' positions by including a small, well specified tactical search that must be executed in order for the result of the decision tree to be reliable. Even then, excessively tactical endings are likely to be a nightmare as probably some things fall through your tactical search sieve and wind up being a list of individual special cases that have to be tested for.

[hgm]

It would be an interesting exercise to attempt this for KPK and KBPK. In King Slayer/Simple I added recognizers for this, but to keep those simple, I used 'one-sided recognizers': they only recognize a sub-set of the draws, but when they say it is draw, it must be 100% certain that it is indeed a draw. Then the search can be cut there, as you know there is nothing to find. The score I return is still the naive eval divided by some large factor rather than a hard 0, because when the engine has the upper hand in a position that is a theoretical draw, you don't want it to stop trying by giving away its advantage. E.g. when you give away the Pawn in KPK immediately, because one 0 score is as good as any other, you would not even win against engines that do not know the opposition rule, and have no hash table.

In positions that are not recognized as a draw I just let the engine search on. If they are draws the search sooner or later discovers it. And if not, the naive evaluation in combination with normal search is usually a good way to make progress. (Which is a necessity in won positions; merely moving from one won position to another won't make you win!)

[cdani]

It would be an interesting exercise to attempt this for KPK and KBPK.

Yes, it's my idea. And then try to do it in more complicated ones.

In King Slayer/Simple I added recognizers for this, but to keep those simple, I used 'one-sided recognizers': they only recognize a sub-set of the draws, but when they say it is draw, it must be 100% certain that it is indeed a draw. Then the search can be cut there, as you know there is nothing to find. The score I return is still the naive eval divided by some large factor rather than a hard 0, because when the engine has the upper hand in a position that is a theoretical draw, you don't want it to stop trying by giving away its advantage. E.g. when you give away the Pawn in KPK immediately, because one 0 score is as good as any other, you would not even win against engines that do not know the opposition rule, and have no hash table.

In positions that are not recognized as a draw I just let the engine search on. If they are draws the search sooner or later discovers it. And if not, the naive evaluation in combination with normal search is usually a good way to make progress. (Which is a necessity in won positions; merely moving from one won position to another won't make you win!)

It's exactly what I think and most engines like Andscacs do more or less, but with hand crafted algorithms.