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
geanalys
eerd.
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