Pentago Is a First-Player Win 136
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."
Comparison to Chess? (Score:5, Interesting)
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)
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: (Score:2)
IIRC, if the entire universe were crammed to neutron star density with computer processing, it still couldn't touch a perfect game in the entire life of the universe.
Re:A rough approx. is 10^60 moves (Score:4, Funny)
Plus, where would you put the chess board?
Re:Comparison to Chess? (Score:5, Informative)
chess
state space complexity 10^47
go
9x9 - 10^38
13x13 - 10^79
19x19 - 10^171
Re: (Score:2, Funny)
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)
keep it classy man. ha ha, women. double ha ha, menses. and yet you're still single, how can that be?
Re: (Score:2)
uh huh, 50 and married with children. livin' the Al Bundy dream....
Re: (Score:3)
Re: (Score:1)
Just because someone is nice does not mean they think they deserve someone or something.
Re: (Score:1)
Chances are pretty good that if you're an intelligent educated straight male nerd type, this isn't the type of woman who can hold your interest.
Re: (Score:2)
Re: (Score:2)
Yeah, exactly what I needed today, too.
Re: (Score:3, Insightful)
three orders of magnitude added 5 out of 28 days
Somehow 10^194 doesn't seem significantly worse than 10^191.
Re: (Score:2)
Re: (Score:3)
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
Re:Comparison to Chess? (Score:4, Informative)
Why is this insightful? He doesn't even understand the word "complexity" in the context it was used!?
GO IS complex. Yes, the brute force complexity is stupidly large.
But also the (non-optimal) pattern strategies that humans use and researchers ARE STUDYING (and have done for some time) are very difficult to emulate.
I love how you just dismiss a whole field of research as if they had not bother to try anything else in the decades this has been study?!
Sheesh...talk about failing to give people the benefit of the doubt...
Re: (Score:3)
A simple neural net (I hate that fucking term) algorithm trained against average Go-playing humans will end up being average at playing Go.
Seems to me like you took a cursory glance at Go and decided it'd be simple to create an algorithm that would be good at it. Without any actual experience.
Have you actually played it? More importantly, have you ever seen a decent player play against a computer?
My dad is an amateur and is not ranked, in chess terms he's not even an expert and basically he's nothing. He stomps the living crap out of the best Go software commercially available; he wins every time. And from reading articles about the state of
Re: (Score:2)
Does it say that on the box? Because I strongly doubt he does. Can your dad beat a top pro with only 4 handicap stones? Because both Zen and Crazy Stone have achieved that.
Maybe he can beat the best commercial go software from 2008 or so. In that case he's still very good, and few people would manage that without being at least club players (and thus ranked).
Re: (Score:2)
Wow, I hadn't heard of Crazy Stone, it looks great, although, $80 is a bit steep, even by modern videogame standards.
Re: (Score:2)
iirc the software he's using is Many Faces of Go, which at the time (2009ish) was regarded the best commercially available program I believe.
Thanks for the info, I'll get him Crazy Stone as a birthday gift. He will go nuts over it.
Re: (Score:2)
Many Faces of Go is a decent program today, and back in its pre-Monte Carlo days it was also decent - as computer go programs went. Version 11 (the last pre-Monte Carlo) I have no trouble believing a non-club player beating. The later versions, well, they're certainly within range for an amateur to beat too (1-4 dan on KGS, depends a lot on the power of your computer) but then your dad is pretty good :)
Re: (Score:3)
How impressive that you can know that without having tried. How do I know you haven't tried it? Because it's totally wrong...
Re: (Score:1)
How impressive that you can know that without having tried. How do I know you haven't tried it? Because it's totally wrong...
Please tell me which of those facts is wrong, and explain why.
Remember to show your work.
Re: (Score:1)
It's not simply a "perimeter game." Many of the most critical aspects of it depend on other parts - ishi-no-shita, to name a single one among many.
The assertion "A simple neural net algorithm trained against average xxx human [activity] will end up being average at xxx human activity" shows hopeless naiveté about both neural net "training" and the organization of human activities.
There are quite strong programs these days, relative to ten or twenty years ago. But there is no program that can win consis
Re: (Score:2)
So I have to show my work, but you don't? A classic of the time- wasting troll.
Re: (Score:3)
As far as I know most worthwhile computer-Go programs don't use alpha-beta for the reasons you stipulate. A lot of the in-game scoring involves trying to calculate territorial control and areas of influence, moyo in Japanese. Like chess, at the beginning of a game computer programs tend to use standard openings (joseki) and as in chess an experienced human player will break out of the book early on in the game to force the computer to start evaluating moves instead. The end-game, like chess simplifies down
Re: (Score:2)
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.
Re: (Score:2)
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
Re: (Score:2)
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.
Re: (Score:2)
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)
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)
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)
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
Re: (Score:2)
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
Re: (Score:3)
Well lets find out.
1... 2... 3... 4... 5...
Re: (Score:2)
6... 7... 8... 9... 10... 11... 12... 13...
Re: (Score:2)
14... 15... 16... 17... 18... 20... 21... 22... 24... 25... 2- aw crap, I lost count.
1... 2... 3...
Re: (Score:2)
You need to count faster or this shit will take forever, man.
Re: (Score:2)
I'll organise them into groups of the same type of particle. Then we can count them each separately. That should save some time.
Re: (Score:2)
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)
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)
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
Re: (Score:1)
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 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:
Re: (Score:2)
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)
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]:
Re: (Score:2)
Sounds like fun (Score:2)
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)
Re: (Score:2)
Your argument would be correct for a game like tic tac toe.
Re: (Score:2)
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
Re: (Score:3)
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 o
Re: (Score:2)
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.
Re: (Score:2)
Chess (Score:5, Funny)
After playing in chess tournaments for 20 years, I have strongly solved that chess is a forced win for any player facing me.
Re: (Score:2)
You've never played against me... I bet I'd lose more.. ;)
Re: (Score:2)
Re: (Score:2)
For some reason this [despair.com] comes to mind...
different than tic tac toe or connect 4? (Score:2)
Re:different than tic tac toe or connect 4? (Score:5, Informative)
No, tic-tac-toe is always a tie.
Re: (Score:3)
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.
Re: (Score:2)
I tend to play games with friends.
Re: (Score:2)
let's play wwf. what is your screen name?
Re: (Score:2)
Unless the complexity is sufficient that the computer has to utilize heuristics as well.
Re: (Score:2)
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.)
Re: (Score:2)
Re: (Score:2)
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)
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
Re: (Score:2)
Re: (Score:2)
Tic-tac-toe is simple enough that a human can reasonablly learn the perfect strategy.
Re: (Score:2)
Re: (Score:2, Insightful)
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.
Re: (Score:2)
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.
Re: (Score:2)
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
Grammar? (Score:2)
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)
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 /.
Re: (Score:2)
But ... but ... spieling cunts.
Re: (Score:1)
This is perfectly ordinary game-theory terminology.
Most wouldn't even call it jargon; it's quite cromulent.
It may be a ""first-player wins" game", but it's not a "first-player win".
Re:Grammar? (Score:5, Funny)
No, now that Pentago is solved, we're reduced to online games of Pedant.
HINT: Last player always wins.
Re: (Score:2)
Another game of that is something up with which I will not put.
Re: (Score:3)
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)
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
Now how easy is it to remember? (Score:2)
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. :-)
Re: (Score:2)
Re: (Score:2)
Wargames... (Score:5, Funny)
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)
Plagerism (Score:1)
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)
Re: (Score:2)
Re: (Score:2)
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.