Number of Possible Outcomes of a Game
MarkD: Moved from the Sandbox page.
MEIJIN TOUYA: Hey, just wondering (I can't think of anywhere else to ask this), but can you give me a number in scientific notation that expresses the number of possible outcomes of a game? I remember it's really huge, and one guy said that there was more possible outcomes than the number of molecules in the known universe. Can anyone give me a formula for this? :) Thanks
Confused: For a game there are only a few possible outcomes:
If you want to split it down further, you can give the reason why a player wins and by how much. This would probably add another few hundred possible outcomes like:
- ... wins by resignation
- ... wins on time
- ... wins by 0.5 point
- ... wins by 1 point
- ... wins by 1.5 points
- etc.
For some rules without a way to deal with superko this list may be infinite, although there's probably no practical use for that gem of knowledge.
The question how many legal positions are there is a lot harder. The absolute upper limit is 3^361 which is roughly 10^172. Quite a lot of these positions are illegal, so the real number is smaller, but finding a good estimate on how much smaller isn't trivial.
Scryer: If a sizeable fraction of these positions are legal, we could get an estimate by randomly spraying B/W/empty on a board and checking the result to see whether it's a legal position, repeating as long as we have patience for it. There's no a priori reason to think the overall proportion would be different from a random sample, is there?
Scryer: I went ahead and did this experiment today (7 Aug 2003). On a 19x19 board with the me randomly assigned to white, black or empty, in my first run 1.18% of 260,000 positions were legal (that is, no stones of either side were totally surrounded). In my second run, 1.22% of 620,000 positions were legal. In my third run, 1.195% of 45,500,000 were legal. I submit that this constitutes some evidence that the actual number of legal positions is near 10^170 -- much greater than the estimated number of particles in the universe (assuming it's finite) even including zero-mass particles such as photons and (if they're really zero-mass) neutrinos. For comparison, my program claims about 48% of 5x5 positions are legal, 24% of 9x9 positions are legal, and 9% of 13x13 positions are legal. I also checked 2x2 by hand: of the 81 possible positions, 57 are legal, and can be reached in actual play (e.g. a1, pass, a2, pass, b1, pass, pass). This matches the 0.704 value the program claims.
Check out Maximum Number Of Live Groups for another 'ultimate' question...
Imperator?: "On a 19x19 board, there are about 4.63x10^170 possible positions and about 10^360 possible games. (By contrast, the number of legal positions in chess is estimated to be between 10^43 and 10^50, and physicists estimate that there are not more than 10^90 protons in the entire universe.)" from the ![[ext]](images/extlink.gif)
Wikipedia
Scryer: The number of possible positions given in this article is certainly the same order of magnitude of my estimate, which is 3.39x10^170 possible positions. I'm confident of at least two digits of accuracy in my estimate given my assumptions above, but I don't know what assumptions the Wikipedia author has made. I think my assumptions (that there are no captured pieces on the board) should correctly reflect the number of possible positions, but I'm willing to listen to reason. In any case, the numbers are close enough and big enough that it doesn't make a difference.
John Tromp On October 13, 1999, I posted the following in a rec.games.go thread on "Number of Legal Go Positions."
my program gives the following counts:
- 1x1: 1 legal, 2 illegal, prob 0.333333
- 2x2: 57 legal, 24 illegal, prob 0.703704
- 3x3: 12675 legal, 7008 illegal, prob 0.643957
- 4x4: 24318165 legal, 18728556 illegal, prob 0.564925
- 4x5: 1840058693 legal, 1646725708 illegal, prob 0.527724
anything larger requires approximation:
- 9x9: prob 0.235
- 13x13: prob 0.087
- 19x19: prob 0.012
(the C programs are available on request)
John Tromp Earlier in 1999, in a thread on "Math and Go", I found a lower bound on the number of possible legal games in Go on 19x19:
1) Partition the board in three sets B,W,E with the properties
|B|=|W|=103, |E|=155, each set is connected, and each point in E is adjacent to both B and W.
2) Consider all N=2^155 subsets of Black stones on E,
and order them in a sequence 0=S_0,S_1,...,S_{N-1} such that
every two consecutive subset differ by only one Black stone
(eg take your standard 155 bit Gray code).
3) A game can now be played as follows:
for i=1 to N-1 do
if |S_i| = |S_{i-1}| + 1 then black plays to S_i
else // it must be that |S_i| = |S_{i-1}| - 1
white plays on all of W in one of 103! ways and occupies
E \ S_i, thereby capturing all of black, while black passes
white plays on the point S_{i-1} \ S_i
black plays on all of B in one of 103! ways and occupies S_i on E,
thereby capturing all of white, while white passes
endif
4) No position is ever repeated
Note that |S_i| = |S_{i-1}| - 1 can be chosen to hold half the N times, and each of these gives 103!^2 choices. The number of possible games on 19x19 is therefore > 103!^2^155 > 2^2^164. Each of these games lasts for 207*(2^155-1) moves.
ilan: In fact, E does not have to be connected for this to work, which is good, since I believe that it cannot be connected and satisfy the criteria of condition 1).
ALGA : There is a french article at Quebec go association web site :
He compares chess and go...
Scryer: There's a thread in rec.games.go (2003-08) about the possibility that quantum computers can sort out the whole lot, no matter how big the numbers are. I haven't studied quantum computers in general, but in my field (cryptography) they aren't magic in this way: it's expected that a suitably large quantum computer could dramatically reduce the level of effort in factoring numbers, to the point where one would need to double the size of keys to get the same level of protection... which is, of course, straightforward. I believe there's currently a project afoot that will (with considerable expense and hardware) allow the researchers to factor any 4-bit number, including 15! I think it unlikely that magic will ever be able to cut through the difficulties of brute forcing go.
Anonymous: I don't think "number of possible outcomes" has been defined yet. How about defining "final board positions".
- the best move would be pass for either player, if it were their turn
- there are no dead stones on the board (you may want to relax this condition)
- all the dame are filled in (you may want to relax this condition)
- what scoring rule and ko rule is being applied? (this probably affects the answer)
Are there any other conditions that should be added?
Alexandre: If you can solve the problem above, then not only are you able to "solve" the game of go, you also have the best player never created, i.e. an algorithm for KamiNoItte Whatever, the number of "final board positions" is completly subjective and is almost infinite...
Ex : the master play the first stone and his opponent resign.
Almost every position may be considered final.
If you then consider the order the moves where played (same position but different games) you can multiply this number...
So what ? We are playing a game with a number of position n times greater than the number of particles in the whole universe (and n is a super very huge number )... great !
Now, let's play in order to get a number smaller : our level in kyu (or for players in dan, the number of handicap stones to the best player around)
Jacques: In the FunGoFacts page, the sentence "It is believed there are more possible game variations than atoms in the universe" leads to this discussion.
This is not only a belief but a trivial fact, even if we limit the game to less than 40 moves.
The mass of universe is equivalent to the weight of 4e78 hydrogen atoms. (Search google, and find somthing like:
http://www.sunspot.noao.edu/sunspot/pr/answerbook/universe.html) Lets assume 4e78 as an upper bound for the numer of atoms.
The number of games, specially on an empty board, is well approached by permutation(361, n).
Meaning: The first player has 361 (=19x19) possible moves, the second has 360, then 359, 358, and so on. The number of games can be approached by 361x360x359x ... x(362-n) (for n moves). This number is just an approximation, because there may be more (when captured stones are removed) or less (because suicide and Ko recapturing is not allowed), but in the first moves of a game, it is a very good approximation. PERM(361,30) = 1.5e76, PERM(361,31) = 5.1e78, PERM(361,32) = 1.6e81
So the sentence should be:
It is a FACT that the number of atoms in the universe is smaller than the possible variations IN THE FIRST 32 MOVES of a 19x19 Go game. (If it's not 32, its very close to 32.)
ThorAvaTahr: First of all I think it is important to be precise when making this statement. The statement is very bold, and it is much stronger when it is able to withstand the obvious critisme. According to all widely accepted theories, the universe is infinite. Therefore, the correct statement limits itself to the "known" or "visible" or, perhaps even better, "observable" universe, which is that part of space that is within the
Secondly normally i would put this sentence in a context of state-space rather than game-tree. This is much easier to explain to people and a (very) rough upper limit can easily be given (3^361 or 10^172, and a Scryer pointed out above very nicely I tend to believe that the order of legal positions would be in 10^(-2) or perhaps 10^(-4) it really doesn't matter ) . Also, this way you avoid having definition problems.
Thirdly I always like to put in into context with a comparison to chess. A well known number for this is the
So, to be a bit too bold I would like to say: The complexity of chess is much lower than the complexity of the universe, which in turn is far less complex than the game of go!
Here I imply that the complexity of the universe is measurable by the number of particles, which is off course not easy to defend, but it still sounds good right?
Szafir? No, it doesn't sound good. You are comparing apples and oranges. Affirming that go is far more complex than the universe is quite an aberration. The number of possible go games is in a way the number of ways to order 19x19 stones in a certain amount of turns, which is a very large number (of the order of 10^360 as stated above). For some reason you choose the complexity of the game to be that number. At the same time you chose the complexity of the universe to be the number of elementary particles. Why? If you want to be fair, you should compute the number of ways those 10^90 or so elementary particles can be ordered in space (which let's assume is 3 dimensional) in a certain amount of time. The time can be somewhat estimated to 20 billion years. I am not sure how to compute a time unit that is small enough to fit any change in the universe but you can be generous enough and set it to one second. For the purpose of the exercise, let's assume the universe is one-dimensional, because it's easier to compute permutations. So there you have it, (10^90)^(20*365*24*3600). Much larger than any number of games of any kind. And if you think of it philosophically, a part of anything cannot be more complex than its whole. A game of go, small and contained in the universe, cannot be more complex than the universe.
Pashley It goes up a bit slower if you take symmetry into account. For the first move, the possiblities are
- one on tengen
- 36 elsewhere on diagonals
- 36 elsewhere on 10,n lines
- 288 not on either.
However there are only 9 unique moves on diagonals (because, for example, you can play 44 in any corner), and 9 on 10,n lines (for example, 10,3 on any side). For the other 288 moves, divide by 8 for symmetry (for example 35 or 53 in any corner), so only 36 unique moves.
Allowing for symmetry, then, there are only 1 + 18 + 36 = 55 unique opening moves.
Anonymous: Yes, bu this luxury can only be afforded to the first move, however, for the second move there are 360 possible positions, i.e.:
![[Diagram]](diagrams/38/1e997dd66edcef759c19172d92a6c514.png)
Centaur: No, if the first move was on a symmetrical point, the number of possibilities for the second move is smaller, depending on the kind of symmetry.
1 at tengen: 9 distinct possibilities on diagonals, 9 distinct possibilities on 10-lines, and 36 possibilities in asymmetrical points = 54 possibilities for 2
1 at diagonal or 10-line except tengen: 18 distinct possibilities on the same diagonal or 10-line, and 171 possibilities elsewhere = 189 possibilities.
1 at asymmetrical point: 2 anywhere on the board = 360 possibilities
After that, depending on the moves the opponents take, there may be other symmetrical positions where the next move is essentially halved or quartered or divided by 8.
Tas: Great divide the number of possible games by a billion, or a quadrillion if you like... it doesn't matter.
Anon Polya Enumeration takes symmetry into account, and can be used to calculate the exact number of distinct arrangements of a square 19x19 lattice where each point can be one of 3 colours. Using this method, it turns out that (3^361)/8 (or 2.1761+e171) is a good approximation because the method involves adding to 3^361, then dividing the total by 8, but the numbers added are only of the order 10^91.
The actual number is
2176120633237899098839852975882054599332534
0618782942649353514838350131459523081252636
6159000928886784499892333724948131279283170
9758243193810863164767480132124547426572862
For each board, either player could play next, so it could be argued that toggling the colours of the black and white stones does not create a new board. In that case, half the number above is a lower bound on the number of boards with 'toggle symmetry' taken into account.
In fact, for all sets of triples (number of black stones, white stones, empty points) - (b, w, e), if b <> w, the toggled pattern (or a geometric symmetry of it) must be in (w, b, e), so the number of boards of that form can be halved. The accurate figure is lower than this, but halving the number for cases where b = w will not work since not every member of (b, b, e) has a distinct toggled pattern in (b, b, e). For example
![[Diagram]](diagrams/47/ef751e0d83fb32200c23782af2982ad8.png)
This number is therefore somewhere between
1088060316618949549419926487941027299666267
0309391471324676757419175065729761540626318
3079500464443392249946166862474065639641585
4879121596905431582383740066062273713286431
and
1116026258137819292496624460820938166596258
0577982625236576029163205629116245683582176
1834365908835526250838642401551243041451091
6968161417781272603245182027904193127799392
ie between 1.0881E+171 and 1.1160E+171
![[Welcome to Sensei's Library!]](images/stone-hello.png "Sensei's Library")