hard-wired bitbases

[benstoker]

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]

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

[hgm]

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.

[wgarvin]

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]

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]

... 5-man bitbases with a better compression ...

Still over 100 MB, I think.

[michiguel]

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]

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]

... 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.

[wgarvin]

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.