9 ms·
Number of legal Go positions computed
- tromp 11y agoPrevious discussion at https://news.ycombinator.com/item?id=9167781 https://news.ycombinator.com/item?id=9167781
- Someone 11y agoThat discussion is worth reading, but looking at the title of the HN article, it was about the earlier result for a 18x18 board. This is a new result for the 19x19 board that appears to use the same URL.
- horsecaptin 11y agoDoes this mean that a computer will soon be beating people at Go?
- deleted 11y ago[deleted]
- yiyus 11y agoNo. This gives us some more information about how difficult the problem is, but it is not a solution.
- muddyrivers 11y agoI doubt it. Here are my thoughts. At the beginning level, players must learn and memorize a large number of Dingshi, which means fixed patterns. Their scopes are small, restricted to less than 30 cross points, if my memory serves right. They mostly happen in the corners or close to the borders, which helps greatly reduce the complexity. If one masters these Dingshi, s/he can easily beat ~90% players based on my experience. This part of the game can be done easily by computers. The next level is to develop skills or feels to identify Xing, which refers to larger patterns. They are still constrained to a small area, like 1/8 ~ 1/6 of the whole board. They are further away from the corners and the boarders. So the complexity increases dramatically. Most players of intermediate level can feel if a Xing is good or not, but not many of them knows why. So s/he develops the intuition, but not the actual skills and insights. That means, if two Xings can be developed from the current state and both feel good, they can't tell which is better in most cases. In reality, there could be dozens of good Xings developed from the current state, and one also needs to consider the potential moves of the opponents. Due to the complexity, the vast majority of players can't go beyond this level no matter how hard they work on. It is like it requires a combination of talent, personality and hard work to become a top mathematician or a NBA starter. The next level requires one's skills and insights to understand Shi, which includes strategy of the whole game, potential, etc. It is to develops the skills and feeling on the whole board. It is to develop accurate calculation on the potential covering area of the existing stones and how strong the potential is. It asks the questions that how synergetic are two regions of your stones , although they may look far apart at present. At this level, players pay great attention to the beginning stage of the game. The board is vastly empty, so the complexity is the highest. The potential gains or losses can be huge. One must consider the opponent's playing history to take fully advantage. It happens often to the players who enter the early stage of this level that they realized in the later stages of the game that one stone should have been placed one position left or right or higher. This initial stage is called Buju. I think computers can get to the second level but it looks very hard to get to the third level in the next 10 years. Keep in mind that there are big differences in term of one's skills and insights even within the highest levels. For amateur players and low level professionals, they are way beyond their understanding. Even it is explained a move would be better if placed just one spot left, they wouldn't understand it.
- dragontamer 11y agoNote that Go computers have exponentially gotten stronger through the monte-carlo method. The most advanced Go computers simply "test" various moves by playing billions of games to completion, and then uses that to test the "probability of winning" with a particular move. In short: use Bayesian logic against the following question: "Calculate the probability of winning given that I've moved a stone at X location". Use monte-carlo to attempt to estimate hard numbers. I'm not familiar with your terminology... my school of Go uses the term "Tesuji" (Japanese) to describe what you seem to call "Dingshi" (sounds like a Chinese name to me...). In any case, a computer with strong Tesuji (or maybe Dingshi in your terminology), combined with a monte-carlo method to look for "long-term strategic" moves is what has gotten Go Computers to where they are today. Humans are superior at parallel processing. Go players activate the brain region of vision, and literally think by seeing the board state. A lot of Go study is seeing patterns and shapes... 4-point bend is life, or Ko in the corner, Crane Nest, Tiger Mouth, the Ladder... etc. etc. Go has probably been so hard for computers to "solve" not because Go is "harder" than Chess (it is... but I don't think that's the primary reason), but instead because humans brains are innately wired to be better at Go than at Chess. The vision-area of the human's brain is very large, and "hacking" the vision center of the brain to make it think about Go is very effective.
- hosh 11y agoSide note, "dingshi" is probably 定式 in Chinese, same hanzi/kanji that is pronounced "joseki" in Japanese. Xing is likely 行 or 形, either having the meaning-sense of "shape" and "motion". Shi is 勢, a very old word used in many different fields. It is used in the Chinese military lingo describe the structure and posturing of the battlefield, and Sun Tzu devoted a whole chapter of the Art of War to discuss it. It's used in Chinese martial art to describe a posture and all of it's potential and projections of power, similar to the Japanese martial art term "kamae". Considering that the generals and leaders of ancient China also used Weiqi to hone their strategic thinking skill, not surprising 勢 is used to refer to whole-board vision.
- tasuki 11y agoPlease note that this article concerns the number of legal positions, not the number of legal games. The number of legal games is much higher, with a lower bound at googolplex, ie 10^(10^100). See: https://matthieuw.github.io/go-games-number/GoGamesNumber.pdf https://matthieuw.github.io/go-games-number/GoGamesNumber.pd...
- pmontra 11y agoThis result is not related to AI. However a new pro-vs-computer match has been announced today for February 6. Japanese original http://www.nihonkiin.or.jp/event/area/other/post_704.html http://www.nihonkiin.or.jp/event/area/other/post_704.html Google translation https://translate.google.com/translate?hl=en&ie=UTF8&prev=_t&sl=ja&tl=en&u=http://www.nihonkiin.or.jp/event/area/other/post_704.html https://translate.google.com/translate?hl=en&ie=UTF8&prev=_t... The translation is pretty bad on technical terms. Obviously it's not about chess or shogi, but about go, and the "ten stage" should be the Tengen title, currently held by Ida Atshushi, the human player. I think this is the first time a Japanese title holder plays in one of these matches. It will be a 4 stone match. If the computer wins it should be at least 5 dan, maybe 6 dan (amateur scale). One should be at least 7 dan to be as strong as the weakest pros.
- tunesmith 11y agoThanks for clarifying amateur vs pro - it's easy to overlook the fact that dan levels are completely different when comparing amateur and pro. Is it that 7 dan amateur is roughly comparable to 1 dan pro?
- igravious 11y ago30kyu -> 1kyu (amateur) 1dan -> 9dan (amateur) 1dan -> 9dan (pro abbrev. to 1p -> 9p) I think 8d ama can start to have competitive games with 1p or 2p... I mean they're getting into the same ball-park in terms of strength but averaged out over time a rank above _will_ beat a rank below, that's why they are in the ranks they are in after all :)
- 33a 11y agoDoes this take into account the super ko rule? If so, seems a bit small. EDIT: Never mind, no it doesn't.
- tasuki 11y agoKos aren't relevant in any way when evaluating the validity of a board position. (They're only relevant when evaluating validity of move sequences.)
- daveloyall 11y agoA note for the author and new readers: L19 means "the number of legal positions for a 19x19 board". cf. L18 which means "the number of legal positions for an 18x18 board". L19 does NOT mean position L:19 on the Go board. :)
- Alex3917 11y agoThe fact that the number of valid positions is 19 x 19 in base 3 is wild. You'd have to be almost dan-level to immediately recognize that the pic above isn't actually a real game.
- 3JPLW 11y agoThere are four leading zeros, meaning that there are 19x19-4 (or 357) base three trits. Still remarkably close.
- tasuki 11y agoIt doesn't look like a real go game any more than randomly sprinkling chess figures on a chess board would :)
- jmount 11y agoThe linked paper seemed really clear (I don't play Go, but I do study dynamic programming algorithms). So it may not pop out unless you play- but it looks like the black stones at Q2-R2 falsify the board (as they have no air holes). Actually I think the simplicity of the legality rule makes this even more interesting.
- tromp 11y agoQ2 and R2 are part of a 9 stone black group that has 4 liberties
- dragontamer 11y agoNot really. The T19 stone makes no damn sense, there's literally no reason to put a stone there. The T1 stone is an "empty triangle" AND in the corner, and only serves to weaken that position. The A1 / B1 stones are also worthless, and only serve to weaken white's position. When I played seriously, I was only 14 Kyu (many years ago) and I immediately recognized that the board was not a real game. I'd imagine that any 10 to 20 Kyu player (very weak ranking, probably equivalent to D-rank players in Chess) would immediately recognize that the "game" in the picture was wrong.
- tel 11y ago
- schoen 11y agoNeat, is this sequence in OEIS?
- 3JPLW 11y agoYes: https://oeis.org/search?q=1%2C57%2C12675&sort=&language=english&go=Search https://oeis.org/search?q=1%2C57%2C12675&sort=&language=engl...
- schoen 11y agoCool! It looks like OEIS only lists terms up to n=14, but they seem to be getting them directly from the researcher who did the computation, so hopefully it will be updated in the future.
- hendekagon 11y agoTromp's website is a treasure-trove of really cool things
- Fargren 11y agoI played very little Go a very long time ago, so I don't know this: could there be any legal positions that aren't reachable by any legal moves?
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- tromp 11y agoNo; you can reach any legal position by just playing all its stones and passing for the side that's done placing its stones.
- tetraodonpuffer 11y agoas a benchmark it seems would be interesting to port this to java/scala and running it on a spark cluster, since it's map-reduce from the post (didn't look at the code) it should be possible I would think
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- tromp 11y agoIt's the factorization of L19 that took mere hours. Its computation took tens of thousands of hours...
- pavel_lishin 11y agoCan someone explain why factoring L19 is relevant?
- tromp 11y ago1. It's become a tradition, at least for counting legal positions in Go 2. there are surprising similarities between the runtime complexities of dumb and smart algorithms for counting and factoring
- ultramancool 11y agoTo make sense of big numbers like this where any state is valid, I find it good to compare with cryptographic key sizes, so in case anyone else is wondering: log_2(L19) = 565 bits
- dragontamer 11y agoChess is also a great game to compare against, since these numbers have been computed for chess many years ago. https://en.wikipedia.org/wiki/Shannon_number https://en.wikipedia.org/wiki/Shannon_number 10^43 is the approximate number of chess positions. In contrast, 19x19 Go has approximately 10^170 positions.
- Houshalter 11y agoMost people would probably find decimal digits more intuitive than binary digits. Which the article says is 171. And even writes them all out to give a sense of how huge that number is.
- richard_todd 11y agoDoes 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.
- tel 11y agoAs I remarked elsewhere, what was more interesting to me was that the 2x2 board has hundreds of billions of games (assuming a superko, I suppose). It's easy to recognize that there must be a lot of them, but hundreds of billions is absurdly fast growing. As another data point, the 2x1 board has 8 games.
- sago 11y agoThere are billions of valid games on a 2x2 board? Can anyone explain or link to something that explains how this is possible?
- tromp 11y agoa single 2x2 game can visit as many as 48 of the 57 legal 2x2 positions, with many dozens of passes in between moves, and obviously many captures. This page http://tromp.github.io/java/go/twoxtwo.html http://tromp.github.io/java/go/twoxtwo.html on solving 2x2 go with various search methods may be helpful. I've lost track of my original 2x2 game counting code but suspect it was a close relative of this code.
- sago 11y agoWow, okay, thanks. I've a better respect for why Go is so hard to minimax now.
- Anderkent 11y agoIt's likely because a player might pass his move at any point; the game only ends when two players pass. So you don't need that many possible positions for a huge amount of possible games.
- fargo 11y ago. . . . | B . . . | B . W . | B B W . | . . W W | B . W W | B B . . | B B W . | B B . B | . . W . | . B W . | B B W . Loops are possible in a 2x2
- Anderkent 11y agoA move that returns to a previous board position is illegal, AFAIK. http://senseis.xmp.net/?TrompTaylorRules http://senseis.xmp.net/?TrompTaylorRules : 6. A turn is either a pass; or a move that doesn't repeat an earlier grid coloring
- tel 11y agoLoops are usually disallowed intentionally in this sort of thing, the so-called "superko" rule.
- cinquemb 11y agoAlthough the determinate of that matrix = 0, and if it's conjugate transpose determinant is non zero then I wonder if all valid possible configurations on this board can be represented by a complex lie group? Edit: did the work, it does, but too lazy to describe the group https://gist.github.com/cinquemb/18e494348045725e2b60 https://gist.github.com/cinquemb/18e494348045725e2b60
- awl130 11y agohttps://en.wikipedia.org/wiki/List_of_top_title_holders_in_Go https://en.wikipedia.org/wiki/List_of_top_title_holders_in_G...
- joeyh 11y agoI wonder what's the smallest Go board such that the number of legal positions is a legal position? (Not expecting an answer anytime soon.)
- tromp 11y agoMy previous writeup of the L18 result at https://web.archive.org/web/20150310085851/http://tromp.github.io/go/legal.html https://web.archive.org/web/20150310085851/http://tromp.gith... answers your question: "only L2, L3, L7 and L10 can be represented as legal positions themselves", graced with a picture of L10. L2=57 is 2010 in ternary, which looks like O . X .
- chch 11y agoIt seems like 2x2's 57 legal positions, which becomes 2 0 1 0 in ternary, is a legal position. :)
- fiatjaf 11y agoWhy would anyone waste time calculating this? You may be curious, but you're not living to satisfy useless curiosity.
- jwmerrill 11y agoHacker News' charter (from the guidelines): "anything that gratifies one's intellectual curiosity."
- tel 11y agoMaybe it's a legal position if the numbers spiral out from the center. Or, more precisely, I'd be okay with any sort of "nice" arrangement of digits which made it work.