×

Announcing: Slashdot Deals - Explore geek apps, games, gadgets and more. (what is this?)

Thank you!

We are sorry to see you leave - Beta is different and we value the time you took to try it out. Before you decide to go, please take a look at some value-adds for Beta and learn more about it. Thank you for reading Slashdot, and for making the site better!

Pentago Is a First-Player Win

timothy posted about a year ago | from the heads-I-win-tails-you-lose dept.

Supercomputing 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."

Sorry! There are no comments related to the filter you selected.

Comparison to Chess? (4, Interesting)

jratcliffe (208809) | about a year ago | (#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 (2, Interesting)

Anonymous Coward | about a year ago | (#46047829)

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:A rough approx. is 10^60 moves (2)

Impy the Impiuos Imp (442658) | about a year ago | (#46048269)

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:Comparison to Chess? (5, Informative)

vux984 (928602) | about a year ago | (#46047845)

chess
state space complexity 10^47

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

Re:Comparison to Chess? (2, Funny)

iggymanz (596061) | about a year ago | (#46047921)

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

three orders of magnitude added 5 out of 28 days

                                                                               

Re:Comparison to Chess? (3, Funny)

noh8rz10 (2716597) | about a year ago | (#46048007)

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

Re:Comparison to Chess? (0, Informative)

Anonymous Coward | about a year ago | (#46048293)

I love the attitude that joking about women is somehow "the reason someone is single". Tip: throughout all of the past, plenty of folks made jokes about chicks, and they had relationships the same rate as everyone else. Nowadays, it's such a fucking lie that the women will reject you for being yourself, or that you have to be a feminist, or whatever. Women are not attracted to that. Often, women are attracted to confident jerks, who think nothing of making jokes like this.

Follow their actions, not their words. Supplicating white knights are the ones left mateless.

Re:Comparison to Chess? (2)

Laxori666 (748529) | about a year ago | (#46048359)

Supplicating white knight is also being quite manipulative. What, you think if you're nice you deserve to get a chick?

Re:Comparison to Chess? (1)

Anonymous Coward | about a year ago | (#46049701)

If she wants a nice guy, find a guy who thinks she deserves better...someone willing to share the hard work of building and maintaining a relationship that means something.

Just because someone is nice does not mean they think they deserve someone or something.

Re:Comparison to Chess? (1)

glwtta (532858) | about a year ago | (#46048091)

Oh good, this shit.

Re:Comparison to Chess? (2, Insightful)

Kjella (173770) | about a year ago | (#46048145)

three orders of magnitude added 5 out of 28 days

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

Re:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46048247)

Careful, don't provoke tumblr.

Re:Comparison to Chess? (1)

FatdogHaiku (978357) | about a year ago | (#46049667)

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:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46050145)

Yeah, men are so much easier by comparison we only have 4 states:
hungry, sleeping, horny, taking-a-dump

Re:Comparison to Chess? (2)

ledow (319597) | about a year ago | (#46048031)

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 doing.

All everyone else took away was that he showed photos of himself at a Go convention (on 35mm film). But I thought it was brilliant, and it made me teach myself Go.

I hope he's still working on it. Judging by the website I've found for him, he's busy with a LOT of other areas of mathematics than Game Theory, though.

But I'll never forget the mental "Woah" I got when he explained how much more complicated 19x19 Go was than Chess, even though the rules are vastly simpler.

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

Re:Comparison to Chess? (0, Flamebait)

sexconker (1179573) | about a year ago | (#46048177)

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 doing.

All everyone else took away was that he showed photos of himself at a Go convention (on 35mm film). But I thought it was brilliant, and it made me teach myself Go.

I hope he's still working on it. Judging by the website I've found for him, he's busy with a LOT of other areas of mathematics than Game Theory, though.

But I'll never forget the mental "Woah" I got when he explained how much more complicated 19x19 Go was than Chess, even though the rules are vastly simpler.

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

Go isn't complex. Go is very simple. It's just large. Go is a perimeter game and is really no more complex than Othello. A simple neural net (I hate that fucking term) algorithm trained against average Go-playing humans will end up being average at playing Go. The people who are fascinated by Go's "complexity" are only trying to solve it in bulk with traditional alpha-beta minimax schemes. Such approaches are not well-suited to Go because the score of any given board means very little since it can be completely flipped in a few moves. A game like Chess, on the other hand, is somewhat suited to alpha-beta minimax because pieces are removed as the game goes on and we can weight the pieces. A king is the end-game, a queen is always more important than a bishop, almost always more important than a rook or pawn, usually more important than a knight, etc.

Re:Comparison to Chess? (3, Informative)

MrBigInThePants (624986) | about a year ago | (#46048561)

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:Comparison to Chess? (2)

Spy Handler (822350) | about a year ago | (#46048623)

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 the art in computer Go programming, it would probably be a winning bet to say that my dad (a barely decent player) could beat any computer program ever made.

Re:Comparison to Chess? (1)

Vintermann (400722) | about a year ago | (#46049289)

the best Go software commercially available

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:Comparison to Chess? (1)

lgw (121541) | about a year ago | (#46049453)

Wow, I hadn't heard of Crazy Stone, it looks great, although, $80 is a bit steep, even by modern videogame standards.

Re:Comparison to Chess? (1)

o_ferguson (836655) | about a year ago | (#46049675)

My dad could kick you dad's ass. ;P

Re:Comparison to Chess? (2)

Vintermann (400722) | about a year ago | (#46049087)

Go is a perimeter game and is really no more complex than Othello. A simple neural net (I hate that fucking term) algorithm trained against average Go-playing humans will end up being average at playing Go.

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:Comparison to Chess? (0)

sexconker (1179573) | about a year ago | (#46049727)

Go is a perimeter game and is really no more complex than Othello. A simple neural net (I hate that fucking term) algorithm trained against average Go-playing humans will end up being average at playing Go.

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:Comparison to Chess? (1)

Anonymous Coward | about a year ago | (#46050087)

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 consistently against a strong amateur on a full board, notwithstanding the occasional hyped success against people who have no reason to take the match seriously.

Re:Comparison to Chess? (2)

nojayuk (567177) | about a year ago | (#46049305)

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 as there are many fewer possibile moves on each turn and ownership of large areas of the board have already been decided or conceded at which point calculating a full solution to the end is possible. Its the tricky bit in the middle that's the fun part (especially ko fights).

Small-board Go of 7x7 size has a small enough number of unique positions that its gamespace could be exhaustively evaluated today given the ubiquity of rentable cloud computing and cheap storage to hold the results. All it would cost is time and money. Creating a good Go-playing computer program which can evaluate positions and choose moves wisely is more tricky.

Re:Comparison to Chess? (0)

sexconker (1179573) | about a year ago | (#46050067)

Exactly my point. Go isn't complex, it just has a deep tree that gets very wide at the middle.

Naively walking that tree based on the board's current score is computationally insane, but it's the approach most "Go is more complex than chess!!!" zealots and dumb algorithms take.

When you actually analyze a given board beyond simply scoring that board as-is, you can develop a much more accurate score for each branch. For a fixed amount of time/storage, this means your decisions as to what the best move is will be more accurate. The trick is identifying advantageous boards.

In Chess, we use the values of the different pieces to determine a board's score for the deepest move searched, with an end-game board being absolute.
In Go, you look at the perimeters of territories for the deepest move searched.

Saying Go is complex because some people employ a naive algorithm is like saying calculating Fibonacci numbers is complex because some people use a recursive algorithm to calculate it instead of a simple loop.

Re:Comparison to Chess? (1)

ShanghaiBill (739463) | about a year ago | (#46048813)

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:Comparison to Chess? (1)

Vintermann (400722) | about a year ago | (#46049053)

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 than Zen will be in 5 years.

Re:Comparison to Chess? (1)

nojayuk (567177) | about a year ago | (#46048081)

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:Comparison to Chess? (2, Interesting)

bluefoxlucid (723572) | about a year ago | (#46048555)

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 different to Go in 19x19. On a 13x13 board, abstract strategy and tactics both apply simultaneously: control of a corner exerts strong influence over another corner, and you can develop very quickly. Strategic moves must also be tactical.

Go in 19x19 is, early on, strategic: the stretch of influence is too big, and only vague tactical considerations are helpful because of too much variation. Early play accounts for strategy alone: it accounts for providing a position that has strong but non-specific tactical value for all variations. As the board develops, tactical situations arise: the strategy employed provides a variety of tactical responses to tactical approaches. This exercises, both separately and conjointly, the full utilization of abstract strategic thinking and logical tactical computation.

Thus Go 9x9 and Chess are both tactical calculation; Go 13x13 is strategic-tactical or tactical depending on position, weakly exercising abstract reasoning and more strongly exercising tactical calculation; and Go 19x19 exercises the full breadth of abstract strategic thinking, blended thinking (including feedback looping tactics into strategic impact and strategy into tactical options), and direct tactical thinking (when the immediate position is only a win-lose proposition, not a resultant strategic position proposition).

I am better at Go 13x13 because I can cover the weaknesses in my abilities while abusing the weaknesses in my opponent's abilities. It is an easy game for me because I start with the option of using whichever mode of thinking I'm better at in the current position, and retain that until it's too late to really swing the game. 9x9 relies on tactical calculation, while 19x19 relies on effective use of the greatest breadth of mental skills based on what's on the board more than what I feel like I can handle at the time; I like 19x19 because it forces me to grow and learn.

Computational analysis is not relevant for wide-play of Go because it's impossible and there are other, more abstract ways to do this. There are even computer algorithms to analyze influence and use this to analyze strategic strengths and weaknesses, then analyze those areas of the board to analyze the strategic position. Humans are better at it, but direct computation isn't the only way to approach the problem.

Re:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46047857)

About the same as the number of particles in the universe. An exact number is not known.

Re:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46047919)

About the same as the number of particles in the universe. An exact number is not known.

I think that is true for both numbers.

Re:Comparison to Chess? (2)

jellomizer (103300) | about a year ago | (#46047935)

Well lets find out.
1... 2... 3... 4... 5...

Re:Comparison to Chess? (1)

jellomizer (103300) | about a year ago | (#46047949)

6... 7... 8... 9... 10... 11... 12... 13...

Re:Comparison to Chess? (1)

Sarten-X (1102295) | about a year ago | (#46048113)

14... 15... 16... 17... 18... 20... 21... 22... 24... 25... 2- aw crap, I lost count.

1... 2... 3...

Re:Comparison to Chess? (1)

immaterial (1520413) | about a year ago | (#46048173)

14 15 16 17 18 19 20 21 22...!

You need to count faster or this shit will take forever, man.

Re:Comparison to Chess? (1)

SleazyRidr (1563649) | about a year ago | (#46049973)

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:Comparison to Chess? (1)

jellomizer (103300) | about a year ago | (#46047925)

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? (4, Informative)

Anonymous Coward | about a year ago | (#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:Comparison to Chess? (1)

Anonymous Coward | about a year ago | (#46047971)

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:Comparison to Chess? (1)

WillAdams (45638) | about a year ago | (#46048127)

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:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46048139)

Google "chess unique positions" led me to the wikipedia page for Shannon number.

Upper bound currently seems to be 2^155, or a little less than 10^47.

Re:Comparison to Chess? (1)

krkhan (1071096) | about a year ago | (#46048287)

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). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown ... by De Groot, who averaged the number of legal moves in a large number of master games. Thus a move for White and then one for Black gives about 103 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move!"

Re:Comparison to Chess? (1)

Dunbal (464142) | about a year ago | (#46048749)

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:Comparison to Chess? (2)

krkhan (1071096) | about a year ago | (#46048967)

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 the game of chess.

Re:Comparison to Chess? (0)

Anonymous Coward | about a year ago | (#46050077)

It's a shame we can't use parallel processing.

Re:Comparison to Chess? (1)

maestroX (1061960) | about a year ago | (#46049377)

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 fun (1)

Dan East (318230) | about a year ago | (#46047767)

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)

This is why I don't play deterministic games (0)

Anonymous Coward | about a year ago | (#46047803)

There should be an objectively perfect move to make in every situation. It gets boring fast.

Re:This is why I don't play deterministic games (1)

rodrigoandrade (713371) | about a year ago | (#46048225)

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.

Re:This is why I don't play deterministic games (1)

Hatta (162192) | about a year ago | (#46048367)

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.

Re:This is why I don't play deterministic games (2)

bluefoxlucid (723572) | about a year ago | (#46048783)

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.

Re:This is why I don't play deterministic games (1)

Vintermann (400722) | about a year ago | (#46049383)

Again Go proves superior: Memorizing Go openings is a start. Learning why they work the way they do is required.

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:This is why I don't play deterministic games (0)

Anonymous Coward | about a year ago | (#46049555)

Again Go proves superior: Memoriz-

*sigh* Yeah, I suppose you can't have a single goddamned discussion about chess anywhere in the world without some Pocky-sucking weeaboo hijacking the conversation to evangelize motherfucking Go.

No, no, please. Do go on about how inferior our forms of entertainment are. Please let us know in detail how wrong we are for appreciating the less-than-perfect things that come from countries that aren't from eastern Asia. We want to hear allllllll about it.

Re:This is why I don't play deterministic games (1)

Dunbal (464142) | about a year ago | (#46048771)

It's only fun for the good players :)

Chess (5, Funny)

Anonymous Coward | about a year ago | (#46047805)

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

Re:Chess (1)

KingOfBLASH (620432) | about a year ago | (#46047975)

You've never played against me... I bet I'd lose more.. ;)

Re:Chess (1)

Dunbal (464142) | about a year ago | (#46048789)

He always resigns on the first move, so I doubt it.

Re:Chess (1)

Kjella (173770) | about a year ago | (#46049287)

For some reason this [despair.com] comes to mind...

Re:Chess (0)

Anonymous Coward | about a year ago | (#46049813)

You need to find a new hobby man, try patience or minesweeper!

different than tic tac toe or connect 4? (1)

zerosomething (1353609) | about a year ago | (#46047809)

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? (4, Informative)

mrchaotica (681592) | about a year ago | (#46047839)

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

Re:different than tic tac toe or connect 4? (2)

i kan reed (749298) | about a year ago | (#46047865)

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:different than tic tac toe or connect 4? (0)

Anonymous Coward | about a year ago | (#46047885)

Since one side will have perfect play, and the human side will not, hence your word needs to be changed to "losingness".

Re:different than tic tac toe or connect 4? (1)

i kan reed (749298) | about a year ago | (#46047959)

I tend to play games with friends.

Re:different than tic tac toe or connect 4? (1)

noh8rz10 (2716597) | about a year ago | (#46048019)

let's play wwf. what is your screen name?

Re:different than tic tac toe or connect 4? (0)

Anonymous Coward | about a year ago | (#46050483)

let's play wwf.

World Wildlife Foundation? See who can save the most animals?

Re:different than tic tac toe or connect 4? (1)

sjames (1099) | about a year ago | (#46048049)

Unless the complexity is sufficient that the computer has to utilize heuristics as well.

Re: different than tic tac toe or connect 4? (0)

Anonymous Coward | about a year ago | (#46048185)

See Arimaa

Re:different than tic tac toe or connect 4? (1)

mrchaotica (681592) | about a year ago | (#46048175)

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 3)
  5. X blocks (square 7)
  6. O blocks (square 4)
  7. X blocks (square 6)
  8. The game is a draw.

Every perfectly-played game follows this sequence, after accounting for rotational and reflectional (is that a word?) symmetry. (There are other sequences that could be called "equally good" because they still result in a draw, but I suppose they aren't "perfect" because they contain more moves.)

Re:different than tic tac toe or connect 4? (1)

CastrTroy (595695) | about a year ago | (#46048693)

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.

Re:different than tic tac toe or connect 4? (1)

Vintermann (400722) | about a year ago | (#46049505)

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:different than tic tac toe or connect 4? (0)

Anonymous Coward | about a year ago | (#46050427)

You could analyze all their board positions and check if a perfect opponent would have ever beat them from that point. It still wouldn't "prove" it, but it would go pretty far towards it.

Re:different than tic tac toe or connect 4? (1)

Greyfox (87712) | about a year ago | (#46049509)

The only way to win is not to play!

Re:different than tic tac toe or connect 4? (2, Insightful)

Anonymous Coward | about a year ago | (#46047887)

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:different than tic tac toe or connect 4? (1)

ShanghaiBill (739463) | about a year ago | (#46048993)

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:different than tic tac toe or connect 4? (1)

Vintermann (400722) | about a year ago | (#46049459)

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 exhausting all possibilities.

Grammar? (1)

AmiMoJo (196126) | about a year ago | (#46047855)

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? (5, Funny)

zerosomething (1353609) | about a year ago | (#46047991)

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:Grammar? (1)

gstoddart (321705) | about a year ago | (#46048077)

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

But ... but ... spieling cunts.

Re:Grammar? (0)

Anonymous Coward | about a year ago | (#46048027)

This is perfectly ordinary game-theory terminology.
Most wouldn't even call it jargon; it's quite cromulent.

Re:Grammar? (1)

sexconker (1179573) | about a year ago | (#46048197)

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? (0)

Anonymous Coward | about a year ago | (#46048589)

Cars come in many colors. This car is a red.

What kind of pillow do you want? I'll take a soft.

Would you like fries with that? Give me a large.

Do those burritos have habanero in them? The spicy does.

What kinds of words are implicitly in a sentence? Elided are.

Re:Grammar? (0)

Anonymous Coward | about a year ago | (#46049915)

Where I live, "Give me a large" is the only one of your examples that a self-respecting intelligent person would say. The rest have not crept into the vernacular at all. In fact I think the last one would get you beaten and robbed in an alley.

Re:Grammar? (0)

Anonymous Coward | about a year ago | (#46050317)

Re:Grammar? (5, Funny)

Anonymous Coward | about a year ago | (#46048035)

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

HINT: Last player always wins.

Re:Grammar? (1)

jratcliffe (208809) | about a year ago | (#46048839)

Another game of that is something up with which I will not put.

Re:Grammar? (2)

noh8rz10 (2716597) | about a year ago | (#46048041)

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:Grammar? (1)

Anonymous Coward | about a year ago | (#46048071)

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

Just Goes To Show You (0)

Anonymous Coward | about a year ago | (#46047867)

Finally, we have even more proof that games are only fun when played by, with, or against humans. Maybe that's why computers are incapable of inventing new games to play...

I don't really understand why everyone freaks out about a computer that "wins" by exhausting every possible conclusion and following the obvious path to victory. If you showed them a person doing that, they would be indignant and bored. Apparently watching a computer do something that is very easy for computers to do is more entertaining than watching a human do something that is very difficult for a human to do.

Now how easy is it to remember? (1)

ZahrGnosis (66741) | about a year ago | (#46047879)

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:Now how easy is it to remember? (1)

Uninvited Guest (237316) | about a year ago | (#46048213)

Cue augmented reality app link

Re:Now how easy is it to remember? (1)

Laxori666 (748529) | about a year ago | (#46048383)

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.

Re:Now how easy is it to remember? (0)

Anonymous Coward | about a year ago | (#46048969)

Actually, it takes 15 seconds on a single core. There is no need to hook up to a supercomputer.

Wargames... (5, Funny)

Rhaban (987410) | about a year ago | (#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:Wargames... (1)

Dunbal (464142) | about a year ago | (#46048837)

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

OMG Spoiler Alert!!! (0)

Anonymous Coward | about a year ago | (#46048097)

Now who's going to play that anymore?

Plagerism (1)

Anonymous Coward | about a year ago | (#46048217)

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 (2)

multimediavt (965608) | about a year ago | (#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.

Trax (0)

Anonymous Coward | about a year ago | (#46050465)

How about using a super computer to solve playing trax instead of these boring knowingly-bound games.
http://www.traxgame.com/about_rules.php

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?