vad händer när vi tillämpar avancerad modern teknik på det gamla schackspelet? Och vad händer när en uttråkad nörd med ett överskott av datorkraft genomför sina egna konstiga hemexperiment på spelet?
i år en Pennsylvania mjukvaruingenjör som kallar sig Tom Murphy VII bestämde sig för att skapa några skrattretande dåliga schackspelande algoritmer med allt från maskininlärning och neurala nätverk till en kostnadsfri mängd CPU-cykler — och sedan pitted de dåliga algoritmerna mot varandra för att skapa en ”turnering av dårar.”
” det är det jag tycker är kul… ” säger Murphy i en humoristisk video som beskriver experimenten.
första drag
Murphy har hjärnkraften att dra av den. Han berättar att han 2007 försvarade sin datavetenskap Ph. D. på Carnegie Mellon — som var samma år började eleverna hålla den årliga sigbovik-konferensen på April Fool ’ s Day. Sponsras av” Association for Computational kätteri, ”det var ett slags satirisk särskild intressegrupp ägnas åt en fiktiv forskare som heter” Harry Quizmaster Bovik, ”och med en uppmaning till fånig papper om ämnen som” artificiell dumhet.”
under de senaste 11 åren har Murphy varit en senior staff software engineer på Google (i sina Pittsburgh-kontor). Men i år bestämde han sig för att återvända till April Fool ’ s Day — konferensen-och igen bidrog han med en egen humoristisk forskning.
Murphy skryter stolt över att några av hans tidigare presentationer där involverade löjliga undersökningar som var ”oskiljbara från” riktig ”forskning (till exempel den första nivån av Super Mario Bros.är lätt med lexikografiska beställningar och tidsresor har cirka 20 citat i ”riktig” akademisk forskning).
men detta var året som Murphy riktade sin uppmärksamhet mot Schack.
låt spelen börja
i Murphys första spel är mänskliga spelare ögonbindel och tvingar dem att komma ihåg var bitarna är. Men vad är motsvarande för en dator? Berätta var bitar finns men inte vilka bitar de är (eller till och med vilken färg)…
naturligtvis skulle datorn inte vara försedd med rörelserna som leder upp till en position heller. Det skulle inte ens veta vems tur det var. Ja, det finns en möjlighet att datorns kung är i kontroll — vid vilken tidpunkt nästan alla drag är olagliga utom ett drag som leder din kung till säkerhet. Men för att komma runt det skapade Tom ETT program som genererar en lista över möjliga drag, rankade i preferensordning — från vilken det första lagliga draget kommer att väljas.
”jag gillar att spela mot det, för det är inte så bra”, säger Murphy i videon. ”Men den naturliga frågan är hur inte-mycket-bra är det?”Att testa det mot schackspelprogram visar att ja, det förlorar med stor regelbundenhet-som i ”varje gång.”
sedan satte han sig för att bygga andra dåliga schackspelande algoritmer, så att han kunde jämföra deras relativa prestanda…
man hade en preferens för att placera sina bitar på de vita rutorna när det spelar vitt och på svarta rutor när det spelar svart. (Dess motståndare? En algoritm som föredrog att placera sina bitar på motsatt färgade rutor.) Till slut spelade de båda ganska dåligt. ”De har en preferens, men det har inte riktigt att göra med att vinna.”I själva verket är de båda bara lite sämre än algoritmen som väljer sina rörelser slumpmässigt.
om du hittar min invecklade 42min video om 30 konstiga schackalgoritmer som tävlar i en turnering av dårar för att bedöma mitt program som spelar schack utan att veta vilka bitar som finns på brädet för att vara tråkiga, beror det på att du inte förstår konst:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) juli 15, 2019
det fanns också två algoritmer som han kallade” Huddle ”och” Swarm ” — där en automatiserad spelare söker efter drag som håller sina bitar nära sin egen kung, medan den andra söker efter drag som placerar sina bitar nära motståndarens kung. Detta leder ibland till att Huddles kung tvingas följa sina egna bönder över hela linjen, där åtminstone några få fall dess bonde sedan av misstag befordrades till mer kraftfulla bitar och oavsiktligt kontrollerade den motsatta kungen.
men oftare fungerar det åt andra hållet. ”Om du föredrar att attackera motståndaren, kommer du av misstag att kontrollera det ibland.”I videon avslöjar Murphy att bland de dåliga schackalgoritmerna är den här förvånansvärt inte lika dålig. ”’Swarm’ är faktiskt mycket bättre än ’ Random Move.'”
och en mer framgångsrik strategi är en algoritm som prioriterar fyra specifika typer av drag (i denna ordning): att schackmatt, kontrollera, fånga en bit eller skjuta in i motståndarens territorium.
men det finns andra hemska ideer-som en algoritm som syftar till att spegla motståndarens bitar eller att flytta alla sina bitar till andra sidan av brädet. En algoritm väljer helt enkelt vilket drag som kommer först i alfabetisk ordning.
och det finns en annan algoritm där varje drag väljs från en lista över möjliga drag – med valen dikterade godtyckligt av siffrorna i pi…
överlevnad i Chessland
men i slutändan började hans mest detaljerade algoritm med en fråga: vilken enda schackpjäs är mest sannolikt att ”överleva” – att stanna kvar i styrelsen genom slutet av spelet, och framväxande segrande med alla sina kolleger schackpjäser? Plikttroget undersöker svaret, Murphy besökte free / libre chess site LiChess.org (som nu ser mer än en miljon spel om dagen). Det erbjuder också spel för nedladdning — så Murphy laddade ner alla 506 000 416 av dem.
han sammanfattade resultaten i ett papper som heter ”Survival in Chessland”, vilket förklarar hans metodik. Murphy laddade ner varje komplett spel de hade genom November 2018 – men ytterligare 200 miljoner har tydligen blivit tillgängliga under de åtta månaderna sedan. Även hans November haul representerade en jättestor 875 GB schackspel,” så bearbetning av dessa tog lite omsorg för effektivitet och parallellitet”, säger Murphy i videon.
”lyckligtvis har jag en dator med bara ett obscent antal kärnor och verkligen överdriven RAM, så du måste använda det för något.”
är, hur obscent? I ett e-postmeddelande beskriver han sitt ”kostnadsfria” hemsystem, en 32-kärnig AMD ThreadRipper 2990wx. Att köra de multi-threaded C++ – programmen i några timmar var tillräckligt för att krossa genom hela datasetet. ”Jag tror att folk underskattar vad du kan göra effektivt med en enda maskin!”
”arbetet är ganska enkelt: Jag analyserar PGN( som beskriver spelet), utför sedan rörelserna i spelet, håller reda på ödet för varje bit och summerar sedan räkningarna för varje öde…”
”jag skrev i princip all kod från början, för det här är roligare än att få andras kod att fungera. :)”
Murphys ”survivability” – analys skapade några riktigt vackra visualiseringar av data, vilket visar sannolikheten för överlevnad för varje schackstycke på var och en av de 64 rutorna (med färger som indikerar deras sannolikhet att vara på den rutan i slutet av spelet.)
och då ledde detta till mer dåliga schackspelande algoritmer. För det första finns det en som bara flyttar bitar till de rutor där de är statistiskt mer benägna att överleva. Eller helt enkelt till rutorna där de är mest sannolikt att vara i slutet av ett spel. Och andra algoritmer gör exakt motsatsen — flytta bitar till rutor där de är minst benägna att överleva (eller hamna). Två algoritmer beräknar vilken kvadrat som har den högsta överlevnadsgraden (kontra fångstfrekvens) för en bit på varje kvadrat, med en algoritm som söker det högsta förhållandet som gynnar överlevnad — och den ”fatalistiska” algoritmen som söker det lägsta sådana förhållandet.
”konstigt nog har den de bästa vinstchanserna för dessa strategier.”
och slutligen bestämde han sig för att jämföra dem alla med Stockfish-schackmotorn på flera nivåer (inklusive en speciell algoritm där den tvingas spela sitt minst lovande drag). ”Om man tittar på resultaten är det inte överraskande att det här är den övergripande värsta strategin, och det lyckas förlora för nästan alla.”
men kom ihåg Toms ursprungliga” blindfoldiga ” algoritm, som inte visste vilken bit som ockuperade en kvadrat (eller till och med dess färg)? Han bestämde sig för att förstärka det med ett neuralt nätverk, som utförde maskininlärning — med hjälp av de miljarder positioner som finns tillgängliga i spelen från LiChess.org. Det kunde nu korrekt förutsäga de faktiska bitarna vid varje position med 100% noggrannhet…ungefär en femtedel av tiden. Och även när det är fel, är det bara felaktigt gissat i genomsnitt 3,22 stycken för varje position.
och detta blir en hoppningspunkt för ännu mer vilda beräkningar. Vid något tillfälle drar han slutsatsen att alla spel i deras databas så småningom passerar genom 21,553,382,902 unika positioner. Med 204GB kan du lagra dem alla-tillsammans med nästa drag-men det finns en annan intressant statistik. En hel del 76% av positionerna inträffade exakt en gång. ”Så dessa tar upp mycket utrymme, och de är inte särskilt användbara för att spela, för jag är mycket osannolikt att någonsin se dem igen.”Kasta bort dessa engångspositioner, alla andra möjliga spelpositioner kan lagras med cirka 500 MB minne. Detta kan enkelt omvandlas till en algoritm som spelar det mest populära draget för vilken position den möter (medan du byter i ett slumpmässigt drag om det råkar befinna sig i en unik position).
men då finns det ett enkelt knep för att slå det. ”Så fort jag gör lite av ett konstigt drag börjar det bara spela slumpmässigt. Och då är det väldigt lätt att slå.”
ett sista experiment involverar olika” utspädningar ” av Stockfish — motorn-där dess föredragna drag ersätts av ett slumpmässigt valt drag x procent av tiden.”
” vi kan faktiskt bedöma hur bra en spelare är nu genom att jämföra den direkt med en specifik utspädning av Stockfish…”
efter att alla Murphys utarbetade schackspelsalgoritmer hade testats plikttroget sammanfattade han resultaten i ett massivt bord och avslutade triumferande sin video genom att meddela att han äntligen var redo att driva andra intressen.
”nu är det vidare till nästa projekt, som lär denna hund hur man spelar schack.”
- vad händer när maskininlärning leder mänskligheten till svar som vi inte förstår?
- Möt Sophie, nudeltillverkningsroboten.
- efter 15 år avslöjar forskare en konstgjord arm som kan känna.