Imagine someone who cheats. He might be a poker player, someone with hidden cameras to watch other people’s cards. Or maybe she’s an athlete who secretly takes performance enhancing drugs. One thing is for sure, about this cheater in your mind: he’s probably not sitting in front of an eight by eight board, moving his rook to C4. But chess has cheaters too, and a new model is trying to ferret them out.
Chess has the air of mental mastery – a game that requires brains and constant calculation. But like any game, there are cheaters. At last year’s Chess Olympiad three players were accused of sending coded text messages to one another. Those players were banned from the game for five years.
But when so much of chess is in players heads, and the players at the top are so good at what they do, how do you tell cheating from simply great play? Enter Kenneth Regan, mathematician and international chess master.
By day Regan studies math – the epic P versus NP problem – but in 2006 he got interested in this question of cheating in chess. That year the chess world championship was the location of what chess aficionados call “Toiletgate.” Vladimir Kramnik, the Russian opponent of the Bulgarian Veselin Topalov, was accused of consulting a computer in the bathroom. That bathroom was then locked, but Kramnick refused to continue playing until it was unlocked.
“I thought that the chess world needed someone to try to help investigate these accusations,” Regan told the New York Times. “I felt I was qualified. I felt some definite responsibility.” (Regan was an online commentator that year).
Figuring out who's cheating requires a mathematician because chess is extraordinarily complex. Wolfram Alpha, the encyclopedia of all things math, has a whole page about it. The current estimate for the number of possible games of chess is 10^120 (also known as the Shannon number, after Claude Shannon who worked it out). That’s 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000, 000,000,000,000,000,000,000 different games.
The math there goes like this. Let’s say white goes first. When the game starts there are 20 possible moves for the white side. In response, the black side can make 20 moves. So in the first two moves, there are 400 possible configurations. For the second move, there are now 20,000 possible positions, and so on and so forth.
But even though there are so many possible games, the sample size of moves that Regan has to look at for each player is small – something like 150 or 200 moves for the tournament. There are computer programs that evaluate the value of each move – for example, how much better is moving my knight to C4 rather than E5? But the computer will give you that result in a unit of 1/100th of a pawn. Changing tiny increments changes the whole outcome from the computer - how can you know what is chance and what is cheating?
So Regan started building a model using the moves from games all the way back to the 19th century. By now, he’s analysed almost 200,000 games, including ones from the top 50 tournaments in history. What he can do is look at that computer program and see which moves it predicts, and then compare those moves with the ones of the alleged cheater.
But because chess is so complicated, even Regan’s model can’t conclusively say whether a chess master is really cheating. All he can do is say that the move the player chose is strangely similar to those chosen by a chess program.
If chess isn’t something you think about every day, it’s important to note that these kinds of models aren’t just about figuring out who’s cheating. “What he is doing, what these people are doing, is they are trying to model how people make decisions,” Jonathan Schaeffer, a computer science professor who invented a program that solved the game of checkers, told the New York Times.
Understanding how people behave and make choices is just as, if not more complicated that the number of moves involved in chess. Regan’s model could provide insight into our economic choices, and how we weight all the information around us to make decisions.
Via the New York Times
Photo from David Lapetina, Wikimedia Commons