Deep Blue in Check
By ai-depot | June 30, 2002
The Essence of Chess
Fundamentally, chess is a turn-based logic game. Each player gets to move one piece after the other has finished, hence the “turn-based” part. The “logic game” part implies that there is a finite set of legal options at each stage in the game, in this case defined by simplistic rules restricting the movement of pieces. The complexity of any logic game - and thereby also chess - arrises from the long sequences of moves that are required to win the game. Therein lies the challenge: a player, whether human or artificial, needs the ability to deliberate over the best sequence of moves that will ultimately win the game.
Generally, the ability of deliberative thought is associated with intelligence, hence the stereotype linking chess with brainy people and as the main challenge of A.I. There’s little doubt in my mind that deliberative reasoning is one of the components of intelligence, none the less it does not remain its only requirement!
Brute Force Approach
You may not be surprised to hear that logic games have been modelled mathematically. In fact, such studies class as a branch of economics! (Try finding a book in the library about this, chances are you’ll have to head towards the economics section ;)
Without going into too much detail, a chess game is a specific sequence of moves out of the set of all the possible moves. There are approximately 35^100 legal options for a chess game (that’s a 2 with about one hundred and fifty four trailing 0’s), which just goes to show how much there is to think about! In computer science, this is also called the search space size, so keep that in mind for the next section on Artificial Intelligence!
It’s a safe bet that nobody on earth could consider every option. The fact that no-one would have the patience to try and do so has not been an issue, until computers that is! Computers don’t mind trundelling through wads and wads of mechanical calculations at all… but unfortunately they can’t: it takes way too much time. Assuming you can process… [Alex lifts his pinky to his lower lip :] … 2 million moves per second, just like Deep Blue, the universe would end by the time you finished (i.e. 4.1477e+137 millenia away!)
Obviously, this is a problem, and in comes intelligence to the rescue.
Humans and Flaws
Someone that has never played chess before, once the rules have been explained, will usually play fairly randomly. You can’t expect much more from lazy humans… unless you place a lot of money on a win (or threaten to push them off a cliff if they loose). In this case, the approach they will attempt to take will be very naive: they will attempt to think through most options, trying to plan ahead a couple moves. They will not do very well at this, since they’ll miss out some key moves, and tend to forget what the context of their train of thougt was.
Humans are bad at this. But they have the benefit of pattern recognition and learning to give them the edge… cue the grand champions.
Experience and Learning
It is of general belief that your average Grand Champion (if you dare call any grand champion average ;) considers only few moves per second. Evidence that supports this involves chess experts talking through the options they have considered after the move has been performed. Another experiment tests their ability to remember board configurations: this would not be a problem if that many moves were indeed considered. It turns out only common board positions can be remembered by experts, and the random configurations are as much a mistery to the expert than a complete beginner. This shows two things:
- Grand champions only consider few moves consciously
- Background experience allows them to discard fruitless options
Admittedly, it’s not entirely certain that our brains process such a limited number of moves per second: what if we did everything unconciously? This interesting article debates the issue. Although this is highly unlikely, since human intelligence is first and foremost based on high-level pattern recognition and learning. This allows the grand champions to deal with a situation using empathy and knowledge-based anticipation.
This approach contrasts with the one taken by Artificial Intelligence research in computer chess over the past five decades.
Tags: none
Category: essay |
