One jump ahead : challenging human supremacy in checkers

by Jonathan Schaeffer

Hardcover, 1997

Status

Available

Call number

794.2/0285

Library's review

Indeholder "Preface", "Acknowledgments", " I Can't Lose", "The Opening", " 1. This Was Going to Be Easy", " 2. Bottomless Well", "The Middlegame", " 3. Valuable Lessons", " 4. The Illusion of Intelligence", " 5. A Nobel Turing Trio", " 6. Didn't Samuel Solve That Game?", " 7. The Case for the
Show More
Prosecution", " 8. You Look Like a Checkers Player", " 9. The Fudge Factor", " 10. I Feel Like a Teenager Again", " 11. Gentlemen, Start Your Engines", " 12. Trust Me", " 13. A Wake-Up Call", " 14. Prelude to Disaster", " 15. Programmed by God", " 16. Divine Intervention", " 17. Dissension Among the Ranks", " 18. Home Away From Home", " 19. It's a Draw!", " 20. Let Me Suggest the Unthinkable", "Behind the Electronic Façade", "The Endgame", " 21. Gentlemen's Agreement", " 22. I'm Ready to Go", " 23. Get a Life, Jonathan", " Epilogue", " Appendix A. Further Reading", " Appendix B. Tinsley's Record", " Appendix C. Tinsley's Losses", " Appendix D. Chinook's Record", " Appendix E. Chinook Technical Specifications", " Appendix F. Tinsley-Chinook Games", "Index".

Ganske underholdende bog om en mand, der vil skrive et computerprogram, der kan spille Dam fejlfrit. Han er en meget habil skakspiller og har også skrevet flere skak-programmer, før han løber tør for gode ideer og i 1988 beslutter sig for at koncentrere sig om Dam. Et gammelt program skrevet af en Samuel kan spille men ikke ret godt, for den tids computere var ret langsomme og programmet er skrevet efter at kunne udnytte dem så godt som muligt. Nyere computere har kræfter til at se mange halvtræk frem, så meget af Samuel's program kan undværes. En Norman C. Treloar skriver til Schaeffer og tilbyder sin assistance og ret store ekspertise i at spille spillet. Et par af Schaeffers medarbejdere, Joe og Duane, bruger en aften med Norm og forbedre Schaeffer's program "The Beast" ret kraftigt. Så det må være nemt at skrivet et program, der kan hamle op med verdensmesteren. Vi er nu i juni 1989.
Norm har en masse eksempler som viser at man er nødt til at have både en åbningsdatabase og en database over slutspil. Fx "First Position" som ellers kræver mindst 20 halvtræk for at se at Hvid vinder. De melder Chinook (som "The Beast" er blevet omdøbt til) til den første Computer Olympiad i London i den anden uge af August 1989. Schaeffer får mange nye værdifulde bekendtskaber der. Og noget at tænke over, for de gode dam-spillere tror ikke meget på hans projekt. Men Chinook vinder over de andre programmer og spiller også mod de gode menneskespillere. Men nogle af eksemplerne, som kommer op, tyder på at topspillerne vil løbe om hjørner med Chinook.
Vi får et glimrende eksempel på en evalueringsfunktion og hvordan den virker.
Schaeffer kommer i kontakt med Ken Thompson, der bare for sjov laver en database over alle situationer med 5 brikker og sender den til ham. Dels har Thompson programmeret perfekt på ca en tyvendedel af den tid Schaeffer skulle bruge og dels har Schaeffer heller ikke adgang til så meget computerkraft som Thompson. Chinook gør dog ikke så store fremskridt. Schaeffer prøver at få det til at køre hurtigere, men skal så bruge mere tid på at debugge. Her er en fin diskussion om nogle af de første programmer, der kan spille Mølle og Dam. I 1949 havde Arthur Lee Samuel et program skrevet i rå maskinkode (dvs ikke engang assembler) til Illiac, men maskinen var ikke køreklar. Faktisk havde programmet indflydelse på instruktionssættet til Illiac, fordi man havde brug for inspiration til andet end regneprogrammer. I 1953 dukkede ideen om brug af hashing op og IBM 701 var ved at blive bygget. Det var IBM's første serieproducerede computer og kunne lejes for kun $12.000 om måneden.
Til næste North American Computer Chess Championship møder han Herbert Simon (som i 1958 forudsagde en skak-mester "within ten years"). Arthur Samuel og hans program spiller mod R. W. Nealey, som ikke er "master player" andre steder end i hans egen fantasi. Begge parter laver store fejl og resultatet er ret tilfældigt. Men i folkloren bliver det til at Samuels program har løst problemet fuldstændigt og fx spænder den opfattelse ben for Schaeffer, når han prøver at skaffe penge til sin egen forskning.
I 1990 er Chinook nået til et punkt, hvor en database med alle situationer med 6 brikker ville være rar. (5 brikker er mest af typen hvor den der har flest brikker vinder). Den er bare lidt stor. Der er 2503611964 positioner. Databasen kan deles i fire (6:0)-behøver ikke blive beregnet. (5-1) har 467999856 positioner, (4-2) har 1174279692 og (3-3) har 783806128. Man kan så dele op efter hvor mange Møller (Kings) der er for hver, men 2112 og 2211 har hver 217836864 positioner. Man kan dele yderligere op og størrelserne på enkeltstykkerne kunne godt klemmes ned. I 1990 var 8 Mb en masse hukommelse, men hver position skulle kun rumme win/lose/draw/unknown. En andet-års studerende, Brent Knight, bliver hyret som programmør. Senere slutter Paul Lu sig til og de bidrager godt til projektet. Fx viser det sig at det er supersvært at fintune evalueringsfunktionen pr automatik. Hvis det havde virket, havde det været godt, men et negativt resultat er også et resultat. Schaeffer køber en bog om Tinsley's partier og sprætter den op og OCR-skanner den. Den viser sig at have masser af fejl, men når de er rettet, er det en imponerende kilde til at se Tinsley over skulderen. Desværre for Schaeffer ser Tinsley ud til at være skræmmende god. Ud af ca 200 partier finder de 1 fejl. De arrangerer en Checkers konference i starten af juni 1990 og inviterer nogle gode spillere med i det håb at Chinook vil klare sig godt nok til at blive accepteret som almindelig turneringsspiller. Det skjulte håb er at kunne kvalificere sig til en match mod Marion Tinsley. Desværre viser Schaeffer en opstilling til Leo Levitt, som straks siger at den er uafgjort. Schaeffer bliver deprimeret, for han det var den ene fejl, de troede at have fundet i Tinsleys spil i bogen med Tinsley-partier.
Så facit er altså at Tinsley ser ud til at lave ca 0 fejl. Den gode nyhed er at de bliver inviteret til at komme med til turneringer. Indtil første turnering starter bruger de hektisk tiden på at finde fejl i programmet (inklusive en compiler fejl) og i åbningsspillet og i evalueringsfunktionen og på at trimme deres database med 6 brikker tilbage. De opfinder deres egen paging/cache algoritme og får løst problemerne med at bruge små og langsomme maskiner. Schaeffer vil gerne spille mod Marion Tinsley, der er matematiker, supervenlig og umulig at slå i Mølle og Dam. Han har trukket sig som verdensmester fordi han ikke rigtigt havde lyst til at spille mere.
Chinook kommer med til en turnering i 1990 og får lov at bruge en RS6000 fra IBM med hele 32 Mb ram. Norm og Schaeffer dukker op og bliver hilst velkommen af en venlig mand, der viser sig at være Marion Tinsley. Han er ikke med i turneringen, men de møder først Earl Pitney (som de slår 2 - 0), så Tim Laverty (1 - 0), så Richard Hallett, (1 - 0), Joe Schwartz (1 - 0), Elbert Lowder (2 - 0). Ron King (0 - 0), Earl Morrison (0 - 0). Chinook vinder Mississippi State Checkers Champignonship med 22 point mod Halletts 21. Men turneringsledelsen lader hånt om resultatet og kårer Hallett som vinder.
Senere vinder Chinook en kvalifikationsturnering (lidt heldigt) og er nu først i køen til at spille mod Tinsley. Poul Lu kommer i menneskehænder i en anden turnering med Chinook og fx lægger modspillerne mærke til svagheder i en runde og putter dem i bogen til næste runde. Av.
Schaeffer prøver at forstærke programmet ved at putte mere i åbningsbogen, hvilket er højst tiltrængt for i litteraturen er eksempler på fælder der først klapper efter så lang tid at Chinook ikke har en chance for at søge så dybt. Tiden er også ved at rinde ud. De gode Dam-spillere er oppe i årene og hvert nyt nummer af deres medlemsblad har flere nekrologer. Marion Tinsley er i en klasse helt for sig selv og Schaeffer vil frygteligt gerne spille mod ham, mens han stadig er på toppen. Faktisk foreslår Tinsley selv en demonstrationsmatch. I et af partierne finder Tinsley efterfølgende at han har en vindende position, men Chinook kan ikke se den før 50 ply ude i en søgning og det er helt på den anden side af hvad der er tid til i et turneringsparti.
Chinook spiller en match mod Don Lafferty (den næststærkeste efter Tinsley) og holdet har forberedt nogle Cooks, dvs åbninger, der ikke er beskrevet og analyseret til døde i litteraturen. Lafferty får til gengæld Chinook ud i en håbløs position, som selv Schaeffer kan se er håbløs, men hvor Chinook ikke kan se det indenfor dens søgehorisont på 19 halvtræk. Evalueringsfunktionen bliver rettet til, så brikker der i realiteten er døde ikke tæller som en positionel fordel. Vistnok.
Så kommer der et chok for teamet, for Marion Tinsley fraskriver sig titlen som verdensmester. Nogenlunde på samme tid har de ellers fået hjælp til at beregne slutspilsdatabaser på Lawrence Livermore National Laboratory. Takket være kontakter der får de gratis tid, når ingen andre bruger deres BBN TC2000 computer. At checke 4040.00 basen tager 1 dag. Det er 736281000 positioner, men trivielt parallelliserbart. Næste skridt løber ind i at disk i/o er meget langsommere end ram i/o, så det virker som om programmet bare løber ind i en mur. Lidt caching hjælper, men helt undgå disk access kan de ikke, så de kan ikke nå at beregne databasen inden den match mod Tinsley, de håber på. Jonathans kone, Steph, når dog at frembringe en familieforøgelse på normeret tid. Chinook får flak fra nogle af Checkers-samfundet, så Jonathan bruger lidt tid på at skrive en artikel om hvad de har fået ud af slutspilsdatabasen, fx et par ret svære slutspilsscenarier, hvor man kan vinde selv om traditionel visdom ville sige remis. De spiller mod Asa Long, der selv som 88-årig er blandt de bedste 5 spillere i verden. De vinder et parti med en Cook og taber et på grund af en typo i deres åbningsbog.
De udvider programmet, så det fx ved at der er forskel på remis-linier. Nogle er velkendte og alle de gode spillere kender dem, så hvis man nu vælger en mere snørklet vej til remis, er chancen større for at lokke modstanderen til at lave en fejl.
Både IBM's Deep Blue skakprogram og Chinook står lidt i stampe, for deres tidlige successer skyldtes mest at modstanderne var uforberedte. Nu bliver begge programmer taget alvorligt og fx har Chinook nu kun 3 sejre i de sidste 50 partier mod mennesker. Jonathan spiller en del partier mod et andet program Colossus og det program har en skræmmende stor åbningsbog.
Der er selvfølgelig også bugs i programmet, fx en, hvor programmet ved at det er ved at vinde, men spiller den sværeste kombination i stedet for den letteste. Lowder udnytter det til at lave en gentagelse i spillet, så i stedet for at vinde må Chinooks operatør tilbyde remis. Øv!
Undervejs beretter Johathan også om hans tålmodige kone, Stephanie, og deres datter Rebecca. Og om telefonlinier, der var upålidelige og tit gik ned. Men det lykkes at få en turnering, sponseret af Silicon Graphics, stablet på benene. En match mellem Marion Tinsley og Chinook. Den starter 17 august 1992 og bliver ret spændende. Et par småjusteringer af parametre gør en stor forskel. Men en fejl på computeren eller i programmet, måske en deadlock på printerporten driller. Status den 14 august er 12.0 - 12.0. Næste parti taber Chinook og endda på en måde, så det er tydeligt at det bare er et program. Da den opdager at den har tabt, spiller den et håbløst træk i stedet for at forsøge at trække pinen ud, så modstanderen måske snubler over sine egne ben?
28 august 1992: Tinsley 18.5 mod Chinook 17.5. Tinsley er 65 år gammel og øm over sin status som ubesejret i turneringer og matche. Næstsidste parti: Efter 5 træk printer Chinook "remis".
Så Tinsley ender med at vinde 4-2 over Chinook med 33 partier, der ender i remis.
Efterfølgende arbejder holdet på at færdigberegne 8-briks databasen. Og på at finde en fejl der er i 2230.70 databasen (kun 1, men hvorfor). 6 april 1993 er de på 70% af hele databasen.
Ideen med at remis-linier ikke er lige meget værd, bliver også forfulgt.
Den 20 juli 1993 spiller de mod Lafferty og deres database er nu 99.8% færdigberegnet. Den fylder 5.6 Gb og til matchen har de en HP 9000/720 computer, De første 9 partier ender i remis. De får uventede bank. Diskussioner efterfølgende og et tilbud fra Martin Bryant om at han får 6-briks database og de får hans åbningsbog. Det får Norm til at forlade gruppen, men uden permanent fjendskab til følge. Martin fylder hullet ud for han bliver en del af gruppen.
Jonathan tager et halvt år til Holland hos Jaap van den Herik på universitetet i Limburg i Maastricht. Her får han gode ideer til at styrke Chinook.
Vel tilbage forbereder de sig på en ny match mod Marion Tinsley. Martins åbningsbog bliver kodet til Chinook-format og efterprøvet. Dels for at finde fejl (der er ret mange) og dels for at finde cooks.
Ideen er at bruge den sidste måned inden matchen på at køre test. Så de sætter en match op med Derek Oldway og bruger en gammel version af åbningsbogen (for ikke at afsløre nogle af deres cooks).
Derek Oldway dør i juli 1994 og det amerikanske mesterskab ender med Marion Tinsley, Chinook og Lafferty på delt førsteplads og reglerne giver så Lafferty førstepladsen. I august 1994 er man klar til en ny match mellem Tinsley og Chinook. De første seks partier er remis og Chinook ser ikke ud til at være i problemer, men Tinsley har det ikke så godt. Han spørger Jonathan om det er muligt at lade Don Lafferty tage over for ham. En tur til lægen og et røntgenbillede viser en udvækst på hans bugspytkirtel. Tinsley trækker sig og Chinook bliver erklæret verdensmester. Og sætter titlen på spil mod Don Lafferty med det samme, men det bliver modtaget dårligt. Matchen resulterer i 20 remis og så beholder Chinook titlen. Udvæksten er kræft, så Marion fortsætter til kemoterapi og Jonathan kan tage hjem. Det har været to dårlige uger. Og oveni kommer et slagsmål med ACF i slutningen af 1994 for de anerkender ikke at Chinook har vundet mesterskabet. 7 januar 1995 spiller de mon Don Lafferty. De bruger Ken Thompsons 8-cpu SGI Challenge (der kører Plan 9). Chinook kører på Tinsleys strategi - play safe to avoid a loss and wait for a cook. Og vinder 1-0 ud af 32 partier. ACF er flere måneder om at godkende resultatet og har ikke skrevet om det i ACF bulletin. Marion Tinsley dør i april 1995. I marts 1996 spiller Ron King og Don Lafferty mod hinanden og det ender uafgjort, så King beholder titlen.
Alle de gamle spillere er ved at dø ud, så gad vide hvad fremtiden er for turnerings- og mesterskabsspil?

Schaeffer er ca 4 år ældre end mig, så jeg kan nikke genkendende til mange beskrivelser af datalogi og programmører fra den tid. Der er sjove overvejelser når computerprogrammet skal spille mod et menneske på tid. Tak til Rob Lake, Norm Treloar, Joe Culberson, Duane Szafron og Brent Knight for ikke at tale om Jonathans kone og datter, Stephanie og Rebecca.
Show Less

Publication

New York : Springer, c1997.

Description

"Playing chess is like looking out over a limitless ocean; playing checkers is like looking into a bottomless well." Marion Tinsley, World checkers champion This extraordinary book tells the story of the creation of the world champion checkers computer program, Chinook. From its beginnings in 1988, Chinook became a worthy opponent to the world champion by 1990 and by 1992 had defeated all the world's top human players. In this fascinating account, Jonathan Schaeffer, the originator and leader of the Chinook team, provides an engrossing story of failures and successes. He describes the human story behind the program and his own feelings in learning from mistakes and technical problems in a continuous effort to improve Chinook's performance. Over the ten year period beginning in 1988, we follow the development of Chinook from an innocent question asked over lunch through to the final match against the then world champion, Marion Tinsley. As the story unfolds, readers are introduced to the rules of checkers and the basics of computer game programs, as well as to the key figures of the story. As a result, all those interested in computing and games will enjoy this book. " Schaeffer's personal involvement in the Chinook project, along with his engaging and open story-telling makes the book surprisingly gripping." A.K. Dewdney… (more)

Language

Original language

English

Physical description

xiv, 496 p.; 24.2 cm

ISBN

0387949305 / 9780387949307

Local notes

Omslag: Indbundet
Indskannet omslag - N650U - 150 dpi
Side 88: I wish I could write as fast and as well as he can. Of course, I wish I had a Nobel Prize and a Turing Award too.
Side 101: En fin liste af citater med nonsens som fx den her fra 1978: "Although computers had long since been unbeatable at such basic games as checkers ..."
Side 273: COKO III versus Genie skakprogram bøf.
Side 379: Despite all the hype about the Internet, it can be an exercise in hypertension.
Side 391: Dum programmeringsbøf.

Pages

xiv; 496

Library's rating

Rating

(4 ratings; 3.1)

DDC/MDS

794.2/0285
Page: 0.2664 seconds