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:
  • by Luthair (847766) on Tuesday January 15, 2013 @08:54AM (#42590567)
    Done.
    • by wonkey_monkey (2592601) on Tuesday January 15, 2013 @09:08AM (#42590659) Homepage
      You'd be surprised where you can stick a Raspberry Pi, you really would.
    • by pellik (193063) on Tuesday January 15, 2013 @09:16AM (#42590719)
      While there may come a day when this is necessary, we're far from that point now.

      The man suspected of cheating in the article was relying on analysis being performed somewhere outside of the tournament hall, which was then broadcast to him. This was enabled by having the moves of all the games broadcast live over the internet (which normal for tournaments like this). When they suspected him of cheating they disabled the broadcast, and he blundered predictably. It seems that all they need to stop this kind of cheating is a simple one or two move delay on the broadcast of games.

      The economics of chess mean there isn't enough prize money to cover the cost of very sophisticated methods of cheating at the rank-and-file tournaments. There is money for the top 10 players in the world, so if cheating spreads that far maybe a faraday cage will show practical application.
      • A fifteen minute delay - rather than one or two moves - is often used nowadays.

      • by amicusNYCL (1538833) on Tuesday January 15, 2013 @06:20PM (#42597831)

        The man suspected of cheating in the article was relying on analysis being performed somewhere outside of the tournament hall, which was then broadcast to him.

        While that's a fine assumption, there's not a single bit of physical proof to back that up. That's the basis of this whole "conundrum". The entire body of evidence they have against the guy is purely statistical. It would be interesting to sponsor a challenge or competition to try and reproduce how he would have done this, starting with the participants being searched. Even so, without any proof we can't really accuse him of cheating. He can always just use the "put up or shut up" defense.

    • Re: (Score:3, Funny)

      by Anonymous Coward

      Faraday CageMatch!

  • A simple wireless enabled butt plug and knowledge of Morse code or similar encoding is all that would be required. Unless they scanned the entire frequency spectrum and found nothing, meaning that nobody in the room had an electronic device that radiates, then my good friend Occam thinks this is likely to be the answer.
    • I almost forgot the most important ingredient: Saltpeter ;-)
    • Re: (Score:2, Insightful)

      by DickBreath (207180)
      Cheating at chess requires two-way transmission of information.

      Your suggested wireless enabled anal probe allows transmission of coded data to the chess player who is cheating. But how does the remote computer know what move the cheater's opponent made? You must also describe a mechanism whereby the cheating chess player is able to transmit the opponent's move back to the remote computer.

      It is possible there could be an accomplice. Or a hidden camera.
      • by vlm (69642)

        It is possible there could be an accomplice. Or a hidden camera.

        Or a live studio audience member with a smartphone.

      • Re: (Score:3, Informative)

        by b.emile (1222958)
        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.
      • But how does the remote computer know what move the cheater's opponent made? You must also describe a mechanism whereby the cheating chess player is able to transmit the opponent's move back to the remote computer.

        Dead simple. The moves were broadcast in real time on the internet by the game organisers. This is apparently a common practice for chess tournaments, just as it is for sports. And we can be pretty sure that that's the way that this part of the cheating was done, because in the penultimate game they switched off the internet broadcast, and that was one of the two games which the cheat lost.

    • by pellik (193063)
      They didn't really even perform a strip search. He voluntarily removed his shirt and they checked his pockets. A crotched phone would have sufficed.
    • by dissy (172727)

      He was playing at a 3000 level, and suspected of cheating. So they disabled the live internet broadcast of the game, and suddenly he was playing at barely above a 2000 level.

      If you wish to claim he was not cheating, you still need to explain away how he was playing so well when and only when the game was being broadcast live over the internet, and was playing so poorly once the feed was disabled.

      The fact he was cheating is clear by that alone. Disabling a live internet feed that you yourself are not watch

      • Did you reply to the wrong post? Re-read what I wrote. I neither claimed he was or was not cheating. What I did do was offer a very simple explanation of how he could have cheated, which is valid without regard to if he cheated or not. Frankly, I don't care if he cheated or not. I simply find it amusing that there are people who couldn't think of a simple and plausible way that he may have cheated. Once again, to be clear, I certainly never stated or implied that he did not cheat.
  • by Stolpskott (2422670) on Tuesday January 15, 2013 @09:00AM (#42590605)

    It is possible that the chess equivalent of a lower-league football player could find incredible reserves of concentration and mental clarity for the first time in his career. It is equally possible that he could have solicited help in some imaginative form-
    Take athletics as an example - an athlete who improves their personal best performances year on year has not yet reached their peak. But if they improve too much in one year, then the suspicion of drug-assistance is raised and they can be tested for that. Sometimes, the athlete is guilty, but the drug is so new that their tests return a negative result, so they are allowed to continue competing. Subsequent improvements in the test process allow for re-evaluation and retesting, and retrospective bans.
    However, with a chess match, no such retrospective action can be taken because if the person cheated and was not caught, how are the invigilators (referees) going to retest? Was the cheating mechanism some kind of visual signal from the audience? If an audience is allowed to live-observe the games, you can have cameras on them, so that can be tested. But just about any other option involves the accused having some kind of signal receiver on their person, and that is not something that can be checked reliably retrospectively.
    So if they are accused on the spot, then the onus must be on the accuser to prove the accusation on the spot. No proof? Then not guilty, resume the games.

    • It is possible that the chess equivalent of a lower-league football player could find incredible reserves of concentration and mental clarity for the first time in his career. It is equally possible that he could have solicited help in some imaginative form-

      It's possible to have an outlier game but it's very, very unlikely in an activity like chess. A lot of the research into how grand masters learn and play shows that there is an amazing amount of (sub-conscious) memorization taking place. For example, show a grand master a board from a tournament for a split second and they will be able to recreate it from memory without a problem. Show them a board of equal complexity that was randomly generated (i.e. not a position that would ever occur in a real game)

    • by Solandri (704621)
      Innocent until proven guilty is a criminal prosecution standard. It's used for deciding whether to deprive someone of their personal liberties and lock them up.

      In civil litigation where deprivation of liberties is not at stake (mostly financial matters), the standard is a preponderance of the evidence. Basically if you can surpass 50% certainty.

      In private matters, a private chess tournament can throw someone out for whatever reason they damn well please. If I don't like that someone is barefoot at
  • by girlinatrainingbra (2738457) on Tuesday January 15, 2013 @09:03AM (#42590619)
    What if they are not cheating? Some possibilities:
    1 -- they learned chess mostly/exclusively by playing against a machine rather than against human opponents. Then their strategy would mostly be informed by or similar to the type of gameplay which they have observed kicking their own ass as they learned to play. Thus they might "play like a computer" because they have internalized the computer's algorithms as they learned to play chess.
    2 -- they randomly play chess in manners that appear like a computer's algorithms. In fact, hey, when they say that the person's moves closely mirror the moves a computer would make, shouldn't they specify which computer program/algorithm they mean for making chess moves? If you're running gnu/linux, you can play Xboard ( http://en.wikipedia.org/wiki/Xboard [wikipedia.org] ) as the front-end (visual GUI) with multiple possible engines [wikipedia.org] driving it underneath (such as Gnu chess [wikipedia.org]). You can even run Xboard to provide a running analysis of a game being played by others as you enter the moves played (see the man pages for analysis options). Different engines would probably come up with different moves/styles of play, right? So saying that a person's moves and play style mirror a computer is an insufficiently detailed accusation. The chess engine being suspected ought to be specified and indicated, in my opinion.
    3 -- yes it is strange that someone with a normally low rating would suddenly get so far against a grand-master, and yes it is less suspicious when that happens with a yougner player, but why couldn't it occur with an adult player? Suspicion is just suspicion, not evidence.
    4 -- there is a comment in the article about using Faraday cages at the match in order to decrease the risk for cheating. Remember that these days computers are very small, smaller than a deck of cards (yes, fancy phone in your pocket, I'm talking about you being as powerful as a supercomputer from the 1970s or 1980s). They could rig a fancy interface for their toes and have a shoe computer for all that you know.
    5 -- is this all fallout from the pete rose type stuff, or because of lance armstrong from yesterday?
    .
    :>)
    A cheating scandal in chess. Wowza.
    • by MyLongNickName (822545) on Tuesday January 15, 2013 @09:20AM (#42590765) Journal

      I play chess at the tournament level, and have played computer chess since the early 80's when the things were little more than jokes.

      You simply cannot internalize the chess computer's algorithms. Believe it or not computers suck at chess and positional understanding. I did an experiment where I played a series of games against Fritz. I gave myself infinite time, sometimes taking 30-40 minutes per moves. I am not a titled player, but am above average for a tournament player. I did very well against Fritz when I had time to make sure my calculations were solid and found many times that Fritz really misevaluated the position. In one case, it insisted that it was up by 1.5 pawns but after 6 or 7 normal humans moves that a "C" player would have found, Fritz realized it was actually slightly worse.

      Put a computer in a closed position and it flounders. The computer does not understand a position, it simply has a fairly decent evaluation engine combined with the ability to see every stinking possibility. It does not get tired. It does not have the emotional baggage that sometimes makes chess mistakes.

      The computers understanding (evaluation) of a position is perhaps FIDE (ELO) 2000. It's calculation ability is perhaps FIDE 4000. Combine the two, and you get a "person" capable of FIDE 3000 chess. Give a grandmaster more time, and you tip the balance to the positional understanding rather than the raw calculation speed.

      So now you get to the point about "internalizing" the chess moves is simply not possible. Put a computer in a complex Queen vs Rook ending, and you will see the computer play moves that a human just would never do. It isn't based on a few principles and understanding them. It is based on a 12 eyed monster seeing every stinking move possible 12-14 plies deep. Computers revolutionized our understanding of this endgame and many more.

      Beyond the endgame, there are many points in a chess game where you can tell a computer made a move. First, the move objectively works, but does not fit any type of theme, or normal principle of the game. It isn't simply a good or even great move, it isn't that it just doesn't make sense immediately but rather it doesn't fit any framework of human understanding.

      So, yes, I am convinced that you can pick up on cheating based upon a series of moves given the right circumstances.

      And no, this is nothing new. Cheating has gone on in chess for decades. Computers have just made it easier for the non-elite to cheat.

      • Even the author of the paper, KW Regan, concedes in his third paragraph that at certain board positions or at certain points in a game, alpha-beta pruning or the chess engines will come to the same "desired move" as a good human player would:
        a move that is given a clear standout evaluation by a program is much more likely to be found by a strong human player.

        from http://www.cse.buffalo.edu/~regan/chess/fidelity/ [buffalo.edu] : Measuring fidelity to a computer agent

        • Did you actually read my response?

          Of course there are points where a human will coincide with a computer. In fact in most cases this will be true. But there are points in a game where there is a wide disparity.

          A couple questions for you: Do you play chess? Have you played in a tournament? A nationally rated tournament? Played against computers at top level? Written an algorithm for computer chess? I've done all the above and though I admit I am not a master of chess, I understand how one determines someone

      • I also play chess at tournament level and respectfully disagree. Many grandmasters make moves that are unintuitive, such as Fischer, and I do not see how you could distinguish a very good computer's move from a grandmaster. I analyzed the game here: http://www.chessvibes.com/reports/bulgarian-chess-player-strip-searched-after-suspection-of-cheating [chessvibes.com] and could point out some interesting moves, but nothing that rang out as a computer move.

        From my own experience playing chess online, I end up losing on
        • I can point you to players like IM Jeremy Silman who routinely points out that a move is a "computer move" in his books. Go play a computer in a Q v R endgame with you up the Queen. It will outplay any Grandmaster. There are many open positions where a computer will play moves that a GM would not even consider.

          And who in the world would pass up fool's mate? It is a checkmate on the second move and I have no idea how this is some type of proof of a computer program?

          • I guess you didn't understand my point about losing to fools mate. A person can pass it up, a computer program cannot.

            Q v R endgame is a bad example, it is a known end game with a set pattern to win and I would assume all grandmasters know it. Although I do have trouble with it myself, but I am no grandmaster.
            • Anyone who passes up a free checkmate on #2 is clearly not a computer. It is also clearly not an intelligent person. I

              Q v R is a known pattern, but that does not mean it is a rote series of moves. I can win the ending, but a compute will put up a damn strong defense because it will push the loss out as far as possible. If the human makes an inaccuracy, they can easily go past the 50 move draw limit. Even Grandmasters have failed.

              • As a P.S., the longest forced win for the superior side in Q v R is 30 moves. So, no, this is not trivial.

                • 30 moves in a set pattern at an end game, and that is mostly just getting into position, just like a bishop & knight mate. I do not believe a supposed grandmaster would fail and the moves would look exactly the same as a computer. Here it is rated as level easy: http://board-games.wonderhowto.com/how-to/beat-rook-with-queen-chess-endgames-224673/ [wonderhowto.com]

                  As far as losing to fools mate, as soon as a person proves to be a person by skipping the obvious mate, then I resign and start a real game with the person.
                  • Re: (Score:3, Insightful)

                    by Anonymous Coward

                    I have some bad news for you; none of your opponents are computers, and your "test" is silly. Computers play chess well; if you are playing the sort of opponents who will stick around after you drop a fools mate, then you are very low rated, maybe 1100. None of your opponents will be computers because computers will all earn ratings well over 2000, and the people who are cheating won't waste their time playing you--they are cheating because they want rating points, and they won't get those from playing an 1

      • by retchdog (1319261)

        wow, the first post by someone who knows what they're talking about. in contrast, i know almost nothing about chess, but something about statistics.

        everyone should read the article. matching ivanov's moves to a computer's moves is only one test. the author of the article also has an algorithmic chess rating methodology he calls "intrinsic rating" which intends to estimate quality of play along the FIDE scale. it is, of course, flawed as any algorithm for this would be, but most importantly it is a fixed alg

    • 1. Some algorithms work by simply looking ahead at all possible move combinations by you and your opponent. It then determines a "score" based on the favor of the outcome in whichever player's direction. It may then, for each outcome or only for "favorable" ones, go down another turn for both players. Eventually it will select a move that results in the most "favorable" outcomes and the least "unfavorable" ones based on how the other player moves. This isn't something you can internalize as the computer
    • by dissy (172727) on Tuesday January 15, 2013 @09:24AM (#42590787)

      What if they are not cheating? Some possibilities:

      But they pretty much know he was by the evidence, it's only _how_ that is unknown.

      He was playing much much higher than his ranking should normally permit. They suspected the internet broadcast of the game was being analyzed and moves sent back to him somehow.
      So, they disabled the internet broadcast. From that point forward, he made mistakes over and over, much more in line with his ranking.

      It wasn't just his unexpected high performance, but also the expected drop in performance once the internet broadcast of the game was disabled.

      • by 3seas (184403)

        Typecast.... its a prison...

      • It wasn't just his unexpected high performance, but also the expected drop in performance once the internet broadcast of the game was disabled.

        Kind of an important fact to put into the stub don't you think, timothy?

    • by BasilBrush (643681) on Tuesday January 15, 2013 @10:34AM (#42591497)

      1 -- they learned chess mostly/exclusively by playing against a machine rather than against human opponents. Then their strategy would mostly be informed by or similar to the type of gameplay which they have observed kicking their own ass as they learned to play. Thus they might "play like a computer" because they have internalized the computer's algorithms as they learned to play chess.

      Not possible. The cheater made exactly the same moves as the chess program Houdini 2.0c. Not "play like a computer", but play identical to a specific version of an actual computer program. With the exception of the opening moves, which of course are just a random choice from the usual standard openings.

      • by 3seas (184403)

        The human brain is not capable of working like that.... Aliens do the programming of computers.....

  • First, if a player is so clever that cheating can't be detected in situ, but only after the fact by statistical analysis, then there is nothing that can done. I read the article a few days ago, and this is what I came away with. That they have some vague idea that the wins are statistically unlikely, but if there is process that can be shown to facilite the cheating, then you are going to have matches and ranking determined by statistical algorithm, not competition.

    In any case one end up with a competit

    • by niado (1650369) on Tuesday January 15, 2013 @11:08AM (#42591999)

      they have some vague idea that the wins are statistically unlikely

      I wouldn't call it a 'vague idea'. Ivanov, while being a very good player at a 2227 'master' rating, was playing at an estimated level of over 3000 over the course of an entire tournament (until they cut the internet feed). This would make him the best player in the world by far [fide.com], and also the greatest player the world has ever seen.

      This would be like a college basketball small forward chosen number 10 or so in the NBA draft beating Lebron James 1on1 9 times in a row. To quote the article:

      Either:

      1 Borislav Ivanov is probably the first adult (as opposed to a junior talent) with a confirmed low rating ever to achieve a 2600+ GM norm performance in an event of nine rounds or more or

      2 [He] is the first player ever to successfully cheat at a major tournament over multiple rounds without the cheating mechanism being detected.

  • It's simple (Score:3, Funny)

    by Megane (129182) on Tuesday January 15, 2013 @09:28AM (#42590817) Homepage
    He's being haunted by the ghost of a grandmaster [wikipedia.org] chess player!
  • Solution (Score:3, Funny)

    by Eisenfaust (231128) on Tuesday January 15, 2013 @09:35AM (#42590869) Homepage

    Hold the tournament on a commercial airliner that repeatedly takes off and lands. Certainly if someone on board the plane was using an electronic device during take off or landing something terrible would happen ;)

  • Is that the one with the birds or the little old lady?

  • by jvarsoke (80870) on Tuesday January 15, 2013 @10:45AM (#42591675)

    Over the board (OTB) is one thing, but online (c)heating becomes incredibly hard to detect in situ, for pretty obvious reasons. The online chess community has taken a couple of approaches to detect this. For PlayChess Online (a server that hosts online games), they try to detect if your computer is running another process that is a known Chess Engine while you are playing your game. Easily subverted by having two computers, or even a Virtual Box setup.

    The most successful way to detect cheating is in postmortem review. I worked with the ICC/FICS Slow Time Control league team (one guy usually) who would run move correlation statistics off suspicious games. There were lots of parameters in his analysis to tweak: ignore book (pre-planned) openings, use endgame tables, tolerance threshold, plys deep to look, how many branches to examine, etc. I was part one of the peer reviewers of the system and an occasional game. The basic idea was to run the moves through a few engines and find out how high the move correlation was for both players. In certain points of the game, the move correlation is very high because good candidate moves are obvious. However, over a single 35move game (avg), GM correlation with any of the popular chess engines (even HIARCS, which supposedly plays more like a human) was around 23%. 1800 level players (club level) were even less. Magnus Carlsen wasn't on the scene yet; he apparently learned more from the computer than any human. Perhaps he'd be higher. The typical cheater scored around 98%.

    This of course is not to say that there couldn't be a player who "thought like a computer". But this would put in question the main criticism of game specific AI, and general AI, that they do not actually model how the human brain thinks. Finding a human who thought like a computer would actually be incredibly interesting to the whole field of AI. That being said, the burden at that point is on the cheater to prove because he is well beyond a reasonable doubt.

  • by ub3r n3u7r4l1st (1388939) on Tuesday January 15, 2013 @11:21AM (#42592239)

    Setup a Fool's mate [wikipedia.org] intentionally. A cheater using an auto-play program will fall for it at no time. A human cannot spot a fool's mate that fast. As long as the game is finished (checkmate or not) within 30 seconds since it started, the game will not count as rated.

"Time is money and money can't buy you love and I love your outfit" - T.H.U.N.D.E.R. #1

Working...