How Do You Detect Cheating In Chess? Watch the Computer 328
First time accepted submitter Shaterri writes "Which is more likely: that a low-ranked player could play through a high-level tournament at grandmaster level, or that they were getting undetected assistance from a computer? How about when that player is nearly strip-searched with no devices found? How about when their moves correlate too well with independent computer calculations? Ken Regan has a fascinating article on one of the most complex (potential) cheating cases to come along in recent memory."
Re:Simply put.. (Score:4, Informative)
Not necessarily: The best human chess players can beat the not-best computer chess programs.
Re:Did they give him an anal probe? (Score:3, Informative)
Re:Simply put.. (Score:5, Informative)
It seems pretty obvious upon RTFA that this guy is likely to have cheated.
One of Ivanov’s losses was in a long game in a closed position (the kind where computers perform poorly), and at the end, Ivanov made a rudimentary mistake. It stood out because of how well he had played in the other games. The other loss was in the penultimate round, when the organizers, as a precaution, stopped broadcasting the games on the Internet so that people outside the playing hall could not try to assist the players.
Please mod this post up so other people can see it -- I'm sorry I don't have an account and I'm late for work.
Re:Simply put.. (Score:5, Informative)
It is mathematically proven to be unsolveable within finite time
Every game ends in a finite number of moves, therefore the permutation of all games is also finite.
Re:Simply put.. (Score:5, Informative)
In addition to the problems pointed out by MyLongNickName, it is worth pointing out that problems being in NP don't mean they aren't solvable. Quite the opposite in fact: any fixed problem in NP is solvable. The issue is that some problems in NP (the so-called NP complete problems) are conjecturally difficult to solve. Roughly speaking, P is the set of questions which can be solved in time that is bounded by polynomial of the length of the problem statement. So for example, "Is the number n prime?" can be answered in time which is polynomial in the length of its input (here the input is the digits of n). Problems in NP are problems which when the answer is "yes" a proof exists that is the answer is yes, and the proof size is bounded by a polynomial of the input length, and the proof can be verified in polynomial time. So to solve a problem in NP one essentially needs to just check all the possible proofs of short size. The big conjecture is that P and NP are actually distinct- that is that there are problems where it is easy to prove a solution works but finding a solution is tough.
But there's another problem here. Even saying that chess is in NP isn't accurate. There are multiple generalizations of what one means by chess and since complexity classes require not single problems but sets of problems, what framework you use to call "chess" matters. http://cstheory.stackexchange.com/questions/6563/what-is-the-computational-complexity-of-solving-chess [stackexchange.com] discusses this in some detail. In some frameworks, "chess" is actually in the much larger set of EXP or PSPACE, which are worse than NP in general, but are still finite time solvable.
Re:Simply put.. (Score:4, Informative)
Re:Simply put.. (Score:5, Informative)
The penultimate round was also against the strongest opponent, the tournament winner. Ivanov won the final match, which had no Internet broadcast.
We appear to need a more complex answer than "the cheating was done using the broadcast".
Re:Did they give him an anal probe? (Score:4, Informative)
No, he lost the second-to-last round playing the eventual tourney winner, during which the broadcast was shut off.
He won the last round with no broadcast.
Re:Simply put.. (Score:5, Informative)
So it is doubtful that Garry Kasparov would lose to Chessmaster XI at its highest AI on a normal computer a.k.a. not Deep Blue.
Don't bet on it. Deep Blue [wikipedia.org] was designed in 1996. That was 17 years ago. A modern laptop has more computing power than Deep Blue had. Chess algorithms have also improved. You can download free chess programs from any app store that will play at grandmaster level.
Playing chess against a computer is like having a weight lifting contest with a forklift.