Number of legal Go positions computed | Hacker News Reader

Number of legal Go positions computed

tromp.github.io

213 pointstromp67 comments

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)?

That 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..

Sorry, but how did you compute this? Do you know that there are less than 10^85 board positions which have a symmetry?

The 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.

I 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).

You'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.

I 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?

No; you can reach any legal position by just playing all its stones and passing for the side that's done placing its stones.

A 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. :)

The 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.

There are four leading zeros, meaning that there are 19x19-4 (or 357) base three trits. Still remarkably close.

It doesn't look like a real go game any more than randomly sprinkling chess figures on a chess board would :)

The 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.

Q2 and R2 are part of a 9 stone black group that has 4 liberties

Not 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.

As someone who plays currently and is very far away from dan... this board is immediately random looking.

There are only 3^289 possible configurations of pieces on the board, so the fact that the number of legal configurations fits in a 289-digit ternary number is kind of trivial.

Yeah, I'm surprised more comments aren't pointing this out. To spell it out further:

> the number of valid positions [of a game on a 19 x 19 board] is 19 x 19 in base 3

This statement is true when replacing 19 with any number, since the number of legal and illegal configurations is exactly 3^(n*n).

I would say no more than 10kyu (eg a14 a15)

The fact that it is 19x19 in base 3 is not that suprising. If you visualize all possible positons (legal or not) then you have 19x19 board of 3 states (black, white, note). So it's 3 * * (19 * 19). Which is 1 and 19 * 19 zeros in base 3. Only some of these positions are legal so the number is lower - quite a bit, that's why there are leading zeros in top left.

A1 and b1 too

As 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.

Table 7 on page 30 of our paper shows 9 games for 2x1. Did you forget the shortest game "pass pass"? The number of non-empty games is even, according to the color of the first stone played.

Yup, forgot pass-pass!

There are billions of valid games on a 2x2 board? Can anyone explain or link to something that explains how this is possible?

a 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

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.

Wow, okay, thanks. I've a better respect for why Go is so hard to minimax now.

It'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.

. . . . | 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

A move that returns to a previous board position is illegal, AFAIK.

http://senseis.xmp.net/?TrompTaylorRules : 6. A turn is either a pass; or a move that doesn't repeat an earlier grid coloring

Loops are usually disallowed intentionally in this sort of thing, the so-called "superko" rule.

Isn't it generally a rule that the game board can never be returned to a state it was previously in?

Generally the rule is that you can't return the board to the position it was last in, but some rule sets extend it to any position it was ever in to avoid a few pathological scenarios. Without this infinite loops can exist.

If it was because of loops, wouldn't there be infinite games?

Previous discussion at

https://news.ycombinator.com/item?id=9167781

That 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.

To 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

Chess 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

10^43 is the approximate number of chess positions. In contrast, 19x19 Go has approximately 10^170 positions.

Most 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.

Tromp's website is a treasure-trove of really cool things

Although 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

Does this take into account the super ko rule? If so, seems a bit small.

EDIT: Never mind, no it doesn't.

Kos aren't relevant in any way when evaluating the validity of a board position. (They're only relevant when evaluating validity of move sequences.)

Neat, is this sequence in OEIS?

Yes: https://oeis.org/search?q=1%2C57%2C12675&sort=&language=engl...

Cool! 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.

They couldn't fit more terms on the A094777 page, but it links to a more complete table at https://oeis.org/A094777/b094777.txt which will soon be updated with the 19x19 result.

Congratulations on your results.

Does this mean that a computer will soon be beating people at Go?

No. This gives us some more information about how difficult the problem is, but it is not a solution.

I 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.

Note 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.

Side 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.

Please 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.pd...

This 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

Google translation 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.

Thanks 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?

30kyu -> 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 :)

Can someone explain why factoring L19 is relevant?

1. 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

I wonder what's the smallest Go board such that the number of legal positions is a legal position?

(Not expecting an answer anytime soon.)

My previous writeup of the L18 result at

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 .

It seems like 2x2's 57 legal positions, which becomes

2 0

1 0

in ternary, is a legal position. :)

https://en.wikipedia.org/wiki/List_of_top_title_holders_in_G...

Maybe 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.

as 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

Why would anyone waste time calculating this? You may be curious, but you're not living to satisfy useless curiosity.

Hacker News' charter (from the guidelines): "anything that gratifies one's intellectual curiosity."

Reply on news.ycombinator.com