Exponentieel complex

Erik van der Werf heeft een vereenvoudigde versie van Go met hulp van de computer opgelost. Het complete bordspel is daarvoor veel te ingewikkeld.

GO IS EEN KLASSIEK Oosters spel waarbij twee spelers beurtelings een ronde steen plaatsen op een leeg kruispunt van een bord met een 19x19 lijnen, om zoveel mogelijk gebied te omsluiten. Eerder dit jaar promoveerde de informaticus Erik van der Werf aan de Universiteit Maastricht op het proefschrift `AI techniques for the game of Go'.

Het oplossen van spellen heeft zich de laatste jaren ontwikkeld tot een geheel eigen tak van het artificiële-intelligentieonderzoek (AI). Van der Werf onderzocht hoe een Go-programma kan profiteren van de zoektechnieken die succesvol zijn toegepast in schaakprogramma's, en van leertechnieken die worden gebruikt in bijvoorbeeld Backgammon-programma's. Van der Werf verkleinde het speelveld drastisch, en schreef het computerprogramma MIGOS, dat Go op heel kleine borden volledig oplost.

Een spel is opgelost wanneer voor iedere zet de beste tegenzet bekend is, en dus ook het verdere verloop en de uitkomst van het spel. Go op een 19x19 bord zal nooit worden opgelost, de complexiteit is daarvoor veel te groot.

5x5 bord

Go op een speelveld van 2x2 of 3x3 is tamelijk triviaal; het enige lastige is de regel met betrekking tot herhaling van stellingen, waarvan verschillende interpretaties bestaan. In 2000 loste een Japans programma Go op een 4x4 bord op. Erik van der Werf is er nu als eerste in geslaagd om Go op een 5x5 bord helemaal door te rekenen en daarmee op te lossen: Zwart wint met de maximale score van 25 punten. Door het toepassen van slimme zoek- en leertechnieken doorzocht MIGOS slechts 1,5 miljard eindposities, in plaats van de (minstens) 10 eindposities (complexiteit 25) van de volledige variantenboom voor dit kleine bord.

De lijst van opgeloste spelen groeit langzaam maar gestaag. Boter-Kaas-Eieren is bijvoorbeeld zó simpel dat ook zonder computer eenvoudig te bepalen is dat het bij optimaal spel van beide kanten altijd onbeslist eindigt. Ook vier-op-een-rij is opgelost: wie begint, wint. Maar dat was zonder computer nooit gelukt.

Om een spel op te lossen, bekijkt een computer alle mogelijkheden, en zoekt de kortste weg naar een geforceerde winst. De zettenreeksen vanuit de beginsituatie (de wortel) vormen een vertakt netwerk met eindposities (bladeren), in de vorm van een boom. Eindposities hebben een ondubbelzinnige waarde: gewonnen, verloren of onbeslist. De variantenboom groeit exponentieel, als het aantal mogelijke zetten tot de macht van de lengte van de partij. De volledige variantenboom voor Boter-Kaas-Eieren bevat 9! = 362.880 eindposities (de eerste speler kan kiezen uit 9 zetten, de tegenstander heeft daarna nog 8 zetten, enzovoort). In werkelijkheid is dit getal kleiner, want het spel eindigt zodra iemand drie-op-een-rij heeft bereikt. Bij niet-optimaal spel van de tegenstander kan dat al na 5 zetten het geval zijn. De complexiteit van een spel wordt vaak uitgedrukt als de logaritme (het aantal nullen) van de hoeveelheid eindposities in de volledige variantenboom. Voor Boter-Kaas-Eieren is de complexiteit dus 5. Dan blijkt dat Vier-op-een-rij zeer veel complexer is, namelijk 21. Schaken heeft een complexiteit van maar liefst 123, en Go spant de kroon met 568. Het aantal mogelijke zettenreeksen in Go is (conservatief geschat) een getal met 568 nullen!

Vanwege de enorme complexiteit is het doorzoeken van de variantenboom in Go een onmogelijke opgave. In de beginpositie kan Zwart kiezen uit 361 zetten. Wit heeft daarna 360 mogelijkheden, enzovoort. Een volledige variantenboom van alleen de eerste tien zetten bevat al meer dan 10 eindposities. Een computer zou daarover langer moeten rekenen dan de leeftijd van het Heelal. Maar erger nog dan deze exponentiële explosie, is dat een computer aan 10 stenen op een bord van 361 kruispunten nog absoluut niet kan zien wie er gaat winnen.

De volgende uitdaging is het oplossen van Go op een bord van 6x6. Dat lijkt slechts een klein beetje complexer, maar schijn bedriegt. Er zijn nu 36 kruispunten in plaats van 25, waardoor de complexiteit oploopt van 25 naar 41. Dat betekent 10 biljard (10) maal zoveel eindposities als Go op een 5x5 bord. De ontwikkeling van computers volgt al 40 jaar lang de Wet van Moore – genoemd naar Gordon Moore, een van de oprichters van Intel – die zegt dat het aantal transistoren op een microchip iedere 18 maanden verdubbelt. De snelheid van een computer houdt hiermee gelijke tred. Als die wet stand blijft houden, kan MIGOS over 20 jaar Go op een 6x6 bord binnen een redelijke tijd oplossen.

Je zou denken dat mensen het bij dergelijke exponentieel complexe opgaven afleggen tegen de brute rekenkracht van een computer, maar dat is niet zo. Menselijke spelers hebben Go op een 6x6 bord namelijk wel opgelost: Zwart wint met 4 punten. Maar totdat een computer dit kan verifiëren, is het niet zeker dat die oplossing ook werkelijk correct is. Toch schat Erik van der Werf de kans dat het correct is op 90 procent.

Een 6x6 bord waarop al 8 zetten zijn uitgevoerd, heeft nog 28 lege kruispunten, en een complexiteit van 29. Dat is op dit moment het maximaal haalbare voor een pc-programma. MIGOS rekende een aantal van dit soort stellingen door. Met de moeilijkste stelling was het programma 13 dagen bezig, en evalueerde in die tijd 220 miljard eindposities. MIGOS kon weliswaar niet bewijzen dat zwart met 4 punten wint (de uitkomst van menselijke analyses), maar toonde wel aan dat Zwart zal winnen met tenminste 2 punten. Ook Go op een 7x7 bord is misschien al door mensen opgelost. Na jarenlange studie kwam een groep Japanse amateurs, bijgestaan door twee professionals, tot de conclusie dat Zwart wint met 9 punten. Het zal nog heel lang duren voordat een computer dat resultaat kan verifiëren.

kasparov

Een computer hoeft een spel niet volledig op te lossen om van mensen te winnen. Hoewel een computer nooit het schaakspel (complexiteit 123) zal kunnen oplossen, evenaren schaakprogramma's wel het niveau van de menselijke wereldtop. Gary Kasparov, waarschijnlijk de sterkste schaker ooit, verloor in 1998 een match tegen Deep Blue, een supersnelle IBM-computer met speciaal ontworpen schaakprocessoren. Inmiddels spelen ook pc-schaakprogramma's op dat niveau. Het programma Hydra heeft zelfs nog nooit van een mens verloren. Deze zomer werd Michael Adams, momenteel nummer 13 op de wereldranglijst, in een match over zes partijen met 5,5 – 0,5 door Hydra verpletterd. Maar Go-spelers kunnen voorlopig rustig slapen. Zelfs een zwakke professional zal niet binnen 25 jaar door een computer worden verslagen.