Home /
Blog /
Computers verslaan ons in elk bordspel? Niet als het aan een Go-grootmeester ligt

Computers verslaan ons in elk bordspel? Niet als het aan een Go-grootmeester ligt

vrijdag 13 maart 2015
 

 
 

ComputersIn 1956 had Arthur Samuel een geweldig idee. Hij wilde een programma schrijven dat in staat was hem te verslaan met dammen. Zijn plan van aanpak startte een discipline wat we nu ‘machine learning’ noemen. Laat de computer duizenden keren tegen zichzelf spelen en de computer zal een damgrootmeester worden.

En zo schreef hij ’s werelds eerste ‘self-learn’ programma. Met succes, want in 1962 versloeg zijn programma de kampioen van de staat Connecticut, in de Verenigde Staten. In 1994 versloeg een programma een damgrootmeester. Inmiddels zijn er programma’s die ons verslaan in de bordspellen Othello, Scrabble, Backgammon, Jeopardy en zelfs schaken. In 1997 won IBM’s Deep Blue supercomputer van de toenmalige wereldkampioen schaken, Garry Kasparov.  

Er is echter één bordspel waar het een computer maar niet lukt om een grootmeester te verslaan. Dat spel heet Go. Dit is een bordspel dat zeer populair is in China, Korea en Japan. Het is de Oosterse versie van schaken. Go is zo’n 2500 jaar geleden bedacht in China. Het werd gespeeld door generaals en keizers. Sindsdien wagen de intellectuelen onder ons zich aan dit bordspel. Net als schaken is het een spel waar alle informatie beschikbaar is voor je tegenstander. Het is een strijd tussen twee personen, waarbij de essentie is het plaatsen van witte en zwarte stenen. Je doel is om het territorium van je tegenstander te omsingelen. Tegelijkertijd moet je uit handen zien te blijven van de vijand. Het lijkt gemakkelijker dan schaken, dat is het niet. Toen Garry Kasparov werd verslagen door IBM’s super programma, konden de beste Go programma’s nog niet eens winnen van een amateur.

Al vanaf 1962 proberen programmeurs een programma te schrijven dat in staat is om een Go-grootmeester te verslaan. Pas in 1968 maakte Alfred Zobrist het eerste programma dat in staat was om een absolute beginner in Go te verslaan. Ondanks de ontwikkelingen op het gebied van computing, blijft het verslaan van een Go-speler op expert niveau nog steeds een raadsel. ‘AI’s greatest unsolved riddles’, zegt Remi Coulom. Remi Coulom is een computerwetenschapper, onderdeel van een kleine community die hopen dit raadsel op te lossen.

Waarom lukt het maar niet om een programma te schrijven dat in staat is om een grootmacht in Go te worden? Dat is het beste uit te leggen als we kijken naar schaken. Bij schaken heeft wit, wit opent, twintig mogelijke zetten die hij kan doen. Vervolgens is zwart aan de beurt. Ook zwart heeft twintig mogelijke zetten. Wanneer beide partijen een zet hebben gedaan, zijn er 400 mogelijke zetten die kunnen worden gedaan. Bij Go zijn de mogelijkheden bij de eerste twee zetten iets uitgebreider. Ten eerste beginnen de spelers daar op een volledig blanco bord. Mat als gevolg dat zwart 361 mogelijke zetten heeft. Wit heeft er vervolgens 360 die hij kan doen. Dat houdt in dat, in de eerste ronde van mogelijke zetten, een programma rekening moet houden met 129.960 zetten. Wat houdt dat voor programmeurs in? Dat zowel de programmeurs als de algoritmes het niet gemakkelijk hebben.

Vanaf de jaren ’60 boekte ontwikkelaars van Go-programma’s wel degelijk vooruitgang. Maar de laatste stap in de ontwikkeling, nodig om een grootmeester te verslaan, kan maar niet worden gemaakt. In de jaren ’90 kwamen ontwikkelaars erachter dat zij niet boven een bepaald niveau uit konden stijgen. Gevorderden in Go konden worden verslagen, experts niet. David Fortland, hoofd engineer van Hewlett Packard’s PA-RISC processor in de jaren ‘70, legt uit: ‘The issue is being able to look at the whole board, not just the local fights.’ Go wordt gespeeld op meerdere vlakken van het bord. Er vinden allerlei kleine veldslagen plaats, in plaats van één hele grote veldslag zoals bij schaken het geval is.

Remi Coulom nam in 2014 de uitdaging aan om grootmeester Norimoto Yoda te verslaan. Coulom schreef het Go-programma Crazy Stone. En wonder boven wonder, Coulom won. Is nu eindelijk de laatste stap gemaakt? Zijn programma’s nu ook in staat om een grootmeester te worden in Go? Nee. Coulom en zijn programma begonnen met een ontzettend voordeel. De wedstrijd begon namelijk niet op een leeg bord. Het programma Crazy Stone begon met vier zwarte stenen (zijn kleur) geplaatst in alle vier de hoeken van het bord. Dit is een behoorlijk nadeel voor het spel van grootmeester Yoda. Hij moest zijn agressieve stijl intomen. Na de wedstrijd werd Coulom gevraagd wanneer een programma, zonder te starten met een voordeel, in staat is te winnen van een grootmeester. Coulom’s antwoord: ‘I think maybe in ten years.’

 

Terug naar overzicht
 
 
Terug naar overzicht

Heb je nog vragen?

Je kunt ons bellen
Telefoon:
020 - 5300500
... of we bellen jou
of je mailt ons