Live data from Hacker News

Number of legal 18x18 Go positions computed. One more to go

tromp.github.io

41–50 of 116 posts

Re: Number of legal 18x18 Go positions computed. One more to go

#41
post #23

Anyone here play? It is pretty much the ultimate boardgame. Its like game-theory the game. From the very start you are embroiled in interesting risk/reward and provoking you opponent to overextending type stuff. Great place to play is gokgs.com I actually cant play many strategy games anymore because I realize this is like go with a load of crap thrown on it. My friend and I call this 'false complexity' the game isnt…

I really enjoy playing go. I found the online platforms burdensome and poor at matching me with beginners of similar experience. For years I've imagined Go bringing the world closer together through a platform that combines use of a physical board with Internet connectivity. Playing in person is so much more gratifying. if anyone would like to simulate this experience together we can Skype play

>poor at matching me with beginners of similar experience

I don't know what server(s) you tried, but unfortunately quite a few of them have a sandbagger problem at the lower ranks. Also the ranking system itself has its inconveniences. The difference between a 19 kyu and a 16 kyu might be nearly negligible, but the difference between a 3 kyu and a 1 kyu is usually not. Coupled with the fact that it takes servers a few games to get an accurate rank, it often makes for a frustrating experience for beginners.

Re: Number of legal 18x18 Go positions computed. One more to go

#42

Anyone here play? It is pretty much the ultimate boardgame. Its like game-theory the game. From the very start you are embroiled in interesting risk/reward and provoking you opponent to overextending type stuff. Great place to play is gokgs.com I actually cant play many strategy games anymore because I realize this is like go with a load of crap thrown on it. My friend and I call this 'false complexity' the game isnt…

I love Go. But from a game-theoretic view it is theoretically rather trivial, as are chess, checkers, and any other game in which players with perfect information alternate moves. The winner of a Go game is whoever more reliably predicts the ultimate result of various potential intermediate positions. The only interesting game theoretic aspects at all arise to the extent one can predict one's opponents' likely errors…

Actually, go has some deep complexity that chess and checkers do not have, primarily from the idea of "ko".

Read "Mathematical Go".

https://math.berkeley.edu/~berlek/cgt/gobook.html

Re: Number of legal 18x18 Go positions computed. One more to go

#43

Anyone here play? It is pretty much the ultimate boardgame. Its like game-theory the game. From the very start you are embroiled in interesting risk/reward and provoking you opponent to overextending type stuff. Great place to play is gokgs.com I actually cant play many strategy games anymore because I realize this is like go with a load of crap thrown on it. My friend and I call this 'false complexity' the game isnt…

I love Go. But from a game-theoretic view it is theoretically rather trivial, as are chess, checkers, and any other game in which players with perfect information alternate moves. The winner of a Go game is whoever more reliably predicts the ultimate result of various potential intermediate positions. The only interesting game theoretic aspects at all arise to the extent one can predict one's opponents' likely errors…

Actually, it's interesting in the sense of combinatorial game theory (https://en.wikipedia.org/wiki/Combinatorial_game_theory) not the branch of decision theory for interactive rational agents known as game theory (https://en.wikipedia.org/wiki/Game_theory). Two only very distantly related subjects which unfortunately have confusingly similar names.

Re: Number of legal 18x18 Go positions computed. One more to go

#44
post #42

Earlier quoted context omitted.

I love Go. But from a game-theoretic view it is theoretically rather trivial, as are chess, checkers, and any other game in which players with perfect information alternate moves. The winner of a Go game is whoever more reliably predicts the ultimate result of various potential intermediate positions. The only interesting game theoretic aspects at all arise to the extent one can predict one's opponents' likely errors…

Actually, go has some deep complexity that chess and checkers do not have, primarily from the idea of "ko". Read "Mathematical Go". https://math.berkeley.edu/~berlek/cgt/gobook.html

His point wasn't concerning the complexity, but rather the fact that both players have perfect information about the state of the game.

Re: Number of legal 18x18 Go positions computed. One more to go

#45
post #43

Earlier quoted context omitted.

I love Go. But from a game-theoretic view it is theoretically rather trivial, as are chess, checkers, and any other game in which players with perfect information alternate moves. The winner of a Go game is whoever more reliably predicts the ultimate result of various potential intermediate positions. The only interesting game theoretic aspects at all arise to the extent one can predict one's opponents' likely errors…

Actually, it's interesting in the sense of combinatorial game theory ( https://en.wikipedia.org/wiki/Combinatorial_game_theory ) not the branch of decision theory for interactive rational agents known as game theory ( https://en.wikipedia.org/wiki/Game_theory ). Two only very distantly related subjects which unfortunately have confusingly similar names.

Sorry, did you mean to write "rational rational agents"? If so, why repeat "rational"?

Re: Number of legal 18x18 Go positions computed. One more to go

#46
post #13
post #7

Earlier quoted context omitted.

Of course they are taking symmetries into account. They are including symmetries in their definition of what the different states are, and thus accounting for them in the count, but they absolutely are pruning symmetries in their implementation. Read the draft of the paper ( https://tromp.github.io/go/gostate.ps ) if you're interested in the techniques.

I'm not pruning any board symmetries. So, yes, the 4x4 position with only one Black stone adjacent to a corner would be counted 8 times (with the Black stone at A2 or A3 or B1 or B4 or C1 or C4 or D2 or D3). The only symmetry that the algorithm takes advantage of is color symmetry; but even there nothing is pruned; the count for a color-normalized state is simply doubled.

I apologize. I had skimmed the paper, but not read it in depth, and it was clear that you had considered symmetries (such as Figure 4 in the paper); I assumed, then, that your algorithm would prune symmetries and simply account for them by multiplying the results in each class by the number of symmetries. I hadn't yet finished reading the paper, however.

Re: Number of legal 18x18 Go positions computed. One more to go

#47
post #43

Earlier quoted context omitted.

Actually, it's interesting in the sense of combinatorial game theory ( https://en.wikipedia.org/wiki/Combinatorial_game_theory ) not the branch of decision theory for interactive rational agents known as game theory ( https://en.wikipedia.org/wiki/Game_theory ). Two only very distantly related subjects which unfortunately have confusingly similar names.

Sorry, did you mean to write "rational rational agents"? If so, why repeat "rational"?

Nope, it was a typo; I edited my phrasing a couple of times, and the last edit left two copies of the word. Fixed, thanks.

Re: Number of legal 18x18 Go positions computed. One more to go

#48

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?

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.

Re: Number of legal 18x18 Go positions computed. One more to go

#49
post #31

Earlier quoted context omitted.

Well it "ends" the game but play can resume. Plus, there's the crazy hypothetical play in the way-over-complicated Japanese rules. I think, in theory, you can play multiple almost-compete games after the game is "over". Each hypothetical play is just to resolve one group, as I understand.

Indeed, the Japanese rules are not suitable for mathematical analysis of the game; see https://en.wikipedia.org/wiki/Rules_of_go#Counting_phase That's why our paper "Combinatorics of Go" assumes the so-called Logical Rules at http://tromp.github.io/go.html , which do end a game on consecutive passes.

I would also like to point out, for the benefit of anyone else here (just replying to you to clarify your point), that the Logical Rules referred to are commonly referred to as the Tromp-Taylor Rules, after John Tromp (the submitter and parent commenter) and Bill Taylor, who wrote them up as a simplified version of the New Zealand rules; and that these, in turn, are in the branch of Chinese-style, or area-scoring rules (counting the sum of stones on the board and territory surrounded for score), to contrast with Japanese and Korean style, or territory-scoring rules (counting the sum of territory surrounded minus captured stones for the score).

The reason that rulesets in the Chinese style branch are more amenable to mathematical analysis are that you can play the game until you have an unambiguous result about the life or death of a group, and thus these rulesets usually involve simply resuming the game and playing it out if there is any dispute about whether a group is alive or dead (or, for the logical rules, don't involve resumption at all, you just play it out and score it as is after two passes, with all empty points that reach two colors being counted for no one; since in area scoring games, ending the game before that point is mainly a convention for human players who don't feel the need to play all the way to the point of killing obviously dead groups).

Under Japanese style rules, playing within your territory to kill a disputed group may reduce your own score, so rather than just playing it out to the end, there are an elaborate set of conventions for determining the life or death of particular shapes. This elaborate set of conventions is much more difficult to represent mathematically.

The American Go Association rules of Go have an interesting hack to allow you to use Japanese-style territory scoring, but wind up with the same result as Chinese-style area scoring would give you, by having you actually give your opponent a stone as a capture when you pass, plus making the game-ending passes be two or three passes such that each player has the same number of turns. This preserves the benefit of area scoring, that any dispute on life or death can be resolved by resuming the game and playing it out until the situation is completely unambiguous, while still allowing the somewhat easier method of counting that territory scoring provides (filling in liberties with captured stones, and then just counting the remaining territory, and thus having to actually count to a lower number).

The Tromp-Taylor rules do make some adjustments for the sake of making it even more amenable to analysis that most other rulesets do not, such as allowing suicide. This doesn't actually affect the strategy in very many games, as it's very rare to encounter a situation in which a suicidal move would be the best choice, but it tends to make analysis a bit simpler as there is one fewer constraint to worry about. I feel like allowing suicide is more elegant, but it is only allowed in a few rulesets.

It is unfortunate that for such a simple game, there is no one agreed upon worldwide rule set. There are a couple of different parameters that you can tweak in a ruleset that give you a game that is very similar, but different enough in a few corner cases to make them different games; territory vs. area scoring (and with territory, the large number of conventions on life and death you need to make it work), simple ko vs. situational superko vs. positional superko, suicide vs. no suicide, counting points in seki, and komi (number of extra points for the second player to make up for the first-move advantage).

Re: Number of legal 18x18 Go positions computed. One more to go

#50

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?

iirc the best two pieces of software in the world are approximately 2dan
Post reply on HN