h.g.muller wrote:I did a kind of back-of-the-envelope calculation on what would be needed to build 6-men pawnless bitbases entirely in RAM. A pawnless 6-men has 8G positions. The idea would be to keep this in RAM as compressed data, and use my slice-by-slice algorithm for the generation, packing and unpacking the data from and to a fixed-length encoded buffer (allowing random access) capable of holding a single slice. This buffer could then use a 4-bit encoding, one bit for the wtm state (won or non-won), and 3 bits for btm state (undecided, non-lost (= permanent escape), lost in current cycle, lost in previous cycle, lost earlier, with 3 spare codes).
A simple Huffman coding scheme would distinguish the 10 states (combined wtm and btm) by codes 0, 10, 1100, 1101, 11100, 11101, 11110, 11111, in decreasing frequency. The code 0 would initially be assigned to undecided & non-won, which is about 60% of the TB in the early cycles, while 10 would be undecided & non-won (about 30%). As the number of won positions would increase during the building, at some point it would be better to change to 0 = undecided & won, 10 = lost earlier & won. The fraction of positions lost in current or previous cycle will be pretty small at any stage, and these will get the 5-bit codes. Typical frequencies occurring during TB building then would compress the data to about 1.7 bit per positions, meaning the thus compressed TB would take up 1.7GB of RAM.
If we are building 2+4, we would do it in 1+4 slices (alternately keeping the first or second white piece fixed). Such a slice would have 1G positions (a slice has in general no symmetry, as the fixed piece breaks it). Thus with 4 bits per position, it would require a 0.5G buffer. This brings the RAM requirement to above 2GB. I am not sure if better compression could get it down so much that it could be done in a machine with only 2GB of RAM. (These estimates are for end-games with all different pieces; as soon as there is exchange symmetry of identical pieces, or as soon as Bishops or other color-bound pieces are involved, the size would reduce so much that it would easily fit.)
For 3+3 life is much easier: we could do that in 1+3 slices, and the slice buffer would only need 16M positions = 8MB. With the main TB in RAM, the fact that we have to do two passes per cycle if we split the cycle in 3 passes (one for each white piece), in stead of a single pass, is probably not that much of a performance hit. If one of the pieces is factorizable, like the Rook, we could do it in 1.5+3 slices, reducing the number of passes per cycle again to 1, but now requiring a slice buffer of 64MB, which is still small enough to make it fit next to the main TB in 2GB. If there is no Rook, we could make use of the fact that a King (which will always be amongst the white pieces) does not need a full slice buffer, but can be treated as a 'streaming slice' in a buffer of 21/64 of the normal size (so 0.17 GB). This might make it possible to do all 3+3 in 2GB.
For 4+2 life is very easy, as we can do it in 2+2 slices, requiring only one pass per cycle, and an 8MB slice buffer. 5+1 bitbases are not really of interest, as they are all completely won. (Well, if you don't count things like KBBBBK with all B on the same color, which are completely drawn.) Similarly 1+5 will never have any won positions for the bare King. SO it is really only the 2+4 which might not be doable in 2GB (but no problem in 3GB). At least, not which such a simple Huffman compression.
First of all: 6-men have 64G positions
But exactly in such a case, where we need to save as much space as possible we should do at least the easiest index-optimizations:
462*62*61*60*59 = 5.76G positions
5.76 * 1.7/8 = 1.22G space required
But I think that as soon as you can store everything in RAM other algorithms could be used. I for myself am only looking for a new way of generating bitbases, as my RAM cant hold 6-men at once. But in general, the algorithm I used only takes 2 bit per position without any compression (could be reduced to 1 bit, but the second bit gives a speedup)
I think I introduced it in some other part of this board anyway:
First one retrograde white move (from a btm-white-wins position) then one retrograde black move and finally verifying the position as won for white by checking all possible black moves and see if they lead to a wtm-won position. As soon as another btm-white-wins position is found do the same again.
So it would take 5.76 * 2/8 = 1.44G RAM
If you hold everything in RAM you dont have to distinguish between lost in current cycle, lost in previous cycle and lost earlier, as the structure falls away if you can use recursive programming.