4 ms·
Does anyone try to count equivalence classes (after rotation or reflection) instead of raw board positions? To my mind, that would also be of interest if you w
by richard_todd 11y ago
Does anyone try to count equivalence classes (after rotation or reflection) instead of raw board positions? To my mind, that would also be of interest if you want to know how many actually distinct game situations there are. I guess as a rough under-estimate you'd just divide the count by (4 rotations * 2 reflections)?
- tromp 11y agoThat estimate would be equally precise and rough, in that the first 85 of 170 digits would all be correct. Correcting the last 85 digits amounts to counting all positions with various symmetries, which would be as big an undertaking as computing L19, but a whole lot messier..
- qwerty1793 11y agoSorry, but how did you compute this? Do you know that there are less than 10^85 board positions which have a symmetry?
- tromp 11y agoThe bulk of symmetric positions are those with 180 degree rotation or reflection symmetry, and there are at most 3^{10x19} of those (I had mistakenly bounded it as 3^180). So it's actually less than 10^90, meaning that L19/8 is correct in the first 80 digits.
- comboy 11y agoI think there are two more reflections on diagonals. Plus you can switch colors (although with komi that's technically not the same position). But if we are thinking real game then for some positions there is one more dimension with information which KO cannot be played at the moment (I don't think they included that in the computation).
- tromp 11y agoYou're confusing the number of reflections (4) with the increase in size from the cyclic rotation group of size 4 to the dihedral group of size 8 (a factor of 2). Note that any reflection can be decomposed into a fixed reflection followed by a rotation.