38 ms·

Just because the number of legal positions is computed doesn't mean we're anywhere close to "solving" 18x18 Go, right? What's the utility of computing the numb

Just because the number of legal positions is computed doesn't mean we're anywhere close to "solving" 18x18 Go, right? What's the utility of computing the number of legal positions?

lambda 12y ago
No, nowhere remotely close. This is just a matter of trying to precisely characterize the state space; there are upper and lower bounds that have been established, but it's an interesting computational problem to precisely characterize exactly how many legal positions there are. I think that there's not much utility in this work beyond "it's an interesting challenge," but, well, there's not much utility in any game beyond "it's an interesting challenge."
- deleted 12y ago
  [deleted]
  - sjtrny 12y ago
    Government funding, collaboration with outside companies and IP. Looks like John Tromp was affiliated with CWI (http://en.wikipedia.org/wiki/Centrum_Wiskunde_%26_Informatica http://en.wikipedia.org/wiki/Centrum_Wiskunde_%26_Informatic...), which is funded by the Netherlands gov. Take a look at the "spin off companies" section in the wikipedia article. Often government funded research organisations turn some of their research into products to help fund themselves.
jszymborski 12y ago
something something top-down dynamic programming shuffles on, muttering
placeybordeaux 12y ago
It's just an open problem in combinatorics. Plenty of math doesn't have a specific utility associated with the problems.
joe_the_user 12y ago
Well, it would be interesting problem in combinatorics if you calculated the result in an interesting fashion. Something like numberjack, which uses constraint programming for combinatorial optimization, would be useful and an article about how someone did this would be useful but alas the op is just a dull statement of a result and doesn't have much merit imho.
tromp 12y ago
As George Mallory said when asked "Why did you want to climb Mount Everest?" "Because it's there." The number of legal Go positions is a simply defined number that is easily approximated but an enormous computational challenge to compute exactly. I've made it my Mount Everest:-) I also want to see if the number, written as 19x19 trits in ternary, corresponds to a legal position, which would be totally awesome (but at 1.2% the odds are against it).
vacri 12y ago
Techniques developed to figure out this problem can be used in other fields. Developing them against a 'fact-checkable' issue can help troubleshoot issues, as opposed to using them on a dataset where we don't know what it's supposed to look like.
ep103 12y ago
iirc the best two pieces of software in the world are approximately 2dan
- xcombelle 12y ago
  between 4 and 6 dan is closer to truth
  - ep103 12y ago
    That's extremely impressive. Dang.
joelangeway 12y ago
One example that just occurred to me: The base 2 log of the number of legal positions of a 9x9 go game is about 126.3, which means if I use a good hash of board positions yielding twice that number of bits, I have a better than 50/50 chance of having no collisions. That is very good to know if you've got anything like a transposition table in a Go playing program.
- cstoner 12y ago
  Generally, a Zobrist hashing system is used (which is a specific type of transpositon table) for Go. It's also probably used for chess, but I don't follow chess AIs as closely.
- Someone 12y ago
  You don't really need that precise an estimate. 81 * 2log3 ~= 128.38 So, the number of legal positions is only a factor of about 5 down from the number of positions disregarding life.

Just because the number of legal positions is computed doesn't mean we're anywhere close to "solving" 18x18 Go, right? What's the utility of computing the number of legal positions?

lambda 12y ago

No, nowhere remotely close. This is just a matter of trying to precisely characterize the state space; there are upper and lower bounds that have been established, but it's an interesting computational problem to precisely characterize exactly how many legal positions there are. I think that there's not much utility in this work beyond "it's an interesting challenge," but, well, there's not much utility in any game beyond "it's an interesting challenge."

deleted 12y ago
[deleted]
- sjtrny 12y ago
  Government funding, collaboration with outside companies and IP. Looks like John Tromp was affiliated with CWI (http://en.wikipedia.org/wiki/Centrum_Wiskunde_%26_Informatica http://en.wikipedia.org/wiki/Centrum_Wiskunde_%26_Informatic...), which is funded by the Netherlands gov. Take a look at the "spin off companies" section in the wikipedia article. Often government funded research organisations turn some of their research into products to help fund themselves.

jszymborski 12y ago

something something top-down dynamic programming shuffles on, muttering

placeybordeaux 12y ago

It's just an open problem in combinatorics. Plenty of math doesn't have a specific utility associated with the problems.

joe_the_user 12y ago

Well, it would be interesting problem in combinatorics if you calculated the result in an interesting fashion. Something like numberjack, which uses constraint programming for combinatorial optimization, would be useful and an article about how someone did this would be useful but alas the op is just a dull statement of a result and doesn't have much merit imho.

tromp 12y ago

As George Mallory said when asked "Why did you want to climb Mount Everest?" "Because it's there." The number of legal Go positions is a simply defined number that is easily approximated but an enormous computational challenge to compute exactly. I've made it my Mount Everest:-) I also want to see if the number, written as 19x19 trits in ternary, corresponds to a legal position, which would be totally awesome (but at 1.2% the odds are against it).

vacri 12y ago

Techniques developed to figure out this problem can be used in other fields. Developing them against a 'fact-checkable' issue can help troubleshoot issues, as opposed to using them on a dataset where we don't know what it's supposed to look like.

ep103 12y ago

iirc the best two pieces of software in the world are approximately 2dan

xcombelle 12y ago
between 4 and 6 dan is closer to truth
- ep103 12y ago
  That's extremely impressive. Dang.

joelangeway 12y ago

One example that just occurred to me: The base 2 log of the number of legal positions of a 9x9 go game is about 126.3, which means if I use a good hash of board positions yielding twice that number of bits, I have a better than 50/50 chance of having no collisions. That is very good to know if you've got anything like a transposition table in a Go playing program.

cstoner 12y ago
Generally, a Zobrist hashing system is used (which is a specific type of transpositon table) for Go. It's also probably used for chess, but I don't follow chess AIs as closely.
Someone 12y ago
You don't really need that precise an estimate. 81 * 2log3 ~= 128.38 So, the number of legal positions is only a factor of about 5 down from the number of positions disregarding life.