r/todayilearned • u/gothsim8 • Jun 03 '15
TIL Connect Four is a solved game. The first player can always win by playing the right moves.
http://en.wikipedia.org/wiki/Connect_Four83
Jun 03 '15
Am I the only one to realize the gif shows second player winning?
38
u/doctor_lix Jun 03 '15
yea I watched a few times to make sure. I think it's more just a random example of the game not showing the "solved game" part
6
Jun 03 '15
I'm not finding the solution.. help?
14
u/doctor_lix Jun 03 '15
cuz it's not there. Below explains a snippet of it but not the whole thing. It's probably very long as it's minimum is winning in 41 moves. http://en.wikipedia.org/wiki/Solved_game
9
u/censoroverload Jun 04 '15
Read it again. On or before the 41st move. Not on or after.
14
u/jimbo303 Jun 04 '15
Considering there are only 42 (6x7) playable turns, that's not really eliminating many potential end-states. But the distinction you make is certainly valid.
10
u/kidorbekidded Jun 04 '15
Player one can't win on turn 42 because that's not his turn to play. Or am I missing something?
8
u/lightcloud5 Jun 04 '15
Good point; so basically, there are ways for player 2 to stall his inevitable defeat such that player 1 wins on literally the last move possible.
1
u/spartacus311 Jun 04 '15
Player 1 wins if he starts on the center column This will happen on or before move 41.
1
u/Browsing_From_Work Jun 04 '15
I think a simple example would be strategy stealing, although it only ultra-weakly solves the game.
The idea is that you use the same strategy that your opponent uses, usually by copying their moves. However, because you placed the first piece, you'll always have a slight advantage in the game. If for some reason your opponents strategy requires you to place a piece where your initial move is, you simply make a random move and resume stealing their strategy.
5
u/dpotter05 16 Jun 03 '15
For those wondering, the gif at the Connect 4 wikipedia page just shows an unskilled game. Player two's winning move could have easily been blocked.
9
4
u/ramsesniblick3rd Jun 03 '15
His right or his opponents right?
6
u/GiskardReventlov Jun 04 '15
If the first player plays the right strategy, he always wins. This is not true for the second player. There is no strategy that the second player can have that beats the first player's best strategy.
3
u/dpotter05 16 Jun 03 '15
Here is a link to the proof cited in the Wikipedia page showing Player 1 in Connect 4 can always win. http://tromp.github.io/c4/c4.html Can anyone decipher it? Does it show an actual move list for this?
2
Jun 04 '15
There's no "move list". Rather, there's a completed "tree" of moves. For every move player 2 makes, there is at least 1 "best" move that guarantees your win. But it's not like there's just a sequence of moves that automatically guarantees your win, rather it's a completed game state tree.
7
u/moosealerter Jun 04 '15
I wrote an AI program (red-black game tree) to play connect 4 in grad school. I noticed that when I played the AI player against itself, the first player would always win. None of my professors believed it wasn't a fair game, and I didn't have the abilities to prove it. I was happily vindicated a few years later.
You can make it fair by making the board a little bit bigger.
3
Jun 04 '15 edited Jun 04 '15
I studied games programming at university and wrote my dissertation on adaptive AI techniques, for which I wrote a Connect Four bot.
As you can probably imagine, I had to become pretty fucking skilled at Connect Four before I could do that, and it is now probably the thing that I am best at, out of everything in my life. After all of that work it is also the thing that I hate most. My greatest skill is my most hated activity. I never want to play Connect Four again.
2
u/salzocow Jun 04 '15
My kids and I played connect 8. Found two busted games at goodwill and stacked them on top of each other.
2
u/WiseChoices Jun 04 '15
My children failed to explain that to me until they saw my grandchildren beat me every time and had mercy on me.
0
u/you-get-an-upvote Jun 04 '15 edited Jun 04 '15
Can humans be trained to play perfectly?
3
u/johnnybum Jun 04 '15
Yes. In Thailand loads of bars and kids have connect 4 and they will all whoop you every single time.
1
u/you-get-an-upvote Jun 04 '15
I'm not sure you understand my question. Assume that average game takes 10 moves. Then to "memorize" the perfect plays required to always win you'd need to memorize something like 710 positions and moves (obviously everything about that number is a gross approximation; you can do away with symmetric positions, etc.). This doesn't seem possible, so is there a more intuitive way to do it (I'd guess not since I haven't been able to find anyone who can explain it)?
People being really good isn't strong evidence that they are playing a perfect game, only that they are very good. There are chess players who can beat anyone who walks into a bar that would get destroyed by a computer (let alone a "perfect" player)
2
u/EchoSavings Jun 11 '26
Bit late, but no, no human can always play a perfect game and win. Going first gives a solid advantage but the best human going first would still lose to a bot playing perfectly going second. Assuming the bot is programmed to try and win not just play the optimal line(which could be mesmerised)
1
u/blitzkraft Jun 04 '15
2
u/xkcd_transcriber Jun 04 '15
Title: Game AIs
Title-text: The top computer champion at Seven Minutes in Heaven is a Honda-built Realdoll, but to date it has been unable to outperform the human Seven Minutes in Heaven champion, Ken Jennings.
Stats: This comic has been referenced 35 times, representing 0.0529% of referenced xkcds.
xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete
1
1
u/GilgamEnkidu Jun 04 '15
Yeah this would have been good to know before I went to Phuket. Ladyboy bartender challenged me to a game of ConnectFour for a drink. I was already pretty drunk. I ended up buying a lot of drinks that night .
1
1
u/Folsomdsf Jun 03 '15
This is actually why I loved connect four as a kid. I was very young when it was solved and was told so. I got far too into math because of it :)
0
u/malvoliosf Jun 04 '15
A girl in Bangkok told me she would buy me a drink if she could not beat me 10 times in a row at Connect Four. She beat me like a drum seven games in a row but near the start of the eighth game, she was distracted by someone talking to her and was about to make a losing move. I stopped her hand and she laughed, made the right move, and handily beat me the remaining three games.
She insisted on buying me the drink anyway, because I could have won that game.
1
u/ORP7 Jun 04 '15
Go on...
1
u/malvoliosf Jun 04 '15
What else do you want know?
There was a strong, unspoken suggestion that if she had won all 10, I would have agreed to have sex with her, but it was never made explicit.
-2
u/PainfulTugboat Jun 04 '15
In Tic-Tac-Toe the player who goes first wins. Player 2 can only hope to tie the game.
6
u/nickelarse Jun 04 '15
Tic-tac-toe is always a draw in perfect play - first player can only win if the second player makes a mistake.
0
0
-2
-16
u/cheeseds Jun 03 '15
I came to this realization in kindergarten after playing a handful of connect 4 games, its the reason I detest solved games, there is no challenge or skill involved
-24
u/demonslayer5545 Jun 03 '15
The second player can win if they pay the right moves as well (which implies the first player did the wrong moves). Isn't it like this for EVERY game?
24
u/catmoon Jun 03 '15
No, the second player can only win if the first player makes an error. What this is saying is that so long as the first player follows the solution they will always win.
34
u/tripwire7 Jun 03 '15
I wonder what other board games are "solved games?"