Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Supercomputing Classic Games (Games)

Pentago Is a First-Player Win 136

Posted by timothy from the heads-I-win-tails-you-lose dept.
First time accepted submitter jwpeterson writes "Like chess and go, pentago is a two player, deterministic, perfect knowledge, zero sum game: there is no random or hidden state, and the goal of the two players is to make the other player lose (or at least tie). Unlike chess and go, pentago is small enough for a computer to play perfectly: with symmetries removed, there are a mere 3,009,081,623,421,558 (3e15) possible positions. Thus, with the help of several hours on 98304 threads of Edison, a Cray supercomputer at NERSC, pentago is now strongly solved. 'Strongly' means that perfect play is efficiently computable for any position. For example, the first player wins."
This discussion has been archived. No new comments can be posted.

Pentago Is a First-Player Win More

Pentago Is a First-Player Win

Comments Filter:

  • Comparison to Chess? (Score:5, Interesting)

    by jratcliffe ( 208809 ) on Thursday January 23, 2014 @01:42PM (#46047765)

    Out of curiousity, does anybody know what the number for chess that compares to the 3e15 number for pentago is? In other words, how much "bigger" is chess?

    • A rough approx. is 10^60 moves (Score:2, Interesting)

      by Anonymous Coward

      Assuming the game goes for at least 30 moves, and that each player has roughly 10 options per move you get 10^(2*30). 10 options times 30 moves * 2 (there are two players, so two moves per "move").

    • Re:Comparison to Chess? (Score:5, Informative)

      by vux984 ( 928602 ) on Thursday January 23, 2014 @01:50PM (#46047845)

      chess
      state space complexity 10^47

      go
      9x9 - 10^38
      13x13 - 10^79
      19x19 - 10^171

      • Re: (Score:2, Funny)

        by iggymanz ( 596061 )

        woman
        state space complexity: 10^191
        23 out of 28 days

        three orders of magnitude added 5 out of 28 days

                                                                                       

        • Re: (Score:3, Funny)

          by noh8rz10 ( 2716597 )

          keep it classy man. ha ha, women. double ha ha, menses. and yet you're still single, how can that be?

          • uh huh, 50 and married with children. livin' the Al Bundy dream....

        • Re: (Score:2)

          by glwtta ( 532858 )
          Oh good, this shit.

        • Re: (Score:3, Insightful)

          by Kjella ( 173770 )

          three orders of magnitude added 5 out of 28 days

          Somehow 10^194 doesn't seem significantly worse than 10^191.

        • You forgot an important random variable... the fact that you will forgot something deemed "important" by them. At that point toss out the equation and go sleep on the couch. Do it too often and you won't have to worry about that either.

      • Re: (Score:3)

        by ledow ( 319597 )

        I was lucky enough to have a lecturer at university who was actively working on solving Go. Professor Wilfred Hodges at QMW, University of London.

        It was his talk about the complexity of the game of Go on my induction day that convinced me to go to that university, and I was able to have him as a course lecturer for certain related courses later on (graph theory).

        He is a typical, mad-haired, Einsteinian-looking sandals-in-winter professor, and he gave a marvellous intro to Go, complexity and the work he was

        • Apparently there is no decent Go computer player in the world that can beat more than an average Go human player.

          This was true a decade ago. Today, both algorithms and hardware have made huge advances. There are some very good go programs. I consider myself an above average player of both chess and go (I have won amateur tournaments at both). I never win against a modern chess program. I rarely win against a modern go program.

        • Apparently there is no decent Go computer player in the world that can beat more than an average Go human player.

          Not true any longer. Not by far. The best humans are still best, but computers are getting good. Really good. Holding 6 dan at KGS good. That means they are a match for the top club players.

          To put it into perspective: If you make Go your only hobby right now, and practice every day for 5 years, and you're a damn smart guy, you're still unlikely to become better than Zen is now - let alone better

          • Are they actually 6dan kgs? They don't play 6dans, they plan a small number of low dans at high handicap. Fuseki is one of the areas that Go programs are really bad at (unless you stay exactly within a limited Fuseki database), which the handicap artificially bypasses, and the abstractness of openings it is a pretty defining characteristic of Go. So I think claiming a rank of 6 dan is premature.

            • Yes, there's always questions about the accuracy of rankings/ratings in a system where people can choose who to play. But if only lower dans are willing to play the top bots, that speaks volumes in itself.

              In general, since players are protective of their ratings and pick and choose who to play, while the bot makes no such considerations, I'd say the bot is probably stronger than its awarded rating indicates.

      • Re: (Score:2)

        by nojayuk ( 567177 )

        In Go it is assumed black going first has the advantage and in an even game white is given some points in compensation (komi).

        I vaguely recall reading that Go on a 7x7 board had been strongly solved some time ago by exhaustive computer analysis and I assumed that 9x9 Go would be the next to be solved. Is anyone working on the problem at all? How much would it cost to rent enough computer power to do so? Could it be done using BOINC?

      • Re: (Score:3, Interesting)

        by bluefoxlucid ( 723572 )

        Go on 9x9 is very similar to Chess neurologically: it's a tactics game. I'm bad at it. I hate chess for emotional-political reasons: it is technically inferior to Go, being that it is tactical, and thus I cannot stomach nor can I support wasting my time on such an inefficient pursuit. Someone has been reasoning, correctly, that I should practice Chess to gain additional, non-domain tactical exercise so as to improve my Go playing. I have been, incorrectly, resistant.

        Go in 13x13 is strategically dif

        • Re: (Score:2)

          by vux984 ( 928602 )

          it is technically inferior to Go, being that it is tactical,

          I don't think tactics vs strategy has any inherent mapping from inferior to superior at all. Even if we agree Chess is tactical, the conclusion that its "technically inferior" doesn't follow.

          and thus I cannot stomach nor can I support wasting my time on such an inefficient pursuit

          Sheesh... because mastering Go is a more efficient pursuit and a valuable investment of your time? What does that even mean? And in what universe is it true?

          Computationa

          • To be crude and inaccurate, Chess is technically inferior to Go because Chess is almost entirely tactical--"Left Brained" (inaccurate, but familiar)--while Go fully exercises tactical and strategic thinking--"Left Brained" and "Right Brained", as they say. Chess cannot stimulate the same centers of the brain as Go, but Go can cover every neurological function stimulated by Chess.

            Go is a valuable use of my time because it provides me with mental exercise that has helped with some of the weaknesses in my

    • Now that the computer found every iteration, I bet it could optimize itself and only store the pathways that will lead to a win, and cut down the iterations.

    • Re:Comparison to Chess? (Score:4, Informative)

      by Anonymous Coward on Thursday January 23, 2014 @01:58PM (#46047937)

      According to the summary, 3e15 is the number of possible positions. The number of possible positions in chess is around 4e46.

      http://en.wikipedia.org/wiki/Shannon_number

    • Re: (Score:1)

      by Anonymous Coward

      The number of legal positions in chess is estimated to be between 10^43 and 10^47 (a provable upper bound), with a game-tree complexity of approximately 10^123. The game-tree complexity of chess was first calculated by Claude Shannon as 10^120, a number known as the Shannon number. Typically an average position has thirty to forty possible moves, but there may be as few as zero (in the case of checkmate or stalemate) or as many as 218.

      https://en.wikipedia.org/wiki/Chess#Mathematics_and_computers

    • Interestingly, that (the number of possible moves in chess and whether it was finite or infinite) was used as a plot point in the sci-fi novel _Starstrike_

    • Re: (Score:2)

      by krkhan ( 1071096 )

      By the way, 3x3 Chess was strongly solved [homeunix.org] in 2004.

      On the other hand, Claude Shannon has argued [computerhistory.org] about the original game being unsolvable by computers:

      "With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule).

      • Re: (Score:2)

        by Dunbal ( 464142 ) *

        A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move

        I'm guessing that we have gotten a little faster since then with our current peta and soon to be exascale machines... micro-second? An eternity. Recalculate that spreadsheet, professor.

        • Re: (Score:3)

          by krkhan ( 1071096 )

          A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move

          I'm guessing that we have gotten a little faster since then with our current peta and soon to be exascale machines... micro-second? An eternity. Recalculate that spreadsheet, professor.

          Shannon -- the "professor" -- was simply taking into account the technology available at the time.

          Hans-Joachim Bremermann has also made an interesting argument [archive.org]:

          "Speed, memory, and processing capacity of any possible future computer equipment are limited by specific physical barriers: the light barrier, the quantum barrier, and the thermodynamical barrier. These limitations imply, for example, that no computer, however constructed, will ever be able to examine the entire tree of possible move sequences of th

    • Not sure about the mathematical complexity, but the (chess) strategy of controlling the center, in this case the center of boards opposed cross nevers fails to win as a white player.

  • Sounds like a lot of fun to play against a computer. Not. (maybe I'm just getting old, but I'm not much into futility these days)

  • Chess (Score:5, Funny)

    by Anonymous Coward on Thursday January 23, 2014 @01:44PM (#46047805)

    After playing in chess tournaments for 20 years, I have strongly solved that chess is a forced win for any player facing me.

  • Is this surprising? It appears that any game of connecting a row of pieces on a flat plane is a first player wins game. Connect 4 and tic tac toe all have the first player winning.

    • Re:different than tic tac toe or connect 4? (Score:5, Informative)

      by mrchaotica ( 681592 ) * on Thursday January 23, 2014 @01:48PM (#46047839)

      No, tic-tac-toe is always a tie.

      • All these posts have the caveat of "with perfect play"

        Human play is about creating mental shortcuts that create useful heuristics for "winningness", and developing those shortcuts is most of the fun to be had.

        • Tic-tac-toe is so small that even humans can play perfectly. For example, here are the perfect play maps for X [wikipedia.org] and O [wikipedia.org], which only look complicated until you realize that, due to symmetry, many of the cases are actually the same.

          Here is a move list for a perfectly-played game. (For the purposes of the following, number the squares from 1 to 9 in telephone keypad order.)

          1. X plays a corner (assume square 1)
          2. O plays the center (square 5)
          3. X plays a side adjacent to its previous move (assume square 2)
          4. O blocks (square
          • I read somewhere that some humans can actually play perfect checkers. When you think about it, there aren't really that many possible moves. not anywhere close to chess anyway. I'm not sure if it's factually correct that the best players can play perfectly, but this reference [ikebarberl...tre.ubc.ca] says that the reigning champion hasn't lost a game in 40 years. That's pretty impressive.

            • Bear in mind that the variant of checkers played competitively outside UK/US, International Draughts, is played on a 10x10 board and it has "long" queens (a la pool checkers in UK/US). It is far from solved, although it has even more problems with tied games on high level than chess.

          • Re: (Score:2)

            by Alsee ( 515537 )

            The move sequence you posted does represent a valid example of perfect-play presuming a perfect opponent. However if we expand "perfect play" to mean perfect play vs a perfect opponent while also maximizing the real-world odds of winning, then your second X move is quite bad, chuckle. It presents the O player with a chain of blatant forced-block moves, forcing a tie.

            A far stronger play sequence is X1, O5, X9.

            This presents player O with an apparently free choice play. The choice boils down to playing in a co

            • A far stronger play sequence is X1, O5, X9. This presents player O with an apparently free choice play. The choice boils down to playing in a corner or a side. Humans have an implicit knowledge that corner squares are more powerful than side squares. Furthermore the symmetry of the X1, O5, X9 board amplifies the reflex to play in the more symmetrical corner square. In my experience above-average-intelligence-humans have a greater than 95% likelihood of playing a corner move when facing that position! This

        • Tic-tac-toe is simple enough that a human can reasonablly learn the perfect strategy.

      • Re: (Score:2)

        by Greyfox ( 87712 )
        The only way to win is not to play!

    • Re: (Score:2, Insightful)

      by Anonymous Coward

      If you are always losing as the second person in tic-tac-toe, you might want to lay off the drugs or stop posting on Slashdot as your IQ is too low.

    • It appears that any game of connecting a row of pieces on a flat plane is a first player wins game.

      Not true. Othello/Reversi favors the second player.

    • For tic tac toe or straightforward connect N games, It is impossible to construct a situation where not having a piece in a position is better than having it. Zugzwang is impossible. Thus you know these games are either a first player win or a tie.

      But this argument doesn't work for connect-4 (a la Hasbro). There, you sometimes prefer not to have a piece in a position, because your opponent could win by putting one on top of it. As it happens it's still a first player win, but it's tricky to prove without ex

  • Can't the editors write a headline that meets the basic rules of grammar? How about "In the game of Pentago the first player can always win", or "Pentago is strongly solved".

    • Re:Grammar? (Score:5, Funny)

      by zerosomething ( 1353609 ) on Thursday January 23, 2014 @02:04PM (#46047991) Homepage

      Can't the editors write a headline that meets the basic rules of grammar? How about "In the game of Pentago the first player can always win", or "Pentago is strongly solved".

      No cause with out those grammar mistakes their would be 30 pricent fuer com-mints on /.

      • No cause with out those grammar mistakes their would be 30 pricent fuer com-mints on /.

        But ... but ... spieling cunts.

    • Re:Grammar? (Score:5, Funny)

      by Anonymous Coward on Thursday January 23, 2014 @02:08PM (#46048035)

      No, now that Pentago is solved, we're reduced to online games of Pedant.

      HINT: Last player always wins.

    • I thought it meant, the game of Pentago is a really awesome first person shooter. or other game from the first person perspective. You know, the opposite of "Pentago Is a First-Player FAIL"

    • Re: (Score:1)

      by Anonymous Coward

      How about Researchers Discover Ironclad Winning Strategy for The First Player in Pentago, A Game Suitable for Play During Dark and Stormy Nights in Diverse Locales Such As London

  • I wonder if there is a minimal instruction set that someone can follow to guarantee the win if they go first. It's one thing to prove a game always winnable, but it's another to write an efficient algorithm to always win in a particular amount of time. Timed Chess playing computers have amazingly complex and cool algorithms, but that's at least partially because chess hasn't been solved in this way.

    For example, I wonder what the best first move is. :-)

    • Cue augmented reality app link
    • According to the article, moves below a certain number of stones are looked up in a 4-terabyte database, and moves with a certain number of stones require 15-20 seconds of computation on the supercomputer. So, definitely the algorithm as-is isn't learnable by a human.. though the human could wear some google glasses that hooks up to the supercomputer of course.

  • Wargames... (Score:5, Funny)

    by Rhaban ( 987410 ) on Thursday January 23, 2014 @02:06PM (#46048011)

    If Matthew Broderick had played pentago, the computer would have concluded the first country launching a nuclear missile always wins the war.
    Il came close

    • Re: (Score:2)

      by Dunbal ( 464142 ) *
      No the computer would probably still be working its way through the possible outcomes. We'd be safe for another 100 years or so...

  • Plagerism (Score:1)

    by Anonymous Coward

    This poster just copied/pasted his /. entry from some web site. If I copy a CNN article and submit it as my own, can I get front page on slashdot too???

  • Connect Four (Score:3)

    by multimediavt ( 965608 ) on Thursday January 23, 2014 @04:33PM (#46049829)
    Connect Four was the same way. Whoever went first wins. Didn't take a supercomputer to figure that out, either. Once you did figure that out, though, it pretty much made playing that game pointless. Up in the back of the closet it went. Something tells me Pentago will be joining it, soon.

Slashdot Top Deals

He has not acquired a fortune; the fortune has acquired him. -- Bion

Close