Vrije Universiteit Amsterdam
Informatie voor de pers. Vrije Universiteit Amsterdam.
07/08/2002
---
Nieuwe clustercomputer lost antiek spel op
Met vier op een rij lukte het al eerder; dammen, schaken en go zijn
nog toekomstmuziek. Maar informaticus dr. John Romein rekende met een
clustercomputer van 72 pc´s het 3500 jaar oude Afrikaanse bordspel
awari helemaal door. Binnenkort kun je op internet awari spelen tegen
het web en daarbij de moeilijkheidsgraad instellen op ´onfeilbaar´.
Binnen de kunstmatige intelligentie werken onderzoekers al jaren aan
het oplossen van steeds complexere spelletjes.
Hoewel awari, ook wel orient genoemd, een eenvoudig spel lijkt, zijn
er bijna 900 miljard verschillende bordstellingen mogelijk. Het
helemaal doorrekenen van het spel betekent dat je vanuit al die
bordstellingen de beste zet moet bepalen.
Awari wordt tegenwoordig wereldwijd gespeeld. Twee spelers hebben elk
zes kuiltjes met in totaal 48 stenen. Die stenen strooien ze uit op
het bord, waarna ze volgens de regels van het spel stenen van het bord
winnen. Wie de meeste stenen verovert, wint het spel.
Om alle mogelijke bordstellingen van awari door te rekenen, gebruikte Romein de nieuwe clustercomputer van de Faculteit der Exacte Wetenschappen. Die computer bestaat uit 72 pc´s met elk twee 1 Ghz Pentium-III processoren, 1 gigabyte geheugen en een harde schijf. De pc´s zijn met elkaar verbonden door een supersnel netwerk.
Romein schreef de software die nodig was om de clustercomputer awari te laten doorrekenen. Het programma begint te rekenen vanuit de eindstellingen, waarin alle stenen zijn veroverd, en redeneert terug tot de beginstelling. Romeins programma maakte optimaal gebruik van alle hardware: de 144 processoren deden er samen slechts 51 uur over om de vele miljarden stellingen door te rekenen. Een belangrijk probleem dat Romein moest oplossen was dat de 72 gigabyte geheugen van de clustercomputer lang niet genoeg is om de gegevens van alle stellingen te onthouden. Een ander probleem was de excessieve netwerkbelasting: de ´samenwerking´ tussen de pc´s resulteerde in een totale dataoverdracht van maar liefst 1,0 petabit (10^15 bits).
Het eindresultaat van alle berekeningen is een database van 778
gigabyte waarin je voor elke stelling van het spel de uitslag en de
beste zet kunt opvragen. Binnenkort, hopelijk in de loop van deze
maand staat die database op de website http://awari.cs.vu.nl. Op die
site komt ook een awari spelend programma dat Romein nu aan het maken
is, zodat je tegen het web awari kunt spelen. De moeilijkheidsgraad
kun je op onfeilbaar instellen, want het programma heeft immers de
beschikking over een alwetende database. Als je dan zelf ook
onfeilbaar speelt, eindigt het potje awari in gelijk spel. Na het
doorrekenen is namelijk bekend dat het niet uitmaakt wie begint:
optimaal spel van beide spelers eindigt in gelijk spel. Dus daar zal
het niet aan liggen als je verliest...
Vrije Universiteit Amsterdam