Forgot your password?
typodupeerror
AI Games

How Do You Detect Cheating In Chess? Watch the Computer 328

Posted by timothy
from the and-one-and-two-and-one-and-two dept.
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."
This discussion has been archived. No new comments can be posted.

How Do You Detect Cheating In Chess? Watch the Computer

Comments Filter:
  • Re:Simply put.. (Score:4, Informative)

    by dkleinsc (563838) on Tuesday January 15, 2013 @09:03AM (#42590617) Homepage

    Not necessarily: The best human chess players can beat the not-best computer chess programs.

  • by b.emile (1222958) on Tuesday January 15, 2013 @09:43AM (#42590951) Homepage
    The NYT article [nytimes.com] linked from TFA clearly states that the tournament was broadcast live on the internet, and this fellow lost due to a rudimentary mistake in the last round when the organizers switched off the live broadcast, which lends some credence to the OP's suggestion. As another poster stated, a 1 or 2 move delay in the live broadcast would mitigate this issue.
  • Re:Simply put.. (Score:5, Informative)

    by Anonymous Coward on Tuesday January 15, 2013 @09:47AM (#42590977)

    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)

    by Rockoon (1252108) on Tuesday January 15, 2013 @10:04AM (#42591121)

    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)

    by JoshuaZ (1134087) on Tuesday January 15, 2013 @10:32AM (#42591451) Homepage

    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)

    by santax (1541065) on Tuesday January 15, 2013 @10:42AM (#42591607)
    Actually, 6 piece endgames have been solved already. It's sad but true :(
  • Re:Simply put.. (Score:5, Informative)

    by mister_playboy (1474163) on Tuesday January 15, 2013 @12:01PM (#42592951)

    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".

  • by mister_playboy (1474163) on Tuesday January 15, 2013 @12:09PM (#42593103)

    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)

    by ShanghaiBill (739463) * on Tuesday January 15, 2013 @12:24PM (#42593345)

    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.

When you make your mark in the world, watch out for guys with erasers. -- The Wall Street Journal

Working...