Slashdot Mirror
Pentago Is a First-Player Win
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."
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?
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)
Better known as 318230.
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.
It all starts at 0
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").
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".
const int one = 65536; (Silvermoon, Texture.cs)
SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
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. :-)
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
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???
Yes, but do you know every objectively perfect move? Not even Gerry Kasparov or Magnus Carlson do, so chess is still a fun game no matter how good or how bad you play.
Your argument would be correct for a game like tic tac toe.
Yes, but do you know every objectively perfect move? Not even Gerry Kasparov or Magnus Carlson do, so chess is still a fun game no matter how good or how bad you play.
They do know a lot of the objectively perfect opening and closing moves. The mid-game is still open, but in order to get there in a good position you have to memorize a lot of openings. And then in order to know what you want to do during the midgame, you have to memorize a lot of closings.
Chess is a fun game to play casually, but there's a lot of rote if you actually want to do well.
Give me Classic Slashdot or give me death!
It's only fun for the good players :)
Seven puppies were harmed during the making of this post.
Again Go proves superior: Memorizing Go openings is a start. Learning why they work the way they do is required.
In Go, your opening is strong for a reason. Somebody plops a stone in the middle of it, or does an approach out of turn, you have an advantage or at least are no worse off than if you played a standard opening. Fast players just play standard openings and get into midgame--Koreans like to do this. The Japanese like to analyze their opponent, the board, and form a long-term strategy based on standard openings, often not even following the standard more than 2 or 3 moves. Standard openings like Ni Ren Sei and San Ren Sei are only a few moves (Ni Ren Sei is black on two adjacent corners, white on two adjacent corners, black's move--which is usually approach, or strengthen, sometimes split).
In Go, your opponent can do more than just move a piece toward you in a bumbling and foolish manner. He can jump right into the middle of your opening and screw it up. Mid-level players do this a lot: a slightly stronger opponent will disrupt a weaker opponent because he can make a position off the disruption, and the weaker opponent does not know why he is playing the Low Chinese other than because it is a correct opening--and thus makes a really screwy position responding poorly.
Go is about concepts. Memorizing Joseki is often advertised as a good way to start; it is a poor way to continue. Joseki study is done to learn why: to learn about variations, about how a joseki is strong, about why a korean Jung-Sek is formed differently from a similar looking Japanese Joseki--what was the goal?
Life and Death is often by rote... for the simple shapes. Vulnerable points. Recognizing the shapes before they come.
Support my political activism on Patreon.
Again poor Go players show their silliness. Do you think Carlsen can skip why Caro-Kahn works the way it does?
And yes, I refuse to believe you are a strong go player, because then you'd know how silly that statement was.
xkcd is not in the sudoers file. This incident will be reported.
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.
Chess seems a zero sum game to me. The utility you lose in losing a piece is equal to the utility I gain by you losing that piece. Or in the case of a sacrifice, the utility you gain by losing a piece is equal to the utility I lose by you losing a piece.