How to generate a "simple" bitbase?

[Alessandro Scotti]

Hi,
I'm a bit stuck on Hamsters (lots of "tuning" with no results so far, grrr...) so I'd like to write something that doesn't take weeks to test, but could rather offer immediate reward!
I have a KPK bitbase in Hamsters, and would like to generate it on the fly. Also a recent post showed that it could be nice to also have a very limited subset of KQKP just to cover rook and bishop pawns in 7th.
Can you explain a "simple" method of generating those two bitbases (Win/Draw) or point to some easy to read documentation?
Eventually I would like to understand how to generate tablebases but I'd rather start with something small I can actually do...

[Dann Corbit]

Hi,
I'm a bit stuck on Hamsters (lots of "tuning" with no results so far, grrr...) so I'd like to write something that doesn't take weeks to test, but could rather offer immediate reward!
I have a KPK bitbase in Hamsters, and would like to generate it on the fly. Also a recent post showed that it could be nice to also have a very limited subset of KQKP just to cover rook and bishop pawns in 7th.
Can you explain a "simple" method of generating those two bitbases (Win/Draw) or point to some easy to read documentation?
Eventually I would like to understand how to generate tablebases but I'd rather start with something small I can actually do...

The simplest way to generate a bitbase is just to generate every possible legal position, and call a tablebase to find the answer (no, really).


So, you could use Nalimov tablebase files and iterate over them, creating a bitbase map from the data.

If you just want to use tablebase files I suggest using the files of Scorpio. In fact, I think it is a crime not to do that. If every engine writer makes his own tablebase files, then I'm going to get mad. I have hundreds and hundreds of chess engines (something close to 2000, I think). Here are the bitbase files for one chess engine:

Code: Select all

 Directory of C:\programme\winboard\egbb

[.]           [..]          egbbdll.dll   kbbbk.w.cmp   kbbk.b.cmp    kbbk.w.cmp    kbbkb.b.cmp   kbbkn.w.cmp   kbbkp.w.cmp   kbbkq.b.cmp
kbbkr.b.cmp   kbbnk.w.cmp   kbbpk.w.cmp   kbk.b.cmp     kbk.w.cmp     kbkb.b.cmp    kbkb.w.cmp    kbkn.b.cmp    kbkn.w.cmp    kbkp.b.cmp
kbkp.w.cmp    kbnk.b.cmp    kbnk.w.cmp    kbnkb.b.cmp   kbnkn.b.cmp   kbnkp.w.cmp   kbnkq.b.cmp   kbnkr.b.cmp   kbnnk.w.cmp   kbnpk.w.cmp
kbpk.b.cmp    kbpk.w.cmp    kbpkb.b.cmp   kbpkn.b.cmp   kbpkp.w.cmp   kbpkq.b.cmp   kbpkr.b.cmp   kbppk.b.cmp   knk.b.cmp     knk.w.cmp
knkn.b.cmp    knkn.w.cmp    knkp.b.cmp    knkp.w.cmp    knnk.b.cmp    knnk.w.cmp    knnkb.b.cmp   knnkn.b.cmp   knnkp.w.cmp   knnkq.b.cmp
knnkr.w.cmp   knnnk.w.cmp   knnpk.w.cmp   knpk.b.cmp    knpk.w.cmp    knpkb.b.cmp   knpkn.b.cmp   knpkp.w.cmp   knpkq.b.cmp   knpkr.b.cmp
knppk.b.cmp   kpk.b.cmp     kpk.w.cmp     kpkp.b.cmp    kpkp.w.cmp    kppk.b.cmp    kppk.w.cmp    kppkb.b.cmp   kppkn.b.cmp   kppkp.w.cmp
kppkq.b.cmp   kppkr.b.cmp   kpppk.w.cmp   kqbbk.w.cmp   kqbk.b.cmp    kqbk.w.cmp    kqbkb.w.cmp   kqbkn.w.cmp   kqbkp.w.cmp   kqbkq.b.cmp
kqbkr.w.cmp   kqbnk.w.cmp   kqbpk.w.cmp   kqk.b.cmp     kqk.w.cmp     kqkb.b.cmp    kqkb.w.cmp    kqkn.b.cmp    kqkn.w.cmp    kqkp.b.cmp
kqkp.w.cmp    kqkq.b.cmp    kqkq.w.cmp    kqkr.b.cmp    kqkr.w.cmp    kqnk.b.cmp    kqnk.w.cmp    kqnkb.w.cmp   kqnkn.w.cmp   kqnkp.w.cmp
kqnkq.b.cmp   kqnkr.w.cmp   kqnnk.w.cmp   kqnpk.w.cmp   kqpk.b.cmp    kqpk.w.cmp    kqpkb.w.cmp   kqpkn.w.cmp   kqpkp.w.cmp   kqpkq.w.cmp
kqpkr.w.cmp   kqppk.w.cmp   kqqbk.w.cmp   kqqk.b.cmp    kqqk.w.cmp    kqqkb.w.cmp   kqqkn.w.cmp   kqqkp.w.cmp   kqqkq.w.cmp   kqqkr.w.cmp
kqqnk.w.cmp   kqqpk.w.cmp   kqqqk.w.cmp   kqqrk.w.cmp   kqrbk.w.cmp   kqrk.b.cmp    kqrk.w.cmp    kqrkb.w.cmp   kqrkn.w.cmp   kqrkp.w.cmp
kqrkq.w.cmp   kqrkr.w.cmp   kqrnk.w.cmp   kqrpk.w.cmp   kqrrk.w.cmp   krbbk.w.cmp   krbk.b.cmp    krbk.w.cmp    krbkb.w.cmp   krbkn.w.cmp
krbkp.w.cmp   krbkq.b.cmp   krbkr.b.cmp   krbnk.w.cmp   krbpk.w.cmp   krk.b.cmp     krk.w.cmp     krkb.b.cmp    krkb.w.cmp    krkn.b.cmp
krkn.w.cmp    krkp.b.cmp    krkp.w.cmp    krkr.b.cmp    krkr.w.cmp    krnk.b.cmp    krnk.w.cmp    krnkb.w.cmp   krnkn.w.cmp   krnkp.w.cmp
krnkq.b.cmp   krnkr.b.cmp   krnnk.w.cmp   krnpk.w.cmp   krpk.b.cmp    krpk.w.cmp    krpkb.w.cmp   krpkn.w.cmp   krpkp.w.cmp   krpkq.b.cmp
krpkr.w.cmp   krppk.w.cmp   krrbk.w.cmp   krrk.b.cmp    krrk.w.cmp    krrkb.w.cmp   krrkn.w.cmp   krrkp.w.cmp   krrkq.w.cmp   krrkr.w.cmp
krrnk.w.cmp   krrpk.w.cmp   krrrk.w.cmp
             181 File(s)    378,661,505 bytes

Now, multiply that by 2000 and I see a disk space problem developing. The same is also true for regular EGTB. I have already donated a ton of disk to my Nalimov EGTB collection:

Code: Select all

 Directory of J:\programme\winboard\nalimov

[.]                [..]               kbbk.nbb.emd       kbbk.nbw.emd       kbbkb.nbb.emd      kbbkb.nbw.emd      kbbkn.nbb.emd
kbbkn.nbw.emd      kbbkq.nbb.emd      kbbkq.nbw.emd      kbk.nbb.emd        kbk.nbw.emd        kbkb.nbb.emd       kbkb.nbw.emd
kbkn.nbb.emd       kbkn.nbw.emd       kbkp.nbb.emd       kbkp.nbw.emd       kbnk.nbb.emd       kbnk.nbw.emd       kbnkb.nbb.emd
kbnkb.nbw.emd      kbnkn.nbb.emd      kbnkn.nbw.emd      kbnkq.nbb.emd      kbnkq.nbw.emd      kbnkr.nbb.emd      kbnkr.nbw.emd
kbpk.nbb.emd       kbpk.nbw.emd       kbpkb.nbb.emd      kbpkb.nbw.emd      kbpkn.nbb.emd      kbpkn.nbw.emd      kbpkp.nbb.emd
kbpkp.nbw.emd      kbpkr.nbb.emd      kbpkr.nbw.emd      knk.nbb.emd        knk.nbw.emd        knkn.nbb.emd       knkn.nbw.emd
knkp.nbb.emd       knkp.nbw.emd       knnk.nbb.emd       knnk.nbw.emd       knnkb.nbb.emd      knnkb.nbw.emd      knnkn.nbb.emd
knnkn.nbw.emd      knnkp.nbb.emd      knnkp.nbw.emd      knnkq.nbb.emd      knnkq.nbw.emd      knnkr.nbb.emd      knnkr.nbw.emd
knpk.nbb.emd       knpk.nbw.emd       knpkb.nbb.emd      knpkb.nbw.emd      knpkn.nbb.emd      knpkn.nbw.emd      knpkp.nbb.emd
knpkp.nbw.emd      knpkr.nbb.emd      knpkr.nbw.emd      kpk.nbb.emd        kpk.nbw.emd        kpkp.nbb.emd       kpkp.nbw.emd
kppk.nbb.emd       kppk.nbw.emd       kppkb.nbb.emd      kppkb.nbw.emd      kppkn.nbb.emd      kppkn.nbw.emd      kppkp.nbb.emd
kppkp.nbw.emd      kppkq.nbb.emd      kppkq.nbw.emd      kppkr.nbb.emd      kppkr.nbw.emd      kqbk.nbb.emd       kqbk.nbw.emd
kqbkq.nbb.emd      kqbkq.nbw.emd      kqk.nbb.emd        kqk.nbw.emd        kqkb.nbb.emd       kqkb.nbw.emd       kqkn.nbb.emd
kqkn.nbw.emd       kqkp.nbb.emd       kqkp.nbw.emd       kqkq.nbb.emd       kqkq.nbw.emd       kqkr.nbb.emd       kqkr.nbw.emd
kqnk.nbb.emd       kqnk.nbw.emd       kqnkq.nbb.emd      kqnkq.nbw.emd      kqpk.nbb.emd       kqpk.nbw.emd       kqpkq.nbb.emd
kqpkq.nbw.emd      kqqk.nbb.emd       kqqk.nbw.emd       kqrk.nbb.emd       kqrk.nbw.emd       krbk.nbb.emd       krbk.nbw.emd
krbkq.nbb.emd      krbkq.nbw.emd      krbkr.nbb.emd      krbkr.nbw.emd      krk.nbb.emd        krk.nbw.emd        krkb.nbb.emd
krkb.nbw.emd       krkn.nbb.emd       krkn.nbw.emd       krkp.nbb.emd       krkp.nbw.emd       krkr.nbb.emd       krkr.nbw.emd
krnk.nbb.emd       krnk.nbw.emd       krnkq.nbb.emd      krnkq.nbw.emd      krnkr.nbb.emd      krnkr.nbw.emd      krpk.nbb.emd
krpk.nbw.emd       krpkb.nbb.emd      krpkb.nbw.emd      krpkn.nbb.emd      krpkn.nbw.emd      krpkq.nbb.emd      krpkq.nbw.emd
krpkr.nbb.emd      krpkr.nbw.emd      krrk.nbb.emd       krrk.nbw.emd       kbbbk.nbb.emd      kbbbk.nbw.emd      kbbkp.nbb.emd
kbbkp.nbw.emd      kbbkr.nbb.emd      kbbkr.nbw.emd      kbbnk.nbb.emd      kbbnk.nbw.emd      kbbpk.nbb.emd      kbbpk.nbw.emd
kbnkp.nbb.emd      kbnkp.nbw.emd      kbnnk.nbb.emd      kbnnk.nbw.emd      kbnpk.nbb.emd      kbnpk.nbw.emd      kbpkq.nbb.emd
kbpkq.nbw.emd      kbppk.nbb.emd      kbppk.nbw.emd      knnnk.nbb.emd      knnnk.nbw.emd      knnpk.nbb.emd      knnpk.nbw.emd
knpkq.nbb.emd      knpkq.nbw.emd      knppk.nbb.emd      knppk.nbw.emd      kpppk.nbb.emd      kpppk.nbw.emd      kqbkb.nbb.emd
kqbkb.nbw.emd      kqbkn.nbb.emd      kqbkn.nbw.emd      kqbkp.nbb.emd      kqbkp.nbw.emd      kqbkr.nbb.emd      kqbkr.nbw.emd
kqnkb.nbb.emd      kqnkb.nbw.emd      kqnkn.nbb.emd      kqnkn.nbw.emd      kqnkp.nbb.emd      kqnkp.nbw.emd      kqnkr.nbb.emd
kqnkr.nbw.emd      kqpkb.nbb.emd      kqpkb.nbw.emd      kqpkn.nbb.emd      kqpkn.nbw.emd      kqpkp.nbb.emd      kqpkp.nbw.emd
kqpkr.nbb.emd      kqpkr.nbw.emd      kqqkb.nbb.emd      kqqkb.nbw.emd      kqqkn.nbb.emd      kqqkn.nbw.emd      kqqkp.nbb.emd
kqqkp.nbw.emd      kqqkq.nbb.emd      kqqkq.nbw.emd      kqqkr.nbb.emd      kqqkr.nbw.emd      kqrkb.nbb.emd      kqrkb.nbw.emd
kqrkn.nbb.emd      kqrkn.nbw.emd      kqrkp.nbb.emd      kqrkp.nbw.emd      kqrkq.nbb.emd      kqrkq.nbw.emd      kqrkr.nbb.emd
kqrkr.nbw.emd      krbkb.nbb.emd      krbkb.nbw.emd      krbkn.nbb.emd      krbkn.nbw.emd      krbkp.nbb.emd      krbkp.nbw.emd
krnkb.nbb.emd      krnkb.nbw.emd      krnkn.nbb.emd      krnkn.nbw.emd      krnkp.nbb.emd      krnkp.nbw.emd      krpkp.nbb.emd
krpkp.nbw.emd      krrkb.nbb.emd      krrkb.nbw.emd      krrkn.nbb.emd      krrkn.nbw.emd      krrkp.nbb.emd      krrkp.nbw.emd
krrkq.nbb.emd      krrkq.nbw.emd      krrkr.nbb.emd      krrkr.nbw.emd      kqbbk.nbb.emd      kqbbk.nbw.emd      kqbnk.nbb.emd
kqbnk.nbw.emd      kqbpk.nbb.emd      kqbpk.nbw.emd      kqnnk.nbb.emd      kqnnk.nbw.emd      kqnpk.nbb.emd      kqnpk.nbw.emd
kqppk.nbb.emd      kqppk.nbw.emd      kqqbk.nbb.emd      kqqbk.nbw.emd      kqqnk.nbb.emd      kqqnk.nbw.emd      kqqpk.nbb.emd
kqqpk.nbw.emd      kqqqk.nbb.emd      kqqqk.nbw.emd      kqqrk.nbb.emd      kqqrk.nbw.emd      kqrbk.nbb.emd      kqrbk.nbw.emd
kqrnk.nbb.emd      kqrnk.nbw.emd      kqrpk.nbb.emd      kqrpk.nbw.emd      kqrrk.nbb.emd      kqrrk.nbw.emd      krbbk.nbb.emd
krbbk.nbw.emd      krbnk.nbb.emd      krbnk.nbw.emd      krbpk.nbb.emd      krbpk.nbw.emd      krnnk.nbb.emd      krnnk.nbw.emd
krnpk.nbb.emd      krnpk.nbw.emd      krppk.nbb.emd      krppk.nbw.emd      krrbk.nbb.emd      krrbk.nbw.emd      krrnk.nbb.emd
krrnk.nbw.emd      krrpk.nbb.emd      krrpk.nbw.emd      krrrk.nbb.emd      krrrk.nbw.emd      kbpknp.c.nbw.emd   kbpknp.c.nbb.emd
kbpknp.b.nbw.emd   kbpknp.b.nbb.emd   kbpknp.a.nbw.emd   kbpknp.a.nbb.emd   kbpknp.9.nbw.emd   kbpknp.9.nbb.emd   kbpknp.8.nbw.emd
kbpknp.8.nbb.emd   kbpknp.7.nbw.emd   kbpknp.7.nbb.emd   kbpknp.6.nbw.emd   kbpknp.6.nbb.emd   kbpknp.5.nbw.emd   kbpknp.5.nbb.emd
kbpknp.4.nbw.emd   kbpknp.4.nbb.emd   kbpknp.3.nbw.emd   kbpknp.3.nbb.emd   kbpknp.2.nbw.emd   kbpknp.2.nbb.emd   kbpknp.1.nbw.emd
kbpknp.1.nbb.emd   kbpknp.0.nbw.emd   kbpknp.0.nbb.emd   kbpkbp.6.nbw.emd   kbpkbp.5.nbw.emd   kbpkbp.4.nbw.emd   kbpkbp.3.nbw.emd
kbpkbp.2.nbw.emd   kbpkbp.1.nbw.emd   kbpkbp.0.nbw.emd   knpknp.6.nbw.emd   knpknp.5.nbw.emd   knpknp.4.nbw.emd   knpknp.3.nbw.emd
knpknp.2.nbw.emd   knpknp.1.nbw.emd   knpknp.0.nbw.emd   kppkpp.nbw.emd     kpppkp.nbw.emd     kpppkp.nbb.emd     kpppkr.nbw.emd
kpppkr.nbb.emd     krppkr.3.nbb.emd   krppkr.2.nbw.emd   krppkr.2.nbb.emd   krppkr.1.nbw.emd   krppkr.1.nbb.emd   krppkr.0.nbw.emd
krppkr.0.nbb.emd   kbbkbb.nbw.emd     kbbkbn.nbw.emd     kbbkbn.nbb.emd     kbnkbn.nbw.emd     kbnknn.nbw.emd     kbnknn.nbb.emd
kqnkqn.nbw.emd     krrkrr.nbw.emd     kbnnkr.nbw.emd     kbnnkr.nbb.emd     kbppkr.6.nbb.emd   kbppkr.5.nbw.emd   kbppkr.5.nbb.emd
kbppkr.4.nbw.emd   kbppkr.4.nbb.emd   kbppkr.3.nbw.emd   kbppkr.3.nbb.emd   kbppkr.2.nbw.emd   kbppkr.2.nbb.emd   kbppkr.1.nbw.emd
kbppkr.1.nbb.emd   kbppkr.0.nbw.emd   kbppkr.0.nbb.emd   knppkr.3.nbb.emd   knppkr.2.nbw.emd   knppkr.2.nbb.emd   knppkr.1.nbw.emd
knppkr.1.nbb.emd   knppkr.0.nbw.emd   knppkr.0.nbb.emd   kbbknn.nbw.emd     kbbknn.nbb.emd     kpppkb.nbw.emd     kpppkb.nbb.emd
kpppkn.nbw.emd     kpppkn.nbb.emd     kpppkq.nbw.emd
             379 File(s) 43,865,434,028 bytes

And then I made FEG for CM... Also, I have made tables for a Russian Pascal engine (I think it was Booot).

What I would like to see is an open and standard way to collect the perfect play data so that all of my chess programs can access the same information without rolling their own every time. I'm sure it's lots of fun to write your own EGTB engine, but DARN they eat disk like a mad herd of hungry munching freeloaders.

[Alessandro Scotti]

The simplest way to generate a bitbase is just to generate every possible legal position, and call a tablebase to find the answer (no, really).

Hi Dann,
that's how Kiwi's bitbases are generated! For Hamsters though, I'd like to generate the above two tables on the fly, without relying on external data.

[GeorgeLyapko]

And then I made FEG for CM... Also, I have made tables for a Russian Pascal engine (I think it was Booot).

Sorry Dann, but Booot is not Russian, Booot is Ukrainian engine...

[hgm]

Generating bitbases is practically the same thing as generating table bases, except that you pack the DTM in a smaller number of bits. In practice, during the building, you have to distinguish undecided positions from won positions, and amongst the won positions you have to distinguish those that were declared won in the last iteration from those that were already known to be won before (so you can build the next generation from those new wins). So you will need more than 1 bit per position. When you build table-bases, you can recgnize the iteration explicitly from the DTM code, as each generation produces the next DTM.

You can find an open-source tablebase generator on my website. It uses 7 bits per position for the DTM with black (= the losing side) to move, and 1 bit to indicate if the position is won with wtm. The amount you could save on this by shrinking the 7 bits to 2 is too small to bother. Building the tablebase 'on the fly'will take more time than you can afford before it takes more memory than you can afford.

Problem: the generator only does pawnless endings. With pawns it could be simpler (delete the symmetry stuff), but you would have to seed it with won positions after promotion.

[Alessandro Scotti]

You can find an open-source tablebase generator on my website. It uses 7 bits per position for the DTM with black (= the losing side) to move, and 1 bit to indicate if the position is won with wtm. The amount you could save on this by shrinking the 7 bits to 2 is too small to bother. Building the tablebase 'on the fly'will take more time than you can afford before it takes more memory than you can afford.

Thanks H.G. I'll try to have a look at it. I think building KPK is affordable for time and memory because Glaurung already does that and I don't need much more for now.

[hgm]

On my 1.3GHz Pentium M it typically took 2 seconds to build a pawnless 4-men. (One-sided wins only; to get the wins for the other side, you had to do an independent run.) But the one on my website might not be the fastest version.

For pawnless 5-men it typically took 240 sec.