Chinook (datorprogram)
Chinook är ett datorprogram som spelar pjäs (även känt som drag). Den utvecklades mellan åren 1989 till 2007 vid University of Alberta , av ett team ledd av Jonathan Schaeffer och bestående av Rob Lake, Paul Lu, Martin Bryant och Norman Treloar. Programmets algoritmer inkluderar en öppningsbok som är ett bibliotek med öppningsdrag från spel som spelas av schackstormästare; en djupsökningsalgoritm; en bra rörelseutvärderingsfunktion; och en slutspelsdatabas för alla positioner med åtta pjäser eller färre. All Chinooks kunskap programmerades av dess skapare, snarare än lärde sig med hjälp av ett artificiellt intelligenssystem .
Man vs. maskinvärldsmästare
Chinook är det första datorprogrammet att vinna världsmästartiteln i en tävling mot människor. 1990 vann den rätten att spela i världsmästerskapet för människor genom att vara tvåa efter Marion Tinsley i US Nationals. Till en början American Checkers Federation och English Drafts Association emot en dators deltagande i ett mästerskap för mänskliga rättigheter. När Tinsley sa upp sin titel i protest skapade ACF och EDA den nya titeln Man vs Machine World Championship, och tävlingen fortsatte. Tinsley vann med fyra vinster till Chinooks två, med 33 oavgjorda.
I en revansch utsågs Chinook till Man-Machine World Champion i schack 1994 i en match mot Marion Tinsley efter sex oavgjorda matcher, och Tinsleys tillbakadragande på grund av cancer i bukspottkörteln. Medan Chinook blev världsmästare, besegrade den aldrig den bästa damspelaren genom tiderna, Tinsley, som var betydligt överlägsen även sin närmaste kamrat.
1995 försvarade Chinook sin man-maskin-titel mot Don Lafferty i en 32-matcher match. Slutresultatet blev 1–0 med 31 oavgjorda resultat för Chinook över Lafferty. Efter matchen bestämde sig Jonathan Schaeffer för att inte låta Chinook tävla mer, utan istället försöka lösa pjäser. Vid den tiden var den klassad till 2814 Elo . Lösningen uppnåddes och resultatet publicerades 2007.
Algoritm
Chinooks programalgoritm inkluderar en öppningsbok, ett bibliotek med öppningsdrag från spel som spelas av stormästare; en djupsökningsalgoritm; en bra rörelseutvärderingsfunktion; och en slutspelsdatabas för alla positioner med åtta pjäser eller färre. Den linjära handgjorda utvärderingsfunktionen tar hänsyn till flera funktioner på spelbrädet, inklusive antal pjäser, antal kungar, fångade kungar, vändning, förrymda pjäser (ohindrad väg att bli kung) och andra mindre faktorer. All Chinooks kunskap programmerades av dess skapare, snarare än lärde sig med artificiell intelligens.
Tidslinje
- 1997 - Jonathan Schaeffer skriver en bok om Chinook som heter One Jump Ahead: Challenging Human Supremacy in Checkers . En uppdaterad version av boken publicerades i november 2008.
- 24 maj 2003 - Chinook slutför sin 10-delade databas med 5 stycken på varje sida.
- 2 augusti 2004 - Chinook-laget tillkännager att turneringsöppningen i schack som kallas White Doctor (10–14 22–18 12–16) har visat sig vara oavgjort.
- 18 januari 2006 - Chinook-teamet meddelar att öppningen 09–13 21–17 05–09 har visat sig vara oavgjord.
- 18 april 2006 - Chinook-teamet meddelar att öppningen 09–13 22–17 13–22 bevisligen är oavgjord.
- 10 mars 2007 - Jonathan Schaeffer tillkännager (vid ACM SIGCSE 2007-konferensen) att en slutlig lösning för pjäser förväntas inom 3–5 månader.
- 19 juli 2007 - Tidskriften Science publicerar Schaeffers lags artikel "Checkers Is Solved", och presenterar deras bevis på att det bästa en spelare kan uppnå när han spelar mot en spelare med perfekt information är oavgjort.