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