Computer kraakt Go-spel

11 januari 2005

NWO-promovendus Erik van der Werf heeft als eerste ter wereld met een computerprogramma het Go-spel op een speelbord van 5x5 opgelost. Een volledig Go-speelbord telt 19 bij 19 lijnen. Van der Werf onderzocht nieuwe computertechnieken die de Go-programma's moeten verbeteren en op termijn de beste menselijke spelers kunnen verslaan. De onderzoeker promoveert op 27 januari aan de Universiteit Maastricht.

Naast het Go-spel op het speelbord van 5 bij 5 lijnen, loste Van der Werf ook Slag-Go (een vereenvoudigde versie van Go) op voor borden tot en met 6x6. Met hun laatste programma MAGOG wonnen Van der Werf en zijn collega's afgelopen zomer de bronzen medaille op het 9x9 Go-toernooi van de negende Computer Olympiade in Israël.

Techniek
Het onderzoek van Van der Werf richtte zich op zoektechnieken en leertechnieken voor spelprogramma's. Zoektechnieken worden gebruikt in schaakprogramma's om een aantal zetten vooruit te denken. Zo kunnen de tactische complicaties in posities beter worden beoordeeld. Wanneer een zoekprogramma efficiënt genoeg is om zo ver vooruit te denken dat er eindstellingen worden bereikt, kan het in principe perfect spelen. Het MIGOS-programma waarmee de Maastrichtse onderzoeker het Go-spel op het 5x5-speelbord oploste, is gebaseerd op zoektechnieken.

Om Go voor grotere speelborden optimaal te spelen, zijn alleen zoektechnieken niet voldoende. Het programma kan dan niet altijd meer zo diep zoeken dat eindstellingen worden bereikt. Van der Werf richtte zich daarom ook op leertechnieken, die in spelen als Backgammon of andere complexe toepassingen als beeldherkenning worden gebruikt. Bij de leertechnieken leert de computer van menselijke voorbeeldpartijen, die door het Go-programma worden geanalyseerd. De promovendus gebruikte de leertechnieken voor het voorspellen van sterke zetten, het voorspellen van leven en dood en voor het schatten van potentieel gebied.

Tactiek
Go is een Oosters bordspel voor twee spelers die proberen gebied te omsingelen met stenen van hun kleur. Spelers kunnen de stenen van de tegenstander slaan door ze met eigen stenen in te sluiten. De speler met het meeste gebied wint het spel. Volgens de legende werd het spel in 2300 voor Christus voor het eerst gespeeld door een Chinese keizer die zijn zoon tactiek, strategie en concentratie wilde leren.

In 1997 werd wereldkampioen schaken Kasparov verslagen door schaakcomputer Deep Blue. Bijna acht jaar later is er echter nog geen Go-programma ontwikkeld dat een sterke amateur zou kunnen verslaan. In het midden van de jaren tachtig stelde de Taiwanese industrieel mr. Ing één miljoen dollar beschikbaar voor de maker van het eerste Go-programma dat een professionele speler kon verslaan. Het prijzengeld verliep in 2000 door de dood van mr. Ing, maar een Go-programma dat voldoende sterk is moet nog steeds worden ontwikkeld.

..............................

Meer informatie:

• ir. Erik van der Werf (UM, IKAT - Institute for Knowledge and Agent Technology)
• t: +31 (0)43 388 34 91, E.vanderWerf@cs.unimaas.nl
• promotie 27 januari, promotor prof. dr. H.J. van den Herik