Automatische detectie van cheaten

Automatische detectie van cheaten : volwassen ?

Een van de voordelen om te werken bij een (groot) studiebureau, is dat je bijvoorbeeld toegang hebt tot wetenschappelijke papers en ander materiaal, zoals bv verzameld in sciencedirect.com. Een database van heel wat wetenschappelijke kennis en jawel, als ex-schaker tik je dan wel eens chess in. Zo kreeg ik onlangs deze paper in de zoeklijst : ‘On the limits of engine analysis for cheating detection in chess’ door David J. Barnes en Julio Hernandez-Castro, van de School of Computing, University of Kent.

Het is een relatief recente paper (oktober 2014), gepubliceerd in het journal Computers & Security 48 (2015), 58-73. Beide auteurs zijn schakers op clubniveau, maar hun achtergrond is eerder number crunching, die in dit geval aangewend werd op het schaken.

Ik begin maar meteen bij het einde : de paper concludeert dat er op vandaag geen goede methode is die waterdicht kan bewijzen of er gebruik gemaakt is van een computer tijdens het spelen. Daar goede handhelds met sterke programma’s eigenlijk pas sinds een goede vijf jaar mogelijk zijn, vormt dit een interessante dataset voor het probleem. Meer dan 90% van de partijen is gegarandeerd computervrij (van Morphy tot Kramnik). Dat is een goede basis om het algoritme te checken – het is onmogelijk dat er voor bv 1990 partijen gespeeld zijn met computerhulp (misschien enkele correspondentiepartijen, maar het niveaus van de programma’s was toen nog beperkt – zelfs in cr).

De paper gaat uit van het uitgangspunt dat het probleem zich in de eerste plaats stelt op internet sites – wanneer partijen ‘live’ kunnen gecheckt worden, zou het gemakkelijker zijn om cheaters er meteen uit te halen.

Voor over the board (OTB) schaken, als er uiterlijk niets te merken is aan de speler, is het zeer moeilijk om iets te bewijzen, vooral als de speler een niveau vertoont dat niet bijster afwijkt van zijn actuele (historische) niveau. Daarnaast heeft een automatische methode, als die (nog) niet sluitend is, het nadeel dat er ‘false positives’ kunnen opduiken. De paper geeft enkele interessante voorbeelden van ‘perfecte partijen’, gespeeld lang voor de intrede van computers.

Deze paper is niet de eerste publicatie die zich hieraan wijdt. Kenneth Regan heeft hier pionierswerk verricht, waar deze paper op verder bouwde. Regan gebruikte een methode die rekening hield met de elo van de speler voor en na het tornooi, zijn tornooiprestatie en de zetkeuze van de speler, vergeleken met zetkeuzes van gelijkwaardige spelers in gelijkaardige stellingen (een schaker ziet onmiddellijk de gaten in zo’n aanpak: vorm van de dag, ondergekwoteerde jeugdspeler, speelstijl, humeur, omgevingsfactoren en gewoon de occasionele blunder). Deze nadelen worden ook geïdentificeerd door Barnes en Hernandez.

Opmerkelijk is dat de auteurs de actuele strategie van schaakservers ontoereikend noemen op lange termijn. Deze servers houden hun methodes om cheats te ontdekken geheim, maar deze ‘security by obscurity’ faalt uiteindelijk – eenmaal gekraakt is de statische methode voorbijgestreefd. En elke code wordt uiteindelijk gekraakt. Zo is blijkbaar het protocol van de ICC lek als een zeef en is het mogelijk om niet alleen kredietkaartgegevens te stelen, maar zelfs de account over te nemen en via zo’n account te cheaten met programma’s.

In concreto werd de analyse gedaan op een databank van Chessbase, aangevuld met TWIC-databases tot 2013. In totaal 7 miljoen partijen, maar voor de analyse werden slechts 120.000 partijen gebruikt; de grote databank werd wel gebruikt om de openingsbib van 87 miljoen stellingen mee op te bouwen. De analyses werden gedaan met Stockfish 3.0. De partijen werden afgebroken tot stellingen, die in multi-PV werden geanalyseerd. Wanneer de gespeelde partijzet niet tot de top vijf behoorde, werd dit gedetecteerd. Maar daar waar Regan bij zijn controle de partijzetten vergeleek met de beste zet van de computer, gingen de auteurs hier iets verschillend te werk. Hun parameter (coincidence value) keek naar het percentage van zetten van mensen die samenviel met zetten van de computer met dezelfde evaluatie. Een subtiel maar belangrijk verschil. Zo hielden ze rekening met het feit dat sommige zetten hetzelfde effect hebben, en het dus geen verschil maakt voor cheatdetectie welke zet de mens kiest (bv in een eindspel met een koning van a2 naar c1 lopen kan via twee verschillende wegen: a2-b2-c2 of a2-b1-c1). Op A UCI-based Chess Game Analyser kan je de C++ code terugvinden.

Maar we mogen cheaters niet onderschatten – tenminste de slimme cheaters niet. Die gaan in rustige stellingen misschien voor een tweede of derde keuze van de computer, en wanneer de stelling gewonnen is, maakt het ook niet meer uit als het mat in 15 of 19 is. Vandaar dat ook de gemiddelde waarde van de afwijking van de gespeelde zet met de computerzet nodig is. Een hele slimme cheater, die telkens suboptimale zetten speelt, zal tegen een speler van laat ons zeggen <2500 nog altijd kunnen winnen, ook als hij nu en dan een licht voordeel ‘laat schieten’. Uiteindelijk worden veel partijen beslist door blunders, en dan is één goede zet voldoende om een blijvend voordeel te houden.

De openingsbib werd opgebouwd en bevat voor elke zet de ‘datum’ wanneer deze voor het eerst gespeeld werd (wat op zich al een interessant gegeven is). Zo kon er gecheckt worden of een sterke zet al bekend was (en meer waarschijnlijk, dat deze bekend was bij de speler) of een nieuwtje (iets meer kans dat het een computerzet is). Maar de databank werd vooral gebruikt als startpunt, vanaf welke zet de partijen origineel waren en de echte cheatdetectie kon beginnen. Het heeft immers geen zin om te checken of een speler goed zijn theorie geleerd heeft of niet.

De analyse startte met 70.000 partijen tot 1950 en 50.000 partijen vanaf 1950 tot 2005. Deze partijen werden geanalyseerd tot op zoekdiepte 8. De meest verdachte partijen werden dieper geanalyseerd (25.000 op ply 10). Dit proces werd verdergezet tot er nog 250 partijen overbleven die op zoekdiepte 22 werden uitgebeend. Dit lijkt een ‘beperkte’ aanpak, gezien de huidige rekenkracht, maar het onderzoek gaat wel enkele jaren terug en wie eens een databank van 250.000 partijen wil analyseren (automatisch mogelijk in Fritz), zal zien dat zelfs op diepte 8 of 10, het toch een tijdje zal duren.

Naast de meest logische zaken die werden geïdentificeerd, zaten er ook bevestigingen in van menselijk gedrag: zo werden meer fouten gemaakt naarmate de partij langer duurde. Lange partijen die wel constante parameters op dit vlak vertonen, springen hier uit de band en kunnen gemakkelijk gedetecteerd worden. Niettemin tonen dergelijke partijen (van voor het computertijdperk) aan dat in uitzonderlijke gevallen twee mensen een perfecte partij kunnen spelen. Anderzijds zaten er ook perfecte korte partijen tussen, die eerder kunnen toegeschreven worden aan huiswerk. 

Het artikel besluit met een illustratie van ‘false positives’; partijen met bijna-perfect spel, maar van (ver) voor het computertijdperk. En voor wie dacht dat de romantische spelers enkel goed waren voor spectaculaire aanvallen en het uitbuiten van zwak spel van de tegenstander, think again. De eerste partij is nl. Kennicott-Morphy, 1857. De partij is 14,5 zetten ‘theorie’ (= al eerder gespeeld en wschl bekend bij beide spelers) en daarna speelt Morphy tien perfecte nieuwe zetten (perfecte match met de zetten van Stockfish op diepte 18). Morphy komt nog enkele keren terug met een perfecte prestatie (blindpartij met zwart tegen Schulten, New York 1857; de zevende matchpartij tegenMongredien in Parijs 1859 en Morphy-Muarian in New Orleans 1866). Nu zien we ‘eindelijk’ het respect dat zelfs wereldkampioenen hadden voor Morphy bevestigd.

Hadden computers al bestaan in 1889, dan was Max Weiss zeker aan de tand gevoeld over een partij tegen Burille in New York. Weiss speelde na 6,5 zetten maar liefst 26 opeenvolgende perfecte zetten en won de partij.

De auteurs besteedden ook aandacht aan Mamedyarov-Kurnusov, een partij die de schaakwereldpers haalde door slechte verliezer Mamedyarov, maar die in hun methode zelfs geen ‘false positive’ zou zijn, wegens de beperkte lengte en het feit dat Kurnosov slechts zes perfecte zetten speelde. Omgekeerd geredeneerd: had Kurnosov wel gecheat, dan zou dit een perfecte moord geweest zijn. We weten ondertussen wel dat hij zuiver op de graat was – niemand minder dan Geurt Gijssen deed het onderzoek ter plaatse.

De auteurs gaan dan verder met hun onderzoek en controleren of het laten lopen van single thread of multi-thread een invloed heeft op de analyse. Het besluit is duidelijk op dit punt: enkel single thread analyse geeft hetzelfde herhaalbare resultaat, terwijl multi-thread variaties oplevert (te verklaren door de manier waarop het programma de deeltaken over de verschillende processoren verdeeld worden).

Opmerkelijk is dat de auteurs een webservice willen opstarten, zodat het controleren van cheaters relatief snel zou kunnen gebeuren. Dit zou de pakkans nog verhogen, ook bij perfecte camouflage (letterlijk door gebruik van draadloze communicatie, maar ook door een min of meer random keuze door de speler of zijn assistent van suboptimale, maar nog altijd goede zetten).

Tot besluit geef ik hier nog enkele partijen die door de auteurs werden uitgelicht als ‘verdacht’, ware het niet dat ze voor de computer-era gespeeld werden. Het is net alsof je kijkt naar een auto die deelneemt aan de paardenwagenrace van Ben-Hur J.  J. Carames-Fedorovsky, Buenos Aires 1965 en Browne-Timman, Wijk aan Zee 1980, opzoeken en naspelen die handel!

HK5000