211service.com
Waarom neurale netwerken klaar lijken om de beste Human Go-spelers voor de eerste keer te verslaan
Computers beginnen snel beter te presteren dan mensen op min of meer elk gebied. Zo hebben machine vision-experts onlangs een algoritme onthuld dat beter presteert dan mensen in gezichtsherkenning. Soortgelijke algoritmen beginnen ook mensen te matchen bij objectherkenning. En menselijke schakers hebben lang geleden de strijd om computers te verslaan opgegeven.
Maar er is een gebied waar mensen nog steeds triomferen. Dat is in het spelen van het oude Chinese spel Go. Computers hebben dit spel nooit onder de knie. De beste algoritmen bereiken alleen het vaardigheidsniveau van een zeer sterke amateurspeler die de beste menselijke spelers gemakkelijk overtreffen.
Dat lijkt te veranderen dankzij het werk van Christopher Clark en Amos Storkey aan de Universiteit van Edinburgh in Schotland. Deze jongens hebben dezelfde machine learning-technieken toegepast die de algoritmen voor gezichtsherkenning hebben getransformeerd tot het probleem van het vinden van de volgende zet in een spelletje Go. En de resultaten laten weinig hoop dat mensen dit spel zullen blijven domineren.
Kort gezegd, Go is een spel voor twee spelers dat meestal wordt gespeeld op een 19 x 19 raster. De spelers plaatsen afwisselend zwarte en witte stenen op het rooster in een poging om uiteindelijk meer van het bord te bezetten dan hun tegenstander wanneer het spel eindigt. Spelers kunnen de stenen van hun tegenstander verwijderen door ze met hun eigen stenen te omringen.
Experts denken dat er twee redenen zijn waarom computers Go niet onder de knie hebben. De eerste is het enorme aantal zetten dat in elke fase van het spel mogelijk is. Go-spelers hebben 19 x 19 = 361 mogelijke startzetten en er zijn meestal honderden mogelijke zetten op elk punt in het spel. Daarentegen is het aantal zetten bij schaken meestal ongeveer 50.
Het tweede probleem is dat computers het moeilijk vinden om de sterke en zwakke punten van een bestuursfunctie te beoordelen. Bij schaken geeft het simpelweg optellen van de waarde van elk stuk dat op het bord achterblijft een redelijke indicatie van de sterkte van de positie van een speler. Maar dit werkt niet in Go. Het tellen van het aantal stenen dat elke speler heeft, is een slechte indicator van wie er wint, zeggen Clark en Storkey.
De manier waarop state-of-the-art Go-algoritmen dit probleem aanpakken, is door na elke zet het hele spel uit te spelen en dit op veel verschillende manieren te doen. Als de computer in de meeste van deze partijen wint, wordt die zet als een goede zet beschouwd.
Het is duidelijk dat dit een tijdrovende en rekenintensieve taak is. Toch slaagt het er over het algemeen niet in om menselijke Go-experts te verslaan, die de staat van een Go-bord meestal met weinig meer dan een blik kunnen evalueren.
Veel experts zijn van mening dat het geheim van het Go-playing-meesterschap van de mens patroonherkenning is - het vermogen om sterke en zwakke punten te herkennen op basis van de vorm die de stenen maken in plaats van door verschillende stappen vooruit te kijken.
Dat is de reden waarom de recente ontwikkelingen in algoritmen voor patroonherkenning computers zouden kunnen helpen om het veel beter te doen. Deze vooruitgang heeft enorme databases met afbeeldingen gebruikt om diepe convolutionele neurale netwerken te trainen om objecten en gezichten te herkennen met het soort nauwkeurigheid dat nu overeenkomt met menselijke prestaties. Het is dus redelijk voor te stellen dat dezelfde soort aanpak een groot verschil kan maken voor de geautomatiseerde evaluatie van Go-borden.
En dat is precies wat Clark en Storkey hebben gedaan. De vraag die deze jongens een diep convolutief neuraal netwerk hebben getraind om te beantwoorden, is: is het mogelijk om de volgende zet in het spel te voorspellen, gegeven een momentopname van een spel tussen twee Go-experts?
De manier waarop ze dit aanpakken, is door een enorme database met Go-spellen te gebruiken om een neuraal netwerk te trainen om de volgende zet te vinden. Clark en Storkey gebruikten meer dan 160.000 partijen tussen experts om samen met hun volgende zet een database van 16,5 miljoen posities te genereren. Ze gebruikten bijna 15 miljoen van deze position-move-paren om een achtlagig convolutioneel neuraal netwerk te trainen om te herkennen welke zet deze deskundige spelers vervolgens maakten. Dit was een proces dat enkele dagen in beslag nam.
Vervolgens gebruikten ze de rest van de dataset om het neurale netwerk te testen. Met andere woorden, ze presenteerden het netwerk een bordpositie uit een spel en vroegen het de volgende zet te kiezen. Clark en Storkey zeggen dat het getrainde netwerk in staat was om de volgende stap tot 44 procent van de tijd te voorspellen en overtrof de eerdere stand van zaken op deze taak met aanzienlijke marges.
Dat is interessant, niet in de laatste plaats omdat de nieuwe aanpak geen van de eerdere stappen gebruikt om zijn beslissing te nemen; evenmin evalueert het toekomstige posities.
Nadat ze het neurale netwerk hadden getraind, speelden Clark en Storkey het vervolgens uit tegen twee van de beste Go-algoritmen die er zijn. De eerste heet GNU Go, die speelt op een niveau dat gelijk is aan dat van een gemiddelde amateur met een rangorde van 6-8 kyu. (Go-ranglijsten variëren van een beginner met een rangorde van 30-20 kyu tot een professionele expert met een rangorde van 1 kyu).
Het tweede was een ultramodern programma genaamd Fuego 1.1, met een rangorde van ongeveer 5-4 kyu. Een menselijke speler zou gewoonlijk vele jaren van studie vergen om dit niveau te bereiken.
De resultaten suggereren duidelijk dat het schrijven aan de muur is voor menselijke Go-spelers. Het neurale netwerk van Clark en Storkey versloeg GNU Go bijna 90 procent van de tijd in een reeks van 200 games. Met andere woorden, na een paar dagen training was het neurale netwerk in staat om GNU Go consequent te verslaan.
Tegen Fuego 1.1 deed het het minder goed en won slechts iets meer dan 10 procent van zijn games. Toch is dat een prestatie van formaat. Zelfs maar een paar wedstrijden tegen deze tegenstander kunnen winnen, geeft aan dat er een hoge mate van vaardigheid is verworven, zeggen Clark en Starkey.
Dat is duidelijk veelbelovend. Hoewel de netwerken spelen met een 'zero step look ahead'-beleid en een fractie van de rekentijd gebruiken als hun tegenstanders, zijn ze nog steeds in staat om beter te spelen dan GNU Go en een aantal games weg te nemen van Fuego, zeggen ze.
En er is duidelijk verbeterpotentieel, bijvoorbeeld door deze aanpak te combineren met andere die wel eerdere zetten gebruiken en vooruit kijken. Een idee dat Clark en Starkey suggereren, is om het convolutionele neurale netwerk parallel te laten lopen met de conventionele benadering om de boom van mogelijke bewegingen die moeten worden onderzocht, te helpen snoeien.
Er is geen suggestie van Clark en Storkey dat deze aanpak de beste Go-spelers ter wereld zal verslaan. Maar het is zeker slechts een kwestie van tijd voordat zelfs Go-spelers zullen moeten buigen voor hun geautomatiseerde opperheren.
Referentie: arxiv.org/abs/1412.3409 : Diepe convolutionele neurale netwerken aanleren om Go te spelen