Having discovered that perfect play in nuclear war is always a draw, “Joshua” from WarGames sees no point in playing it.

When people play games, they often make mistakes. Hopefully they learn from these mistakes and get a little better each time, uncovering the game’s secrets and inching ever closer to perfection.

If a game is simple enough, even casual players may figure out a system for “perfect play,” or a guaranteed way of choosing the best possible moves. Even if a game is complicated, expert players may still be able to get close to perfect play, not being completely flawless, but able to capitalize on an opponent’s single mistake.

Of course, if a person can play a game well, a computer probably can too. A computer can use its fantastic memory and processing power to look much further ahead, analyze many more moves, and become practically invincible. And if they get as far as achieving perfect play, you don’t even need to play them – you already know the outcome.

But is perfect play always achievable for a machine? And if not, can a human hope to play better? Here are five games, listed in order of increasing complexity, that offer a glimpse into what it takes to reach perfect play as man or machine.

Tic-tac-toe

Tic-tac-toe is simple enough that kids discover perfect play on their own. They realize that starting in the center gives the most options, and they take it from there.

Soon enough, they figure out that tic-tac-toe is what’s called a draw game – perfect play on both sides results in a tie. And since perfect play isn’t hard to achieve, kids quickly get bored and move on to more challenging games.

Connect Four

Unlike tic-tac-toe, Connect Four is not a draw game – the first player always wins with perfect play. So in theory, a person can beat any machine as long as they get to go first. In practice though, people don’t stand much of a chance against a perfect play program, even if they go first.

There is only one correct opening move – the center column (shown above). Any other move is a blunder against a perfect play opponent. If you start in a column adjacent to the center, you’re now playing for a draw at best. If you start in any other column, you’ve already lost. And even if you get the first move right, what about all the others?

Connect Four has 10¹⁴ possible positions, making it simple enough that the best programs can achieve perfect play, but complicated enough that people probably can’t. With practice, nearly perfect play is achievable for a human, which will be good enough against most other people, but not against the best programs.

Checkers

Photo by scott*eric

Marion Tinsley, world champion of checkers (English draughts, to some of you) from 1955-1958 and 1975-1991, is considered the greatest player ever. He lost only 7 games in 45 years, and said he could visualize 150 moves in advance. (He’s also an example of the 10,000 hour rule, having studied checkers for about 10,000 hours in grad school.)

Impressive, but how would that stack up to a computer? Well, checkers has about a million times as many possible positions as Connect Four, which put perfect play out of reach of computers for a long time, and making man vs. machine competitions interesting.

In 1990, Tinsley faced off against the program Chinook in the Man vs. Machine World Championship. Tinsley won the match with 4 wins, 2 losses (remember he had only 7 career losses), and 33 draws. Of course, that wasn’t the end of it, because programs are always getting better.

In their 1994 rematch, after six drawn games, Tinsley resigned for health reasons, and died from pancreatic cancer seven months later. Chinook was the world champion, but unfortunately it was never known if he could have beaten Tinsley in 1994.

In 1995, Chinook beat the best living human player, Don Lafferty, with 1 win, 0 losses, and 31 draws. Chinook was retired after that, when the owner decided to solve the game instead of continuing to compete with people.

They solved checkers by brute force in 2007, after 18 years of calculations on up to 200 desktop computers. These calculations proved that checkers is a draw with perfect play, and also gave Chinook an algorithm for ensuring at least a draw in all cases.

Thus, the man vs. machine debate is resolved as far as checkers goes, though you can still play against Chinook if you like (his strength has been reduced so as not to take all the fun out of it).

Chess

OK, but what about chess, the game of kings? The number of different chess positions is more than the square of the number of different checkers positions. Chess is a true thinking game that requires human ingenuity, right?

Well, it’s true that people seem to have something that machines don’t as far as chess goes. For a long time, machines would analyze millions of positions per second to achieve massive lookahead, but they’d still lose to the top human players. It’s not that the people had better lookahead; they just didn’t need it – they simply didn’t see the bad moves.

We’re still not sure what gives great chess players their ability. For example, how is it that any strong player is able to play blindfolded? In 1937, George Koltanowski set the Guinness record by playing 34 simultaneous blindfolded games, winning 24 and losing 10 in 13 hours.

There are conflicting reports about whether top chess players have better memories, better visuospatial abilities, greater intelligence, certain personality types, etc., but it’s clear that knowledge and experience are critical. It also helps to start young and be left-handed.

Anyway, whatever gift the best human players had, it let them trounce the best chess programs for a really long time. But this started to change in the mid 1990s when technology was finally starting to become a threat to the top grandmasters.

The reigning world champion Garry Kasparov, considered by most people to be the greatest (human) chess player of all time, was ultimately defeated by IBM’s chess playing computer, Deep Blue.

In 1989, Kasparov had defeated Deep Thought, an earlier version of Deep Blue, 2-0 in a 2 game match. In 1996, Deep Blue won the first game of a 6 game match, but Kasparov won the match 4-2 (with just the one loss – draws are half a point).

In 1997, a heavily upgraded Deep Blue – the 259th most powerful supercomputer in the world, capable of evaluating 200 million positions per second – defeated Kasparov 3.5 to 2.5 in a 6 game match.

It wasn’t entirely clear that the 1997 Deep Blue was a better player, because Kasparov wasn’t at his best. He resigned prematurely in game 2, believing his position to be hopeless, though later analysis revealed that it could have been a draw. And after being tied at 2.5 after 5 games, he committed an uncharacteristic blunder in the opening of game 6, resigning after only 19 moves.

Kasparov wanted a rematch, but IBM decommissioned Deep Blue, considering the man vs. machine contest to be over. Today, the computer Deep Rybka 3 has an Elo rating of 3238, far above Kasparov’s peak of 2851 (the all-time high for a human).

Chess is generally believed to be a draw with perfect play, though it hasn’t been proven (some people believe that the first player (white) can always win). And while machines are far from achieving perfect play, humans are no longer a match for the best of them.

That’s kind of depressing, isn’t it? What do people still have going for them, if even chess has been conquered by computers?

Well, computers still have one major handicap – they can’t think. When commenting on Deep Blue’s victory over Kasparov, cognitive scientist Douglas Hofstadter said:

“It was a watershed event, but it doesn’t have to do with computers becoming intelligent. They’re just overtaking humans in certain intellectual activities that we thought required intelligence. My God, I used to think chess required thought. Now, I realize it doesn’t. It doesn’t mean Kasparov isn’t a deep thinker, just that you can bypass deep thinking in playing chess, the way you can fly without flapping your wings.”

Indeed, previous attempts to make computers model the thought process of grandmasters had failed. Deep Blue succeeded largely on the basis of brute force, with only modest ability to selectively explore the reasonable moves by identifying the bad ones.

Computers are great at tactics, and humans are great at strategy. But as Richard Teichmann said, “Chess is 99% tactics,” which puts humans at a disadvantage. However, an invention of Kasparov’s called “advanced chess” combines the best of both worlds, letting a human and a computer work together as a team, with the human guiding strategy and the computer handling tactics.

But despite the massive number of different positions in chess, and despite a computer’s poor strategic ability, machines can get close enough to perfect play because chess actually isn’t as complicated as it appears.

Even for a human, chess openings don’t involve creativity. They’re based on simply memorizing predetermined sequences that have been perfected over time. Both sides might play out their first 20 to 35 moves without actually having to think, just by following standard openings.

Most people consider e4 (shown above) to be the best opening move for white, with c5 (“the Sicilian Defense,” shown above) being black’s best response. Except that every serious player knows that, so they’ve memorized all the lines that follow from it, so it loses its effectiveness somewhat.

So then people think they’ll mix it up, and d4 becomes a promising alternative as the next best opening move, except that now everybody knows that too, and they’ve memorized all the lines following from that as well.

Anyway, computers are very good at memorization, so after humans have gone to all the trouble of working out the best openings, a program can simply play them out without having to think at all.

Endgames, while often challenging for humans, can be very formulaic for a machine. Once the board is down to a small number of pieces, the perfect moves can be looked up in a database of precalculated sequences, without having to do any thinking on the fly.

The downside is the incredible amount of storage space required – 7.05 gigabytes to store all endings with 5 pieces, 1.2 terabytes to store all endings with 6 pieces, and 7 piece endings expected to be out of reach until 2015. If all endings can be worked out for 32 pieces, chess will be solved.

Some people doubt that perfect play in chess will ever be attained, but regardless, the man vs. machine debate is over. Simply by maintaining a repository of the best opening moves, storing huge numbers of endgame scenarios, and using brute force to search through millions of positions at each point in the midgame, computers have become superior in just about the only game left that some people could do better.

Go

But wait, don’t bow down before the machine just yet. People are still better than programs at Go, the ancient Asian board game. In fact, the best Go programs are routinely beaten by talented children.

There are two main reasons why. First is the computational complexity. While there are “only” 10⁵⁰ possible positions on an 8 x 8 chess board, there are 10¹⁷¹ possible positions on a 19 x 19 Go board. This is greater than the number of atoms in the universe, squared. It’s been said that a computer would need 30,000 years to look as far ahead in Go as Deep Blue could in chess in 3 seconds.

Furthermore, because chess starts with a fixed configuration and works its way down to a small number of pieces, a lot of processing time can be saved by working out openings and endings in advance. Not so with Go, where you start with an empty board, pieces can be played anywhere, and the game gets more complicated as you progress. All this makes brute force a woefully ineffective strategy.

But it’s not just the number of positions that makes Go so complicated. After all, you could simply increase the board size of any game to make it as complicated as you want.

The big problem for computers is that Go isn’t easy to understand logically. Even if computers had terrific lookahead, they’d still have a hard time evaluating the possible positions to see which one was best. Go players can often tell that a move is good, without being able to say why.

For a computer to play Go well, it’s not a matter of increasing processing power. It will take breakthroughs in artificial intelligence: learning, decision making, strategic thinking, knowledge representation, pattern recognition, and intuition.

For now, computer’s aren’t very good at these things. And that makes Go just about the only game where it pays to be human.

Let’s hear your thoughts. Will there always be a game, whether Go or something else, where the best humans can beat the best computers? Does allowing people and computers to team up, as in advanced chess, improve the game or make a mockery of it? Is a game ruined when you can simply look up the perfect moves on a smartphone? Is there a point in playing a game you know you can’t win, or is the only winning move not to play?

• Where Does Human Consciousness Come From?
• Mario And Luigi: A Tale Of Two Brothers
• I Have No Mouth, And I Must Scream
• Dweep And Lolo
• Bloxorz: An Addictive Game To Fuel Your Imagination