Slashdot Mirror
How Do You Detect Cheating In Chess? Watch the Computer
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."
Done.
Where the hell did you get that from? Your quest for the first post clearly outweighed your desire to read anything written and think.
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
I almost forgot the most important ingredient: Saltpeter ;-)
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
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.
Not necessarily: The best human chess players can beat the not-best computer chess programs.
I am officially gone from
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 ) as the front-end (visual GUI) with multiple possible engines driving it underneath (such as Gnu chess). 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.
If you win against a computer you are cheating
I thought it was more if you win playing the same moves that a computer would make you are cheating.
This presupposes that computers play chess differently to humans. My understanding with chess is that there are certain 'stock' moves, openings and such like, that players memorize and use to their advantage. What if someone has set up positions and studied a computer response to those positions or play, would repeating the learned computer moves be the equivalent of cheating? What impact does an eidetic memory have on this where a person is able recall those positions and moves exactly?
The idea that there was some undetected cheating mechanism at play in the case in the article seems to go against the principle of Occam's Razor. The simplest solution to the issue is that either Ivanov just had a great tournament, or that his opponents played into situations for which he'd prepared with the aid of a computer, or a combination of the two. Such appears to be the level of mistrust in chess though that this simple solution is dismissed in search of something more fantastical.
You may think me a tired, old, cynic. I'd have to disagree about the tired bit.
So what is your excuse then?
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
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.
I thought it was more if you win playing the same moves that a computer would make you are cheating.
In the old days, beyond student level, you had to play against tough human opponents to grind out experience, slowly learn to play like your human opponents, and with any luck you'd advance beyond your human trainers.
In the new day, because the computers are the strongest players and always available etc, you'll grind your experience out against a computer, slowly learn to play like your computer opponents, and with any luck you'll advance beyond the programmers of your computer trainers.
It seems inevitable that in a couple generations human chess will look "computer" to a current player.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
Too limited. Needs to block light.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
There was no point. It was all in your head. The "point" was never stated or implied.
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
It is mathematically proven to be unsolveable within finite time, as the problem is in class NP.
No. No it is not. I am not sure where you got this, but chess is easily solvable in finite time. It is a simple tree search but incredibly massive. My desktop, given enough time and a massive increase in memory, could solve chess. Granted the memory would take up a planet the size of Saturn and the time would run into issues with the heat death of the universe, but this is much different than being "unsolvable within finite time".
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
He's being haunted by the ghost of a grandmaster chess player!
#naabhaprzrag, #sverubfr-000, #agi-fcbafberq, negvpyr[pynff*=' negvpyr-ary-'] { qvfcynl: abar !vzcbegnag; }
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 ;)
Grrrrr... don't bother me, I'm thinking.
If you win against a computer you are cheating
I thought it was more if you win playing the same moves that a computer would make you are cheating.
This presupposes that computers play chess differently to humans. My understanding with chess is that there are certain 'stock' moves, openings and such like, that players memorize and use to their advantage. What if someone has set up positions and studied a computer response to those positions or play, would repeating the learned computer moves be the equivalent of cheating? What impact does an eidetic memory have on this where a person is able recall those positions and moves exactly?
I can comment a bit at this. I used to play in chess tournaments in my state some years ago. I was at a very low level in most of them. To put it in simple terms, I was about as far away in talent from the best players in my state (not my country or the world, but just my state) as I could be. I gave up playing chess because bluntly put, computers ruined it. You are right that players memorize openings. The list of known openings and known variations of those openings is staggering. Honestly, it's more than most people can memorize. Back in the 1990s when I played, it was unusual for a known opening to go beyond maybe 7 or so moves before you "got out of book" as they put it and responses started to deviate from known ones. Keep in mind that while you could always deviate very early from known responses, the odds of such being successful were quite low as if the move was really any good, it would already be known. Now add to this the knowledge that since white moves first, he controls the game. So if I as a player think "I'm really hoping white opens with e4 as I've been dying to try out the black side of this variation of the Ruy Lopez", white may open with d4, destroying my chance to defend an e4 opening. Even if white opens with e4 as I hope, on his 2nd move he may prevent the Ruy Lopez variation that I wanted to play. So you can see that what you have to learn is quite enormous because when you play black,you have to be prepared for all kinds of openings that you may not ever play when you have the white pieces.
Computer analysis took to openings to deeper levels of known good responses. So an opening that used to be maybe 7 moves long before you got out of book was now 13-14 moves long. At some point it just becomes impossible to keep up. To be honest with you, I put a lot of time into trying to improve and I really didn't make much progress. It was already tough enough for me to keep up before computers got involved and I just gave up as I felt like I was getting left further and further behind. To be honest with you, a lot of the tournaments weren't much fun. A lot of the guys who showed up to them were really weird. It made me question whether I really wanted to spend a lot of time getting better at something that attracted defective people to it. It's not unheard of for guys to be exceptionally good at chess and be homeless because they can't keep a job. Fischer himself was a genius player but if there was ever a crazier World Champion than him, I don't know who that would be.
The NYT article 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.
this space intentionally left blank
Please stop referring to yourself in plural. Only the Queen and we, Anonymous Coward, are allowed to do that.
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.
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.
"His name was James Damore."
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 watching should have exactly zero effect on your game performance. In his case it had a major effect on his game performance.
The question isn't IF he was cheating, but how.
Not off-topic. Dead on.
Lance Armstrong was initially judged by the USADA to have used PED based not on testing results, but on the testimony of former teammates, some of whom failed their own tests, and may have had an ax to grind. First, because they feel they may have been singled out because of their assocation with Armstrong,second because they may have been pressured by Armstrong or the relationship to use PED, third because they may actually have witnessed Armstrong either taking PEDs or encouraging it, and fourth ALL of the above. The end result is that no one in cycling at the international level will be able to withstand the mere accusations. Non-analytical positives will become the norm. Every champion will be suspect, unless 100% testing is done, and then, as in Armstrong's case, new tests will be conducted on previosuly collected samples, in effect finding athletes guilty in arrears for using PEDs not yet known. Eventually coffee and Gatorade will be banned. And this will stain cycling to the point that fans like myself will turn away.
Chess will go this route. No Master of any rank will be allowed to exceed their 'reasonable' ability. Analysis will be conducted, perhaps electronic surviellance will be used to both check for transmissions and as forensics to be subjected to detailed analysis, suspects will be accused, strip-searched, imaged, run through the metal detectors, scrutinized, and judged guilty based on non-analytical positives. Chess will devolve into the meanest of states, blood sport not for the winners, but for the losers. I expect past upsets to be scrutinized for problems and winners discredited, even posthumously.
A pox on all of it. I'm watching the America's Cup. Less cheating, more suspense, and people could drown.
deleting the extra space after periods so i can stay relevant, yeah.
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 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.
Actually, 6 piece endgames have been solved already. It's sad but true :(
Not any more.
Garry Kasparov lost a match to a program several years ago - back when he was the world champion. Nowadays it is taken as a given that a top program on adequate hardware will overwhelm any human player. The human may win the odd game but most of the time he will be steamrollered.
Mielipiteet omiani - Opinions personal, facts suspect.
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.
There were forced lines in (for example) the Sicilian which went to over 20 moves back in the 70's. If you could not follow them (I certainly could not), the idea was to avoid those lines. There was far more thud and blunder at the level I played at which was just fine - I never took chess that seriously and never even dreamed of playing it professionally.
The Pirc used to be a good "alternative" opening but towards the end of my time as a player I found more and more opponents who could handle it better with white than I as black. Time to say goodbye!
Mielipiteet omiani - Opinions personal, facts suspect.
correct me if I'm wrong but the states of the game would be finite even if turns can go on forever.
"Science can amuse and fascinate us all, but it is engineering that changes the world. " - Asimov.
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, 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.
Going to the FA,
Either
or
The level of mistrust in chess is not that high but this case was exceptional.
There was one thing in the article which was pretty much garbage - Although Magnus Carlsen recently broke Garry Kasparovâ(TM)s all-time rating record to reach 2861, my program for "Intrinsic Ratings" clocked Ivanov's performance in the range 3089-3258 depending on which games and moves are counted according to supplementary information in the case . . ..
Magnus Carlsen's rating is based on his results over the last 12 months. He has played tournaments to a standard of over 3000, just not over a whole year. If you play a tournament containing strong players, win most of your games and draw the rest, you will have a stratospheric rating from that tournament. Ivanov actually lost a game or two and the author is clearly cherry-picking, only counting games where he won and ignoring those where he did not.
ELO ratings are based on wins, draws and defeats, along with the opponent's rating. The quality of the moves made is totally irrelevant.
Mielipiteet omiani - Opinions personal, facts suspect.
Also, these moves, which can be equated to "experience", is often fed to the computer by a human.
Modern techniques often uses a mix of random chance, adaption, human fed experience, statistical experience etc.
Hence it'll play "humanly", it'll play "ruley", it'll play "alien"... Maybe that can be concidered "computery". But there is overlaps with humans in the "humanly" department, and if humans study statistically proven moves, then there's more... Etc.
It's not "moves" that can be memorized that would distinguish a computer from a human player. It is when the player makes entire series of moves that make no sense until you can see 14 moves ahead.
Setup a Fool's mate 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.
New Economic Perspectives
You told him to go die in a fire. You are the last person who should be telling someone the appropriate way to behave.
Support a great indie game: http://www.abaddon360.com
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".
Do what thou wilt shall be the whole of the Law
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.
Do what thou wilt shall be the whole of the Law
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 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.
I thought it was more if you win playing the same moves that a computer would make you are cheating.
In the old days, beyond student level, you had to play against tough human opponents to grind out experience, slowly learn to play like your human opponents, and with any luck you'd advance beyond your human trainers.
In the new day, because the computers are the strongest players and always available etc, you'll grind your experience out against a computer, slowly learn to play like your computer opponents, and with any luck you'll advance beyond the programmers of your computer trainers.
It seems inevitable that in a couple generations human chess will look "computer" to a current player.
In the "old days", when I used to play in USCF tournaments (1980s), most all programs played from an opening book, and once taken out of the book moves, utilized a brute force tree search, rating each position with a score as it went. down the tree. The longer they were given to "think", the more moves they could "look ahead". This caused programs to be very good at tactical play, as they wouldn't miss any obvious errors that were within the next few moves. It did leave them susceptible to being overpowered strategically. Learning to post your pieces in good strategic locations is something that isn't a simple heuristic to program. A great book on how grandmasters see things was written by Sammy Reshevsky (http://en.wikipedia.org/wiki/Samuel_Reshevsky), and titled "Think Like a Grandmaster".
Just another day in Paradise
Computer dominance of chess will surely end when tournament organizers realize how rampant doping is, and kick those silicon fuckers out.
What does it even mean? NP is the class of problems that can be decided using a non-deterministic Turing machine in polynomial time.
"Polynomial time" refers to the class of algorithms that run in O(n^c) where c is a constant.
The "n" in O(n^c) refers to the size of the input. Big-O notation is only meaningful when talking about asymptotic behaviour (as n approaches infinity).
But chess is a given, specific problem, where n=8 (let's say), and there is no asymptotic behaviour anywhere. N is always the same - it's a specific problem, with a specific input size. So talking about NP in relation to chess is simply meaningless. It's only relevant to chess on an NxN board, but who plays THAT? (and more importantly, how many computer programs play NxN chess? What are the rules? How many bishops are there on the NxN board?)
I also played (back in the 80s...never got beyond a 1500 rating myself). Your comment that most openings didn't go beyond 7 or so moves is incorrect. Look up "The Encyclopedia of Chess Openings", and you'll see what I mean. It was a five volume set of books back in my time. As you pointed out, you had to learn to play a whole set of openings. As black, learning the Pirc (e4 opening), Grunfield (d4 opening), and English (c4 opening) covered 99% of all the games I ever played. Beyond that, learning strategic positioning, and basic endgames will allow you to win against nearly anyone who doesn't play regularly. There's a lot of pattern recognition necessary to play well, which requires a lot of practice. Also, learning to pick out "candidate moves" (see "Think Like a Grandmaster" by Sammy Reshevsky), and how to analyze them helped me a lot.
Just another day in Paradise
Sorry, that is not the way it works. Humans playing computers rather learn to play "anti computer" chess. You cannot learn to do the dumb calculation of all variants to depth >20 ply by playing a computer, even though the computer will do this. It just does not work that way. The human advantage is about "understanding" positions, and if you do not use this ability you will not get very good.
It might play at "grandmaster level," but it will not play "like a grandmaster." Humans and computers approach chess very differently, which is why this case is so interesting. From the statistical analysis, the guy's either cheating, or he's the not only best player in the world (3000+ level gameplay) but also the first human who thinks like a computer. Well, a human who thinks like a computer so long as a live internet feed of the game is being broadcast, but suddenly plays like a 2200-level human when the feed is cut.
We don't have a state-run media we have a media-run state.
The call on moderators to look at your ID to me appeared to be just a cute way of calling you dick breath while pointing out that your handle by slashid conveniently is DickBreath ;) Well played!
"Keep at least 3-6 full bottles of hard alcohol on hand, a 2 week resignation notice,..." - Poetmatt
Or a computer who looks like a human...
He's not. If you read the article, he's a regular 2200 level master, who ordinarily plays like a human, but suddenly started playing like a 3000+ level computer.
We don't have a state-run media we have a media-run state.
The first series (1996) was a PR scam. It is incorrect to say he was playing 'Deep Blue'. It is far, far more correct to say he was playing a team, comprising many of the top players, who used Deep Blue to test their moves before implementing them. The programming on the machine changed daily. In the second series, the program was - according to IBM - only changed between games ... although there was a serious question of a mid-game change (Game 1) that led to the computer's loss.
... not so much. Deep Blue's 'innovation', such as it was, was simply to numerically rate a sequence of moves, discarding the lowest scoring, and then continuing its computation from that point. (...and it was a supercomputer) Contrasting with the previous 'Brute force, try all possibilities, select the best after _n_ moves.' As chess is, practically, a finite game, once computers reach the level of _n_ that is about the end point of all games, they aren't going to lose anymore. A lot of the modern chess programs that are free/cheap follow the brute force model, not the more analytical method pioneered by Deep Blue. The top machines do have better coding that Deep Blue ... more importantly, the number of plies has improved, due to better weighting (far more situational / far less point oriented).
That said, yeah, a lot of modern machines leave their predecessors in the dust, computationally. Chess algorithms
It's actually looking for Sarah Connor.....after this game. Just one more!
Defining Statistics and Social Research
He won the last round with no broadcast.
Some sources (commenters on chess sites) say the feed was back on for the last round. http://www.chess.com/news/suspected-cheater-strip-searched-4830?page=2