Thursday, February 04, 2010

Computer Chess

I have just read a wonderful article by Gary Kasparov called The Chess Master and the Computer. In it he describes how the earliest efforts to construct chess-playing machines were motivated in part from a desire to understand human learning processes, but how this ambitious goal quickly gave way to what's known as the brute force approach in which millions of possible board positions are systematically evaluated for the best possible move. The result is that there are now chess programs capable of playing at grandmaster level on a powerful PC and the question of the superiority of the human player or computer has been resolved in favour of the latter.

But Kasparov does not leave the matter there and this is where the article is so interesting. Though he was defeated in a chess match by IBM's Deep Blue in 1997, there is no resentment in his critique. While bemoaning the contemporary pragmatist approach in which 'the dreams of creating an artificial intelligence that would engage in an ancient game symbolic of human thought have been abandoned', Kasparov remains true to the conviction that research into game playing machines is as much about understanding human thought processes as it is about demonstrating the calculating power of computers. And he describes a new form of chess competition - advanced chess or freestyle chess - played between teams of human players using computers. Some of the insights gained from such competitions, in which the only constraint is the time available to each team, are fascinating - but for that you should read the article for yourself.

Reading the Kasparov article brought to mind a computer chess project of my own - mobility chess.

The way chess programs work involves the computer identifying all the possible moves available to it and, for each of those moves, all the possible responses available to the other player and so on, with the resulting board positions proliferating like the leaves on a tree. The number of moves that the computer can look ahead depends on the computer power available. In practice, the search is refined by considering only sensible moves on each side. Each of the board positions examined is given a score according to an evaluation function that assesses the value of the pieces and their positions. The computer selects the move that will lead to the board position with the highest score despite all the best efforts of its opponent.

The unique feature of mobility chess is the extreme simplicity of its evaluation function. While most evaluation functions attempt to assess the inherent strength and security of individual pieces or patterns of pieces, in mobility chess the only thing that counts is how many distinct moves there are available to choose from. For a given board position, the program simply counts the number of alternative moves available to the player whose turn it is and subtracts the moves available to the other player.

I wrote the program and played it a few times. It played an interesting game considering its sole goal was to keep as many options open as possible. It's principal weakness was an annoying tendency to develop its rooks too early but then that's something I recall doing myself when I first played chess as a child. Since the evaluation function in mobility chess is so simple the program has time to examine more positions - that is, to look further ahead. Perhaps looking a little further ahead would be sufficient to demonstrate the folly of early rook development - who knows? It would be an interesting exercise to develop a common framework within which different evaluation functions could be played off against one another. Would the winner be the function that took a very sophisticated (if computationally costly) view of a position or one - as in mobility chess - that is almost trivially simple?

There's no doubt which outcome I would favour; I'm drawn to that science (or is it art?) that concerns itself with ways in which complex behaviour emerges from very simple rules. But, of course, complexity is not guaranteed. Mobility chess might equally well turn out to be extremely boring. I haven't played it enough to guess at how things might turn out.

No comments:

Post a Comment