211service.com
Deep Learning Machine leert zichzelf schaken in 72 uur, speelt op internationaal masterniveau
Het is bijna 20 jaar geleden dat IBM's Deep Blue-supercomputer de regerend wereldkampioen schaken, Garry Kasparov, voor het eerst versloeg volgens de standaard toernooiregels. Sindsdien zijn schaakcomputers aanzienlijk sterker geworden, waardoor de beste mensen weinig kans hebben, zelfs niet tegen een moderne schaakengine die op een smartphone draait.
Maar hoewel computers sneller zijn geworden, is de manier waarop schaakengines werken niet veranderd. Hun kracht is gebaseerd op brute kracht, het proces van het doorzoeken van alle mogelijke toekomstige bewegingen om de beste volgende te vinden.
Natuurlijk kan geen mens dat evenaren of ergens in de buurt komen. Terwijl Deep Blue zo'n 200 miljoen posities per seconde zocht, zocht Kasparov waarschijnlijk niet meer dan vijf per seconde. En toch speelde hij op in wezen hetzelfde niveau. Het is duidelijk dat mensen een truc in petto hebben die computers nog moeten beheersen.
Deze truc is bij het evalueren van schaakposities en het verfijnen van de meest winstgevende zoekmogelijkheden. Dat vereenvoudigt de rekentaak drastisch, omdat het de boom van alle mogelijke bewegingen terugsnoeit tot slechts een paar takken.
Computers zijn hier nooit goed in geweest, maar vandaag verandert dat dankzij het werk van Matthew Lai aan het Imperial College London. Lai heeft een kunstmatige-intelligentiemachine gemaakt, Giraffe genaamd, die zichzelf heeft geleerd schaken door posities veel meer als mensen te evalueren en op een geheel andere manier dan conventionele schaakengines.
De nieuwe machine speelt direct uit de doos op hetzelfde niveau als de beste conventionele schaakengines, waarvan er vele gedurende vele jaren zijn verfijnd. Op menselijk niveau is het gelijk aan de FIDE International Master-status, waardoor het in de top 2,2 procent van de toernooischakers staat.
De technologie achter Lai's nieuwe machine is een neuraal netwerk. Dit is een manier om informatie te verwerken die is geïnspireerd op het menselijk brein. Het bestaat uit verschillende lagen knooppunten die op een manier met elkaar zijn verbonden die veranderen naarmate het systeem wordt getraind. Dit trainingsproces gebruikt veel voorbeelden om de verbindingen zo te verfijnen dat het netwerk bij een bepaalde invoer een specifieke output produceert, bijvoorbeeld om de aanwezigheid van een gezicht op een foto te herkennen.
In de afgelopen jaren zijn neurale netwerken enorm krachtig geworden dankzij twee ontwikkelingen. De eerste is een beter begrip van hoe deze netwerken kunnen worden afgesteld terwijl ze leren, mede dankzij veel snellere computers. De tweede is de beschikbaarheid van enorme geannoteerde datasets om de netwerken te trainen.
Dat heeft computerwetenschappers in staat gesteld om veel grotere netwerken te trainen die in vele lagen zijn georganiseerd. Deze zogenaamde diepe neurale netwerken zijn enorm krachtig geworden en presteren nu routinematig beter dan mensen in patroonherkenningstaken zoals gezichtsherkenning en handschriftherkenning.
Het is dus geen verrassing dat diepe neurale netwerken patronen in het schaken zouden moeten kunnen herkennen en dat is precies de benadering die Lai heeft gekozen. Zijn netwerk bestaat uit vier lagen die samen elke positie op het bord op drie verschillende manieren onderzoeken.
De eerste kijkt naar de algemene staat van het spel, zoals het aantal en het type stukken aan elke kant, welke kant moet worden verplaatst, rokaderechten enzovoort. De tweede kijkt naar stukgerichte kenmerken, zoals de locatie van elk stuk aan elke kant, terwijl het laatste aspect is om de vierkanten in kaart te brengen die elk stuk aanvalt en verdedigt.
Lai traint zijn netwerk met een zorgvuldig gegenereerde set gegevens uit echte schaakspellen. Deze dataset moet de juiste positieverdeling hebben. Het heeft bijvoorbeeld geen zin om het systeem te trainen op posities met drie dames per kant, omdat die posities in echte games vrijwel nooit voorkomen, zegt hij.
Het moet ook een grote verscheidenheid aan ongelijke posities hebben die verder gaan dan die welke gewoonlijk voorkomen in schaakspellen op het hoogste niveau. Dat komt omdat, hoewel ongelijke posities zelden voorkomen in echte schaakspellen, ze de hele tijd opduiken in de zoekopdrachten die de computer intern uitvoert.
En deze dataset moet enorm zijn. Het enorme aantal verbindingen binnen een neuraal netwerk moet tijdens de training worden verfijnd en dit kan alleen met een enorme dataset. Gebruik een dataset die te klein is en het netwerk kan zich in een toestand nestelen die de grote verscheidenheid aan patronen die in de echte wereld voorkomen niet herkent.
Lai genereerde zijn dataset door willekeurig vijf miljoen posities te kiezen uit een database met computerschaakspellen. Vervolgens creëerde hij meer variatie door een willekeurige legale zet aan elke positie toe te voegen voordat hij deze voor training gebruikte. In totaal genereerde hij op deze manier 175 miljoen posities.
De gebruikelijke manier om deze machines te trainen is om elke positie handmatig te evalueren en deze informatie te gebruiken om de machine te leren de sterke en de zwakke te herkennen.
Maar dit is een enorme opgave voor 175 miljoen posities. Het zou kunnen worden gedaan door een andere schaakengine, maar Lai's doel was ambitieuzer. Hij wilde dat de machine zichzelf leerde.
In plaats daarvan gebruikte hij een bootstrapping-techniek waarbij Giraffe tegen zichzelf speelde met als doel de voorspelling van zijn eigen evaluatie van een toekomstige positie te verbeteren. Dat werkt omdat er vaste referentiepunten zijn die uiteindelijk de waarde van een positie bepalen - of het spel later wordt gewonnen, verloren of gelijkgespeeld.
Zo leert de computer welke posities sterk en welke zwak zijn.
Nadat je Giraffe hebt getraind, is de laatste stap om het te testen en hier zorgen de resultaten voor interessante lectuur. Lai testte zijn machine op een standaarddatabase genaamd de Strategic Test Suite, die bestaat uit 1500 posities die zijn gekozen om het vermogen van een engine om verschillende strategische ideeën te herkennen te testen. Het ene thema test bijvoorbeeld het begrip van besturing van open bestanden, een ander test het begrip van hoe de waarden van bisschop en ridder in verschillende situaties ten opzichte van elkaar veranderen, en weer een ander test het begrip van centrumbesturing, zegt hij.
De resultaten van deze test worden gescoord op 15.000.
Lai gebruikt dit om de machine tijdens de training in verschillende stadia te testen. Terwijl het bootstrapping-proces begint, bereikt Giraffe snel een score van 6.000 en piekt uiteindelijk op 9.700 na slechts 72 uur. Lai zegt dat dat overeenkomt met de beste schaakengines ter wereld.
[Dat] is opmerkelijk omdat hun evaluatiefuncties allemaal zorgvuldig met de hand ontworpen kolossen zijn met honderden parameters die gedurende meerdere jaren zowel handmatig als automatisch zijn afgesteld, en aan veel ervan is gewerkt door menselijke grootmeesters, voegt hij eraan toe.
Lai gaat verder met dezelfde soort machine learning-aanpak om de kans te bepalen dat een bepaalde zet waarschijnlijk de moeite waard is om na te streven. Dat is belangrijk omdat het onnodig zoeken in onrendabele takken van de boom voorkomt en de rekenefficiëntie drastisch verbetert.
Lai zegt dat deze probabilistische benadering 46 procent van de tijd de beste zet voorspelt en 70 procent van de tijd de beste zet in de top drie plaatst. De computer hoeft zich dus niet bezig te houden met de andere zetten.
Dat is interessant werk dat een grote verandering vertegenwoordigt in de manier waarop schaakengines werken. Het is natuurlijk niet perfect. Een nadeel van Giraffe is dat neurale netwerken veel langzamer zijn dan andere soorten gegevensverwerking. Lai zegt dat Giraffe er ongeveer 10 keer langer over doet dan een conventionele schaakengine om hetzelfde aantal posities te doorzoeken.
Maar zelfs met dit nadeel is het concurrerend. Giraffe kan spelen op het niveau van een FIDE International Master op een moderne mainstream pc, zegt Lai. Ter vergelijking: de topmotoren spelen op supergrootmeesterniveau.
Dat is nog steeds indrukwekkend. In tegenstelling tot de meeste schaakengines die tegenwoordig bestaan, ontleent Giraffe zijn speelkracht niet aan het kunnen ver vooruit kijken, maar aan het nauwkeurig kunnen evalueren van lastige posities en het begrijpen van gecompliceerde positionele concepten die intuïtief zijn voor mensen, maar ongrijpbaar zijn voor schaken motoren voor een lange tijd, zegt Lai. Dit is vooral belangrijk in de openings- en eindfase van het spel, waar het uitzonderlijk goed speelt.
En dit is nog maar het begin. Lai zegt dat het eenvoudig moet zijn om dezelfde benadering toe te passen op andere games. Een die opvalt, is het traditionele Chinese spel Go, waar mensen nog steeds een indrukwekkend voordeel hebben ten opzichte van hun siliciumconcurrenten. Misschien kan Lai daar een volgende keer iets van snappen.
Referentie: arxiv.org/abs/1509.01549 : Giraffe: diepe versterking gebruiken Leren schaken