Chinook (programma)
Chinook is een computerprogramma dat checkers, een damspel, speelt. Het programma werd ontworpen tussen 1989 en 2007 en is nu onverslaanbaar. Het is ontworpen aan de Universiteit van Alberta onder leiding van Jonathan Schaeffer. Andere ontwikkelaars van Chinook zijn Yngvi Bjornsson, Neil Burch, Rob Lake, Joe Culberson, Paul Lu en Steve Sutphen.
Geschiedenis
bewerkenHet Chinook-project startte in 1989 en had als doel de wereldkampioen dammen te verslaan door middel van een programma.
Een jaar later, in 1990, werd Chinook tweede in de US nationals, hierdoor mag men normaal meedoen aan het menselijke wereldkampioenschap. De American Checkers Federation en de English Draughts Association waren echter tegen het deelnemen van een computer in een menselijk wereldkampioenschap en daarom mocht Chinook niet deelnemen aan het wereldkampioenschap.
Marion Tinsley, de toenmalige wereldkampioen, was op zoek naar meer competitie. Deze vond hij niet bij zijn menselijke tegenstanders waar hij al meer dan 40 jaar van won. Daarom wou Tinsley een spel spelen tegen Chinook. Na een opgave van Tinsley's wereldtitel in 1992 en een afspraak voor een wedstrijd tussen Tinsley en Chinook werd er een nieuwe titel gemaakt: Man vs. Machine world Championship. Hier verloor Chinook van Marion Tinsley, Tinsley won 4 keer en Chinook 2 keer, er waren 33 gelijke spellen.
In 1994 vond er een herkansing plaats voor Chinook in het wereldkampioenschap. Deze keer won Chinook door een opgave van Tinsley na 6 spellen met gelijke stand. Door deze opgave is Chinook nooit geslaagd in zijn oorspronkelijke doel, het verslaan van de wereldkampioen.
In 1995 verdedigde Chinook zijn wereldtitel op het wereldkampioenschap tegen Don Lafferty. Hier won Chinook van Lafferty met 31 gelijke spellen en 1 winnend spel. Datzelfde jaar besloot Jonathan Schaeffer dat Chinook niet meer tegen menselijke tegenstanders zou spelen omdat het programma te sterk was geworden.
Omdat Schaeffer en zijn team nu geen doel meer voor ogen hadden zochten ze naar een ander doel, ze gingen dammen oplossen. Dit wil zeggen dat het algoritme achter Chinook ervoor zorgt dat Chinook niet kan verliezen. Het wint altijd behalve tegen een perfect spel van de tegenspeler, hier haalt het dan een gelijkspel.
Om dammen op te lossen was er een gemiddelde van 50 computers in parallel nodig, deze onderzochten al de mogelijke resultaten van elke mogelijke zet. Voor dit onderzoek heeft men een zoekruimte van 5 × 1020 nodig. Dit is 1 miljoen keer groter dan het spel Connect Four en 100 miljoen keer groter dan Awari. Dit maakt dammen het grootste en moeilijkste spel dat momenteel compleet is opgelost.
Tijdlijn
bewerken- In 1989 werd het project gestart. Het bouwen van een programma dat de wereldkampioen dammen kan verslaan.
- In 1990 zou Chinook mogen meespelen in een menselijk wereldkampioenschap door een tweede plaats bij de US nationals. Dit werd echter niet toegelaten door de American Checkers Federation en de English Draughts Association.
- In 1992 werd Chinook tweede op het nieuwe wereldkampioenschap, Man vs. Machine world Championship.
- In 1994 won Chinook het wereldkampioenschap na een opgave van zijn tegenstander Marion Tinsley.
- In 1995 verdedigde Chinook zijn man-versus-machine-wereldtitel tegen Don Lafferty.
- In 1996 besloot Jonathan Schaeffer om Chinook niet meer te laten concurreren en wou hij, samen met zijn team, dammen oplossen.
- Op 10 maart 2007 maakte Jonathan Schaeffer bekend dat een complete oplossing voor dammen verwacht werd in 3 tot 5 maanden.
- Op 29 april 2007 maakte het ontwikkelingsteam van Chinook bekend dat ze dammen volledig opgelost hadden. Het programma kon niet slechter dan een gelijke stand eindigen.
Algoritme
bewerkenChinook maakt gebruik van databases waaronder een openingdatabase en een einddatabase. De openingdatabase bevat allemaal openingszetten die ooit gezet zijn door grootmeesters. De einddatabase bevat alle mogelijke posities met 8 stukken of minder. Chinook maakt daarnaast ook nog gebruik van een zoekalgoritme en een goedezetevaluatiefunctie. Deze evaluatiefunctie behandelt diverse aspecten van het spelbord waaronder het aantal stuks, het aantal koningen en gevangen koningen en nog andere factoren. Hierdoor evalueert Chinook het spel en weet hij welke zet hij het beste kan zetten. Al deze kennis is geprogrammeerd door de makers van Chinook, hierdoor is het geen artificiële intelligentie en leert het programma dus niet van zijn eventuele fouten.