University at Buffalo - The State University of New York

• Print

• Comments

By Bert Gambini

Published: April 12, 2012

According to legend, the inventor of chess gave his game to the Sultan of India in exchange for a rice grain that would double progressively for each of the board’s 64 squares.

It was a cheat. No one could have so much rice.

The fable is amusing, but the fact is that cheating has become an issue at the game’s highest levels.

“The 2006 World Championship almost blew up over accusations of cheating,” says Kenneth Regan, UB associate professor of computer science, whose work to verify or debunk the cheating allegations was the subject of a New York Times feature story last month.

Regan has played chess nearly all of his life and is ranked as an International Master. His credentials in chess and academia put him in a unique position to investigate the 2006 match between Russia’s Vladimir Kramnik and Veselin Topalov of Bulgaria.

While careful observation might catch a card sharp, sophisticated technology is used to cheat at chess. But the same technology contributing to the dishonesty also can be used to uncover it.

Regan sits in front of his computer in a small office in Davis Hall, the new engineering building on the North Campus. Boxes overflow with papers. An iced coffee is next to the keyboard. It’s a warm day and condensation has formed on the cup, representing the struggle between the cold liquid and the room temperature. Yet, the real strain is on Regan’s computer, which is running four simultaneous chess simulations. He opens a text file that reveals some of the burden.

“That’s 458,036 lines,” he says.

He begins speaking about once accidentally clicking “print,” but stops, laughs and lifts his hand from the keyboard, making a single, dismissive stroke in the air that ends the story like it had been erased from an imaginary dry-erase board.

Regan compares actual game records to how a computer would respond under the same circumstances. Investigators can support the accusation of cheating if a player’s moves too closely match a computer’s.

He uses a program called, Rybka. Regan didn’t write it, but has modeled Rybka for chess.

Rybka examines positions 13 steps ahead of an initial move, considering 900 million possibilities in 10 minutes and processing 1.5 quadrillion positions annually through the combined efforts of two computers.

“That’s almost the U.S. national debt expressed in pennies,” he says.

That’s a stack of pennies 40,000 times larger than the solar system’s diameter, yet still, incidentally, not as many rice grains as secured by the game’s cunning inventor.

In the 2006 match, Topalov accused Kramnik of consulting a program much like Rybka during his opponent’s frequent bathroom trips. Kramnik won what is remembered as “Toiletgate.”

Organizers found the bathroom behavior as unusual as the game’s data. Kramnik’s moves closely followed computer simulations, a point that Regan said proved nothing.

So in October 2006, an online chess editor publicly asked for assistance. In that moment, Regan went from International Master to principal investigator, his first entry into chess analysis.

“Up to this point in the controversy, there was no respect for the basic norms of science,” he says. “There was a statistical coincidence, but there was no log file or any mention of methodology.”

Regan says the allegations could not be supported solely by the data. It would be like a local highway department declaring a stretch of road unsafe based exclusively on frequent accidents without considering contributing factors, such as weather conditions.

“The analogous point in chess is that some games offer players only one possible move to either maintain a defense or initiate an attack,” he says. “And there is a high statistical likelihood that a top player will find that move, just as a computer would.”

Regan says Kramnik was forced into situations and simply responded with the right move.

“When you look at the last half of the game, Kramnik does match the computer nearly all of the time,” Regan says. “But throw out those moves where he had no option and the remaining decisions are human—including one mistake.”

Despite Regan’s work, there was nothing he could do to calm the emerging crisis.

“I was going to take apart the accusation and point out the affront to science,” he says. “But instead, I was bailing water out of my basement.”

Buffalo’s “October Surprise” storm of 2006 had knocked out power to Regan’s home.

By the time service was restored, publicity surrounding the accusations already had been picked up by the mainstream press.

But Regan continued analyzing, an impressive workload considering that Rybka knows nothing about chess.

“Chess is simply the source of the numbers that give hindsight values to the various options,” says Regan. “Rybka can model any situation where you’re making a decision based on a large number of options.”

Regan says that Rybka doesn’t just look for the best option, but helps determine options for the future and evaluates how skillful people are at identifying value. “We don’t know the future,” he says, “but my model can determine how good someone is at ‘sniffing it out.’

“If we use it to evaluate an executive making financial decisions, we can put a value on what all these options were based on how things worked out,” he says. “It’s just like finding the best chess move when you don’t know if your play is going to contribute to a win or make you vulnerable to defeat.”

Curiously, Rybka itself has been the subject of accusations similar those it was designed to analyze.

“There is right now a scandal where Rybka is accused of being derived from other programs without acknowledgement,” he says.

Rybka might be a cheat?

“Absolutely.” he says. “The irony of it.”

Pass the rice, please.