Denne gang fik Charlie faktisk brugt noget matematik: Kombinatorisk spilteori, en variation over Dijkstras korteste vej algoritme, noget om en laserlæser (mystisk ord på dansk…), som opfangede signaler fra tasterne på et computertastatur. Og så skulle Charlie og Amita have holdt forelæsning om den multivariate hypergeometriske fordeling.
Kombinatorisk spilteori
Spilteori har vi set på flere gange på bloggen – I kan bruge søgefeltet, hvis I vil se mere. Denne gang var det kombinatorisk spilteori. Det drejer sig om to-personers spil, der er perfekt information: Begge spillere kan se, hvad den anden gør, og kender konsekvenserne af egne handlinger. (I modsætning til fangernes dilemma, hvor pointen er, at man ikke ved, hvad den anden gør – eller med en anden formulering: Begge skal bestemme sig samtidig, om de vil tilstå eller holde mund).
Man skiftes til at “trække”.
Mange sædvanlige spil er hører under denne overordnede ramme: Skak, dam, kryds og bolle, Go, Mølle,… Men ikke kortspil, hvor man sædvanligvis ikke har fuld information.
Taber er enten den, der ikke kan flytte mere. Eller den, der flytter det sidste mulige flyt.
Eksempel: Hex er et spil for to som ovenfor, og det er en rigtig god historie, så den får I. Det blev opfundet af Piet Hein i 1942, og det indeholder mange interessante matematisk-datalogiske problemstillinger. Piet Hein sagde selv, at han fik ideen, da han overvejede 4-farveproblemet. Thomas Maarup, matematikstuderende i Odense, skrev speciale om Hex og dets historie i 2005. Det skrev Information en artikel om. Piet Hein skrev en del om spillet i Politiken, hvor det gik under navnet Polygon, mens han selv kaldte det Con-Tac-Tix. Politikens artikler involverede læserne i at finde gode strategier, gode modoffensiver til givne strategier etc. og man kan se reklamer for spillet, herunder en, der forestiller nogle Hex-spillere i beskyttelsesrum (det var jo under 2.Verdenskrig), som ikke vil komme op, før de har spillet færdig.
I 1949 blev det genopfundet af John Nash (ham, der er portrætteret i filmen “A beautiful Mind”. Han fik Nobelprisen for spilteori.) De studerende på Princeton University kaldte det Nash eller John (en myte er, at det hed John, fordi de spillede det på mosaikkerne på badeværelsesgulvet, og John er slang for toilet… Men det er nu en myte ifølge bogen A beautiful Mind.) Spillet blev lavet kommercielt af et amerikansk firma, som døbte det Hex.
I Hex har man et bræt inddelt i sekskantede (hexagonale) felter. To spillere sætter hhv. sorte og hvide brikker (eller røde og blå). Målet er for begge at danne en sammenhængende sti på tværs af brættet (og forhindre den anden i det). På billedet kan man se, at stierne løber “på tværs” af hinanden.
Hex er et godt spil, idet det ikke kan ende uafgjort: Hvis en spiller er forhindret i at lave en sammenhængende sti på tværs, er det fordi den anden har lavet en.
Vindende strategi
En strategi er en opskrift, som en af spillerne kan bruge til i hvert eneste træk at analysere det, der hidtil er sket, til at sætte en ny brik.
Strategien er vindende, hvis …. jeps, hvis den spiller, der bruger strategien, altid vinder.
Et spil, der
1) altid slutter efter endeligt mange træk med en vinder
2) Har perfekt information
er “determined”, i.e., der er en vindende strategi for en af spillerne. Argument:
Spiller I spiller for ikke at tabe: I hvert træk spiller I for at sikre, at spiller II ikke har en vindende strategi efter spiller I’s træk. Hvis ikke Spiller I kan gøre det, må spiller II have en vindende strategi. Omvendt, hvis spiller I kan det, vil spiller II ikke vinde, og det vil spiller I altså, eftersom spillet er slut efter et endeligt antal træk. Så det var en vindende strategi…
Der er altid en vindende strategi i Hex for den, der begynder spillet, men man ved ikke, hvad den er – kun, at den eksisterer. Beviset er et såkaldt strategirøveri. Først viser man, at en af spillerne har en vindende strategi (det har vi gjort); og derefter, at hvis det er for spiller nummer 2, kan første spiller stjæle strategien ved at lade somom, den første brik bare blev sat tilfældigt. Det virker, fordi det ikke kan være en ulempe at sætte en ekstra brik.
Man kan nu undre sig over, at man ikke bare kan regne alle tilfælde igennem og bestemme en vindende strategi. Det kan man for små spil (med lille bræt). Men dettager rigtig lang tid, og bruger rigtig meget plads på en computer at lave sådan en analyse.
Man forestiller sig en algoritme, der kan svare ja eller nej til, om en placering af en brik er et led i en vindende strategi. Pladsen, der skal bruges til analysen, vokser med sidelængden, n, af brættet. For et 10×10 bræt, er der 10^39 mulige positioner for brikkerne. Så det fylder meget. Faktisk er spørgsmålet om Hex PSPACE fuldstændigt – den plads, en algoritme som beskrevet her, kræver, vokser som et polynomium i n. Og alle andre PSPACE problemer kan oversættes til Hex, så en algoritme for Hex giver en for alle de andre. PSPACE problemer er, tror man i hvert fald, værre end NP problemer. NP-problemer er problemer, hvor man kan ” finde en løsning” til et ja/nej spørgsmål. PSPACE handler om at checke, om en løsning virker fremover, uanset, hvad den anden spiller gør. Og det ser jo umiddelbart værre ud. Men man ved det ikke.
Læs mere om matematikken f.eks. på Mathworld
Eller du kan jo også bare spille det – eksempelvis online på boardspace.net. Der findes også apps, så man kan spille på sin smartphone – se f.eks. de eksterne links under Wikipedia.