maandag 20 april 2015

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

6 opmerkingen:

  1. Is er een waardemeter bij "opeenvolgende perfecte zetten" afhankelijk van de moeilijkheid van de stelling en de kwaliteit van de tegenzetten?

    BeantwoordenVerwijderen
  2. Goede opmerking, zover is men nog niet (dat blijkt toch niet uit de paper). Het probleem natuurlijk is: hoe definieer je "de moeilijkheid van de stelling". Is een (taktisch) "rijke" stelling moeilijk? Of net een positionele stelling, waar een ogenschijnlijk onschuldige voortzetting toch langetermijn nadelen oplevert? Ik vermoed dat Tal in zo'n analyses waarschijnlijk eerder slecht uit de hoek komt, maar we weten hoe sterk die speelde.
    Simpele criteria als aantal mogelijke zetten, of varianten die leiden naar extreme waarden voor wit of zwart lijken me nog te bruut om als criterium te hanteren. Ik weet dat Fritz zo'n klokje heeft, waar de complexiteit van de stelling mee aangeduid wordt, maar heb geen idee hoe die score opgebouwd is (op taktische criteria?).

    BeantwoordenVerwijderen
  3. Uit bovenstaand artikel krijg ik in indruk dat de methode van Kenneth Regan gebaseerd is op het checken van hoe vaak de gespeelde zet overeenstemt met de topkeuze van een engine. Echter dit is een veel te simplistische voorstelling. Kenneth Regan bepaalt per zet het verschil in 100sten van een pion tussen de computerevaluatie van de gespeelde zet en de computerevaluatie van de beste zet volgens de engine. Dit verschil in 100sten wordt dan aan een logaritmische berekening onderworpen om zo een gekalibreerde afwijkwaarde te verkrijgen die verder kan worden gebruikt. Bovendien worden scores van 3 pionnen = 300 hondersten van een pion genegeerd om te vermijden dat een mindere zet in een gewonnen stelling die echter nog steeds een gewonnen stelling oplevert, tevens als fout wordt beschouwd.

    Ik heb de methode David J. Barnes en Julio Hernandez-Castro niet in detail bestudeerd maar mijn eerste indruk is dat de detectie methode van Kenneth Regan niet inferieurder is, integendeel.

    http://www.cse.buffalo.edu/~regan/papers/pdf/Reg12IPRs.pdf beschrijft in een notedop hoe de methode van Kenneth Regan werkt.

    BeantwoordenVerwijderen
  4. Als je af en toe live uitzendingen volgt met commentaar dan besef je snel dat zelfs grootmeesters de moeilijkheid van bepaalde zetten niet kunnen inschatten. Soms wordt een zogenaamde makkelijke zet gemist en een andere keer zijn ze overtuigd dat de computerzet niet zal worden gevonden wat dan net wel gebeurt.
    Als het al soms moeilijk/ onmogelijk is voor mensen om zonder voorafgaande testen te definiëren wat de moeilijkheidsgraad is dan is het onbegonnen om dit in een script te schrijven die door een computer kan worden gebruikt.
    In een interview http://schaken.chess.com/blog/SamCopeland/an-interview-with-im-and-anti-cheating-expert-dr-ken-regan kon ik het volgende halen:
    "Right now my work may be measuring accuracy more than challenge."

    De ontwikkelde detectiemethodes zijn dus erg beperkt bruikbaar. Slechts domme cheaters die langdurig valsspelen en zelf niet een minimaal niveau halen, kunnen met deze detectiemethode worden opgespoord.

    Anand zei zelfs dat 1 keer ja of nee antwoord krijgen over een offer in een partij voldoende kan zijn om 150 punten als tpr hoger te scoren. Op http://www.uschess.org/content/view/12677/763 zei Regan hierover : "An isolated move is almost un­catchable using my regular methods."

    BeantwoordenVerwijderen
  5. De detectie-modellen vandaag zijn gebaseerd op een vergelijking met het oplossen van problemen die gemiddeld verschijnen in een partij gespeeld door een speler van een bepaald niveau. Hiermee wordt de kwaliteit van de tegenzetten grotendeels genegeerd. Regan spreekt zelfs over solitairschaak in zijn paper.

    Uiteraard elke partij, tornooi heeft zijn eigen typische karakteristieken. De kwaliteit van de tegenzetten in een partij zal een belangrijke invloed hebben op de foutenlast. Minder bekend is het "nettlesome" principe die o.a. aan bod kwam in het artikel http://en.chessbase.com/post/carlsen-the-nettlesome-world-champion. Hierover wil ik ook nog eens een artikel schrijven om aan te tonen dat dit aspect zelfs op een bescheiden amateursniveau eveneens een belangrijke impact kan hebben.

    BeantwoordenVerwijderen
  6. "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)."

    Als je mijn artikel "http://schaken-brabo.blogspot.be/2012/05/analyseren-met-de-computer.html" nog herinnert dan is het geen verrassing dat ik daar heel wat ervaring mee heb. Je volgt niet rigoureus een algoritme als dit niet reproduceerbaar is. Echter zoals tevens de auteurs van de paper opmerken, gaat het werken met single-thread gepaard met een serieus tijdsverlies. Tijd staat gelijk aan kwaliteit. Uiteindelijk moet je een afweging maken wat het belangrijkste is: reproduceerbaarheid of kwaliteit van de analyses. Wel net zoals de auteurs kies ik voor kwaliteit dus voor multi-thread.
    Om toch een zekere stabiliteit te verkrijgen zorg ik wel steeds ervoor dat er geen andere programma's op mijn computer tezelfdertijd lopen als er analyses worden gemaakt. Dit verhoogt tevens ook de kwaliteit van de analyses omdat meer resources beschikbaar zijn.
    Het is ook de reden waarom ik vorig jaar mij een nieuwe portable aanschafte naast mijn desktop die zeker nog niet verouderd was. De desktop werd steeds vaker opgeëist door mijn kinderen en hierdoor moest ik te vaak mijn analyses voor lange tijd onderbreken.

    BeantwoordenVerwijderen