Forgot your password?

5 Incredible Breakthroughs in Game Theory

By Edited Mar 9, 2016 3 2

Game theory is a fascinating field. Instead of just playing a game, people would dissect it, analyze it from total objective point of view and try to "solve" it, ie find the theoretical outcome with perfect play.

Computers have of course played an important part in the development of the solutions and hare are 5 incredible breakthrough that were made possible thanks to them (and thanks to the hard work of people behing them).

1. Connect Four, Solved in 1988

Who hasn't played Connect Four has a kid? But did you know that this game has been solved? And this isn't even a recent news, this has been the case since 1988!

And the result is... (the answer after the break)

Connect 4
Amazon Price: $19.99 $13.08 Buy Now
(price as of Mar 9, 2016)
Connect 4 is a fun game, based on strategy, with no luck involved. Good for kids or for long winter days...

The first player can force a win! And if you don't think this is incredible enough, have a look at the following diagram. Where would you play?

Connect Four Solution Move 3

Personally, I would have played on c1 or e1. But the only winning move is d3! With perfect play, other moves lead to a draw. 

I am not going to go through the whole solution, but just know that the game has been solved and that the first player can force a win. You can still have fun playing other moves...

2. Othello/Reversi

There are games where humans cannot compete against the computer. Othello/reversi is one of them. Why? Because there are only few legal moves and it is easy for a computer to count the number of discs in all the variations. For human beings, though, it is hard to see in advance very accurately which discs are changing color and a simple mistake of calculation for one of them can have dramatic consequences.

Quoting wikipedia: "the best Othello computer programs have easily defeated the best humans since 1980 [...]. In 1997, Logistello defeated the human champion Takeshi Murakami with a score of 6:0"

Othello/Reversi has not been entirely solved but it seems that perfect play leads to a draw. An interesting result is that the same game played on a 6x6 board has been solved and is a win for the second player (proved in 1993).

3. English Draughts, Solved in 2007

Draughts/Checkers is a fabulous board game and the only thing I regret about it is the rules difference between the countries. I have played this game with friends from Italy, Spain, UK, South Africa, etc... and I don't remember two people having the same rules.

For example, can a piece takes backwards? Must a piece takes as many pieces as possible? Can a king/queen/double piece takes even if there is some space between it and the piece to be captured....

And the slighest rule difference can cause a completely different strategy and some frustration for someone who had calculated everything with other rules. You can find a quite a comprehensive difference list at Wikipedia: http://en.wikipedia.org/wiki/Checkers#National_and_regional_variants

But back on the English draughts variant, the game has been solved in 2007 and with perfect play, the game is a draw. The program Chinook, for example is now to a level that it can not lose a single game.

To Play the Game

Sheesham & Boxwood Draughts Box
Amazon Price: $42.00 Buy Now
(price as of Mar 9, 2016)
A beautiful wooden set.

4. The Rubik's Cube Can Be Solved in 20 Moves, 2010

This is another major breakthrough. In 2007, it was proven that any Rubik's cube configuration could be solved in 26 moves or less. In 2008, this number was lowered to 22 moves.

The world was then holding its breath (didn't you?) until it was finally known that the Rubik's cube God's Number was 20. It is an incredible number in two sense.

First, because some configurations DO need 20 moves to be solved, ie we knew from a long time that we could not go below 20.

And the second magnific Nature's coincidence is that there are 20 pieces to solve in a Rubik's cube (8 corners and 12 edges).

Get a Cube!

Dayan 5 ZhanChi 3x3x3 Speed Cube White
Amazon Price: $13.99 Buy Now
(price as of Mar 9, 2016)
Despite its price, this is one of the best cubes. It was used for several world records.

5. Chess Solved to 7 Pieces, 2013

No, chess is not solved yet and I don't expect it to be in the near future. However, in Mars this year, the company ChessOK announced that they had solved the game up to 7 pieces, which means that we know for sure the outcome of any position with 7 pieces or less on the board and how to perfectly play these positions.

I read this news on their website on April, 1st and thought it was an April fool joke! Such a breaktrough was not expected before a long time (at least 2015) and I am surprised this did not bring more attention in the news (isn't game theory a very important topic?).

ChessOK is making these so-called Lomonosov Ending Tablebases available to some of his customers but in the future they will probably be available to the public.

The Future?

Those were incredible breaktrouh in Game Theory but I expect even more game solutions in the future. International Checkers, Chess up to 8 pieces, Othello/Reversi, ... Maybe even some news in games known to be hard for the computer (Shogi, Go, ...)?

Man does not have a bright future against the machine, but progress in this branch is still very exciting as it may bring many unexpected results...

Further Reading

Game Theory: A Nontechnical Introduction (Dover Books on Mathematics)
Amazon Price: $11.95 $5.97 Buy Now
(price as of Mar 9, 2016)
A nice introduction to game theory.


May 6, 2013 4:06am
Excellent article! I'm terrible at game play. Even though I've played all these games, I just cannot think that far ahead!
May 6, 2013 6:10am
Add a new comment - No HTML
You must be logged in and verified to post a comment. Please log in or sign up to comment.

Explore InfoBarrel

Auto Business & Money Entertainment Environment Health History Home & Garden InfoBarrel University Lifestyle Sports Technology Travel & Places
© Copyright 2008 - 2016 by Hinzie Media Inc. Terms of Service Privacy Policy XML Sitemap

Follow IB Entertainment