Can we solve Ataxx?

Information in a 7x7 board: log(3^49)/log(2) = 77.66 bits, too many to fit into a 64-bit register.

Storing the value of each Ataxx position would require at least 2^77.66 trits (win, lose, or draw), which would require an insane amount of storage. No, naive brute force is crazy. But we could work "outside-in" - evaluating the fullest boards and storing their values in a table, then truncating a forward search whenever we hit one of these.

How many of these full boards are there? If n = number of gaps, m = number of black pieces, then there are 49!/(n!*(49-n)!) ways to distribute the gaps, and (49-n)!/(m!*(49-n-m)!) ways to distribute the black pieces around the gaps, for a total of 49!/(n!*m!*(49-n-m)!) positions with a given n gaps and m black pieces.

Interestingly, even a naive list of position values compresses really, really well:

berndj@capybara:~/anthraxx$ ./bruteforce |head -100000000 |bzip2 -c9 |wc

858 2691 107495

That's 100000000 trits (win, lose, or draw) compressing to 107495 bytes: a compression ratio of 184. All information should compress so well! I expect that with clever enumeration sequences, one can improve this compression ratio even more. Ternary Gray code anyone?

Some examples:

n m #positions raw_storage compressed_storage

0 20 28277527346376 7TB 38GB

0 30 18851684897584 5TB 26GB

1 20 820048293044904 205TB 1114GB

1 30 358182013054096 90TB 487GB

5 20 3358097760018881880 840 PB 4.6PB

5 30 219207391989106752 55PB 298TB

I've made a graph of compressed storage vs m, for n = 3. I didn't bother with m > 23 as the numbers are symmetrical about m = 23. It's clear that motivated wealthy individuals are able to store the values of all positions with only a few gaps, say, no more than 3.

Now how long might it take to populate such a vast table?

berndj@capybara:~/anthraxx$ time ./bruteforce |head -100000000 >/dev/null

real 0m34.547s

user 0m34.930s

sys 0m0.350s

Bear in mind that this is just a naive implementation of what is likely to be a very bitbashing-friendly computation (Ataxx was designed to be easier for computers to compute than for humans!) Furthermore, populating this table is embarrassingly parallel - I haven't even used all four of my poor little laptop's CPU cores. By my estimation I could populate the 3 gaps, 23 black table in no more than 66 years. Probably a lot quicker if I spend just another hour teaching bruteforce.c a better representation of board positions, and using a popcount instruction that may or may not exist on my CPU. I'm quite optimistic about even a modest effort being able to muster the CPU power to populate this precious lookup table. There's a caveat here though: this relatively cheap seed table must hold values only for stalemate positions. Completely full boards are all finished, but but only some boards with gaps are stalemated. I should probably adjust the storage requirements about 30% upwards to allow the table entries to encode the fact that the value is unknown - to be filled in later during a forwards search.