Artificial Stupidity: algoritmi One Google Engineer pentru Bad Chess Playing

ce se întâmplă atunci când aplicăm tehnologii moderne de ultimă oră la vechiul joc de șah? Și ce se întâmplă atunci când un geek plictisit cu un surplus de putere de calcul își desfășoară propriile experimente ciudate la domiciliu pe joc?

în acest an, un inginer de software din Pennsylvania, care se numește Tom Murphy VII, a decis să creeze niște algoritmi de joc de șah ridicol de răi, folosind totul, de la învățarea automată și rețelele neuronale la o cantitate gratuită de cicluri CPU-și apoi a pus algoritmii răi unul împotriva celuilalt pentru a crea un „turneu de proști.”

„este ideea mea de distracție…” spune Murphy într-un videoclip plin de umor care descrie experimentele.

primele mișcări

Murphy are puterea creierului să-l scoată. El ne spune că în 2007 și-a apărat doctoratul în informatică. la Carnegie Mellon-care a fost în același an, studenții au început să organizeze conferința anuală SIGBOVIK pe April Fool ‘ s Day. Sponsorizat de” Asociația pentru Erezia computațională”, a fost un fel de grup satiric de interes special dedicat unui cercetător fictiv numit” Harry Quizmaster Bovik „și care a inclus un apel pentru lucrări tâmpite pe teme precum” prostia artificială.”

în ultimii 11 ani, Murphy a fost inginer software senior la Google (în birourile sale din Pittsburgh). Dar în acest an a decis să se întoarcă din nou pentru conferința April Fool ‘ s Day — și, din nou, a contribuit la o cercetare plină de umor.

Murphy se laudă cu mândrie că unele dintre prezentările sale anterioare au implicat investigații ridicole care erau „indistinguizabile de cercetarea „reală” (de exemplu, primul nivel al Super Mario Bros.este ușor cu comenzi lexicografice și călătoria în timp are aproximativ 20 de citări în cercetarea academică „reală”).

dar acesta a fost anul în care Murphy și-a îndreptat atenția spre șah.

să înceapă jocurile

în jocul inițial al lui Murphy, jucătorii umani sunt legați la ochi, forțându-i să-și amintească unde sunt piesele. Dar care este echivalentul pentru un computer? Spunându-i unde se află piesele, dar nu ce piese sunt (sau chiar ce culoare)…

desigur, computerul nu ar fi prevăzut nici cu mișcările care duc la o poziție. Nici n-ar ști al cui e rândul. Da, există posibilitatea ca regele computerului să fie sub control — moment în care aproape fiecare mișcare este ilegală, cu excepția unei mișcări care îl conduce pe regele tău în siguranță. Dar pentru a evita acest lucru, Tom a creat un program care generează o listă de posibile mișcări, clasate în ordinea preferințelor — din care va fi aleasă prima mișcare legală.

„îmi place să joc împotriva ei, pentru că nu este foarte bun”, spune Murphy în videoclip. „Dar întrebarea firească este cum nu-foarte-bun este?”Testarea împotriva programelor de joc de șah dovedește că da, pierde cu mare regularitate-ca în,” de fiecare dată.”

apoi și-a propus să construiască alți algoritmi de joc de șah rău, astfel încât să poată compara performanța lor relativă…

cineva a preferat să-și plaseze piesele pe pătratele albe când joacă alb și pe pătratele negre când joacă negru. (Adversarul său? Un algoritm care a preferat plasarea piesele sale pe pătrate oppositely colorate.) În cele din urmă, amândoi au jucat destul de prost. „Au o preferință, dar nu are legătură cu câștigarea.”De fapt, ambele sunt doar puțin mai rele decât algoritmul care își alege mișcările la întâmplare.

au existat, de asemenea, doi algoritmi pe care i — a numit „Huddle” și „Swarm” – în care un jucător automat caută mișcări care își păstrează piesele aproape de propriul rege, în timp ce celălalt caută mișcări care își plasează piesele lângă regele adversarului său. Acest lucru duce uneori la regele lui Huddle fiind forțat să-și urmeze propriii pioni peste bord, în care cel puțin câteva cazuri pionul său a promovat apoi accidental în piese mai puternice și l-a verificat din greșeală pe regele opus.

dar mai des, funcționează invers. „Dacă aveți o preferință pentru a ataca adversarul, AI de gând să accidental mat-l uneori.”În videoclip, Murphy dezvăluie că printre algoritmii de șah răi, acesta este surprinzător de rău. „”Swarm” este, de fapt, mult mai bine decât ” mișcare aleatorie.”

și încă o strategie de succes este un algoritm care prioritizează patru tipuri specifice de mișcare (în această ordine): să șah Mat, să verifice, să captureze o piesă sau să împingă pe teritoriul adversarului său.

dar există și alte idei teribile — cum ar fi un algoritm care încearcă să oglindească piesele adversarului său sau să-și mute toate piesele în cealaltă parte a tabloului. Un algoritm alege pur și simplu oricare mișcare vine mai întâi în ordine alfabetică.

și există un alt algoritm în care fiecare mișcare este aleasă dintr — o listă de mișcări posibile-cu alegerile dictate în mod arbitrar de cifrele lui pi…

supraviețuire în Chessland

dar în cele din urmă algoritmul său cel mai elaborat a început cu o întrebare: care singură piesă de șah este cel mai probabil să „supraviețuiască” — să rămână pe tablă până la sfârșitul jocului și să iasă victorioasă cu toate piesele de șah ale colegilor săi? Investigând cu atenție răspunsul, Murphy a vizitat site-ul free / libre chess LiChess.org (care acum vede mai mult de un milion de jocuri pe zi). De asemenea, oferă jocuri pentru descărcare — așa că Murphy a descărcat toate cele 506.000.416 dintre ele.

el a rezumat rezultatele într-o lucrare numită „supraviețuirea în Chessland”, care explică metodologia sa. Murphy a descărcat fiecare joc complet pe care l — au avut până în noiembrie 2018-deși alte 200 de milioane au devenit aparent disponibile în cele opt luni de atunci. Chiar și lansarea sa din noiembrie a reprezentat 875 GB de jocuri de șah, „astfel încât procesarea acestora a avut grijă de eficiență și paralelism”, spune Murphy în videoclip.

„din fericire, am un computer cu doar un număr obscen de nuclee și RAM cu adevărat excesiv, așa că trebuie să folosiți asta pentru ceva.”

Er, cât de obscen? Într-un e-mail, el descrie sistemul său de acasă „gratuit”, un AMD ThreadRipper cu 32 de nuclee 2990WX. Rularea programelor C++ multi-threaded timp de câteva ore a fost suficientă pentru a trece prin întregul set de date. „Cred că oamenii subestimează ceea ce poți face eficient cu o singură mașină!”

„lucrarea implicată este destul de simplă: Analizez PGN (care descrie jocul), apoi execut mișcările din joc, urmărind soarta fiecărei piese și apoi însumez numărul pentru fiecare soartă…”

„practic am scris tot codul de la zero, pentru că acest lucru este mai distractiv decât să faci codul altor persoane să funcționeze. :)”

și apoi acest lucru a dus la algoritmi mai răi de joc de șah. În primul rând, este cel care mută piesele în acele pătrate unde statistic sunt mai susceptibile de a supraviețui. Sau pur și simplu la pătrate în cazul în care acestea sunt cel mai probabil să fie la sfârșitul unui joc. Și alți algoritmi fac exact opusul — mutarea pieselor în pătrate unde este cel mai puțin probabil să supraviețuiască (sau să ajungă). Doi algoritmi calculează care pătrat are cea mai mare rată de supraviețuire (față de rata de captare) pentru o piesă pe fiecare pătrat, cu un algoritm care caută cel mai mare raport favorizând supraviețuirea — și algoritmul „fatalist” care caută cel mai mic astfel de raport.

„în mod ciudat, are cele mai bune șanse de câștig ale acestor strategii.”

și, în cele din urmă, a decis să le compare pe toate cu motorul de șah Stockfish pe mai multe niveluri (inclusiv un algoritm special în care este forțat să joace mișcarea sa cea mai puțin promițătoare). „Privind rezultatele, în mod surprinzător, aceasta este cea mai proastă strategie generală și reușește să piardă în fața aproape tuturor.”

dar amintiți-vă algoritmul original „legat la ochi” al lui Tom, care nu știa ce piesă ocupa un pătrat (sau chiar culoarea sa)? El a decis să — l mărească cu o rețea neuronală, care a efectuat învățarea automată-folosind miliardele de poziții disponibile în jocurile de la LiChess.org. Acum a fost capabil să prezică corect piesele reale la fiecare poziție cu o precizie de 100%…aproximativ o cincime din timp. Și chiar și atunci când este greșit, este doar ghicit incorect o medie de 3,22 bucăți pentru fiecare poziție.

și acesta devine un punct de sărituri pentru calcule și mai sălbatice. La un moment dat, el deduce că toate jocurile din baza lor de date trec în cele din urmă prin 21.553.382.902 poziții unice. Cu 204GB le puteți stoca pe toate — împreună cu următoarea mișcare — dar există o altă statistică interesantă. Un enorm 76% din pozițiile au avut loc exact o dată. „Deci, acestea ocupă mult spațiu și nu sunt foarte utile pentru a juca, pentru că este foarte puțin probabil să le mai văd vreodată.”Aruncând aceste poziții unice, orice altă poziție posibilă a jocului poate fi stocată cu aproximativ 500 MB de memorie. Acest lucru poate fi ușor convertit într-un algoritm care joacă cea mai populară mișcare pentru orice poziție pe care o întâlnește (în timp ce schimbă într-o mișcare aleatorie dacă se întâmplă să se găsească prins într-o poziție unică).

dar apoi există un truc ușor pentru a-l învinge. „De îndată ce fac o mișcare ciudată, începe să joace la întâmplare. Și apoi este foarte ușor de învins.”

un experiment final implică diverse” diluții ” ale motorului Stockfish — în care mișcarea sa preferată este înlocuită de o mișcare aleasă aleatoriu x la sută din timp.”

„de fapt, putem evalua cât de bun este un jucător acum comparându-l direct cu o diluție specifică de Stockfish…”

după ce toți algoritmii elaborați de șah ai lui Murphy au fost testați cu atenție, el a rezumat rezultatele într-o masă masivă și și-a încheiat triumfător videoclipul anunțând că este în sfârșit gata să urmărească alte interese.

„acum este următorul proiect, care îl învață pe acest câine cum să joace șah.”

• ce se întâmplă când învățarea automată conduce omenirea la răspunsuri pe care nu le înțelegem?
• Faceți cunoștință cu Sophie, robotul care face tăiței.
• după 15 ani, cercetătorii dezvăluie un braț artificial care poate simți.