Wat gebeurt er als we geavanceerde moderne technologieën toepassen op het eeuwenoude schaakspel? En wat gebeurt er als een verveelde geek met een overschot aan rekenkracht zijn eigen rare huis experimenten uitvoert op het spel?
dit jaar besloot een software engineer uit Pennsylvania, die zichzelf Tom Murphy VII noemt, om een aantal lachwekkend slechte Schaken-spelende algoritmen te maken met behulp van alles van machine learning en neurale netwerken tot een nodeloze hoeveelheid CPU — cycli-en zette vervolgens de slechte algoritmen tegen elkaar op om een “toernooi van dwazen te creëren.”
” It ’s my idea of fun…” Murphy zegt in een humoristische video die de experimenten beschrijft.
eerste zetten
Murphy heeft de hersenen om het uit te voeren. Hij vertelt ons dat hij in 2007 zijn doctoraat Informatica verdedigde. op Carnegie Mellon-dat was hetzelfde jaar de studenten begonnen met het houden van de jaarlijkse SIGBOVIK conferentie op April Fool ‘ s Day. Gesponsord door de” Association for Computational Heresy, “het was een soort satirische speciale belangengroep gewijd aan een fictieve onderzoeker genaamd” Harry Quizmaster Bovik, “en met inbegrip van een oproep voor goofy papers over onderwerpen als” kunstmatige domheid.”
sinds 11 jaar is Murphy senior staff software engineer bij Google (in zijn kantoor in Pittsburgh). Maar dit jaar besloot hij om terug te keren voor de April Fool ‘ s Day conferentie — en opnieuw, bijgedragen sommige humoristische onderzoek van zijn eigen.Murphy schept er trots op dat sommige van zijn vorige presentaties daar belachelijke onderzoeken betroffen die “niet te onderscheiden waren van ‘echt’ onderzoek (bijvoorbeeld het eerste niveau van Super Mario Bros.is gemakkelijk met lexicografische orderverzamelingen en tijdreizen heeft zo ’n 20 citaties in’ echt ‘ academisch onderzoek).
maar dit was het jaar dat Murphy zijn aandacht richtte op Schaken.
laat de spellen beginnen
in Murphy ‘ s eerste spel worden menselijke spelers geblinddoekt, waardoor ze zich moeten herinneren waar de stukken zijn. Maar wat is het equivalent voor een computer? Vertellen waar stukken zich bevinden, maar niet welke stukken ze zijn (of zelfs welke kleur)…
natuurlijk zou de computer ook niet worden voorzien van de zetten die naar een positie leiden. Het zou niet eens weten wiens beurt het was. Ja, Er is een mogelijkheid dat de koning van de computer in toom is – op dat punt is vrijwel elke beweging illegaal, behalve een beweging die uw koning in veiligheid brengt. Maar om dat te omzeilen, creëerde Tom EEN programma dat een lijst van mogelijke zetten genereert, gerangschikt in volgorde van voorkeur — waaruit de eerste legale zet zal worden gekozen.
“I like playing against it, because it’ s not very good,” zegt Murphy in de video. “Maar de natuurlijke vraag is hoe niet-erg-goed is het?”Testen tegen schaakspel programma’ s bewijst dat ja, het verliest met grote regelmaat — zoals in, “elke keer.”
toen begon hij met het bouwen van andere slechte Schaken-spelende algoritmen, zodat hij hun relatieve prestaties kon vergelijken…
men had een voorkeur voor het plaatsen van de stukken op de witte vierkantjes wanneer het wit speelt, en op zwarte vierkantjes wanneer het zwart speelt. (Zijn tegenstander? Een algoritme dat de voorkeur gaf aan het plaatsen van zijn stukken op tegenovergesteld gekleurde vierkanten. Uiteindelijk speelden ze allebei behoorlijk slecht. “Ze hebben een voorkeur, maar het heeft niet echt te maken met winnen.”In feite zijn ze allebei net een beetje erger dan het algoritme dat zijn bewegingen willekeurig kiest.
als je mijn ingewikkelde 42min video over 30 rare Schaken algoritmen concurreren in een toernooi van dwazen om mijn programma dat schaken speelt te beoordelen zonder te weten welke stukken op het bord saai te zijn, dan is het omdat je niet kunst begrijpen:https://t.co/DkaEBGrwAf
— Ik heb een vraag over: 15, 2019
er waren ook twee algoritmen die hij noemde “Huddle” en “Swarm” – waarin een geautomatiseerde speler zoekt naar moves houden zijn stukken dicht bij zijn eigen koning, terwijl de andere zoekt naar moves het plaatsen van zijn stukken in de buurt van de koning van zijn tegenstander. Dit leidt er soms toe dat Huddle ‘ s koning wordt gedwongen om zijn eigen pionnen over de hele linie te volgen, waarbij ten minste een paar gevallen zijn pion vervolgens per ongeluk gepromoveerd tot meer krachtige stukken en per ongeluk checkmated de tegengestelde koning.
maar vaker werkt het andersom. “Als je de voorkeur hebt om de tegenstander aan te vallen, ga je hem soms per ongeluk schaakmat zetten.”In de video, Murphy onthult dat onder de slechte schaakalgoritmen, deze is verrassend niet zo slecht. “‘Swarm ‘is in feite veel beter dan’ Random Move.””
en nog een succesvolle strategie is een algoritme dat prioriteit geeft aan vier specifieke soorten bewegingen( in deze volgorde): schaakmat zetten, controleren, een stuk vastleggen, of duwen in het territorium van de tegenstander.
maar er zijn andere verschrikkelijke ideeën-zoals een algoritme dat probeert de stukken van zijn tegenstander te spiegelen, of al zijn stukken naar de andere kant van het bord te verplaatsen. Een algoritme kiest gewoon welke zet het eerst komt in alfabetische volgorde.
en er is een ander algoritme waarbij elke zet wordt gekozen uit een lijst van mogelijke zetten-waarbij de keuzes willekeurig worden bepaald door de cijfers van pi…
overleving in Chessland
maar uiteindelijk begon zijn meest uitgebreide algoritme met een vraag: welk schaakstuk is meestal waarschijnlijk “overleven” – om op het bord te blijven tot het einde van het spel, en als overwinnaar uit te komen met al zijn collega-schaakstukken? Plichtsgetrouw onderzoek naar het antwoord, Murphy bracht een bezoek aan de gratis / libre chess site LiChess.org (die nu ziet meer dan een miljoen games per dag). Het biedt ook games om te downloaden — dus Murphy gedownload alle 506.000.416 van hen.
hij vatte de resultaten samen in een artikel genaamd “Survival in Chessland”, waarin zijn methodologie wordt uitgelegd. Murphy downloadde elk compleet spel dat ze hadden tot November van 2018-hoewel nog eens 200 miljoen zijn blijkbaar beschikbaar in de acht maanden sinds. Zelfs zijn November haul vertegenwoordigde maar liefst 875GB van schaakspelen, “dus het verwerken van deze nam wat zorg voor efficiëntie en parallellisme,” Murphy zegt in de video.
“gelukkig heb ik een computer met slechts EEN obsceen aantal cores en echt overmatig RAM, dus je moet dat ergens voor gebruiken.”
Er, hoe obsceen? In een e-mail beschrijft hij zijn “gratuite” thuissysteem, een 32-core AMD ThreadRipper 2990WX. Het uitvoeren van de multi-threaded C++ programma ‘ s voor een paar uur was genoeg om door de hele dataset te crunchen. “Ik denk dat mensen onderschatten wat je efficiënt kunt doen met een enkele machine!”
“het werk is vrij eenvoudig: Ik ontleed de PGN (die het spel beschrijft), voer dan de zetten uit in het spel, waarbij ik het lot van elk stuk bijhoud, en Som dan de tellingen voor elk lot op…”
“ik schreef in principe alle code vanaf nul, omdat dit leuker is dan de code van andere mensen aan het werk te krijgen. :)”
Murphy ‘s” survivability ” analyse creëerde een aantal echt mooie visualisaties van de gegevens, waaruit de kans op overleving voor elk schaakstuk op elk van de 64 vierkanten (met kleuren die hun kans om op dat plein aan het einde van het spel.)
en dit leidde tot meer slechte schaakspel algoritmen. Eerst is er die ene die stukken verplaatst naar die vierkantjes waar ze statistisch gezien meer kans hebben om te overleven. Of gewoon naar de pleinen waar ze het meest waarschijnlijk aan het einde van een spel. En andere algoritmen doen precies het tegenovergestelde — stukken verplaatsen naar vierkanten waar ze het minst waarschijnlijk overleven (of eindigen). Twee algoritmen berekenen welk vierkant de hoogste overlevingskans heeft (versus capture rate)voor een stuk op elk vierkant, waarbij één algoritme de hoogste ratio zoekt die overleving ten goede komt — en het “fatalistische” algoritme de laagste ratio.
“vreemd genoeg heeft het de beste kansen om deze strategieën te winnen.”
en uiteindelijk besloot hij om ze allemaal te vergelijken met de Stockfish chess engine op verschillende niveaus (waaronder een speciaal algoritme waar het gedwongen wordt om zijn minst veelbelovende zet te spelen). “Kijkend naar de resultaten, is dit niet verwonderlijk de algehele slechtste strategie, en het slaagt erin om te verliezen van bijna iedereen.”
maar herinner je toms originele” geblinddoekt ” algoritme, dat niet wist welk stuk een vierkant bezet (of zelfs zijn kleur)? Hij besloot om het te vergroten met een neuraal netwerk, dat machine learning uitgevoerd — met behulp van de miljarden posities beschikbaar in de games van LiChess.organisatie. Het was nu in staat om de werkelijke stukken op elke positie correct te voorspellen met 100% nauwkeurigheid…ongeveer een vijfde van de tijd. En zelfs als het verkeerd is, is het alleen verkeerd geraden een gemiddelde van 3,22 stukken voor elke positie.
en dit wordt een startpunt voor nog meer wilde berekeningen. Op een gegeven moment leidt hij af dat alle spellen in hun database uiteindelijk door 21.553.382.902 unieke posities gaan. Met 204GB kun je ze allemaal opslaan-samen met de volgende zet — maar er is nog een interessante statistiek. Maar liefst 76% van de posities kwam precies één keer voor. “Dus deze nemen veel ruimte in beslag, en ze zijn niet erg nuttig om te spelen, want ik ben zeer onwaarschijnlijk dat ik ze ooit weer te zien.”Door deze eenmalige posities weg te gooien, kan elke andere mogelijke spelpositie worden opgeslagen met ongeveer 500MB geheugen. Dit kan gemakkelijk worden omgezet in een algoritme dat de meest populaire zet speelt voor elke positie die het tegenkomt (terwijl het wisselen in een willekeurige beweging als het toevallig vast te zitten in een unieke positie).
maar dan is er een eenvoudige truc om het te verslaan. “Zodra ik een beetje een rare zet maak, begint het gewoon willekeurig te spelen. En dan is het heel gemakkelijk te verslaan.”
een slotexperiment omvat verschillende “verdunningen” van de Stokvismotor — waarbij de gewenste beweging wordt vervangen door een willekeurig gekozen beweging x procent van de tijd.”
“We can actually assess how good a player is now by comparison it directly to a specific verwatering of Stokfish…”
nadat alle van Murphy ‘ s uitgebreide schaakspel algoritmen plichtsgetrouw waren getest, vatte hij de resultaten samen in een enorme tabel, en triomfantelijk concludeerde hij zijn video door aan te kondigen dat hij eindelijk klaar was om andere interesses na te streven.
” nu is het op naar het volgende project, dat deze hond leert Schaken.”
- Wat gebeurt er als Machine Learning de mensheid naar antwoorden leidt die we niet begrijpen?
- Maak kennis met Sophie, de noodle-making robot.
- na 15 jaar onthullen onderzoekers een kunstarm die kan voelen.