EGTB compression (H. G. Muller tablebase...)

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

EGTB compression (H. G. Muller tablebase...)

Post by Dann Corbit » Fri Jan 25, 2008 7:36 am

Given the following uncompressed H. G. Muller tablebase file:
01/24/2008 11:25 PM 268,439,552 KBB_KN

From here:
http://www.quicklz.com/
I ran a compression benchmark against the file, which shows compression ratio and speed of both compression and decompression:

C:\COMPRE~1\bench\Release>bench KBB_KN
LZF 3.1 VER : 22490 KB (28.8%) 150.2 MB/s 289.0 MB/s.
FastLZ 0.1.0 1: 22751 KB (29.1%) 177.6 MB/s 329.5 MB/s.
FastLZ 0.1.0 2: 22507 KB (28.8%) 141.1 MB/s 325.5 MB/s.
LZO 1X 2.02 : 20575 KB (26.3%) 144.5 MB/s 361.7 MB/s.
QuickLZ 1.4.0 4 : 18339 KB (23.5%) 35.0 MB/s 429.1 MB/s.

The QuickLZ 1.4.0 compressor created an 18 MB file that decompresses at 429 MB/Sec.


The size certainly compares well with Nalimov files:
Directory of C:\arena\Engines\Nalimov

06/04/2003 11:00 PM 17,795,185 kbbkn.nbb.emd
06/04/2003 11:00 PM 13,167,012 kbbkn.nbw.emd

I bring this up because it is so cotton-picking hard to get ahold of Eugene for permissions.

I was wondering, which other EGTB formats are available as open source? I believe the Scorpio format is published.

So we have:

H.G.Muller
D.Shawul
E.Nalimov

with source code for EGTB available. Are there any others?

User avatar
hgm
Posts: 24956
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: EGTB compression (H. G. Muller tablebase...)

Post by hgm » Fri Jan 25, 2008 9:14 am

I think there is this Italian EGTB generator gafs.

Note that my generator does not do pawny endings yet. I deferred that to my next generation generator, which should work P-slice by P-slice. But I have too many computer-Chess projects going on at the same time (WinBoard_F, xboard_F, Joker, Joker80, micro-Max, Fairy-Max, piece-value measurements, ressurrection of my 1980 Chess program with a 6502 emulator), and the tablebase generation suffers...

I think ChessMaster also has an EGTB generator, but no one knows the format it spits out.

Tony

Re: EGTB compression (H. G. Muller tablebase...)

Post by Tony » Fri Jan 25, 2008 11:10 am

Dann Corbit wrote:Given the following uncompressed H. G. Muller tablebase file:
01/24/2008 11:25 PM 268,439,552 KBB_KN

From here:
http://www.quicklz.com/
I ran a compression benchmark against the file, which shows compression ratio and speed of both compression and decompression:

C:\COMPRE~1\bench\Release>bench KBB_KN
LZF 3.1 VER : 22490 KB (28.8%) 150.2 MB/s 289.0 MB/s.
FastLZ 0.1.0 1: 22751 KB (29.1%) 177.6 MB/s 329.5 MB/s.
FastLZ 0.1.0 2: 22507 KB (28.8%) 141.1 MB/s 325.5 MB/s.
LZO 1X 2.02 : 20575 KB (26.3%) 144.5 MB/s 361.7 MB/s.
QuickLZ 1.4.0 4 : 18339 KB (23.5%) 35.0 MB/s 429.1 MB/s.

The QuickLZ 1.4.0 compressor created an 18 MB file that decompresses at 429 MB/Sec.


The size certainly compares well with Nalimov files:
Directory of C:\arena\Engines\Nalimov

06/04/2003 11:00 PM 17,795,185 kbbkn.nbb.emd
06/04/2003 11:00 PM 13,167,012 kbbkn.nbw.emd

I bring this up because it is so cotton-picking hard to get ahold of Eugene for permissions.

I was wondering, which other EGTB formats are available as open source? I believe the Scorpio format is published.

So we have:

H.G.Muller
D.Shawul
E.Nalimov

with source code for EGTB available. Are there any others?
I'm still working on my lossy compression bitbases but since I'm busy rewriting XiniX to throw out x88 and only keep bitboards, it's a bit buggy now.

They are based on a sort of obdd. If one setlles for a recognition percentage of 70% ( wich is about the minimum to be usefull) the 5 pieces bitbases need 64 MB

When I have a better computer I'll try to compress the most important 6 pieces (and keep them in memory)
The compression times are rather awfull on this machine (>10days for KRPKRP).

Tony

GeorgeLyapko

Re: EGTB compression (H. G. Muller tablebase...)

Post by GeorgeLyapko » Fri Jan 25, 2008 11:59 am

A.Morozov's Booot uses own format endgame tablebases.

jswaff

Re: EGTB compression (H. G. Muller tablebase...)

Post by jswaff » Fri Jan 25, 2008 3:42 pm

I started one, but it's in the very early stages - so far I've only done KQK. :)
I've put the project on hold to work on DTS.

Tony

Re: EGTB compression (H. G. Muller tablebase...)

Post by Tony » Fri Jan 25, 2008 4:28 pm

jswaff wrote:I started one, but it's in the very early stages - so far I've only done KQK. :)
I've put the project on hold to work on DTS.
Yeah, I know the feeling.

And now I decided to actually start testing my ideas ( rather than just implement them) , it all takes even more time. :?

Tony

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: EGTB compression (H. G. Muller tablebase...)

Post by wgarvin » Fri Jan 25, 2008 10:10 pm

Tony wrote:I'm still working on my lossy compression bitbases but since I'm busy rewriting XiniX to throw out x88 and only keep bitboards, it's a bit buggy now.

They are based on a sort of obdd. If one setlles for a recognition percentage of 70% ( wich is about the minimum to be usefull) the 5 pieces bitbases need 64 MB

When I have a better computer I'll try to compress the most important 6 pieces (and keep them in memory)
The compression times are rather awfull on this machine (>10days for KRPKRP).

Tony
I'm very interested in hearing how this works out. I've been hoping to see practically useful, lossy-compressed bitbases emerge for many years now. (I'm too lazy to try and achieve this myself.)

Its obvious that storing even W/L/D for every position is too expensive to justify for more than 5 pieces. But if a lossy representation could reduce the size by 10x or more, and still play correctly and not fall foul of the 50-move rule, that would be very interesting. Also, lossy data could probably be predicted better by heuristics (and therefore compressed better).

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: EGTB compression (H. G. Muller tablebase...)

Post by bob » Sat Jan 26, 2008 1:29 am

Dann Corbit wrote:Given the following uncompressed H. G. Muller tablebase file:
01/24/2008 11:25 PM 268,439,552 KBB_KN

From here:
http://www.quicklz.com/
I ran a compression benchmark against the file, which shows compression ratio and speed of both compression and decompression:

C:\COMPRE~1\bench\Release>bench KBB_KN
LZF 3.1 VER : 22490 KB (28.8%) 150.2 MB/s 289.0 MB/s.
FastLZ 0.1.0 1: 22751 KB (29.1%) 177.6 MB/s 329.5 MB/s.
FastLZ 0.1.0 2: 22507 KB (28.8%) 141.1 MB/s 325.5 MB/s.
LZO 1X 2.02 : 20575 KB (26.3%) 144.5 MB/s 361.7 MB/s.
QuickLZ 1.4.0 4 : 18339 KB (23.5%) 35.0 MB/s 429.1 MB/s.

The QuickLZ 1.4.0 compressor created an 18 MB file that decompresses at 429 MB/Sec.


The size certainly compares well with Nalimov files:
Directory of C:\arena\Engines\Nalimov

06/04/2003 11:00 PM 17,795,185 kbbkn.nbb.emd
06/04/2003 11:00 PM 13,167,012 kbbkn.nbw.emd

I bring this up because it is so cotton-picking hard to get ahold of Eugene for permissions.

I was wondering, which other EGTB formats are available as open source? I believe the Scorpio format is published.

So we have:

H.G.Muller
D.Shawul
E.Nalimov

with source code for EGTB available. Are there any others?
Don't forget the originals from ken thompson...

Post Reply