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?

Meet TOPIO 3.0 (TOSY Ping Pong Playing Robot). It’s a big step for AI, but can a machine ever be conscious?

What makes humans conscious? As mere collections of organic matter, it’s pretty impressive that we’re even able to ask ourselves this question. What is it that makes our power of self awareness possible?

Setting aside the task of defining what consciousness really means, where does it come from? Here are the options:

1. Humans are not conscious – it’s just an illusion.
2. Consciousness comes from something physical (the brain).
3. Consciousness comes from something non-physical (a soul).

These are the only possibilities, right? Let’s look at each one.

1. Humans are not conscious – it’s just an illusion.

If this is the case, then we immediately run into an apparent contradiction. How is it possible to think about whether you’re conscious without actually being conscious? This is very similar to the argument behind “I think, therefore I am.”

Still, I don’t think we can rule it out entirely. Sometimes I look into the mirror and wonder, “Are you really me, or do I just think you are? And if the latter, do I really think you are, or do I just think I think you are?”

2. Consciousness comes from something physical (the brain).

This seems like a simple and obvious answer, but it’s really not. Because if consciousness comes from the brain, then there’s no reason we can’t build a conscious machine simply by replicating the brain with mechanical parts.

Sure, we’re currently far from having the technology to interconnect 100 billion artificial neurons with 100 trillion artificial synaptic connections. But technology has improved a lot over the last hundred years. What will happen over the next million?

I wouldn’t be too quick to predict limits on technological progress. When we build semi-intelligent nanobots, won’t they be capable of helping us build more intelligent nanobots? And then won’t it be easy to build a brain far better than what we have now?

But no matter how advanced future technology may be, I still have a hard time seeing the leap from artificial intelligence to artificial consciousness.

Artificial intelligence is easy. Even if a program isn’t truly intelligent, it can easily give the appearance of being so. As an example, consider Harold the tic-tac-toe AI.

Harold is a tic-tac-toe program I wrote the other day to test out an idea. He’s really not intelligent in any sense. For example, he doesn’t understand (nor will he ever learn) that if you put two X’s in a row, he needs to block you. All he does is make arbitrary decisions, then he sees what happens.

If he ends up losing, he knows he made a mistake, so he won’t do that again. And if he ends up tying, he knows to try something different next time, in case a win was possible. It’s a bit agonizing to wait for him to learn by playing out all the different variations, but after he’s made every mistake once, he’ll play perfectly.

Now, if Harold just played out all these games in his head before playing against a human, he’d have the appearance of being intelligent. And given an arbitrarily high processing power, there’s no reason we couldn’t generalize this concept to have him play perfect checkers, chess, or indeed solve any problem that had well-defined rules and goals.

And that’s without having any actual intelligence at all – just brute force and a good memory. The possibilities will become really interesting when we start making significant progress on true AI: deduction, reasoning, problem solving, knowledge representation, planning, perception, creativity, etc.

We still have a long way to go before you can have a conversation with a robot without figuring out he’s a robot. But I don’t think intelligent robots (or at least, robots that appear intelligent for all practical purposes) are much of a stretch at all in the very long term. Last April, a program extrapolated the laws of motion from a pendulum’s swings, including conservation of momentum and Newton’s second law (F = ma), without having been programmed with any knowledge of physics.

Let’s say we get to the point where we have true AI. You can talk to a robot (or really, just a program – an AI doesn’t need a body) and fully enjoy its witty banter, beautiful poetry, insightful Zen koan interpretations, etc. It’s still just a program, right? It has no sense of awareness or subjective experience.

Can you imagine a program being truly conscious? Wondering what its life purpose is, whether this external hard drive makes it look too fat, and when it will finally get the right to vote? Moving it to the recycle bin would be kidnapping, and deleting it would be murder. Ridiculous, right?

3. Consciousness comes from something non-physical (a soul).

This would provide a nice answer to the previous question – a program can’t be conscious, because it doesn’t have a soul. Of course, this option comes with its own problems, not the least of which is that it’s a severe violation of Occam’s razor.

The absence of supernatural phenomena is the simplest possible explanation, and therefore most likely to be the correct one. Unless, of course, it’s too simple to be possible.

When a car shuts down from a dead battery, you just put in a new one and it comes roaring back to life. Why doesn’t the same thing happen with people? If someone dies from a heart attack, why can’t you just repair their heart (and anything else that may need it) and watch them come back to life?

What part of them has really died, if all their organs are completely intact? Why doesn’t Frankenstein work in real life?

Then again, maybe it does. The real problem with a fatal heart attack is probably that it causes brain death, and nerve cells aren’t easy to repair. But is this just a matter of technology?

Can we someday inject nanobots into someone’s bloodstream, having programmed them to repair any and all cell damage, and expect the person to live indefinitely in perfect health, not even aging?

Which of these is the right answer? I have no idea.