Til denne challenge skal vi bruge programmeringssproget Haskell. Det erhverver man sig lettest ved at installere værktøjet stack. Det hentes herfra, hvor man finder vejledninger til gængse styresystemer.
Efter installation køres stack setup fra kommandolinien. stack repl starter et Read-Eval-Print Loop ovenpå GHC, en Haskell compiler. Her kan man evaluere udtryk og loade og eksperimentere med eksisterende kode, jf. nedenstående udveksling på kommandolinien:
$ cat Example.hs
module Example where
square x = x * x
$ stack repl
Run from outside a project, using implicit global project config
Configuring GHCi with the following packages:
GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help
Prelude> :l Example
[1 of 1] Compiling Example ( Example.hs, interpreted )
Ok, modules loaded: Example.
*Example> square 7
49Ved hver stack kommando kvittere værktøjet med lidt støj om hvilken konfiguration der arbejdes med. Den vil vi ikke inkludere i eksempler fremover.
Når vi skal køre vores programmer kan vi starte dem med stack runhaskell, som vist her:
$ cat Demo.hs
module Demo where
square x = x * x
main :: IO ()
main = print $ square 7
$ stack runhaskell Demo.hs
49stack kan også bruges til at køre GHC i batch mode til at producere en executable, som nedenfor:
$ cat Demo.hs
module Demo where
square x = x * x
main :: IO ()
main = print $ square 7
$ stack ghc Demo -- -main-is Demo
[1 of 1] Compiling Demo ( Demo.hs, Demo.o )
Linking Demo ...
$ ./Demo
49Ovenstående er det eneste commandline fu vi skal bruge til denne Challenge.
Haskell er et funktionelt sprog. Der er to ting der kendetegner (men ikke definere) denne klasse af sprog: udtryk og funktioner som den centrale enhed i programmer og induktive datatyper. Vi udforsker her de to ideer.
Den primære organisatoriske enhed i Haskell er funktioner - parameteriserede udtryk. Her er et eksempel:
double x = x + xFunktionen double har en enkelt parameter x, og betydningen af double e for et udtryk e er e + e.
I modsætning til Java er Haskell et såkaldt non-strict programmeringssprog, eller mindre præcist et 'lazy' sprog.
Det vil sige, hvor udtrykket double(4 + 4) for en passende metode double i Java ville evaluere som følgende.
double(4 + 4)
double(8)
8 + 8
16Parametre evalueres altså fuldstændigt før metoder kaldes. I Haskell evalueres parametre først når deres værdi strengt talt behøves.
Evalueringen af double (4 + 4) vil i Haskell ske således:
double (4 + 4)
(4 + 4) + (4 + 4)
8 + 8
16Reelt sker der kun een reduktion i skridtet fra (4 + 4) + (4 + 4) til 8 + 8 da underudtrykket (4 + 4) ikke duplikeres som der kunne antydes ovenfor, men deles imellem venstre og højre position af + da de i definition for double fremgår som præcist det samme udtryk, nemlig x.
Java og andre imperative sprog har kommandoen som den centrale program enhed. Her er betydningen af et program hvilken effekt den har på det omkringværende miljø. I Haskell er programmer blot udtryk, og betydningen af et udtryk er en værdi.
Dette er ikke bare dovenskab! Lazy evaluering er et kraftfuldt værktøj der fremmer modularitet og kompositionalitet af kode, samt tillader helt nye kodemønstre.
Prøv at evaluere [1..] i GHCi. (Hint:
Dette er et eksempel på en uendelig datastruktur. GHCi forsøger at printe den, men det vil naturligvis tage lang tid. Men et program kan helt problemfrit behandle endelige dele af denne struktur, eksempelvis:
fac n = product (take n [1..])Her er et andet godt eksempel, der også gør brug af lister. Funktionerne tail, zipWith og take er biblioteksfunktioner, men deres implementationer er også inkluderet her.
tail (_:xs) = xs
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith f [] _ = []
zipWith f _ [] = []
take 0 _ = []
take n (x:xs) = x : take (n - 1) xs
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
x = take 4 fibsEvalueringen af x til udprintning i GHCi foregår nu således:
take 4 fibs
take 4 (0 : 1 : zipWith (+) fibs (tail fibs))
0 : take 3 (1 : zipWith (+) fibs (tail fibs)
0 : 1 : take 2 (zipWith (+) fibs (tail fibs))
0 : 1 : take 2 (zipWith (+) (0 : 1 : zipWith (+) fibs (tail fibs)) (tail (0 : 1 : zipWith (+) fibs (tail fibs))
0 : 1 : take 2 (zipWith (+) (0 : 1 : zipWith (+) fibs (tail fibs)) (1 : zipWith (+) fibs (tail fibs)))
0 : 1 : take 2 ((+) 0 1 : zipWith (+) (1 : zipWith (+) fibs (tail fibs)) (1 : zipWith (+) fibs (tail fibs)))
0 : 1 : ((+) 0 1) : take 1 (zipWith (+) (1 : zipWith (+) fibs (tail fibs)) (1 : zipWith (+) fibs (tail fibs)))
0 : 1 : 1 : take 1 (zipWith (+) (1 : zipWith (+) fibs (tail fibs)) (1 : zipWith (+) fibs (tail fibs)))
0 : 1 : 1 : take 1 ((+) 1 1 : zipWith (+) (zipWith (+) fibs (tail fibs)) (zipWith (+) (fibs (tail fibs))))
0 : 1 : 1 : ((+) 1 1) : take 0 (zipWith (+) (zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs)))
0 : 1 : 1 : 2 : take 0 (zipWith (+) (zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs)))
0 : 1 : 1 : 2 : []Observer at vi nu har manipuleret datastrukturer (lister) og beregnet ting der typisk beskrives via imperative algoritmer med lokale variable og mutationer deraf. Haskell er helt fri for sideeffekter, inklusiv mutation af variable, så imperative algoritmer som "sortér denne liste" skal tit omformuleres til deklarative "sådan er den sorterede udgave af denne liste defineret."
Her er den klassiske insertion sort algoritme:
insert x [] = [x]
insert x (y:xs) = if x < y then x : y : xs else y : insert x xs
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)Beskriv evalueringen af udtrykket insertionSort [2,3,1] som ovenfor, og beskriv med en enkelt sætning hver hvad biblioteksfunktionerne take, tail og zipWith gør.
Det kan lyde ineffektivt at beregne nye lister istedet for at sortere det gamle, men takket være en en compiler og et run-time system der planlægger efter dette mønster kan det være uhyre effektivt, og samtidigt give meget robust og modulær kode.
Nim er et enkelt, turbaseret spil for to spillere. Spillets konfiguration består af tre bunker med et antal genstande i hver. En tur består i at en spiller fjerner mellem én og antallet af genstande fra én bunke. Derefter går turen på skift. Spilleren der fjerner den sidste genstand taber.
Vi vil i resten af denne Challenge skrive en perfekt bot til Nim - en beslutningstagende algoritme der altid vinder et spil Nim, antaget at den starter eller at dens modstander begår en fejltagelse.
Nim er et såkaldt løst spil. Det vil sige, at der findes en beviseligt vindene strategi for den første spiller. I denne challenge vil vi derimod benytte en lidt mindre rafineret metode, der derimod er langt mere general.
Implementationen der beskrives her, og som opgaverne omhandler findes her
En spilleplade kan representeres som 3 tal, som vi gruppere i en triple:
type Field = (Int, Int, Int)Typen (Int, Int, Int) beskriver en datastruktur, præcis som lister - og på samme måde kan den inspiceres og bygges ved hjælp af pattern matching.
initialField :: Field
initialField = (1, 3, 5)
remainingItems :: Field -> Int
remainingItems (a, b, c) = a + b + cVi kan beregne mulige træk som en liste af nye spilleplader, ved brug af list comprehensions, en syntaktisk konstruktion der immitere matematikeres mængdenotation.
moves :: Field -> [Field]
moves (a, b, c) = [ (a', b, c) | a' <- [a - 1, a - 2 .. 0] ]
++ [ (a, b', c) | b' <- [b - 1, b - 2 .. 0] ]
++ [ (a, b, c') | c' <- [c - 1, c - 2 .. 0] ]Lister kan bygges ved udtrykket [ e | a <- as, b <- bs, ..., x <- xs] hvor as, ..., xs er udtryk der evaluere til lister, og e er et udtryk der kan gøre brug af variablene a, ..., x. Resultatet er da listen med e evalueret for alle mulige kombinationer af udvalg af elemeneter i as, ..., xs -- en form for generaliseret krydsprodukt.
Notationen [a, b .. c] er speciel notation for enumerering af lister fra a til c i skridt af forskellen fra a til b.
Eksempelvis evaluere length $ moves initialField til 9.
Vi kan nu bygge et spiltræ: en datastruktur der representere alle mulige spil Nim fra et givent udgangspunkt. En sti fra rod til blad representere et spil Nim fra begyndelse til slut.
Vi kan beskrive et træ ved en datatype:
data Tree a = Node a [Tree a]
deriving ShowDet vil sige, en Tree a datastruktur består i af en Node der indeholder 2 ting: en a værdi og en liste af flere Tree a strukturer.
Vi kan nu bygge spiltræet for en given spilleplade:
gameTree :: Field -> Tree Field
gameTree f = Node f (map gameTree $ moves f)På samme måde som par og lister så bruges Node funktionen både som konstuktør af nye værdi, samt some pattern til at pille værdier fra hinanden.
Antallet af blade (slut-konfigurationer) er et mål for størrelsen af et spil, og kaldes for et spiltræs kompleksitet.
Skriv funktionen leaves :: Tree a -> Integer, der tæller antallet af blade (dermed stier fra rod til blade) i et træ, og brug den til at beregne kompleksiteten af et spil Nim.
Eksempelvis er kompleksiteten af en færdig plade (0,0,0) blot 1 mens kompleksiteten på (1,1,1) er 6.
Prøv at bygge og vise nogle spiltræer i GHCi. Hvilke spilleplader findes i bladene? Hvorfor ender spillet her?
En strategi (eller i mere populære termer en "AI") for at spille Nim er et program der beslutter et træk baseret på en spilleplade: en funktion af typen Field -> Field
Det er klart at Nim er et såkaldt nulsumspil: når én spiller taber vinder den anden, og omvendt. Altså er en vindene strategi for een spiller en tabende strategi for den anden. Ydermere kan vi observere at, hvis en modstander kan tabe fra en spilleplade vi kan trække til, har vi en vindene strategi for den nuværende spiller (og omvendt!).
Det vil vi udnytte med den klassiske minimax algoritme, der virker på grund af ovenstående intuitioner (men det er naturligvis muligt at bevise den korrekt!).
Først en type til at beskrive om vi regner fra "fjenden" eller "vores" side. Her kunne vi have brugt et boolsk flag istedet (eller haft to eksemplarer af alle funktioner!), men en dedikeret datatype dokumentere bedre hensigten:
data Player = Hero | EnemySom led i minimax algoritmen skal vi beregne om en plade har en vindene strategi for en given spiller. Det kan vi gøre rekursivt over et spiltræ. En tom plade betyder at den anden spiller tog den sidste brik, altså har den pågældene spiller vundet, alternativt tabt. Lad os indikere en sejr med 1 og et nederlag med -1.
minimaxScore :: Player -> Tree Field -> Int
minimaxScore Hero (Node (0,0,0) []) = 1
minimaxScore Enemy (Node (0,0,0) []) = -1I det rekursive tilfælde kan vi regne værdien for en given plade ved at finde den største eller mindste værdi bland næste lag i spiltræt når vi leder efter en hhv. vindene eller tabende strategi:
minimaxScore p (Node _ cs) =
minOrMax (map (minimaxScore (nextPlayer p)) cs)
where
minOrMax = case p of
Hero -> maximum'
Enemy -> minimum'
nextPlayer :: Player -> Player
nextPlayer Hero = Enemy
nextPlayer Enemy = HeroVi kan nu besvaret spørgsmålet "kan en given spiller vinde, hvis det er deres tur til at trække fra en given spilleplade?" ved at beregne værdien af roden i minimax træet. Eksempelvis kan man vinde hvis det er eens tur til at trække på pladen (3,0,0): root $ minimaxTree Hero (gameTree initialField) giver 1. Omvendt kan man ikke vinde, antaget modstanderen spiller optimalt fra samme plade: root $ minimaxTree Hero (gameTree initialField) giver -1.
Vi kan nu stykke de to træer sammen til at træffe en beslutning om det næste træk: beregn det vindene minimax træ for spiltræt for den pågældene spilleplade, og udfører trækket til den med den største værdi.
makeMove :: Field -> Field
makeMove = minimumBy (comparing (minimaxScore Hero . gameTree)) . movesNu vi har en færdig algoritme kan du tage et spil med den! Du kan starte den fra kommandolinien med stack runhaskell Nim.hs Hero (1,3,5) hvor Hero angiver at du starter på spillepladen (1,3,5). Du kan også starte spillet fra dit repl med, eksempelvis, gameLoop Hero (1,3,5).
Prøv at spille et par spil - kan du slå vores strategi? Hvad hvis du lader computeren starte?
Prøv at spille et stort spil Nim. Den tænker sig lidt om, gør den ikke?
Problemet kan selvfølgelig tilskrives, at vi benytter en general tilgang til Nim -- men vi gør end ikke dét optimalt. Vi udnytter ikke Haskells lazy evaluation til at undgå at udforske alle spillets tilstande: principielt er vi jo ligeglade med hvordan vi vinder - blot at vi vinder.
Derfor kan udvælgelsen af bedste (værste) spiltræ ændres, således at den ikke behøver betragte alle mulige undertræer hvis den allerede har fundet et vindene (eller tabende) undertræ. Vores udvalgsmetoder minimum' og maximum' delegere blot til biblioteksfunktionerne minimum og maximum, der finder henholdsvis mindste og største element i en ikke-tom liste. De ved altså ikke at vi kun har med tallene -1 og 1 at gøre - maximum xs må nødvendigvis evaluere alle indgange i xs: der kan altid gemme sig et størrer element i næste indgang.
Vi er derimod i et tilfælde hvor vi kender de mulige tal i xs - og det kan vi udnytte!
Skriv mere fyldestgørende implementationer af funktionerner minimum' og maximum', der udnytter at vi kender spannet af mulige tal i listen.
Beskriv ændringer i programmets opførsel, hvis du observere nogle.
Hvis du har gjort det rigtigt burde minimum' [-1..] i GHCi terminere med resultatet -1.
Du deltager i vores challenge ved senest d. 27. November at sende en email til med emne Challenge 9 og svarene på spørgsmål A, B og C samt et attachment med din udgave af filen Nim.hs.