|
De fleste kender spillet Kalaha, som spilles i de fleste børnehaver, men også kan spilles seriøst af voksne. Kalaha er et såkaldt brætspil med fuld information. Det vil sige, at der ikke er skjult information, som det ofte er tilfældet med f.eks. kortspil, hvor man typisk ikke kender modstanderens kort.
Brætspil med fuld information kan være yderst simple som f.eks. kryds & bolle og 4-på-stribe eller komplicerede som f.eks. skak eller go. For sådanne spil findes der altid enten en vindende eller en ikke-tabende (uafgjort) strategi. De fleste ved nok, hvordan man undgår at tabe i det helt simple kryds & bolle spil. For spil så komplicerede som skak ved man simpelt hen ikke, om der er en vindende eller en ikke-tabende strategi - og om det er for hvid eller sort.
Indtil for nylig vidste man heller ikke dette om Kalaha, selv om der tidligere er blevet gjort forsøg på at få det afklaret. Her i foråret har datalogistuderende Anders Keller Carstensen dog løst problemet under vejledning af professor Kim Skak Larsen fra Institut for Matematik og Datalogi på Syddansk Universitet. Resultatet er, at der altid findes en måde, den startende spiller kan vinde på - uanset hvilke træk den anden spiller beslutter at foretage.
For at løse problemet må man overskue et overordenligt stort antal mulige træk - op imod 1 kvintilliard, som skrives som et 1-tal efterfulgt af 33 nuller. Det er så stort et tal, at det har forhindret andre i at gennemanalysere spillet. En større samling avancerede optimeringsteknikker har måttet bringes i anvendelse i den helt rigtige form og sammenhæng, herunder pladsreducerende teknikker for at kunne lagre delløsninger, åbningsbog og slutspilsteknikker fra spilverdenen og parallellisme i form af udnyttelse af alle de CPU'er, en moderne computer har.
Anders' bærbare er nu en uovervindelig Kalaha-spiller - når den selv får lov til at starte!
Prøv selv at spille mod Anders Keller Carstensens computer her.
---------------------------------------------------------------------------------------------------------
Jyllands-Postens netavis, http://jp.dk/, har den 3. juni publiceret en artikel om emnet, "Studerende løser gåden om Kalaha", som i de første timer på udgivelsesdagen lå i top5 over de mest læste artikler.
Artikler findes også på:
www.fyens.dk, 3. juni, "Fynsk studerende løser Kalaha-gåden".
www.tv2fyn.dk, 3. juni, "SDU-studerende knuser Kalaha-kode".
|