4 ms·

Indeed, enumerating all 208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 6281285460898883144

by tromp 11y ago

Indeed, enumerating all 208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935 positions in Go is impossible.

dogecoinbase 11y ago
In your enumeration, what's the board look like at position 348277381979984699478633344862652779770286522453884530548425639456820927419612?
- Jyaif 11y ago
  1/ Convert the number to base 3. 2/ Each digit represents an intersection on the goban, assuming the following mapping: 0 = no stone, 1 = black stone, 2 = white stone.
  - tromp 11y ago
    That would work for all positions regardless of legality, which are in 1-1 correspondence to {0,1,2}^(19*19). The count above is for legal positions only, i.e. those where every connected group of stones is adjacent to an empty point.
- tromp 11y ago
  I can't say, because I didn't enumerate them. I only counted them. See http://tromp.github.io/go/legal.html http://tromp.github.io/go/legal.html for the method used, which is a form of dynamic programming.
  - nhaehnle 11y ago
    Though if it is dynamic programming, then it should be possible for you to answer dogecoinbase's question using not much more computational power than you used to count them in the first place, right? If you think of dynamic programming as counting the number of paths in a directed graph (in this case, from skimming the paper, the nodes correspond to border states), then given a path number, you can trace the path backwards through the graph, as long as you remember the number of paths ending in every vertex.
    - tromp 11y ago
      Yes, you could if you preserved all intermediate counts. But the graph I used has 362 layers each of which can have up to 363 billion nodes, so I had to recycle the space used for the counts (4TB per layer). Also, I didn't even compute with full counts. I reconstructed them using the Chinese Remaineder theorem from 9 separate modular counts. So, yes it's possible, but highly impractical...
ChristianBundy 11y ago
That's called "counting". Enumeration is iterative.

by tromp 11y ago

dogecoinbase 11y ago

In your enumeration, what's the board look like at position 348277381979984699478633344862652779770286522453884530548425639456820927419612?

Jyaif 11y ago
1/ Convert the number to base 3. 2/ Each digit represents an intersection on the goban, assuming the following mapping: 0 = no stone, 1 = black stone, 2 = white stone.
- tromp 11y ago
  That would work for all positions regardless of legality, which are in 1-1 correspondence to {0,1,2}^(19*19). The count above is for legal positions only, i.e. those where every connected group of stones is adjacent to an empty point.
tromp 11y ago
I can't say, because I didn't enumerate them. I only counted them. See http://tromp.github.io/go/legal.html http://tromp.github.io/go/legal.html for the method used, which is a form of dynamic programming.
- nhaehnle 11y ago
  Though if it is dynamic programming, then it should be possible for you to answer dogecoinbase's question using not much more computational power than you used to count them in the first place, right? If you think of dynamic programming as counting the number of paths in a directed graph (in this case, from skimming the paper, the nodes correspond to border states), then given a path number, you can trace the path backwards through the graph, as long as you remember the number of paths ending in every vertex.
  - tromp 11y ago
    Yes, you could if you preserved all intermediate counts. But the graph I used has 362 layers each of which can have up to 363 billion nodes, so I had to recycle the space used for the counts (4TB per layer). Also, I didn't even compute with full counts. I reconstructed them using the Chinese Remaineder theorem from 9 separate modular counts. So, yes it's possible, but highly impractical...

ChristianBundy 11y ago

That's called "counting". Enumeration is iterative.