Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. ×
Math Classic Games (Games) Supercomputing

Finally Calculated: All the Legal Positions In a 19x19 Game of Go (github.io) 117

Reader John Tromp points to an explanation posted at GitHub of a computational challenge Tromp coordinated that makes a nice companion to the recent discovery of a 22 million-digit Mersenne prime. A distributed effort using pooled computers from two centers at Princeton, and more contributed from the HP Helion cloud, after "many hiccups and a few catastrophes" calculated the number of legal positions in a 19x19 game of Go. Simple as Go board layout is, the permutations allowed by the rules are anything but simple to calculate: "For running an L19 job, a beefy server with 15TB of fast scratch diskspace, 8 to 16 cores, and 192GB of RAM, is recommended. Expect a few months of running time." More: Large numbers have a way of popping up in the game of Go. Few people believe that a tiny 2x2 Go board allows for more than a few hundred games. Yet 2x2 games number not in the hundreds, nor in the thousands, nor even in the millions. They number in the hundreds of billions! 386356909593 to be precise. Things only get crazier as you go up in boardsize. A lower bound of 10^{10^48} on the number of 19x19 games, as proved in our paper, was recently improved to a googolplex. (For anyone who wants to double check his work, Tromp has posted as open source the software used.)
This discussion has been archived. No new comments can be posted.

Finally Calculated: All the Legal Positions In a 19x19 Game of Go

Comments Filter:
  • Is it solved then? (Score:5, Interesting)

    by menkhaura ( 103150 ) <espinafre@gmail.com> on Sunday January 24, 2016 @10:23AM (#51361143) Homepage Journal

    Can we consider the traditional game of Go solved, then? And how about chess, what about calculating 32-piece EGTBs?

    • by Anonymous Coward on Sunday January 24, 2016 @10:42AM (#51361203)

      This is a count of legal[1] positions, or how many games you can end up with.

      A "solved" game would be one with efficient real-time evaluation of the next "winning moves", which is entirely a different job.

      [1] That should also depend on the regional rule variation. A legal move by the Chinese rule may not be one by the Korean rule.

    • Re: (Score:2, Insightful)

      by Anonymous Coward

      No- they computed what all the possible boards are. "Solving" Go would involve finding an optimal move for each of those possible boards, which is much harder.

      • by Anonymous Coward

        TFS makes it sound like they didn't even do that much - they merely calculated how MANY there are, which to be clear, is an impressive accomplishment, but there's no amount of storage in the world that can actually hold them all.

    • Re: (Score:2, Insightful)

      by Anonymous Coward

      A solution for Go would involve creating a directed graph, with cycles allowed. The result found in this article is the number of nodes in this graph. The edges in the graph would be legal moves, moving from one legal board configuration to another.

      You would have to additionally label each node in the graph with the scoring value of that position for each player, if the players agreed to end the game at that position. (The game of go does not have an explicit winning goal like "checkmate" in chess, rather t

      • by Amouth ( 879122 )

        You know i've always thought about the beauty that i the simplicity of Go which creates a complexity for formulaic solving.

        But i just thought of a new level, everything you said is dead one, but when you mentioned "without handicaps".. just made me stop and realize that once you figure out how to solve the base, you will need to go back and re do everything for each handicap possibility winch is 1-9 stones, and while they are traditionally placed on star points, that isn't a requirement.

        yea wow, i'ts amazi

      • by Imrik ( 148191 )

        One of the rules of Go is that you can't repeat an earlier board position, meaning cycles are not allowed.

        • That varies between rule sets. It is certainly a popular rule set, but there are others - for example the Nihon Kiin rule set has much more complex rules on kos which allows for some repetitions of the boar position if either player forces a triple ko. How to score, or decide on whether the game is ended is then very different.

          I can't remember any particular stories, but I would suspect that people have died - disembowelled and/ or beheaded - over some of these rule disputes. Which is why the rules have be

    • by ecotax ( 303198 )
      Impressive as it is, it's just the number of legal positions. It doesn't say anything about whether optimal play always results in black or white always winning or not. Compare to the number 26,830 for tic-tac-toe, compared to saying it's a draw.
    • by SuricouRaven ( 1897204 ) on Sunday January 24, 2016 @11:41AM (#51361355)

      This does not solve Go. It does make it possible to estimate how feasible solving Go is: Roughly how many universe-lifetimes will it take for your computer to calculate the next move?

      • A long time ago, I read that a universe jammed with subatomic particle-sized computing components, about 10^^120 (for solid neutrons), running for the age of the universe at the speed of light, couldn't come close to playing a perfect game of chess, which has many powers fewer moves to consider.

  • by Anonymous Coward

    It would help to have more explanation of why a 2x2 board has more than 3^4 possible permutations.

    • Re: 2x2 board (Score:5, Interesting)

      by Teppy ( 105859 ) on Sunday January 24, 2016 @10:41AM (#51361193) Homepage
      A 2x2 board has more than 3^4 possible games, not legal positions. The same legal position may occur in multiple games.
      • That's a pointless measurement, though. A game of checkers has infinite possible games because you can repeat positions. For a player, or an AI trying to win a game, all that matters is the current game state and the possible game states, not how you arrived to that state.

      • More to the point, the 24 (IIRC, including symmetry operations) legal positions for a 2x2 game can occur multiple times in a game.
    • That number probably refers to legal games (=sequences of moves). The result on the 19x19 board enumerates the legal positions, instead. Confusing abstract.
    • The summary is crap from beginning to end. It confuses counting positions with enumerating them. It confuses the number of possible games with the number of possible positions. All in all, a typical timothy post.

    • Re:2x2 board (Score:5, Interesting)

      by johntromp ( 565732 ) on Sunday January 24, 2016 @02:35PM (#51362001)

      Author here.

      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... [github.io]

      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.

      • What do you mean with 2x2 go?

        A square with the 4 corners as legal positions?

        The game is over after a few moves ... so the number of legal positions is rather small and far from billions.

        • Re:2x2 board (Score:4, Informative)

          by johntromp ( 565732 ) on Sunday January 24, 2016 @06:29PM (#51362919)

          2x2 is Go played on a 2x2 board.
          where the 4 corners are the playable points.

          A game can continue for dozens of moves.

          • It can't continue over dozen of moves.
            The maximum is six moves. Depending on the move of the second party it wins after six moves or loses after two.

            • That was meant to read "loses after three".

              If you count symmetries as different variations, you get of course a few more positions but not moves. You also could let the beginner make a mistake after the second had made a mistake, and instead of winning after move 3 he would then lose after move six. There is no way the game can continue in the first case beyond move three and in the other cases beyond move six.

              • This 8 move game disproves your claim:

                . .
                . .
                A2
                X .
                . .
                B1
                X .
                . O
                A1
                X .
                X O
                B2
                . O
                . O
                A1
                . O
                X O
                A2
                O O
                . O
                A1
                . .
                X .
                B2
                . O
                X .
                A2

            • You might want to learn how to play Go:-)

  • by Anonymous Coward

    Spotted a mistake in the code on line 12... sorry, you have to start over, fellas.

  • Error in the title. They most certainly did not calculate all legal positions, only the exact *number* of legal positions. Which is a *very* different thing.
    • by Imrik ( 148191 )

      They calculated what they are, they just didn't save them.

      • by Jeff Y ( 4362625 )
        No, they certainly did not enumerate them in any way. They could not physically have done so (with today's technology). Look at the magnitude of the number again.
  • They haven't calculated all the legal positions. They've counted all the legal positions.

  • ... But only 85 legal positions, with many being mirroring positions.

    Placing two stones of the same color over the diagonal of this board leads to an absorbing state.

    Any other state can be reset by either black or white to a single stone.

    This is assuming the players are not playing with the rule of no repetition (but with the rule of no suicide).

    For clarity, see the rulebook.

    • by jfengel ( 409917 )

      Where does 85 come from? There are 4 positions, each with 3 legal states (back, white, empty). I get 3^4=81. Is there some rule I'm missing that creates 4 more legal states?

      • There are 4 positions, each with 3 legal states (back, white, empty).

        But each player has 3 possible moves, for every position on the board : play on this point ; play on any other legal point ; pass.

    • this. the mirrors really make it even less. and no suicide make it even less still. I highly doubt these numbers,
  • I wonder how many megawatts such a calculation takes?

  • by Hognoxious ( 631665 ) on Sunday January 24, 2016 @05:45PM (#51362791) Homepage Journal

    Has anyone checked the sky? I hope that overhead the stars aren't, without any fuss, going out.

  • by GlobalEcho ( 26240 ) on Monday January 25, 2016 @09:44AM (#51365389)
    Looking into the paper, we see that with L(2,2)=81-16-8=57 various positions that are symmetric transforms of each other are considered distinct. For example, on sees this in the upper right and lower left corners of Figure 1. Now, it's true that superko will break some of that symmetry, but not all of it. How much complexity disappears with more accounting for symmetry?
  • Go is a game played on a board with 20 x 20 = 400 intersections. That's where the pieces are placed, not in the center of the 361squares. I suppose I now know why most of my software is so crappy - nobody checks their assumptions. (There were 90 comments already when I wrote this!) Even when the evidence is staring them in the face, visible in every photo of a Go game, ever. What's gonna happen next, Republicans exhibiting climate denial or something crazy like that?

"I got everybody to pay up front...then I blew up their planet." "Now why didn't I think of that?" -- Post Bros. Comics

Working...