Spelteori

Spelteori täcker in samtliga problem som handlar om spel i någon form. Den typ av spel jag tänkt ta upp är de som spelas av två spelare och som är "öppna", dvs all information om spelet finns tillgänglig för båda spelarna. Exempel på välkända sådana spel är schack och Othello medan ett exempel i den andra kategorin är bridge (de flesta kortspel är av den kategorin eftersom man normalt sett inte ser vad motståndaren har för kort).

De typer av spelteoriuppgifter som förekommer i programmeringstävlingar är (nästan) alla av typen att man ska lösa spelet helt. Större spel som schack kommer aldrig gå att "lösa", dvs spela perfekt, från drag 1 eftersom antalet ställningar är så otroligt många. Istället använder sig schackdatorer av en evalueringsfunktion som efter vissa kriterier bedömer en ställning så gått den kan. Denna evalueringsfunktion är förstås inte exakt och sådana brukar därför aldrig förekomma i objektiva programmeringstävlingar.

Nedan följer några begrepp jag kommer använda mig av i texten:

bräde - spelplanen för spelet (behöver inte vara ett 2D bräde, utan kan vara något abstrakt också).
ställning - komplett information om hur läget är i spelet (har inget att göra med ställningen i en fotbollsmatch t ex :) )
pjäser - de föremål som man flyttar omkring eller placerar ut på brädet.
P1, P2 - P1 är spelare ett (den som börjar spelet) och P2 är spelare två.
vid draget - den spelare som ska göra nästa drag sägs vara "vid draget".
parti - finare ord att använda än "match" när det gäller spel
evaluera - bedöma en ställning (normalt detsamma som att avgöra vilken spelare som vinner om ställningen uppkommer)
oavgjort - om en ställning evalueras till oavgjort så kan varken P1 eller P2 vinna spelet om den andra spelaren spelar perfekt

Ställningen består av vart pjäserna står på brädet samt vem som är vid draget. Denna information är nästan alltid tillräcklig, men det finns undantag. I schack t ex får man inte göra rockad om kungen och tornet har flyttat på sig någon gång under partiet. Om en nytillkommen åskådare tittar på vart pjäserna står på brädet så kan han omöjligen avgöra om så har skett om kungen och tornet just nu står på deras ursprungsplatser - de kan ju ha flyttat till en annan ruta och sedan gått tillbaka. Alltså består en schackställning av både vem som är vid drag, vart pjäserna står, samt om kungen/tornen för vardera sida har flyttats. Dessutom finns det mer "dold" information i en schackställning som jag inte tänker nämna här.

Men som sagt, det räcker nästan alltid med att hålla reda på 1) vem som är vid draget, och 2) vart pjäserna står på brädet för att veta ställningen i spelet.

En ofta otroligt viktig sak är att kunna numrera alla giltiga ställningar (dvs sådana som kan uppkomma i spelet) från 0 och uppåt, eftersom man gärna vill kunna skapa en vektor och lagra information om alla ställningar. Det är inte nödvändigt att numrera ställningarna kontinuerligt, däremot är det förstås viktigt att två olika ställningar inte numreras med samma tal. Några exempel längre ner i texten visar hur man kan göra detta, för tillfället räcker det med att vi antar att en ställningen kan beskrivas som ett icke-negativt heltal. Vi antar också att antalet ställningar är ändligt (det enda spel jag kan komma på just nu som är oändligt är luffarschack; men det har ändå forcerad vinst för P1).

ICKE-UPPREPANDE SPEL

Man kan dela in spel i två kategorier, spel där samma ställning kan uppkomma två gånger i ett parti och spel där det inte kan inträffa. Vi börjar med den senare typen av spel eftersom det är lättare. Om samma ställningen inte kan uppkomma två gånger som kommer spelet onekligen någon gång att ta slut eftersom vi har ett ändligt antal möjliga ställningar (vilket inte nödvändigtvis innebär att antingen P1 eller P2 har vunnit; Tic-Tac-Toe tar t ex slut efter 9 drag och slutar normalt sätt oavgjort). Den absolut enklaste metoden att lösa ett spel av den typen är genom rekursion, eftersom vi vet att rekursionen någon gång kommer att terminera. Om antalet ställningar inte är alltför många så räcker det med att för varje ställning avgöra vem som vinner i ställningen vid perfekt spel, eller om ingen kan vinna (en del spel kan dock inte sluta oavgjort). Det är ofta naturligt att bedöma en ställning som +1 om ställningen är sådan att P1 vinner, -1 om P2 vinner och 0 om ingen vinner (allt detta vid perfekt spel från båda sidor förstås; detta kommer att vara underförstått hädanefter). Det
skulle kunna se ut så här (pseudokod):

int solve(int turn, int position)
{
if game_over(turn,position)
return who_won(turn,position)
generate_moves(turn,position);
if (turn==P1) best=-infinity else best=infinity
loop through all valid moves
perform_move
int val=solve(next_player(turn),new_position)
if (turn==P1 && val>best) best=val
if (turn==P2 && val<best) best=val
undo_move
end loop
return best
}

Notera att variablerna turn och position tillsammans utgör ställningen, men det är ofta praktiskt att dela upp det i två separata variabler.

När man sedan är vid drag räcker det då med att loopa igenom alla möjliga drag, kolla vilken ställning som uppkommer efter draget, titta i evalueringstabellen, och välja det drag som är bäst. Det kan också vara nödvändigt att veta hur långt det är till vinsten. I så fall bör man använda ett annat system än -1,0,+1 systemet. Man kan tänka sig att +100 motsvarar en slutställning (dvs game_over returnerar true) där P1 har vunnit, +99 en ställning där P1 vinner i ett drag, -98 en ställning där P2 vinner i två drag osv. Anledningen till denna numrering är att P1 då alltid försöker maximera värdet medan P2 alltid försöker minimera det (som synes i koden ovan). De exakta ändringarna i koden ovan för att lägga till "antal drag till vinst" lämnar jag som en övning...

Om man direkt skulle implementera pseudokoden ovan skulle det nog inte gå så bra; antalet rekursiva anrop skulle bli väldigt många även för rätt små spel.
Lösningen på detta heter, och det hoppas jag ni redan gissat, dynamisk programmering (DP). Jag kommer att gå in mer på DP i en senare del av kursen eftersom det är så otroligt viktigt att kunna behärska. I det här fallet är det dock väldigt lätt; vi har en funktion som tar två heltalsparametrar och använder sig inte av några globala variabler (dvs, funktionen har inga sidoeffekter, det är en strikt matematisk funktion) - sådana funktioner är perfekta att tillämpa DP på. När värdet på funktionen för en viss parameteruppsättning har beräknats sparar man det i en tabell, och i början av funktionen kollar man först i tabellen om det finns något värde där:

int solve(int turn, int position)
{
if (precalced[turn][position]!=UNKNOWN)
return precalced[turn][position]
if game_over(turn,position)
best=who_won(turn,position)
else
generate_moves(turn,position);
if (turn==P1) best=-infinity else best=infinity
loop through all valid moves
perform_move
int val=solve(next_player(turn),new_position)
if (turn==P1 && val>best) best=val
if (turn==P2 && val<best) best=val
undo_move
end loop
endif
precalced[turn][position]=best
return best
}

DP är det främsta (och egentligen enda) skälet till att vi numrerar ställningarna 0,1,2,... - om parametern position hade varit av en godtycklig typ så hade det inte gått (det är dock möjligt att skriva koden på ett lite annat sätt som vi ska se senare). Även fast numreringen inte behöver vara kontinuerlig så är det förstås viktig att det högsta värdet i numreringen inte är alltför stort. Börjar det bli mycket större än 1 million är man nog på fel spår.

Notera här också värdet UNKNOWN - lämpligen definieras det till ett värde som aldrig annars kan hamna i precalced tabellen. Om partiet kan sluta oavgjort kan man INTE sätta värdet UNKNOWN till det naturliga talet 0 t ex eftersom det används för att beskriva ställningar som har evaluerats till oavgjort.


Nu till ett konkret exempel på ett spel, "Game of Euler", som kan spelas på http://home.swipnet.se/euler/

(läs även gärna historien om spelet på samma sida, den är intressant - om den är sann är en annan sak...) Som synes har man ett bräde på 4x4 rutor där man placerar ut spikar av olika längd. Antingen kan man placera ut dem från kanten (och då har spikarna längden 1, 2 eller 3) eller så kan man placera en spik med längd 1 vart som helst på brädet. Spelet går ut på att inte placera ut den sista spiken innan brädet blir fullt. Eftersom man hela tiden placerar ut nya spikar så kommer samma ställningen inte uppkomma två gånger och spelet kommer ta slut någon gång (högst 16 drag).

Det första man bör göra är att ta reda på hur många olika ställningar som kan uppkomma. Vid en första anblick kan det tyckas som jättemånga, eftersom P1 har 48 olika drag vid startställningen, och P2 har sedan nästan lika många drag osv. MEN det spelar ju ingen som helst roll vilken spelare som placerar ut vilken typ av spik var - det ENDA som har betydelse är vilka rutor som är lediga och vilka som inte är det. Eftersom det finns 16 rutor, och en ruta antingen är ledig eller inte, har vi exakt 2^16 = 65536 olika ställningar, vilket är väldigt överkomligt. Notera för övrigt att jag här inte tar hänsyn till vem som är vid draget - man skulle kanske tycka att det finns 2*65536 ställningar. Detta är förvisso sant, men i just det här spelet har man inga "egna" pjäser - alla pjäser är neutrala. Så om en viss "pjäsutplacering" uppkommit (dvs parametern position i koden ovan) så är resultatet detsamma oavsett vem som är vid drag - om P1 är vid drag och vinner, så vinner förstås också P2 om han är vid drag.

Nästa steg är numrering av ställningarna. I det här spelet är det nästan trivialt, om man är van att handskas med bitmaskar. Istället för att lagra ställningen i en 4x4 matris så lagrar vi den som ett heltal på 16 bitar. De 16 bitarna i heltalet får motsvara en ruta var; lämpligen är bit 0-3 övre raden, bit 4-7 rad 2 osv. När vi sedan genererar dragen kan man direkt operera på heltalet! Tycker man det är jobbigt kan man förstås konvertera om heltalet till en 4x4 array, ta fram alla drag, och sedan konverteratillbaka till ett nytt heltal.

UPPGIFT 1: Implementera spelet Game of Euler. Man ska kunna spela interaktivt mot datorn, och datorn ska förstås spela perfekt. Man ska kunna välja om man vill börja eller inte. Hur inmatningen av drag ska gå till får ni välja själv, det räcker mer än väl att göra ett enkelt kommandoradsprogram. Ert program behöver inte (men det är trevligt) hitta den snabbaste vinsten. Vinner erat program mot programmet på Game of Euler sidan på svåraste svårighetsgraden (16) så har ni klarat uppgiften.

Tips: Den som börjar spelet förlorar, så för att slå datorn på level 16 måste ni ändra om så att datorn börjar... Dessutom, och detta gäller för samtliga spel där man tillämpat DP, behöver man förstås bara evaluera alla ställningar en gång, innan partiet börjar. Sedan är det bara att i varje drag kolla upp i tabellen vilket drag som är det bästa.

UPPGIFT 2: Ett klassiskt spel (som jag glömt namnet på) går ut på att två spelarna turas om att dra horisontella och vertikala streck av längd ett mellan punkter på ett 3x3 rutnät (en miniversion av spelet egentligen). När en spelare dragit ett streck så att en ruta i rutnätet har streck på alla fyra sidor, får den spelaren en poäng. Om en spelare får poäng går inte turen över, utan han måste dra ett streck till. Kan spelaren då omringa ytterligare en ruta får han ytterligare poäng, och fortsätter osv. Spelet är slut när alla 9 rutor har blivit omringade. Notera att man kan få två poäng med ett enda streck - då gäller samma regler som om man hade fått en poäng. Se figur nedan.

*---*   *   *
|
|
*---*---*   *
| 1 |
|   |
*---*---*   *
|   | 2 |
|   |   |
*   *---*---*

I figuren ovan finns det 9 rutor, varav två stycken har blivit inringade. Siffran i dessa rutor anger vilken spelare som fick poäng för rutan. Den spelare som är vid drag kan dra ett streck så att han får rutan till vänster om den ruta som är markerad med en 2:a. Efter att han dragit det strecket är det han på tur igen, och kan då få mittrutan också.

Spelet pågår tills alla rutor blivit inringade, dvs tills alla 24 streck har dragits. Här spelar det återigen ingen roll vem som är vid draget, strecken är neutrala. Det finns alltså 2^24 ställningar, ca 16,7 miljoner (så stora problem dyker normalt sätt inte upp i tävlingar, men detta var ett så pass trevligt problem så jag tog med det ändå). Här måste man se till att maximera antalet rutor man kan få, eftersom slutställningen i sig inte säger vem som vunnit spelet (det går förvisso att lägga till vem som har fått poäng för varje ruta i ställningen, men då skulle antalet ställningar bli 2^(24+9) vilket är alldeles för mycket). Alltså, från en given ställning, hitta det drag som maximerar antalet poäng man själv kan få (eller maximera differensen mellan den egna poängen och motståndarens, det blir samma sak) - detta leder till optimalt spel. Återigen, uppgiften går ut på att gör ett
program som spelar spelet optimalt.

Tips: Det tar ett tag att evaluera alla ställningar, drygt 20 sek på min AMD 1200 (med optimering påslagen i GCC). Vid optimalt spel vinner spelare 2 med 6-3.

UPPGIFT 3: Följande spel spelas av två personer: Först bestäms n st tal, och dessa n tal skrivs upp i en lång rad (0<n<=1000, n är jämnt, talen är i intervallet [0,10000] och summan av alla talen är udda). Därefter turas spelarna om att välja antingen talet som är längst till vänster i raden eller talet som är längst till höger. Det valda talet läggs till spelarens poäng, och
tas bort från raden. Målet med spelet är att maximera den egna poängen.

Skriv ett program som läser in talet n och sedan de n talen (lämpligen från stdin) och sedan räknar ut hur mycket P1 kommer att vinna med, om både P1 och P2 spelar optimalt (P1 vinner nämligen alltid; om summan av tal 1, 3, 5, ..., n-1 är större än summan av talen 2, 4, 6, ..., n, tar P1 i sitt första drag tal 1. Därefter måste P2 ta antingen tal 2 eller tal n, vilket i sin tur leder till att P1 i nästa drag tar tal 3 eller n-1 osv - detta leder dock inte till maximerad vinst!)

Denna uppgift är en variant på en gammal IOI uppgift. Här är spelplanen mer abstrakt än i tidigare uppgifter, men det är samma princip som gäller.


NUMRERING AV STÄLLNINGAR

Innan vi går in på spel där samma ställning kan upprepa sig i ett parti tänkte jag gå in lite mer på hur man konverterar en ställning till ett heltal. I uppgifterna ovan var det väldigt enkelt. Det kan dock vara betydligt krångligare. Om ni inte redan gjort det, läs igenom min uppgift i årets BOI tävling, L-Game (http://www.acc.umu.se/~yarin/lgame/LGame.html). I detta problem är det betydligt svårare att numrera ställningarna på ett ffektiv sätt än i uppgifterna ovan. Återigen finns det 16 rutor, men varje ruta kan ha fyra olika lägen: tom, neutral bit, P1's L eller P2's L. Informationen för varje ruta skulle kunna lagras i 2 bitar, vilket ger totalt 32 bitar - på tok för mycket! Den metod min lösning använder sig av är att inse att en L-bit kan ha 48 olika placeringar på 4x4 brädet. De två L-bitarna ger tillsammans upphov till 48x48 kombinationer (notera att en stor del av dessa är ogiltiga då L-bitarna överlappar varandra, men detta är som jag sagt tidigare inget problem). De återstående två neutrala bitarna kan lagras på lite olika sätt. Enklast är att helt enkelt lagra vilken av de 16 rutorna de båda ligger på. Dessutom måste man i det här spelet lagra vilken spelare som är vid draget eftersom alla bitar inte är neutrala. Allt detta ger totalt 48*48*16*16*2 = 1179648 ställningar (i min lösning gjorde jag det dock lite mer kompakt, jag lagrade rutorna för de neutrala bitarna "relativt" till de lediga rutorna, det totala antalet ställningar blir då 294912).

Det finns dock mera generella metoder att använda om man utnyttjar STL i C++. Man kan t ex använda sig av map för att konvertera en ställning av godtycklig typ till ett heltal. Detta har dock en liten nackdel, och det är att komplexiteten för själva konverteringen är O(log n) istället för som tidigare O(1) (konstant tidsfaktor). Jag har aldrig använt denna metod i praktiken och kan inte svara på om det är praktiskt möjligt att använda den i t ex L-Game för att numrera ställningar, men det verkar sannolikt att det är tillräckligt snabbt ändå. Annars finns det möjlighet att använda sig av hash_map i STL som jag vet väldigt lite om, men det borde vara mycket snabbare än map.

Använder man sig av map blir dock konverteringen från ställningen till heltal "enkelriktad" - det går inte på något snabbt sätt att konvertera tillbaka till ställningen från heltalet, vilket är nödvändigt i pseudokoden ovan. Detta är dock inte helt nödvändigt egentligen; om man istället för att skicka heltal som parametrar skickar ställningen i dess "riktiga" form (t ex som en struct) och konverterar om ställningen till ett heltal när man behöver detta så slipper man tillbakakonverteringen. Denna metod är kanske lättare att använda, men den kan ha en liten nackdel: det är ofta effektivare att skicka ett heltal än en mer komplex datastruktur. Tycke och smak får väl avgöra vilken metod man föredrar.

Det finns ett trick för att få ner antalet ställningar i ett spel, och det är att utnyttja sig av symmetriska ställningar. Ta t ex Game of Euler - om man skulle rotera en ställning eller spegelvända den skulle givetvis inte evalueringen av ställningen påverkas. Detta gör att flera ställningar som man konverterar till olika tal egentligen är samma ställning. I Game of Euler kan man rotera en ställning 0, 90, 180 eller 270 grader samt spegelvända alla dessa rotationer - detta ger upphov till 8 stycken symmetrier. Dock är antalet unika ställningar, efter att ha utnyttjat symmetrierna, inte (2^16)/8 ty vissa ställningar förändras inte om man roterar/spegelvänder dem; t ex ett tomt bräde ser likadant ut efter att man roterat eller spegelvänt det. I Game of Euler är det dock mer besvär än vad det är mödan värt att utnyttja symmetrin eftersom antalet ställningar ändå är så få, men i spel som L-Game (som har lika många symmetrier) kan det vara skillnad mellan Time Limit Exceeded (eller Out of Memory) och Accepted (min L-Game lösning utnyttjar dock _inte_ symmetrierna)!


UPPREPANDE SPEL

Så har då turen kommit till den andra kategorin spel, sådana där samma ställningen i spelet kan uppkomma flera gånger. Varför skiljer sig den här typen av spel ifrån de vi tittat på tidigare? Antag att vi gör en rekursiv lösning som ovan. Det kommer förstås inte fungera så bra, rekursionen kommer aldrig att terminera när man hamnar i en ställningsloop! Tillägget av DP enligt modellen ovan hjälper inte eftersom vi skriver i tabellen i slutet av den rekursiva funktionen. Men skulle man inte kunna detektera när rekursionen loopar och avbryta när det inträffar? Antag att de rekursiva anropen görs i följande kedja, där varje tal motsvarar ställningen som skickas som parameter (notera att i pseudokoden ovan är, som tidigare sagts, detta tal uppdelat i två heltal, av praktiskt skäl):
0 -> 5 -> 76 -> 12 -> 9 -> 95 -> 76

Vi har funnit en ställningsloop, 76 -> 12 -> 9 -> 95 -> 76. Att upptäckta den är inte svårt, det är bara att ha ytterligare en tabell över alla ställningar (eller använda sig av samma tabell som DP:n gör, det är också möjligt) som markerar för varje rekursivt anrop vilka ställningar som ligger på stacken och är "under beräkning".

Det stora, och som det visar sig, olösliga problemet är: vad ska man returnera när man upptäcker en loop? Vi vet ju inte evalueringen av ställningen 76, så vilket värde vi än returnerar kommer det troligen att vara felaktigt. Det går inte heller returnera något specialvärde som säger år föregående ställning (95) att ignorera värdet. Det kan t ex mycket väl vara så att ställningen 76 är en vinnande ställning för P1 men där det vinnande draget _inte_ är det som utforskas just nu (ställning 12). Om ställning 95 skulle ignorera utvärderingen av ställning 76 (eftersom den saknas), så kommer programmet kanske felaktigt tro att ställning 95 inte är vinnande för P1, och då blir det fel hela vägen.

En, mindre bra, lösning som faktiskt fungerar i teorin är att strunta i utvärderingen av ställning 76, så att ställning 95 kan få fel resultat. Om vi struntar att spara detta felaktiga värde i DP tabellen, och istället bara fortsätta ända tills vi har gått igenom hela rekursionen och åter är i ställning 0 - först då skriver vi in resultatet i tabellen. Dvs, resultatet för ställning 0 - vi har fortfarande ingen aning om resultatet för de andra ställningarna... detta är förstås en _oerhört_ dålig metod, komplexiteten blir
exponentiell, minst.

Det stora problemet ovan är att vi inte kan evaluera en ställning förrän samtliga ställningar man kan nå från den har blivit evaluerade först. Men vilka ställningar ska vi börja evaluera då? Det finns bara en typ av ställningar vi direkt vet evalueringen på, och det är alla slutställningar. Vilket leder till idén att vi evaluerar hela spelet "baklänges", dvs vi börjar med slutställningarna, sedan alla ställningar ett drag innan dem, osv. Detta kallas "retrograde analyze".

Det vi måste göra är att avgöra i vilken ordning ställningarna ska evalueras. Detta kan göras genom en variant av topologisk sortering: vi bygger upp en riktad graf där varje hörn i grafen är en ställning och varje kant ett drag från en ställning till en annan. En topologisk sortering är ett sätt att finna en sekvens av hörn i grafen, så att det första hörnet i sekvensen inte har några utgående kanter (dvs i vårt fall så är den en slutställning i spelet), och att varje efterföljande hörn endast har utgående kanter till hörn som ligger före i sekvensen. Man kan se det som att vi plockar bort hörnen i grafen i den ordning de kommer i den topologiska sorteringen, och varje bortplock av
ett hörn medför att alla kanter till det hörnet försvinner - hörnet som plockas bort kommer då aldrig att ha några utkanter.

Nu är det inte riktigt så enkelt. Om grafen innehåller cykler (och det vet vi ju att den gör eftersom de spel vi tittar på nu kan upprepa sig) så kan dessa noder omöjligt komma med i den topologiska sorteringen - en komplett topologisk sortering existerar bara i acykliska grafer (grafer utan cykler). Men bara för att ett hörn finns i en cykel betyder ju inte att ställningen som hörnet representerar skulle leda till oavgjort resultat vid perfekt spel, så vad har vi missat? Antag att ställning A har evaluerats som vinnande för P1, att ställning B inte har evaluerats än och ligger i en cykel i grafen, och att ställning C inte heller har evaluerats. I ställning C är det P1 vid drag, och C har exakt två utgående kanter, till A och B (dvs P1 kan göra två drag i ställningen, dessa skulle leda till att ställningen i A respektive B uppnås). Med vanlig topologisk sorteringen skulle ställning C aldrig evalueras eftersom B aldrig kommer att göra det. Men det behövs ju inte! Vi har redan evaluerat ställning A som vunnen för P1 - det är ointressant vad B kommer att evalueras till, ställning C är vunnen för P1 ändå eftersom han givetvis väljer att göra draget som för honom till ställning A.

Antag nu istället att ställning A och B är som förut, och C också bortsett från att det är P2 vid draget istället. Nu är situationen annorlunda - P2 kommer givetvis inte frivilligt att spela det drag som för till ställning A eftersom han förlorar då. Han kommer istället att välja B, som vi inte vet något om, och således vet vi inte något om C heller. Men om nu även B skulle, så småningom, evalueras till vinst för P1, då är det sämre för P2; vilket drag P2 än gör vid C kommer han att förlora. Alltså har vi evaluerat att även ställning C är vunnen för P1 fastän det är P2 som är vid draget. Vi har kommit fram till följande:

* Om det finns en ställning A så att den som är vid draget kan göra ett
drag som för honom till ställning B som är vunnen för samma spelare, då
är även A vunnen för den spelaren.

* Om det finns en ställning A så att oavsett vilket drag spelaren vid
draget gör för honom till en ställning där han förlorar, då är ställning
A förlorad för den spelaren.

Detta leder fram till följande enkla algoritm (pseudokod):

set all elements in eval to UNKNOWN
loop through all positions
if (game_over(turn,position))
eval[turn][position]=who_won(turn,position)
end loop
do
loop through all positions
losing=true
loop through all moves in position
if (eval[new_turn][new_position]==P1 && turn==P1)
eval[turn][position]=P1
if (eval[new_turn][new_position]==P2 && turn==P2)
eval[turn][position]=P2
if (eval[new_turn][new_position]!=P2 && turn==P1) losing=false
if (eval[new_turn][new_position]!=P1 && turn==P2) losing=false
end loop
if (losing)
eval[turn][position]=not(turn)
end loop
while eval table keeps updating

(jag har här använt mig av P1 och P2 i eval tabellen istället för +1 och -1 för tydlighetens skull)

För det första, algoritmen ovan är inte effektiv. Den yttre loopen kan i värsta fall loopa lika många gånger som antalet ställningar i spelet, så komplexiteten är O(n*(n+m)) där n är antalet ställningar och m antalet drag (kanter i grafen). Men i praktiken skulle det kunna fungera, beroende på spelet: antalet gånger den yttre loopen loopas är faktiskt lika många som den längsta forcerade vinsten i spelet, vilket inte behöver vara speciellt många drag även fast antalet ställningar är väldigt stort.

För det andra, kommer alla ställningar att evalueras om man kör algoritmen ovan? Svaret är: alla ställningar där antingen P1 eller P2 vinner kommer att ha blivit evaluerade. Alltså, om en ställningen inte har blivit evaluerad (dvs fortfarande är UNKNOWN), så är denna ställning oavgjord! Jag tänker inte bevisa att så är fallet utan hoppas att ni antingen kan se det intuitivt eller tror på mitt ord ;-)

Nästa steg är att förbättra algoritmen ovan, och det kan vi göra någorlunda enkelt. Som tidigare konstaterats så kommer de första ställningarna som evalueras vara slutställningarna, därefter ställningar som är kopplade till dem osv. Mer exakt, när kan en ställning evalueras? Om en ställning A evalueras till vinst för P1, och det finns en ställning B som är en_föregångare_ till den (med det menas att det finns ett utkant från B till A, eller, om man så vill, en inkant från A till B) där P1 är vid drag, så är det uppenbart att vi kan
evaluera ställning B också. Det var det lätta fallet; antag nu att ställning B är sådan att P2 är vid draget istället. I så fall kommer P2 undvika att göra draget som leder honom till B om nödvändigt - hans valmöjligheter för nästa drag har minskat med 1. Ursprungligen, när grafen skapas, så har P2 vid B lika många valmöjligheter som antalet utkanter från B (den s k utvalensen). Om antalet valmöjligheter för P2 vid B skulle bli 0, så innebär det att vilket drag P2 än gör vid B så kommer han att förlora. Alltså kan vi nu evaluera B.
Puh, detta blev rörigt - låt oss sammanfatta:

(A och B är två ställningar där det finns ett drag från B till A och där A har evaluerats till vinst för P1)

* Antalet valmöjligheter vid en viss ställningen för en spelare är till att börja med detsamma som antalet möjliga drag vid den ställningen.

* Om P1 är vid draget vid ställning B, så är även B vinst för P1 - P1 spelar helt enkelt det drag som leder till A.

* Om P2 är vid draget vid ställning B, så minskar P2's valmöjligheter i A med 1. Om antalet valmöjligheter i A blir 0, så är B vinst för P1 eftersom oavsett vilket drag P2 gör så kommer han att förlora.

Vad är poängen med det här? Jo, så fort vi har evaluerat en ställning kan vi direkt utnyttja denna information genom att titta på ställningens samtliga föregångare och antingen 1) evaluera en föregångare eller 2) minska en "valmöjlighetsräknare" och om den blir 0, evaluera föregångaren. Vi behöver alltså bara bearbeta varje ställning en gång. Detta implementeras lämpligast genom att använda sig av en kö, där man lagrar alla ställningar som har evaluerats. Man plockar fram en ställning från kön, uppdaterar den ställningens
föregångare vilket medför (kanske) att fler ställningar läggs till kön, osv, ända tills kön blir tom. Så här kan det se ut:

set all elements in eval to UNKNOWN
loop through all positions
no_possibilites[turn,position]=calc_number_of_moves(turn,position)
if (game_over(turn,position))
eval[turn][position]=who_won(turn,position)
add_queue(turn,position)
end if
end loop
while queue is not empty
[turn,position]=pop_queue_front
loop through all premoves in position
if eval[prev_turn][prev_position]!=UNKNOWN
continue to next iteration in loop
if (prev_turn==P1)
if (eval[turn][position]==P1)
eval[prev_turn][prev_position]=P1
push_queue_end(prev_turn,prev_position)
else
if (--no_possibilities[prev_turn][prev_position]==0)
eval[prev_turn][prev_position]=P2
push_queue_end(prev_turn,prev_position)
end if
end if
else
if (eval[turn][position]==P2)
eval[prev_turn][prev_position]=P2
push_queue_end(prev_turn,prev_position)
else
if (--no_possibilities[prev_turn][prev_position]==0)
eval[prev_turn][prev_position]=P1
push_queue_end(prev_turn,prev_position)
end if
end if
end if
end loop
end loop

Komplexiteten för algoritmen ovan är O(n+m) - alla ställningar och kanter i grafen bearbetas exakt en gång.

En viktig skillnad med den här algoritmen jämfört med den förra är loopen "loop through all premoves" - vi måste alltså här på något sätt ta reda på alla ställningar som kan föregå en annan ställning ("baklängesdrag"). Notera också att vi ingenstans i koden behöver loopa igenom alla "framlängesdrag", bortsett från att vi måste räkna _antalet_ framlängesdrag för varje ställning. Det finns två metoder för att få fram denna information:

* Man skriver en funktion som genererar samtliga framlängesdrag i en ställning (för att kunna beräkna no_possibilities), och en annan som genererar samtliga baklängesdrag. Denna metod är att föredra då den kräver mindre minne (speciellt viktigt om antalet drag är många).

* Man skriver endast funktionen som genererar framlängesdragen, och bygger upp hela grafen explicit. Hittar vi ett drag från A till B så drar vi en kant i grafen från B till A istället. Detta får effekten att alla kanter som går från ett hörn till ett annat egentligen är ett baklängesdrag, precis vad vi vill ha. Nackdelen med denna metod är att den kan kräva en hel del minne.

Notera också att vi måste se till att inte ändra evalueringen på en redan tidigare evaluerad ställning! Därav if-continue satsen som ser till att vi ignorerar att ändra evalueringen på sådana ställningar.

Nästa steg att förbättra algoritmen ovan är, förstås, att lägga till så att man inte bara håller reda på vem som vinner i en ställning, utan också hur många drag det är till vinst. Detta är särskilt viktigt i upprepande spel, eftersom man annars kanske aldrig skulle komma till vinsten, utan fastna i en ställningsloop där samtliga ställningar är vinstställningar! Hur man gör detta tillägg lämnar jag återigen som övning, men det fungerar på exakt på samma sätt som för icke-upprepande spel. Återigen tänker jag inte bevisa att det verkligen blir den snabbaste vägen till vinsten man får fram på det sättet - det blir det...

Algoritmen enligt pseudokoden ovan, med tillägget att jag håller reda på hur långt det är till vinst, följer exakt mitt lösningsförslag till L-Game uppgiften i BOI. En faktor som gjorde uppgiften ännu svårare än jag tänkt var att metod två ovan inte fungerar, då det kräver för mycket minne, så man var (tror jag åtminstone!) tvungen att skriva funktioner för att både generera dragen framlänges och baklänges.

Avslutningsvis: Givetvis kan man använda algoritmen ovan även i spel som är icke-upprepande. Detta kan ibland faktiskt bli enklare och snabbare än att använda rekursion (algoritmen ovan är som synes iterativ)!


NIM

Spelet Nim är ett urgammalt spel som kommer från Kina. Det finns mycket att säga om Nim, men det intressanta är att en hel del enkla spel kan reduceras till Nim. Om ni redan känner till Nim och hur man löser det så kan ni hoppa fram lite i texten.

Nim spelas av två spelare. Man har ett antal höger med ett antal stickor i varje hög - i det klassiska Nim hade man 3 höger med 3, 5 respektive 7 stickor i varje hög. Spelarna turas om att välja en hög och antalet stickor han vill ta från högen (minst 1, som mest hela högen). Den spelare som tar den sista stickan vinner.

Om antalet högar och föremål är litet kan man lösa Nim på samma sätt som ett icke-upprepande spel. Värre blir det om man har t ex 100 höger med upp till en miljon föremål i varje hög. Likväl kan man med en till synes förbluffande enkel metod ändå spela perfekt.

Idén till lösningen är att partitionera (dvs dela in) alla möjliga ställningar i spelet i två partitioner (delar), S1 och S2. Slutställningen (dvs 0 stickor i varje hög) tillhör förstås någon av dessa partitioner, vi låter S1 vara denna partition. Om vi nu kan finna en sådan indelning, så att från varje ställning i S2 ska det finnas ett giltigt drag som leder till en ställning i
S1, och från varje ställning i S1 ska _samtliga_ drag leda till en ställning i S2, då har vi löst problemet. Varför då? Jo, notera likheten i detta resonemang med det vi gått igenom tidigare - målet med spelet är att hela tiden se till att man efter sitt eget drag är i en ställning tillhörande S1 (eftersom slutställningen är i S1, och den som når slutställningen vinner). När motståndaren då gör sitt drag kommer han alltid att hamna i S2, oavsett vilket drag han gör. Men när det sedan är vår tur igen, så kan vi alltid göra ett drag som för oss tillbaka till S1. Följer man denna princip så kommer man alltid att vinna, såvida man inte börjar spelet i en ställning i S1 (eller motståndaren börjar i en ställning i S2).

Återstår att hitta en indelning av alla ställningar i S1 och S2 som uppfyller villkoren ovan. Det man gör är att titta på den binära representationen av antalet stickor i högarna och utför en exklusive-eller (xor) operation på samtliga bitar i högarna. Om resultatet blir 0 säger vi att ställningen tillhör S1, annars tillhör den S2. Exempel:

* Slutställningen har 0 stickor i varje hög. Den binära representationen för högstorlekarna är då förstås också 0, och utför vi xor så får vi förstår slutresultatet 0 - slutställningen tillhör alltså S1 som önskat.

* Ställningen (3,5,7) har följande binära representation: (011,101,111). Utför vi 011 xor 101 xor 111 får vi 001, vilket inte är noll. Alltså tillhör (3,5,7) partitionen S2.

* Ställningen (23,0,25,14) har följande binära representation: (10111,00000,11001,01110). 10111 xor 00000 xor 11001 xor 01110 = 00000, alltså tillhör (23,0,25,14) partitionen S1.

Varför fungerar denna indelning? Om vi tar en ställning i S1 så är det rätt uppenbart att om vi ändrar storleken på någon av högarna så kommer resultatet av xor-beräkningen inte längre att vara 0, så vilken drag vi än gör i S1 kommer att leda till S2. Om vi nu tar en ställning i S2, så börjar vi med att kolla vad värdet av xor-beräkningen blir - kalla detta värde för X. Vi vill göra det drag som i någon hög ändrar exakt de bitar som är 1 i X, eftersom det nya värdet då kommer att bli 0. Detta görs enklast genom att man loopar igenom alla
högar, kollar om <högens storlek> xor X blir ett tal mindre än högens storlek (vi får ju inte lägga till stickor till en hög!) Det trevliga är att det alltid finns (minst) en sådan hög; antag att X är 0010011. Det innebär att någon hög har en binärrepresentation med en 1:a i bitposition 4 (den mest signifikanta 1:an i X) - resultat av <den högens storleken> xor X kommer då bli ett mindre tal än högens ursprungliga storlek (jag hoppas att detta är uppenbart).

Slutligen kommer här en kort C funktion som tar som indata antal högar och antal stickor i varje hög och returnerar ett drag som leder till vinst. Om indata är en ställning i S1 (dvs en förlustställning) returneras ett slumpmässigt drag.

void nim(int nopiles, int pile[], int *move_pile, int *move_number)
{
int i,x=0;
for(i=0;i<nopiles;i++)
x^=pile[i];
if (x) {
for(i=0;i<nopiles;i++)
if ((pile[i]^x)<pile[i]) {
*move_pile=i; // Kommer alltid att exekveras någon gång i loopen
*move_number=pile[i]-(pile[i]^x);
}
} else { // Förlustställning
do {
i=rand()%nopiles;
} while (!pile[i]);
*move_number=1+rand()%pile[i];
*move_pile=i;
}
}

NIM-REDUCERBARA SPEL

Låt oss generalisera Nim lite grann. Istället för att tillåta att man får tar hur många stickor som helst från en hög så sätter vi en övre gräns för detta; låt k vara det maximala antalet stickor en spelare får ta från en hög i ett drag (k ändras inte under partiet).

Hur ska man nu gå tillväga? Nu finns det ingen garanti för att metoden ovan fungerar eftersom värdet X kan vara mycket större än k, och således är vi inte tillåtna att göra det drag som skulle föra oss till en ställning i S1.

Låt oss titta på ett riktigt klassikt spel för barn, där man ska räkna till 21. Man börjar på 0, sedan turas spelarna om att lägga till antingen 1 eller 2 till denna summa. Den som kommer upp till 21 (eller mer) förlorar. Detta kan ses som Nim "baklänges" med en enda hög där värdet på k är 2.

Tricket att vinna spelet är att se till att man själv uppnår 20 eftersom motståndaren då måste gå till 21 (eller 22). För att komma till 20 ska man se till att komma till 17 - går motståndaren då till 18 eller 19 kan man alltid komma till 20. För att komma till 17, ska man komma till 14, 11, 8, 5 och 2 - dvs, om man börjar spelet ska man direkt gå till 2 för att vinna.

Varifrån kommer sekvensen 20, 17, 14, ...? Differensen mellan talen är 3. Anledningen till det är att k=2 - vilket tal man en väljer ur intervallet 1..k så kan den andra spelaren sedan välja ett tal som gör att summan k+1 uppnås - man väljer ett tal som "neutraliserar" den andre spelarens drag. Detta funkar förstås för alla värden på k. Det funkar dessutom om man har flera olika högar! Antag att ställningen (a,b,c) tillhör S1. I så fall tillhör också ställningen (a+(k+1),b,c) S1, liksom (a,b+(k+1),c+(k+1)) osv - alla ställningar på formen (a+n1*(k+1),b+n2*(k+1),c+n3*(k+1)) (n1, n2, n3 är heltal >= 0) tillhör S1. Om spelaren vid draget i en ställning väljer att göra ett drag i en hög med k+1 stickor eller fler, så kan man själv alltid göra ett drag som neutraliserar det draget. Alltså, för att avgöra om en ställning tillhör S1 eller inte, så tittar man på antalet stickor i varje hög modulo k+1. Resultatet av modulo k+1 blir att man får högar med högst k föremål, vilket är exakt det antal föremål en spelare som mest får välja, och då kan vi applicera Nim algoritmen enligt ovan.

Koden ovan har här modifierats för att implementera detta:

void nim(int nopiles, int pile[], int k, int *move_pile, int *move_number)
{
int i,x=0,k1=k+1;
for(i=0;i<nopiles;i++)
x^=(pile[i]%k1);
if (x) {
for(i=0;i<nopiles;i++)
if (((pile[i]%k1)^x)<pile[i]%k1) {
*move_pile=i; // Kommer alltid att exekveras någon gång i loopen
*move_number=pile[i]%k1-((pile[i]%k1)^x);
}
} else {
// Förlustställning
do {
i=rand()%nopiles;
} while (!pile[i]);
x=(pile[i]<k)?pile[i]:k;
*move_number=1+rand()%x;
*move_pile=i;
}
}

Vi avslutar Nim-teorin med en uppgift där det inte är helt enkelt att se hur man ska reducera problemet till ett Nim problem.

UPPGIFT 4: På marken har vi ett antal gropar (max 50 stycken) i en lång rad. Groparna är antingen tomma eller innehåller en sten. Det finns minst 1 sten och högst 10 stenar totalt i groparna. En ställning i spelet kan t ex vara ..X.X.....X....XX.X...X där '.' motsvarar en tom grop och 'X' en grop med en sten i. Spelarna turas om att flytta stenarna på följande sätt: den spelare som är vid draget väljer en sten och flyttar den antingen 1 eller 2 steg till vänster. En sten kan bara flyttas om resultatet av förflyttning blir att den hamnar i en tom grop, och man får inte hoppa över en annan sten. T ex så kan den sten som är längst till vänster ovan flyttas ett eller två steg, medan stenen som ligger efter den bara kan flyttas ett steg. Det finns också en sten som inte kan flyttas alls. Den spelare som först inte kan göra något drag förlorar. Detta inträffar förstås när samtliga stenar har samlats längst till vänster - om antalet stenar (som ovan) är 7 skulle slutställningen alltså se ut så här: XXXXXXX................ Skriv ett program som spelar spelet perfekt!

Detta kan alltså lösas med Nim-teori, men man måste tänka till lite för att inse hur det ska gå till. Uppgiften går (med de begräsningar som nämndes) även att lösa med de metoder som nämnts i icke-upprepande spel, men det är inte alls lika snyggt och fungerar inte speciellt bra om antalet stenar är mycket mer än 10. Det kan vara bra träning att lösa spelet med den metoden också, om inte annat för att jämföra de båda lösningarna och kontrollera att de är rätt (genom att t ex låta dem spela mot varandra - det finns, förstås, hela tiden flera
drag som är korrekta och leder till vinst).

Tävlingsuppgifter

Dessa uppgifter kan ta lite tid att göra om man inte hållit på med spelteori så mycket förut - välj själv den/de ni tycker verkar intressant!

Problem Tävlingens hemsida Hjälp och kommentarer
Matrix SM 1999
L-Game (Jimmy) BOI 2002
Queen vs Rook (Jimmy)
Denna uppgift får väl anses vara "examensprovet" i den här typen av spelteori; klarar ni den med en effektiv lösning (max 45 sek) så är ni väldigt duktiga. Den kräver både effektiv draggenerering samt utnyttjande av symmetrier.









Tillbaka