Friday, December 15, 2006

Computer vs. The World Chess Match

Deep Fritz has defeated Kramnik 4-2 in Bonn. Let the next man versus machine contest be Computer versus The World.
But instead of playing a linear series of games, the computer program plays a game tree against humanity. Two websites support the challenge. The first stores every move made so far, publically viewable so that the humans may explore the tree so far. From any human move in the tree, a human may branch off a new variation which the computer calculates a response.

With many humans simultaneously exploring many branches of the game tree, one might expect a computer program to get bogged down. However, computer programs may be replicated, and if we don't insist on strict time controls, we can make the program always play deterministically with respect to the board configuration, irregardless of what physical processor is computing the move. Thus, on one side we have humanity exploring the game tree, and on the other a SETI@Home-style distributed computing project calculating the computer response to each new leaf.

Suppose a winning line is discovered. Humanity may celebrate that it collectively was able to defeat The Machine. But if this contest has actual prizes, we have a problem. The winning line will almost certainly be the product of many people's contributions: how do we divide the prize? The solution is to make this not a contest for the win, but an artistic one: judges award prizes according to how spectacularly embarrassingly poorly the computer is induced to play. Perhaps the programmers may weigh in on the judging, encouraging prizes for uncovering weaknesses that will be fixed in the next version of the program. Judging is the point of the second website, a forum for discussion about the artistic merit of various moves.

When the point is not necessarily to win but to demonstrate the computer playing poorly, some of those demonstrations may occur on drawn or losing lines. We wish for a mechanism to prove the computer erred, drawing or losing a line it could have won or drawn. At a drawn- or lost-by-the-computer leaf of the tree, every computer move back to the root is marked as a potential bad move. At any potential bad move, the human can switch sides, in essence claiming "I can play better from this position than you have." Care needs to be taken to avoid the computer playing against itself, and consequently positions achieved by transposition.

One interesting artistic challenge is to beat the computer once, take the line, switch sides buy some point and show that the computer could have won by beating it again as the opposite color. This will produces another lost-by-computer line, within which is another opportunity to switch sides and show how the computer could have won. The process may be repeated, and the end result is a line where the computer has given up multiple opportunities for a win, as demonstrated in the side variations.

A small variation of this grand scheme is to let "The World" consist of just one person, perhaps the human world champion. This itself is like the idea of a match that the human needs only to win one game, or prove a drawn game could have been won, to win the match.

I wonder if this could be set up as a human-computer simul, with one human and many replicates or the computer program, under the constraint that the program must play the same move in identical game states.

No comments :