Nickerie.Net, vrijdag 20 juli 2007

Perfecte strategie voor Engels damspel berekend

Canada - Volgens een Canadese hoogleraar informatica eindigt checkers altijd in gelijkspel als beide partijen perfect spelen. Het bewijs voor deze stelling publiceerde hij gisteren op de website van het wetenschappelijke tijdschrift Science.

Checkers is een variant van dammen die ook wel bekend staat als 'Engels dammen' en waarbij twee spelers, elk met 12 stenen, op de zwarte vlakken van een schaakbord spelen. In 1989 presenteerde hoogleraar informatica Jonathan Schaeffer van de Universiteit van Alberta in Canada Chinook: een computerprogramma dat het WK checkers in 1994 won van een mens. Dat programma maakte gebruik van een enorme database met zetten die menselijke grootmeesters hadden gedaan. Nadat de checkerscomputer de kampioenstitel had binnengesleept, besloot Schaeffer het spel te gaan 'oplossen'.

Dit zou een indrukwekkende klus worden, aangezien er bij checkers maar liefst 500 triljard (5∙10²⁰) mogelijke spelsituaties bestaan. Daarom begon Schaeffer met een database met alle mogelijke eindspelen die op zouden kunnen treden bij winst, verlies en gelijkspel. Vanaf die eindsituaties zocht hij terug naar mogelijke voorgaande situaties, net zolang tot hij bij een spelsituatie met 10 speelstukken uitkwam. Op dat moment had hij al een database van 39 biljoen spelsituaties, die ondanks compressie 237GB aan ruimte innamen. Deze database vergde dermate veel rekenkracht dat Schaeffer het project in 1997 stilzette, om pas vier jaar later de draad weer op te pakken.

Schaeffer zette vervolgens een voorwaarts zoekalgoritme in om vanaf de beginsituatie te zoeken naar een rij zetten die tot een van de 39 biljoen spelsituaties zou leiden. Hierbij werd niet gezocht naar alle mogelijke zetten en de gevolgen ervan, zoals Chinook of schaakcomputer Deep Blue dat zouden aanpakken; enkel de beste zetten werden geanalyseerd, namelijk de zetten die zo snel mogelijk tot winst zouden leiden. Het doel van een checkersspeler is volgens Schaeffer namelijk het in zo min mogelijk zetten winnen van het spel of verlies zo lang mogelijk uitstellen. Zo bleven van de 500 triljard mogelijke spelsituaties 'nog maar' 100 biljoen posities over.

Checkersspelers hadden al langer het vermoeden dat een spel altijd in remise moest eindigen als beide spelers perfect speelden. Partijen tussen menselijke spelers eindigden zo vaak in gelijkspel dat het vanaf 1934 verplicht was iedere partij op een wereldkampioenschap te beginnen met drie zetten uit een lijst met geaccepteerde willekeurige zetten. Schaeffer heeft nu van 19 van de 300 mogelijke openingszetten bewezen dat ze in remise eindigen bij een perfecte speelwijze. De overige 281 beginzetten leiden volgens de professor tot spelsituaties die door de 19 bewezen openingszetten ook bereikt worden. Hij is daarom ook niet van plan moeite te doen om een volledig bewijs te leveren. Dat zou ook onmogelijk zijn omdat zelfs de grootste supercomputers van dit moment niet genoeg opslagruimte hebben voor de tientallen petabytes aan ruimte die de database inneemt.

Het zal nog heel lang duren voor een spel als schaken wordt 'opgelost'. Wetenschappers vermoeden dat ook dat spel altijd in remise eindigt als het perfect gespeeld wordt, maar het aantal mogelijke spelposities bij schaken is het kwadraat van dat bij checkers. Dit betekent dat er 10⁴⁰ tot 10⁵⁰ mogelijke situaties moeten worden geanalyseerd. Volgens Schaeffer is dat niet onmogelijk, maar zonder een doorbraak in kwantumcomputertechnologie zal niemand aan de lange zoektocht beginnen.

WWW.NICKERIE.NET

E-mail: info@nickerie.net

Designed by Galactica's Graphics