hard-wired bitbases

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
benstoker
Posts: 342
Joined: Tue Jan 19, 2010 1:05 am

hard-wired bitbases

Post by benstoker » Tue Apr 13, 2010 1:13 pm

Some engines hard-wrire KPK bitbases. The engine-that-dare-not-speak-its-name is one example.

Could not other bitbases be hard-wired? Or would that be overkill? Or bloat the program size? What others piece-endings would be a bitbase candidate for hard-wiring?

Sven
Posts: 3743
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: hard-wired bitbases

Post by Sven » Tue Apr 13, 2010 1:38 pm

benstoker wrote:Some engines hard-wrire KPK bitbases. The engine-that-dare-not-speak-its-name is one example.

Could not other bitbases be hard-wired? Or would that be overkill? Or bloat the program size? What others piece-endings would be a bitbase candidate for hard-wiring?
KPK is the only 3-men endgame that may be of interest since KQK and KRK are usually trivial to win and all others are draw by rule. Each 4-men endgame requires about 60 times as much memory as a 3-men endgame (60x meant as a very simple rule of thumb, of course), and there are a lot of potentially interesting 4-men endgames like KBPK, KNPK, KPPK, KQK*, KRK*, K*KP (* = any piece). So the overall memory requirements for hard-wiring all these into an engine are quite huge already, I would estimate about 900 times of memory required for KPK only. At least some factor of Nx100 if you restrict to only a few 4-men. And also the size of the C source you need for that (huge constant tables) grows by that factor.

Using bitbases the "normal" way seems to be better.

Sven

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

Re: hard-wired bitbases

Post by hgm » Tue Apr 13, 2010 1:42 pm

KPK is 3-men, and each extra man makes it 64 times larger. So indeed, you very quickly get into a situation where almost the entire size of the .exe is taken by the bitbases, which would make it very wasteful to make them all contain a copy of this information. Of the 3-men KPK is the ony interesting one, as KBK and KNK are always draw, while KQK and KRK are always won (with wtm).

A 3-men has 64^3 = 256K positions, which at 1 bit per position would be 32KB, indeed a trifle. (Making use of symmetry could still cut that in two, but then again you might want to have it for both wtm and btm.) Add 1 man, and it already brings you to 2 MB.

[edit] I see we simultaneously typed about the same thing. :lol:

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

Re: hard-wired bitbases

Post by wgarvin » Tue Apr 13, 2010 4:28 pm

Sven Schüle wrote:
benstoker wrote:Some engines hard-wrire KPK bitbases. The engine-that-dare-not-speak-its-name is one example.

Could not other bitbases be hard-wired? Or would that be overkill? Or bloat the program size? What others piece-endings would be a bitbase candidate for hard-wiring?
KPK is the only 3-men endgame that may be of interest since KQK and KRK are usually trivial to win and all others are draw by rule. Each 4-men endgame requires about 60 times as much memory as a 3-men endgame (60x meant as a very simple rule of thumb, of course), and there are a lot of potentially interesting 4-men endgames like KBPK, KNPK, KPPK, KQK*, KRK*, K*KP (* = any piece). So the overall memory requirements for hard-wiring all these into an engine are quite huge already, I would estimate about 900 times of memory required for KPK only. At least some factor of Nx100 if you restrict to only a few 4-men. And also the size of the C source you need for that (huge constant tables) grows by that factor.

Using bitbases the "normal" way seems to be better.

Sven
The DarkThought team managed to fit all 4-man bitbases into about 15 MB in a relatively uncompressed form, and that was many years ago. I'd love to see a modern engine using 5-man bitbases with a better compression story. Of course baking them into the executable is probably not ideal, but you could still bundle them with the engine as separate files but make them a required part of it.

benstoker
Posts: 342
Joined: Tue Jan 19, 2010 1:05 am

Re: hard-wired bitbases

Post by benstoker » Tue Apr 13, 2010 4:29 pm

wgarvin wrote:
Sven Schüle wrote:
benstoker wrote:Some engines hard-wrire KPK bitbases. The engine-that-dare-not-speak-its-name is one example.

Could not other bitbases be hard-wired? Or would that be overkill? Or bloat the program size? What others piece-endings would be a bitbase candidate for hard-wiring?
KPK is the only 3-men endgame that may be of interest since KQK and KRK are usually trivial to win and all others are draw by rule. Each 4-men endgame requires about 60 times as much memory as a 3-men endgame (60x meant as a very simple rule of thumb, of course), and there are a lot of potentially interesting 4-men endgames like KBPK, KNPK, KPPK, KQK*, KRK*, K*KP (* = any piece). So the overall memory requirements for hard-wiring all these into an engine are quite huge already, I would estimate about 900 times of memory required for KPK only. At least some factor of Nx100 if you restrict to only a few 4-men. And also the size of the C source you need for that (huge constant tables) grows by that factor.

Using bitbases the "normal" way seems to be better.

Sven
The DarkThought team managed to fit all 4-man bitbases into about 15 MB in a relatively uncompressed form, and that was many years ago. I'd love to see a modern engine using 5-man bitbases with a better compression story. Of course baking them into the executable is probably not ideal, but you could still bundle them with the engine as separate files but make them a required part of it.
What about blocked pawn bitbases?

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: hard-wired bitbases

Post by Dirt » Tue Apr 13, 2010 9:47 pm

wgarvin wrote:... 5-man bitbases with a better compression ...
Still over 100 MB, I think.

User avatar
michiguel
Posts: 6371
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: hard-wired bitbases

Post by michiguel » Tue Apr 13, 2010 10:48 pm

wgarvin wrote:
Sven Schüle wrote:
benstoker wrote:Some engines hard-wrire KPK bitbases. The engine-that-dare-not-speak-its-name is one example.

Could not other bitbases be hard-wired? Or would that be overkill? Or bloat the program size? What others piece-endings would be a bitbase candidate for hard-wiring?
KPK is the only 3-men endgame that may be of interest since KQK and KRK are usually trivial to win and all others are draw by rule. Each 4-men endgame requires about 60 times as much memory as a 3-men endgame (60x meant as a very simple rule of thumb, of course), and there are a lot of potentially interesting 4-men endgames like KBPK, KNPK, KPPK, KQK*, KRK*, K*KP (* = any piece). So the overall memory requirements for hard-wiring all these into an engine are quite huge already, I would estimate about 900 times of memory required for KPK only. At least some factor of Nx100 if you restrict to only a few 4-men. And also the size of the C source you need for that (huge constant tables) grows by that factor.

Using bitbases the "normal" way seems to be better.

Sven
The DarkThought team managed to fit all 4-man bitbases into about 15 MB in a relatively uncompressed form, and that was many years ago. I'd love to see a modern engine using 5-man bitbases with a better compression story.
I do not believe that is the way to go. I think it is better to have a bigger cache with uncompressed information. You are better off using RAM for hash tables rather than compressed info you will not use. The compressed information will need to be decompressed, which takes time. Better to have a cache, uncompressed, with information you will use. At least, that is the philosophy I am trying with the gaviota TBs.

Miguel

Of course baking them into the executable is probably not ideal, but you could still bundle them with the engine as separate files but make them a required part of it.

rjgibert
Posts: 306
Joined: Mon Jun 26, 2006 7:44 am

Re: hard-wired bitbases

Post by rjgibert » Wed Apr 14, 2010 12:20 am

You might consider hardwiring a subset of KPKP where the 2 opposing pawns
block each other. The number of legal positions in that subset should be
smaller than KPK. Note that all conversions of this subset map into KPK so
the 2 would work well together.

Martin Brown
Posts: 46
Joined: Sun Oct 18, 2009 10:07 am

Re: hard-wired bitbases

Post by Martin Brown » Wed Apr 14, 2010 11:07 am

Dirt wrote:
wgarvin wrote:... 5-man bitbases with a better compression ...
Still over 100 MB, I think.
Shredderbases are all34.tbe 1.4MB and all345.tbe 161MB

What is the best compression anyone has managed on bitbases? And is there any prospect of seeing 6 men bitbases one day ? I guess the cost of decompression outweighs any space saving but the full Nalimov 6 men tablebases occupy a heck of a lot of disk space.

You could perhaps make a case for including all34.tbe as hardwired.
Martin Brown

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

Re: hard-wired bitbases

Post by wgarvin » Wed Apr 14, 2010 3:06 pm

If you had (for example) all 4-man bitbases in memory, and used them in the search, then you would never encounter a 3-man bitbase during search -- only when playing out the actual ending over the board.

Similarly, if you manage to have all the relevant 5-man bitbases in memory while searching, you will never need to probe into 4-man bitbases at all during the search.

So at that point "hard coding" certain smaller ones into the engine isn't of much use. You could do it for a small one like KPK just to help you win it efficiently when playing out the actual ending over the board, but you wouldn't need it when searching.

Post Reply