How to Catch a Chess Cheater | Hacker News Reader

How to Catch a Chess Cheater

uschess.org

69 pointsdfan20 comments

This is one of those asymptotically unsolvable problems (like captcha) -- he just created a new game. It's called beat the cheating detector. If you have access to the detector, it becomes trivial even: no matter how advanced the detector, using a chess engine to generate a set of moves and picking the best ones which go undetected works.

It's one thing that bother me about many online games (like counter strike). Unless they make a completely locked up computer, fighting cheats (server-side) is a losing battle. The bright side is that when they become really indistinguishable from good players, we can rest easy that the play isn't being degraded at all (expect for the cheaters themselves) :)

> ... It's called beat the cheating detector. If you have access to the detector, it becomes trivial even: no matter how advanced the detector, using a chess engine to generate a set of moves and picking the best ones which go undetected works.

Except that you have to beat all future detectors as well, which is a lot harder to get access to. E.g. this is how athletes sometimes get caught out doping; they use methods which are undetectable today, but fail in a year or two.

I don't really want to press this comparison too far though, not only are the prevalent levels completely different, but doping is also a lot less clear cut than cheating in chess / counter strike. It's pretty obvious when you're cheating in the one, whereas you could argue that using as-yet not banned substances is fair game. Mind you, we have had players type in recoil-resetting scripts at competitions, and argue that it's just a configuration, so perhaps it's not as clear cut as I make it sound.

That's why you don't "win" the game, but it's an endless competition between cheats and cheat detectors.

You will find neither the ultimate cheat, nor the ultimate cheat detector.

As long as the detectors don't directly detect cheating, but instead improvement at a rate that is too high (like in the article), then if you limit your rate of improvement to a rate and distribution similar to human improvement, it is unlikely that any future program will be able to detect this.

Detecting performance enhancement solely by looking at performance is a losing battle for the detecting side.

Sure, but forcing cheaters to rate-limit their improvements to within reasonable limits would already be a huge win for the detecting side, so I'm not sure I'd call it a losing battle. It'd severely limit the utility of cheating, while at the same time forcing a long history of slow improvement which can be scrutinised.

Taken by itself, I'd tend to agree with you. In practice though, I think this can easily swing the balance in favour of the detecting side. Another angle to analyse chess games would be to see the degree to which a player's moves correlate with known chess engines. Over a long term (say, a few dozen tournaments worth of games), this type of evidence would be particularly damning; the types of chess engines which play relatively human-like, yet still are top-tier simply don't exist. Given the difficulty in creating them, and the relative rewards, I wonder if it will ever be practical to cheat.

As for computer games, I believe there are two ways to effectively combat any "cheating":

1. Restrict what clients see and do, server-side. Many cheats rely on the fact, client game software internally has much more information that it presents to the player (wallhacks, radars/ESPs, etc), and server trusts client-originating data more than it should (speedhacks, norecoils, spawners, etc).

I know, those're due to attempts to reduce network-induced lags and lowering server loads, but having a more powerful server-side (and have an occasional desync if network lags badly) doesn't sound like an unacceptable trade-off to not have players upset by cheaters.

2. Embrace cheats as features and raise everyone abilities to best cheater's ones. There's no need to, say, have an aimbot if you have an "official" in-game ability to have autoaim.

Maybe then we'll finally have scriptable/hackable games, where one could "legally" automate routine tasks and be on a "good" side. Oh, and that MMO grinding/farming phenomena would finally die for good.

One can still cheat even in an environment where data is restricted. The 'cheating' part comes from being able to use the CPU to help the player make better or faster decisions. It doesn't have to be perfect - only enough to help the player gain an edge.

I haven't tried it in probably 15 years (and, I'm sure technique has improved exponentially, since then) but as long as you can access and reverse-engineer the data protocol (which you almost always can), you can add code logic to gain an edge.

That's what second approach is about. If cheaters can use technology to improve their gameplay through an automation - why not enhance everyone's gameplay by making such automation an official built-in game feature?

Look at all the hype 0x10c got on here because the ship had a programmable computer. Give the players some emulated low-spec hardware they can use and an API they can use it with.

Even if it doesn't appeal to everyone, it might keep the worst of the botters away from the games that don't want them.

The undetected move is the one within your track record, so cheating doesn't help much, unless you're cheating every move in every tournament. Would performance enhancing drugs be a better fit to this scenario?

After that teaser intro, was hoping the article would've shed a statistical beam on the 2006 cheating allegations against Kramnik.

> Because the proper construction of statistical evidence against alleged cheaters requires such technical expertise, Regan believes that it’s necessary to establish a centralized authority responsible for the administration of anti-cheating protocol.

> Regan also believes that a centralized authority can best fix public confusion about what constitutes scientific versus unscientific procedure. It’s too easy for people with a poor methodology to spread rumors online.

Ok, this seems reasonable.

> Eventually he would like to oversee the conversion of his 35,000 lines of C++ code into a Windows-driven program or portable app. “I see other people using my methods but not necessarily using my program,” he says.

35,000 lines! After skimming the article, I'd hope it could be done much more compactly in a high-level language, say, Julia, Clojure, or Python.

Maybe it was a typo. I also noticed that the article says "...the number of possible unique chess positions [is] roughly 1043," which is a typo. 1043 should be 10^43.

Not to mention their error in claiming that NP problems were unsolvable.

It's not clear to me whether that includes the evaluation engine or whether he's communicating with an external process. If it's the latter then I agree that it seems like a lot.

.. or C++. He's obviously a very bright guy but not necessarily a coder; there might be a lot of cut and paste in there, code for things that already exist in std, etc etc.

To paraphrase the article, Ken Regan thinks that someone's chess skill improving too fast is conclusive proof that they are cheating.

I'm not sure this is really a true analogy to the examples of catching users of performance enhancing drugs; it would be more like saying 'your time on the track has improved by too much for us to believe, so you must have cheated, and therefore you are disqualified'.

Perhaps it would be better to use his software to target people for higher scrutiny, rather than as categorical proof of cheating. Cheaters, however, could just make sure that they always cheat, and ratchet up the search depth at a rate below the maximum permissible improvement rate.

Just curious: why don't they play in shielded rooms instead? I'm quite sure they are not cheap, but they would be far more reliable.

This method will work only until cheaters up their game (pun intended).

Yeah, the article doesn't mention it but it is likely that you could run Stockfish on a smartphone or so to get good moves without any form of connectivity. (The main problem, I suppose, would be that you would have to feed it the other player's moves somehow, whereas with connected devices someone else can do it for you.)

The clearest give away was insisting on wearing Google Glass ^_^

Reply on news.ycombinator.com