6-men Nalimov EGTB.

[diepeveen]

...snip..
The question is, what is that going to cost? one big I/O (to read a compressed block) is expensive. if you are 40 plies away, you have to do 40 reads to walk the EGTB PV to get to the ultimate mate to see if it is a draw or if it resets the 50 move counter with a capture. But the cost seems to be beyond acceptable. Even a single EGTB probe is expensive enough, this could be 50-100-200 times worse...

You are pondering loud that the checkers guys like Schaeffer & co were wrong in using WDL's and instead should use DTM of 1 stone less, which requires more i/o than WDL's?

Even uncompressed WDL has a 10 to 1 advantage over DTM in i/o in the majority of the endgame in terms of caching. DTM takes 2 bytes a position, WDL stores 5 in 1 byte.

Only when you want to physical mate the opponent it takes a bit longer as you have to search for each move. This is however no big deal. The alternative for the average user is NOT have even the 5 men, as a 7GB download he finds too much, if he would know he can download it anyway.

Now you buy a cdrom and the 5 men are already on CDROM for every customer, or just a 157MB download.

Vincent

[H.G.Muller]

My solution is simply to translate mate in more than 50 to number that is not win and not draw but advantage and stop the search at that point.


I have a table that translate every mate to number of pawns.

Yes, but my question is how you would handle that in a bit-base, which stores only win/draw/lost information. Then, after probing the bit-base, you only get back one of these 3 possibilities. To do what you propose would require you to at least also allow a fourth class of outcomes: "draw by 50-move rule but won otherwise".

That would drive the number of bits required per position from 1.6 (= 2log 3) to 2.

[H.G.Muller]

Bob, Josu?,

The whole problem you are addressing just occurs because DTM is a useless metric. The problem won't occur at all in DTZ50 table bases. Then you know on the first probe if the winning path needs more than 50 moves. One shoud never use DTM ETGBs, only DTZ.

Note that my original question was for neither metric, but for bit-bases that only store win/draw/loss info.

[diepeveen]

Bob, Josu?,

The whole problem you are addressing just occurs because DTM is a useless metric. The problem won't occur at all in DTZ50 table bases. Then you know on the first probe if the winning path needs more than 50 moves. One shoud never use DTM ETGBs, only DTZ.

Note that my original question was for neither metric, but for bit-bases that only store win/draw/loss info.

I've been seeing in my life quite a lot of computergames.

Must be well over 10000, if i include blitz games.

In none of those games i ever saw a 5 men which was > 50 moves to win including conversion. I have seen programs that wrote down too optimistic mate scores. I remember basically someone quoting one time a crafty score from what was it, mate in 57 or so?

I remember bugs in programs showin gmate in 100+ scores, will admit directly that also diep has an estimation of mate in a lot when it sees a position that should be going mate.

Realistically spoken the whole discussion here about mates above 50 moves is in EGTBs that hardly ever come onto the board, let alone that the mate in X happens in computer games a lot, let alone that the programs in questions had any egtb's or any clue about what was happening to them.

Whether you qualify a position that's officially having a DTC of 51 as a draw, or whether you qualify it as a mate, my guess is that it doesn't really matter a lot.

The odds are there that the opponent doesn't have that EGTB, so seeing it as a draw could be a fundamental error.

In fact in future everyone will have WDL 7 men. At that moment someone qualifying a mate in 51 as a win could be game winning, as your opponent doesn't play it perfect, so you win in 38 moves effectively.

There are advantages and there is disadvantages. The only thing we know for sure is that a correct EGTB doesn't exist.

That would need for every position 2 integers:
a) distance till 50 move rule
b) total moves to go till mate.

If you do not have both values, the problem is that the search you are doing will mess up.

Knowing the huge size difference between such a correct DTM50 table and WDL, it's questionable whether it's clever to create such an EGTB. I vote not.

I decided to use WDL (so not WDL50).

The reason might perhaps sound absurd to you, but the simplistic reason is that WDL compresses better than WDL50.

There is no other reason. It's a lot of extra effort though to generate WDL than WDL50 for the 7 men. On average factor 2-4 for the 7 men i count at.

Size of compressed EGTBs is more important for simple practical reasons, than whether you draw in theory 1 in a 100k games at a position that your opponent is going to avoid anyway as he's also going to have WDL and not WDL50.

Note that from within WDL50 you search so deep already that you already hit all kind of positions that are < 50 moves to mate.

So at the moment that you hit mate in 50, which is printed as a 'win', then it's possible that you still win it sooner and within 50 moves. The opposite could happen too, but are we caring to discuss for another 40 postings something that happens once in each 10k+ games or so?

Vincent

[H.G.Muller]

You are perfectly right, of course, that an imperfect EGTB you can afford to have on your hard disk is infinitely better than a perfect one that you couldn't afford because it did not compress well enough.

This makes it all the more strange that people prefer DTM over DTC/DTZ, because the latter usually compress better too. The solution proposed earlier, to check all mate paths for duration, is basically bulding a new (DTZ) EGTB because the one you have precomputed is useless!

You are really the first one to address my original question, with the answer that it is preferable to store the 'slow wins' as wins than as draws, when using bit-bases.

To win some end-games that really are on the board (as opposed to probing for winning conversions) my engine is not clever enough to go without some progress measure, however. Even for KBNK it has only a 50% win probability, and a bit-base there would not help it a bit .

[diepeveen]

You are perfectly right, of course, that an imperfect EGTB you can afford to have on your hard disk is infinitely better than a perfect one that you couldn't afford because it did not compress well enough.

This makes it all the more strange that people prefer DTM over DTC/DTZ, because the latter usually compress better too. The solution proposed earlier, to check all mate paths for duration, is basically bulding a new (DTZ) EGTB because the one you have precomputed is useless!

You are really the first one to address my original question, with the answer that it is preferable to store the 'slow wins' as wins than as draws, when using bit-bases.

To win some end-games that really are on the board (as opposed to probing for winning conversions) my engine is not clever enough to go without some progress measure, however. Even for KBNK it has only a 50% win probability, and a bit-base there would not help it a bit .

Diep could mate KBNK in 1994. When i recently tested it against Nalimov equipped opponent, it put mate from maximin position in perfect manner.

Then i tested by hand extensively maximin positions and found a few where diep needed n+1 moves, where n = maximin.

Vincent

p.s. if you can write your own EGTB format, making some chessknowledge to put mate should be pretty trivial for most endgames.

[H.G.Muller]

Yes, by putting the required knowledge in the evaluation it could certainly be remedied. Even to the point where you don't need the EGTBs at all. For KBNK the only thing that would be needed is the knowledge about which corner the bare King has to be driven to.

Problem is that I am not good enough a chess player to do this for the more complicated endings (and I am too lazy to learn much chess theory ). So I would have to use the EGTBs themselves to extract the information on how the end-games should be won.

For the purpose of deriving progress indicators from DTM or DTZ table bases, as opposed to deriving WDL rules fro probing, I might even play with re-ordering the EGTB according to another measure than just the number of moves, such as distance of the enemy King from the corner.

[diepeveen]

Yes, by putting the required knowledge in the evaluation it could certainly be remedied. Even to the point where you don't need the EGTBs at all. For KBNK the only thing that would be needed is the knowledge about which corner the bare King has to be driven to.

Problem is that I am not good enough a chess player to do this for the more complicated endings (and I am too lazy to learn much chess theory ). So I would have to use the EGTBs themselves to extract the information on how the end-games should be won.

For the purpose of deriving progress indicators from DTM or DTZ table bases, as opposed to deriving WDL rules fro probing, I might even play with re-ordering the EGTB according to another measure than just the number of moves, such as distance of the enemy King from the corner.

My point is that making a function to mate for like 99.9999999% of all positions is a few days work, versus having your own WDL EGTB's is considerable more work.

Vincent

[H.G.Muller]

What would be easier in your experience as a strong chessplayer: determining if a position is won, or giving the move to actually win it? Would it also be possible to make a fuction to determine the WDL status of, say, 99.9% of all positions?

Perhaps table-bases is not the way to go at all...

[Sune Fischer]

Would it also be possible to make a fuction to determine the WDL status of, say, 99.9% of all positions?

Perhaps table-bases is not the way to go at all...

You can not get to 99.9% with a resonable amount of code, but 60-80% is doable in a week or so.

I did these internal recognizers in Frenzee and am getting in the 70-80% hits. It takes a huge load off the IO, the most trivial KQx-K tables gets very close to a 100% so they aren't probed at all.

It's so fast that one can use these all the way to the leaf, but still I'd say it's hardly worth doing. I haven't been able to measure much of a strength increase at all.

It's not that they don't help, it's just that so very few games are undecided at that stage for them to have a chance to make a difference.

-S

[Daniel Shawul]

I think it is possible to get 99% for 4men, without using Search as a predictor. KnightDreamer's bitbases use an ID3-style algortithm for predicition and accuracy is >99% according to the author.
I do not know how they selected the attributes to build the decision tree, which i think is the key to good accuracy. My guess is they used some kind of data mining tool , or they know what attributes to use from experience.
I wrote a predictor ,soley based on my knowledge of the endgames, and i got >99% for simple Kxxk and some kxkx bitbases. The most difficult to predict is those involving pawns, even search will not predict it efficiently because it takes really long to see if the pawn promotes. My predictor function,using eval only,can handle exchanges statically and this raised the prediction rate. Obviously prediction gets harder for 5men and above, but this way i was able to reduce the size of my bitbase sizes by half.

[Sune Fischer]

I think it is possible to get 99% for 4men, without using Search as a predictor. KnightDreamer's bitbases use an ID3-style algortithm for predicition and accuracy is >99% according to the author.

I suspect this is a little different from what I do, if you get 99% accuracy it means 1% is wrong?
I suppose this prevents them from being used close to the root?

I do not know how they selected the attributes to build the decision tree, which i think is the key to good accuracy. My guess is they used some kind of data mining tool , or they know what attributes to use from experience.
I wrote a predictor ,soley based on my knowledge of the endgames, and i got >99% for simple Kxxk and some kxkx bitbases. The most difficult to predict is those involving pawns, even search will not predict it efficiently because it takes really long to see if the pawn promotes.

I think 99% is very good, like you say the pawn positions are the worst. Many tables are trivial, some you can even get 100% on but others are hard to pridict, especially if we talk 5 men.

My predictor function,using eval only,can handle exchanges statically and this raised the prediction rate. Obviously prediction gets harder for 5men and above, but this way i was able to reduce the size of my bitbase sizes by half.

If you combine recognizers with true bitbase tables it should be really effective.
Have you measured the hitrate on your 5 men recogs?

[Klaus Friedel]

I think it is possible to get 99% for 4men, without using Search as a predictor. KnightDreamer's bitbases use an ID3-style algortithm for predicition and accuracy is >99% according to the author.

I suspect this is a little different from what I do, if you get 99% accuracy it means 1% is wrong?
I suppose this prevents them from being used close to the root?

I can't follow you here ? Why shound this prevent anything ?
Maybe you missunderstoud the concept of prediction ? The prediction is only used to achive better compression ratios.
After decompression the bitbases are 100% correct !

Regards

Klaus

[Sune Fischer]

I can't follow you here ? Why shound this prevent anything ?
Maybe you missunderstoud the concept of prediction ? The prediction is only used to achive better compression ratios.
After decompression the bitbases are 100% correct !

Regards

Klaus

Ah that kind of pridiction

When I say "recognizers", I'm talking about substituting bitbases with pure code, for example:

Code: Select all

switch (material_key)  {
  case KR_K:
    if (white_to_move) return WHITE_WINS;
    if (rook_en_prise)  return ITS_DRAW;
    if (black_stalemate) return ITS_DRAW;
    return WHITE_WINS;
...
}