Page 1 of 2
Question to Daniel Shawul
Posted:
30 May 2006, 18:55by 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
Re: Question to Daniel Shawul
Posted:
31 May 2006, 03:36by Ryan Benitez
Re: Question to Daniel Shawul
Posted:
31 May 2006, 07:24by 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.
Re: Question to Daniel Shawul
Posted:
31 May 2006, 07:44by 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
Re: Question to Daniel Shawul
Posted:
31 May 2006, 08:46by Dann Corbit
I think the new compression method of Ratko Tomic is very promising for this sort of thing. Have you tried it?
Re: Question to Daniel Shawul
Posted:
31 May 2006, 11:46by 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
Re: Question to Daniel Shawul
Posted:
31 May 2006, 19:06by 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
Re: Question to Daniel Shawul
Posted:
31 May 2006, 19:14by Dann Corbit
Daniel Shawul wrote:{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.
Re: Question to Daniel Shawul
Posted:
31 May 2006, 21:01by 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.
Re: Question to Daniel Shawul
Posted:
01 Jun 2006, 02:48by Ryan Benitez
Thomas Gaksch wrote: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.
Re: Question to Daniel Shawul
Posted:
01 Jun 2006, 05:58by Daniel Shawul
I meant KnightDreamer.
Re: Question to Daniel Shawul
Posted:
01 Jun 2006, 06:12by 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
Re: Question to Daniel Shawul
Posted:
01 Jun 2006, 07:57by Klaus Friedel
Daniel Shawul wrote: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
Re: Question to Daniel Shawul
Posted:
06 Jun 2006, 14:19by 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
Re: Question to Daniel Shawul
Posted:
06 Jun 2006, 14:22by 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
Re: Question to Daniel Shawul
Posted:
07 Jun 2006, 09:38by Daniel Shawul
Anthony Cozzie wrote: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
Re: Question to Daniel Shawul
Posted:
07 Jun 2006, 18:07by 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
Re: Question to Daniel Shawul
Posted:
08 Jun 2006, 13:16by 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?
Re: Question to Daniel Shawul
Posted:
08 Jun 2006, 18:32by Anthony Cozzie
Seems logical. His are still 2X smaller than yours, though
anthony
Re: Question to Daniel Shawul
Posted:
08 Jun 2006, 18:44by Roger Brown
Anthony Cozzie wrote: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.