Beispiel: Papier-Stein-Schere-Spiel

 

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ] ...

Übersicht: Papier-Stein-Schere-Spiel

Spielregeln

 Das Spiel wird von zwei sich gegenüber sitzenden Personen gespielt. Hinter ihren Rücken formen die Spieler jeweils mit der Hand eine Figur in der Form eines Steines (geballte Faust), eines Papierblattes (flache Hand) oder einer Schere (zwei gespreitzte Finger). Auf ein abgestimmtes Kommando werden die Hände gleichzeitig hinter dem Rücken hervor geholt und die jeweils gewählten Figuren verglichen. Der Gewinner einer Runde wird nach folgenden Kriterien ermittelt: Falls beide Spieler die gleiche Figur gewählt haben, so endet diese Spielrunde unentschieden. Das gesamte Spiel geht in der Regel über eine feste Rundenanzahl, die zu Spielbeginn festgelegt wird.

Datenstrukturen

Im Folgenden soll ein Programm entwickelt werden, welches dieses Spiel nachbildet und den Gesamtsieger anhand der Anzahl der gewonnenen Spielrunden ermittelt. Zunächst werden die benötigten Datentypen eingeführt: 

data Move = Paper | Rock | Scissors
type Round = (Move,Move)
Um den Gewinner einer Runde zu ermitteln wird die Funktion score definiert: 
score :: Round -> (Int,Int)
score (x,y) | x beats y = (1,0)
            | y beats x = (0,1)
			| otherwise = (0,0)
Die Vergleichsfunktion beats kann wie folgt definiert werden: 
( beats ) :: Move -> Move -> Bool
 x beats y = (m + 1 == n) or (m == n + 2)
             where m = code x; n = code y
mit: 
code :: Move -> Int
code Paper   = 0
code Rock    = 1
code Scissors = 2
Jeder Spieler verfolgt eine bestimmte Strategie, um zu gewinnen. Eine einfache Strategie ist beispielsweise nach der ersten Runde immer die Figur zu wählen, die der Gegner in der vorangegangenen Runde gewählt hat. Diese Strategievariante wird auch als Revanche bezeichnet. Eine weitere Strategie, welche als Smart bezeichnet wird, besteht in der Analyse der in der Vergangenheit gewählten Figuren des Gegners und einer anschliessenden Schätzung der nächsten Aktion des Kontrahenden. Wie diese Strategien im Einzelnen implementiert sind, soll zunächst einmal nicht interessieren, sondern wird später intensiv behandelt. Im Folgenden soll einfach davon ausgegangen werden, dass der Typ Strategy schon existiert und somit innerhalb von Funktionsdefinitionen benutzt werden darf.
Die Funktion rounds wird zur Berechnung einer unendlichen Liste von Runden genutzt: 
rounds :: (Strategy,Strategy) -> [Round]
Als Argument erhält die Funktion ein Paar von Strategien und liefert als Resultat die unendliche Liste von Runden zurück, die sich ergeben, wenn jeder Spieler seiner Strategie folgt. Mit Hilfe der Funktion rounds läßt sich die Funktion match definieren, welche das Ergebnis einer bestimmten Anzahl von Spielrunden zurückliefert. 
match :: Int -> (Strategy,Strategy) -> (Int,Int)
match n = total · map score · take n · rounds
mit:
total :: [(Int,Int)] -> (Int,Int)
total = pair (sum · map fst, sum · map snd)

Spielstrategien

 Im Folgenden sollen die vorhin zunächst zurückgestellten Implementierungen geeigneter Spielstrategien näher betrachtet werden. Es stehen zwei unterschiedliche Ansätze zur Implementierung von Strategien im Mittelpunkt.

1.Variante: 
type Strategy = [Move] -> Move
In diesem Fall wird die Strategie durch eine Funktion repräsentiert, die eine Liste der bisher gewählten Figuren als Argument erhält und eine geeignete Aktion(Figur) für die nachfolgende Spielrunde zurückliefert. Beispielsweise könnte die Revanche(recip) Strategie folgendermaßen implementiert werden: 
recip :: Strategy
recip ms = if null ms then Rock else last ms
Die Wahl der Figur in der ersten Spielrunde ist nach dieser Strategie unerheblich. In dieser Definition wird willkürlich der Stein gewählt.

Die Implementierung der smart-Strategie erfolgt nach dem gleichen Muster: 
smart :: Strategy
smart ms = if null ms then Rock else choose (count ms)
mit:
count :: [Move] -> (Int,Int,Int)
count = foldl (⊕) (0,0,0)
mit:
(⊕) :: (Int,Int,Int) -> Move -> (Int,Int,Int)
(p,r,s) ⊕ Paper = (p + 1,r,s)
(p,r,s) ⊕ Rock = (p,r + 1,s)
(p,r,s) ⊕ Scissors = (p,r,s + 1)
Auch in diesem Fall kann in der ersten Runde wieder eine willkürliche Figur gewählt werden. Wiederum wurde der Stein als Anfangselement festgelegt. Die Funktion choose wählt eine Figur anhand einer Analyse der drei Zahlenwerte p,q und r, die jeweils die Anzahl der einzelnen bereits vom Gegner gewählten Figuren darstellen. 
choose :: (Int,Int,Int) -> Move
choose (p,r,s) | m < p = Scissor
               | m < p + r = Paper
			   | otherwise = Rock
			     where m = random (p + r + s)
Die Funktion choose wählt eine Figur in Abhängigkeit davon aus, in welches der folgenden drei Intervalle die Zufallszahl m fällt: 
(0 ≤ m < p) or (p ≤ m < p + r) or (p + r ≤ m < p + r + s)
Falls die Zahl p sehr groß ist, steigt die Wahrscheinlichkeit für die Wahl der Schere an, da Schere gegenüber Papier gewinnt. Falls hingegen r relativ groß ist, ist verständlicherweise die Wahrscheinlichkeit für die Wahl des Papierblattes relativ hoch. Usw. ...
Nachdem nun die zwei Strategien defniert wurden, sind wir nun in der Lage die Funktion rounds zu definieren. 
rounds :: (Strategy,Strategy) -> [Round]
rounds (f,g) = (map last ⋅ tail ⋅ iterate (extend (f,g)))[]
mit:
extend :: (Strategy,Strategy) -> [Round] -> [Round]
extend (f,g) rs = rs ++ [(f (map snd rs),g (map fst rs))]
Die Funktion extend hängt ein neues Paar von Figuren an die Liste der bisher gespielten Runden und rounds generiert die unendliche Liste von Spielrunden, indem sie die Funktion extend laufend auf die initialisierende leere Liste anwendet.

Die Definition von rounds ist im Hinblick auf Effizienz sehr ungeschickt implementiert. Die Ursache hierfür liegt darin, dass die Zeit zur Berechnung eines Resultats für die Strategie proportional lange zur Länge der Liste dauert. Daraus folgt, dass die Funktion extend Ω(n) Schritte zum Hinzufügen einer Runde zu einem Spiel mit n Runden benötigt. Um ein komplettes Spiel mit n Runden zu berechnen, werden so Ω(n²) Schritte benötigt.

2. Variante

Zum Vergleich wird nun eine weitere Möglichkeit zur Repräsentation von Strategien diskutiert.
type strategy = [Move] -> [Move]
In disem Fall ist strategy eine Funktion, die die unendliche Liste von Moves des Gegners als Argument erhält und daraufhin eine unendliche Liste von geeigneten Antworten generiert.

a) Strategie recip 
type recip ms = Rock : ms
Beim ersten Durchgang wird bei dieser Strategie wiederum der Stein gewählt und anschliessend jeweils die Figur, die der Gegner in der vorangegangenen Runde gewählt hat. In diesem Beispiel ist die Realisierung relativ einfach, da ab der zweiten Runde einfach nur die übergebene Liste (Liste der bereits gewählten Figuren des Gegners) zurückgeliefert wird. Zur Ermittlung eines Ergebnisses benötigt diese Version der Strategie recip jeweils eine konstant lange Rechenzeit.

b) Strategie smart 
 smart xs = Rock : map choose (counts xs)
mit:
counts = tail · scanl (⊕) (0,0,0)
Die Funktion counts berechnet die laufende Summe der möglichen Moves. Diese neu Implementierung der smart- Strategy ist ebenfalls sehr effizient, da jedes Ergebnis in einem konstant grossen Zeitintervall berechnet wird. Auf Grundlage dieser neuen Strategieimplementierungen kann nun die Funktion rounds neu definiert werden: 
rounds (f,g) = zip xs ys
               where xs = f ys; ys = g xs
XS entspricht hier der Liste der bisher gewählten Figuren des Gegners nach Anwendung der jeweils gewählten Strategie. Dieser Sachverhalt gilt analog für ys. Rounds berechnet die ersten n Figuren des Spiels in O(n) Schritten, da f und g jeden neuen Move in konstanter Zeit berechnen. Diese Art und Weise Strategien zu implementieren ist also effizienter als die zu Beginn eingefürte Variante.

Schummeln

 Die zweite, effizientere Variante Strategien zu implementieren, besitzt aufgrund ihres Konzepts einen entscheidenen Nachteil gegenüber der ersten. Sie bietet nämlich keinen Schutz gegenüber schummelnden Strategien. Ein Beispiel für eine solche Strategie wäre die Funktion cheat: 
cheat xs = map trumps xs
mit: 
trumps :: Move -> Move
trumps Paper    = Scissors
trumps Rock     =  Paper
trumps Scissors = Rock
Cheat wählt also in jeder Runde jeweils die zum Gewinnen benötigte Figur aus. Das folgende Beispiel zeigt, dass in diesem Fall nichts gegen das Untergraben der Spielregeln getan werden kann. 
xs = cheat ys
ys = recip xs
Bei xs und ys handelt es sich um die Grenzwerte der Approximationsketten xs0, xs1, ... und ys0, ys1, ... wobei folgendes gilt: 
xs0 = ys0 = ⊥ und
xsn+1 = cheat ysn
ysn+1 = recip xsn
Bei der Auswertung einiger Spielrunden, bei denen diese Strategien gegen einander eingesetzt werden, ergibt sich folgendes Bild: 
 xs1 = cheat ⊥ = ⊥
 ys1 = recip ⊥ = ⊥

 xs2 = cheat (Rock : ⊥) = Paper : ⊥
 ys2 = recip ⊥ = Rock : ⊥

 xs3 = cheat (Rock : ⊥) = Paper : ⊥
 ys3 = recip (Paper : ⊥) = Rock : Paper : ⊥

 xs4 = cheat (Rock : Paper : ⊥) = Paper : Scissors : ⊥
 ys4 = recip (Paper : ⊥) = Rock : Paper : ⊥ 

 usw. ...
Es wird deutlich, dass es sich bei den Grenzwerten dieser Sequenzen um unendliche Listen bestehend aus korrekten Elementen(-> keine undefinierten Elemente) handelt. Wie zu erwarten entscheidet die Strategie cheat zudem jede Runde für sich.

Weitere Strategien zum Schummeln: 
a) cunning xs = trumps (head xs) : cunning (tail xs)
Cunning arbeitet genauso wie die Funktion cheat, allerdings mit der Ausnahme, dass cheat ⊥ das Ergebnis ⊥ liefert und cunning ⊥ = ⊥ : ⊥ : ⊥ : ... gilt.

b) oneshot xs = trumps (head xs) : recip (tail xs)
Oneshot schummelt nur in der ersten Runde und delegiert alle weiteren Berechnungen an die Funktion recip.

c) devious = take2 (recip xs) ++ cheat (drop 2 xs)
Devious hält sich die ersten beiden Runden an die Spielregeln und beginnt dann zu schummeln.

Im Folgenden sollen Konzepte betrachtet werden, die das Spiel gegen schummelnde Strategien absichern.
Zunächst wird definiert, welche Bedingungen eine "ehrliche" Strategie erfüllt:

Es wird die Zusicherung(Assertion) open definiert, um zu zeigen, dass die ersten n Elemente der Liste xs korrekt sind.
open (n,xs) => open (n + 1, f xs) für alle n und alle Listen xs gilt.
Mit Hilfe von open läßt sich nun beweisen, dass beispielsweise recip eine "ehrliche" Funktion ist.
Es gilt: 
open (0,⊥) => open (1,recip ⊥) ≡ (1, Rock)
Bei Anwendung dieser Zusicherung auf die Strategie cheat ergibt sich hingegen folgendes:
open (0,⊥) => open (1,cheat ⊥) ≡ open (1,⊥)
Cheat erfüllt diese Zusicherung open nicht. Wie im ersten Fall ist open(0,⊥) gültig, open (1,⊥)jedoch nicht.

Obwohl es bei der mechanischen Auswertung nicht möglich ist Täuschungsversuche zu erkennen, läßt sich eine Funktion police definieren, die folgende Eigenschaften besitzt:
Falls f eine "ehrliche" Strategie und xs eine unendliche Sequenz von gültigen Moves ist, dann gilt police f xs = f xs
Falls f sich in einer Runde nicht an die Spielregeln hält, dann bricht das Spiel mit dem Resultat ⊥ ab. Die Funktion police gewährleistet, dass die Strategie f vor der Kenntnis, der vom Gegner gewählten Figur ein Ergebnis liefert. Police wird folgendermaßen definiert: 
police f xs = ys where ys = f (synch xs ys)

mit:
synch :: [Move] -> [Move] -> [Move]
synch (x : xs) (y : ys) = if defined y then x : synch xs ys else ⊥

mit:
defined :: Move -> Bool
defined | ⊥ = False
        | otherwise = True
Die Redefinition der Funktion rounds würde nun folgendermaßen aussehen: 
rounds (f,g) = zip xs ys
               where xs = police f ys; ys = police g xs
... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ Zurück ] ... [ Weiter ] ...