Question to Daniel Shawul

[Thomas Gaksch]

Hello Daniel,
may i use your EGBBs in Toga II based on Fruit? If yes, are there any 5 piece bitbases which i can download or generate myself?
Thank you for your help.

Greets

Thomas

[Ryan Benitez]

You can get the generator at Dann's site.
http://cap.connx.com/chess-engines/scorpio/

[Thomas Gaksch]

Ryan, thank you for your help. Do you know how long does it take to generate the 5 piece bitbases? There seems to be also an compress utility for the bitbases. Do you have any experience with it. Is ist supported by the dll? What about the performance? Sorry, for so much questions.

Do you know if i need the written permission from Daniel to use his dll?
Daniel, if you read this it would be great if you could give me your permission to use your dll.
Thank you.

[Daniel Shawul]

Hello Thomas

Yes you can use it.
The 5piece tables right now are just too big, i am trying hard to compress them. Currently around 900MB, well it is possible to bring this down to 200MB, but i haven't figured it out yet.
Stay tuned!

regards,
daniel

p.s: you can send me a private email

[Dann Corbit]

I think the new compression method of Ratko Tomic is very promising for this sort of thing. Have you tried it?

[Daniel Shawul]

Hi Dann

No i haven't tried that one but will try it later.

But i tried many other variations
RLE + huffman
LZ77 + huffman (what i think datacomp uses)
RLE + LZ77 + huffman

The best i got with the above 3 was 1gb with the third one. DataComp also gives 1gb. I do not think that the best compression algorithm would be able to beat datacomp by more than 50%. That will bring down the size maximum to 700MB.

IMO what really decreses the size is prediction of outcome using some kind of genetic algorithm (decision trees or neural nets).
I have noted that with prediction done before compression, all the best compressors have hard time beating simple RLE + huffman.

The problem is coming up with a good predictor for 5men especially those with pawns. All the literature i have found revolves around solving simple 4piece (KRK, KQKQ) endgames by induction rules.
I coud not find any work on 5 pieces.

BTW do you know the details about KD, i have mailed the author but did not get a response yet.

regards,
daniel

[Klaus Friedel]

Hello Daniel,

as you already know I'm also experimenting with EGTB compression. I made some experiments with let's call it "dimension permutation".
I insert a step before compression. I try all permitations of dimensions and measure compresssion ratio.

So we for example generate KRPkr, measure compression ratio,
reindex the bitbase as KRPrk, KRrkp, rkPRK .... and all other permutations. For 5 men there are 5! = 120 permutations, thats doable in reasonable time.

In the example the size of the best was about 70% of the default.
No huge gain, but notable.

Regards,

Klaus

[Dann Corbit]

{snip}
BTW do you know the details about KD, i have mailed the author but did not get a response yet.
{snip}
I do not know whay you mean by KD. I am sure that I am just being thick.

[Greg Simpson]

I was looking at the liscense.txt file on Dann's site, and I noticed this clause: "* It is illegal to endorse or promote products derived from this software without specific prior written permission from Daniel Shawul."

I don't understand what this means, but it appears to be putting some kind of restriction on any program using the code there. Any such restriction seems to me likely to violate the GPL, so Toga II couldn't use it. My understanding is that DLLs used this way are considered part of the program.

[Ryan Benitez]

Ryan, thank you for your help. Do you know how long does it take to generate the 5 piece bitbases? There seems to be also an compress utility for the bitbases. Do you have any experience with it. Is ist supported by the dll? What about the performance? Sorry, for so much questions.

Do you know if i need the written permission from Daniel to use his dll?
Daniel, if you read this it would be great if you could give me your permission to use your dll.
Thank you.

I have not tried to generate 5 piece yet. Because of the size it is best to just used 4 piece and the 5 piece with pawns bitbases.

[Daniel Shawul]

I meant KnightDreamer.

[Daniel Shawul]

Hi Klaus,

How does your method work for endgames with pawns?
If it shows 70% for those , i think this is an easy gain.
I think that 4men and pawnless 5men are very easy to compress and prediction is quite easy. For example the sizes of my bitbases for them is just 140MB , it shoots up to 950MB when egbbs with pawns are included. So i think that a small improvment on these bitbases will pay off.

regards,
Daniel

[Klaus Friedel]

Hi Klaus,

How does your method work for endgames with pawns?
If it shows 70% for those , i think this is an easy gain.
I think that 4men and pawnless 5men are very easy to compress and prediction is quite easy. For example the sizes of my bitbases for them is just 140MB , it shoots up to 950MB when egbbs with pawns are included. So i think that a small improvment on these bitbases will pay off.

regards,
Daniel

The 70% are for the given example.

Indexing as rkPRK gives 23408555 Byte compressed.
Indexing as KrPRk I get 18682787 Bytes.

Update: The current best compression:
PrR[Kk] with 16540324 Bytes
[Kk] means : Both kings index combined excluding illegal positions.


Klaus

[Anthony Cozzie]

This is completely logical. When the pawn is advanced the strong side will score much better.

IMO the best results would be obtained by a a combination of bitbases and tablebases - bitbases in the search (in RAM) and tablebases at the root position if a win is reached. Of course you already knew that.

I quote from the KnightDreamer homepage:

"Decision trees grown with an ID3-style algorithm is used to predict if a position is won, lost or drawn. In unclear cases small searches can be performed. An accuracy above 99% is reached for most endgames. A table with the exceptions is compressed with run length encoding and huffman codes. The exception table is probed on the fly, without generating any decompressed tables. Eugene Nalimov?s EGTBs are used as an oracle during generation of the egms."

Have you tried something like this?

anthony

[Anthony Cozzie]

RRRR. OK, I am an idiot.

Anyway, you don't need to do a neural net, you just need to come up with rules using your own neural net

For example, with KBPKB you could just predict draw unless the pawn is on the 7th rank and the Bishop doesn't cover the queening square, and you will be right 90% of the time I'd guess.

anthony

[Daniel Shawul]

RRRR. OK, I am an idiot.

Anyway, you don't need to do a neural net, you just need to come up with rules using your own neural net

For example, with KBPKB you could just predict draw unless the pawn is on the 7th rank and the Bishop doesn't cover the queening square, and you will be right 90% of the time I'd guess.

anthony

My neural nets are only 1000ELO

Yes, I tried to include pawn promotions but it did not redcuce the size much. As you said KBPKB is typicall easy to predict, but there are a lot more where pediction is harder KNPKN,KRPKR,KRPKQ.
For most of the endgames (260 out of 290) i get prediction >= 90%. But those bitbases which are hard to predict take huge part of the total size. Now i am more or less convinced that i have to use at least a search of 2 plies(which implies the 5men cant be used in qsearch anymore), combined with specific evaluation functions for each to have any chance of reducing the total size to 200-300MB.
regards,
Daniel

[Anthony Cozzie]

Well, it would be a project. However, some thoughts:

For KRPKR you can look at the Toga/Fruit source code.

For KRPKQ I would guess the key for the weak side is having the king the close to the Rook, otherwise it will be lost to a queen check.

For all the pawn-up endings the rank of the pawn is probably very important.

I haven't tried any of these things, but if I were you I would just do trial and error one bitbase at a time. After you did a few you would probably have a good idea on how to get things done. And as a bonus your elo might improve a bit

What I am not sure of is how much actual strength an engine would gain from the 5-man bitbases. 6 and 7 pieces seem much more useful.

anthony

[Daniel Shawul]

I came across a thought that is a possible surprise
I thought that KnightDreamer's bitbases were for *both* sides to move. Well i now really really think that it is only for one of the
sides to move. My own bitbases are total 970MB but when i throw out one of the side's (the one with big size), the total bitbase size goes down to 330MB!! KD's bitbases are 230MB.
So i may not need to do anything more!
Also i checked size of shredderbases and two sizes are specified 157MB, and 441MB. So i am guessing the former is one side to move only. It also says the latter is 10x faster which i think is because both white/black to move bitbases are available, you don't need to min-max to get the value of a position. I hope my little sherlock story is correct
Can some one confirm this?

[Anthony Cozzie]

Seems logical. His are still 2X smaller than yours, though

anthony

[Roger Brown]

Seems logical. His are still 2X smaller than yours, though

anthony

Hello Anthony Cozzie,

So you are saying that size does matter?



Sorry, I could not help myself.

Later.