Sunday, 12 June 2011

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.

2 comments:

  1. Interesting post! We seem to take CPU cores for granted these days. The i5 and i7 chips are great leaps in hyperthreading, but then hardware is only as good as the software controlling it all.

    ReplyDelete
  2. You should look into CUDA. GPU's are made for massively parallel operations.

    ReplyDelete