Benutzer:Megatherium/Spielwiese

Zugbasiertes Spiel Bearbeiten

Ein zugbasiertes Spiel ist ein 9-Tupel $G=(n,S,s_{0},E,V,f_{p},f_{v},f_{s},f_{w})$ mit:

Anzahl der Spieler $n\in \mathbb {N}$ , den Zufallsspieler nicht mitgezählt
Menge der Spielzustände $S$
Startzustand $s_{0}\in S$
Endzustände $E\subseteq S$ , sei $A=S\setminus E$
Menge der Ansichten $V\neq \emptyset$
Spielerfunktion $f_{p}:A\rightarrow \{0,...,n\}$ , die den Spieler am Zug bestimmt.
Sichtfunktion $f_{v}:A\times \{1,...,n\}\rightarrow V$ , die festlegt, welche Information über den aktuellen Spielzustand jeder Spieler erhält.
Übergangsfunktion $f_{s}:A\times [0,1]\,\rightarrow S\setminus \{s_{0}\}$ , die aus dem alten Zustand und dem Zug den neuen Zustand bestimmt.
Gewinnfunktion $f_{w}:S\times \{0,...,n\}\rightarrow \mathbb {R}$ , die jedem Spieler einen Gewinn zuweist.

Zu Beginn erhält jeder Spieler $k\in \{0,...,n\}$ den Gewinn $f_{w}(s_{0},k)$ . Wenn der nach $i\in \mathbb {N}$ Zügen vorliegende Zustand $s_{i}$ Element von $A$ ist, dann wählt der Spieler $f_{p}(s_{i})$ den nächsten Zug $m_{i}\in [0,1]$ . Dabei bezeichnet $f_{p}(s_{i})=0$ den Zufallsspieler, der seinen Zug unabhängig von den bisherigen Zügen $m_{0}$ bis $m_{i-1}$ und gleichverteilt wählt, d. h. es gilt $\forall [a,b]\subseteq [0,1]:P(m_{i}\in [a,b])=b-a$ . Der nächste Zustand ist dann $s_{i+1}=f_{s}(s_{i},m_{i})$ , und Spieler $k\in \{0,...,n\}$ erhält den Gewinn $f_{w}(s_{i+1},k)$ . Der gesamte Gewinn von Spieler $k$ nach $i$ Zügen ist also $\textstyle \sum _{j=0}^{i}f_{w}(s_{j},k)$ .

Das Tupel $G$ und die Zuordnung der Werte von $f_{p}$ zu den Spielern ist allen Spielern vorab bekannt, d. h. alle kennen die Spielregeln und ihre jeweilige Rolle im Spiel. Nach jedem Zug erhält jeder Spieler eine Information über den aktuellen Zustand: In Zustand $s_{i}$ bekommt Spieler $k\in \{1,...,n\}$ den Funktionswert $f_{v}(s_{i},k)$ mitgeteilt. Er erfährt auch seinen Gewinn $f_{w}(s_{i},k)$ . Weitere Information über den Spielverlauf erhalten die Spieler nicht.

Mit der Zugmenge $[0,1]$ lässt sich das Verhalten des Zufallsspielers problemlos definieren (Gleichverteilung). Das bedeutet andererseits praktisch keine Einschränkung gegenüber einer allgemeineren Zugmenge. Jede endliche Zugmenge kann durch Aufteilung von $[0,1]$ in Teilintervalle dargestellt werden, und in einer reellen Zahl können mehrere (sogar abzählbar unendlich viele) reelle Zahlen codiert werden.

endliches Spiel: $S$ ist endlich
zyklusfreies Spiel: ein früherer Spielzustand kann nicht wiederholt werden, $i\neq j\Rightarrow s_{i}\neq s_{j}$
zufallsfreies Spiel: $\forall s\in A:f_{p}(s)\neq 0$
Spiel mit zufallsfreiem Verlauf: $\forall s\in A\setminus \{s_{0}\}:f_{p}(s)\neq 0$
Spiel mit perfekter Information: für jeden Spieler $k\in \{1,...,n\}$ ist die Abbildung $A\rightarrow V:s\mapsto f_{v}(s,k)$ injektiv
endloses Spiel: $E=\emptyset$
Konstantsummenspiel: $\forall s\in S\setminus \{s_{0}\}:\textstyle \sum _{k=1}^{n}f_{w}(s,k)=0$

Halali 9x9 Bearbeiten

Name	Partei	Anzahl	Wert (Punkte)	Zugweite	Schlägt
Bär	blau	3	10	1	Jäger, Holzfäller
Fuchs	blau	10	5	beliebig	Fasan, Ente
Biber	blau	2	5	1	Laubbaum
Jäger	braun	12	5	beliebig	Bär, Fuchs, Biber, Fasan, Ente
Holzfäller	braun	3	5	1	Laubbaum, Nadelbaum
Fasan	neutral	13	3	beliebig	-
Ente	neutral	12	2	beliebig	-
Laubbaum	neutral	13	2	-	-
Nadelbaum	neutral	12	2	-	-

Goban Bearbeiten

Spieldatenbank Bearbeiten

Gegeben ein Spiel für zwei Parteien, ohne Zufall und mit perfekter Information, in dem es neben den Ausgängen Partei 1 gewinnt und Partei 2 gewinnt höchstens noch einen weiteren möglichen Ausgang gibt, nämlich remis (unentschieden).

Wähle zunächst eine nicht zu große Teilmenge $T\subseteq S$ aller Spielsituationen $S$ , da es bei einem ernsthaften Spiel in der Regel zu viele Situationen gibt, um sie alle zu erfassen. Die Teilmenge muss abgeschlossen sein, d. h. durch einen Zug in einer Situation in $T$ entsteht immer eine Situation, die ebenfalls in $T$ liegt.

Bestimme eine Indexfunktion $i:T\rightarrow \mathbb {N}$ , die den Index in ein Array angibt, in dem Informationen zu jeder Situation gespeichert werden, wobei verschiedene Situationen verschiedene Indizes bekommen müssen. Man kann aber Symmetrien nutzen, um Platz zu sparen: zwei verschiedene, aber effektiv gleiche Situationen $x,y$ können auf den gleichen Index $i(x)=i(y)$ abgebildet werden. Das betrifft zum Beispiel zueinander links-rechts-symmetrische Schachstellungen, in denen es keine Rochaderechte mehr gibt. In das Array wird zu jeder Situation zunächst unbewertet eingetragen. Außerdem werden die Einträge für Partei 1 gewonnen und für Partei 2 gewonnen vorgesehen, in Verbindung mit der Zahl der Züge (d. h. Halbzüge) bis zur Endsituation bei beiderseits optimalem Spiel.

Ermittle alle Endsituationen in $T$ , die von einer Partei gewonnen sind, und trage in das Array die entsprechende Bewertung ein. Als Zahl der Züge wird 0 eingetragen, da kein Zug bis zur Endsituation mehr zu spielen ist.

Dann werden in der Hauptschleife des Programms immer wieder alle noch nicht bewerteten Situationen s betrachtet. Die in s möglichen Züge werden ermittelt, und für jeden wird die zur erreichten Situation im Array eingetragene Information ausgelesen. Dadurch teilt man die Züge in Gewinnzüge, Verlustzüge und unbewertete ein. Gibt es in s nur Verlustzüge, trägt man ein, dass s für die Partei am Zug verloren ist, zusammen mit einer Zügezahl, die das Maximum der Zügezahlen der erreichten Situationen ist, plus Eins, weil der Zug von s aus mitzuzählen ist. Die Partei am Zug versucht mit ihrer Wahl, die Niederlage möglichst lange hinauszuzögern.

Gibt es Gewinnzüge, dann gewinnt die Partei am Zug in soviel Zügen, wie das Minimum der Zügezahlen der dadurch erreichten Situationen beträgt, wiederum plus Eins. Wenn es aber auch unbewertete Züge gibt, darf man s nur bewerten, wenn sicher ist, dass keiner davon schneller gewinnt als die ermittelten Gewinnzüge. Das ist der Fall, wenn im n-ten Durchlauf der Hauptschleife der schnellste Gewinnzug nicht mehr als n Züge braucht. Im ersten Durchlauf werden alle Situationen bewertet, die in einem Zug gewonnen oder verloren sind. Im zweiten werden alle bewertet, die in höchstens zwei Zügen beendet werden usw. Im n-ten Durchlauf sind also alle entschiedenen Situationen, die höchstens n-1 Züge bis zum Ende brauchen, bereits bewertet. Jeder Zug, der in weniger als n Zügen gewinnt, wird somit gefunden.

Dies setzt man fort, bis bei einem Schleifendurchlauf keine weitere Situation mehr bewertet wird. Die noch unbewerteten Situationen sind dann remis.

Das Vorgehen als Pseudocode im Pascal-Stil:

for each s in T   { bewerte Endsituationen }
   Z(s) := 0     { Z(s) ist Abkürzung für Z(i(s)) mit Indexfunktion i }
   if s ist für Spieler 1 gewonnen then
      B(s) := 1  { auch hier eigentlich B(i(s)) }
   else if s ist für Spieler 2 gewonnen then
      B(s) := 2
   else
      B(s) := 0   { unbewertet }
   end if
end for
w := true
n := 1
inf := 999999 { symbolisch unendlich; größer als jede vorkommende Zügezahl }
while w
   w := false
   for each s in T
      if B(s) = 0 then
         mover := Zugrecht(s)  { Partei, die in s am Zug ist (1 oder 2) }
         win := inf
         loss := 0
         zl := Zugliste(s)
         for each m in zl      { alle in s möglichen Züge }
            p := Situation(s,m)  { Situation, die durch Zug m aus s entsteht }
            if B(p) = mover then   { m ist Gewinnzug für mover }
               if win > Z(p) then win := Z(p) end if
            else if B(p) = 0 then   { p ist noch unbewertet }
               loss := inf
            else                   { m verliert }
               if loss < Z(p) then loss := Z(p) end if
            end if
         end for
         if win < inf and (win <= n or loss < inf) then
            B(s) := mover    { mover gewinnt }
            Z(s) := win + 1   { Halbzüge bis zum Sieg, m eingerechnet }
            w := true
         else if win = inf and loss < inf then  { alle Züge verlieren }
            B(s) := 3 - mover   { die andere Partei }
            Z(s) := loss + 1   { Halbzüge bis Niederlage }
            w := true
         end if
      end if
   end for
   n := n + 1
end while

Anwendung auf Schach Bearbeiten

Eine überschaubare Größe von $T$ ergibt sich durch Begrenzen der Figurenzahl. Mit $n$ Steinen sind grob $2^{6n+1}$ Stellungen möglich. Mehr, wenn Bauernumwandlungen berücksichtigt werden, jedoch weniger, wenn man Symmetrien nutzt. Die Abgeschlossenheit folgt daraus, dass die Zahl der Steine nicht größer werden kann.

Die Regel der dreifachen Stellungswiederholung kann ignoriert werden. An der Bewertung der entschiedenen Situationen ändert das nichts, denn um einen Gewinn zu realisieren, muss man keine Wiederholung herbeiführen. Die am Ende noch unbewerteten Situationen können von keinem Spieler gewonnen werden, egal, ob bei Stellungswiederholung die Partie beendet wird oder ob sie endlos weiter geht.

Anders sieht es bei Spielen aus, die eine Stellungswiederholung nur eingeschränkt erlauben oder ganz verbieten, wie etwa Xiangqi oder Arimaa. Wenn man diese Regel auch hier ignoriert, gilt für die entschiedenen Situationen das gleiche wie oben, aber die unbewerteten sind zum Teil für eine Partei gewonnen, weil sie die Gegenpartei in eine Situation treiben kann, in der wegen der Stellungswiederholungsregel bestimmte Züge, die die Niederlage abwenden würden, nicht erlaubt sind.

Auch die 50-Züge-Regel wird meist ignoriert. Im Nachhinein kann man in vielen Fällen anhand der Zügezahl bis zum Matt, die für eine Stellung ermittelt wurde, entscheiden, ob sie wegen der 50-Züge-Regel remis ist. Wenn die Zügezahl nicht größer 100 ist, dann ist sie entschieden. Anderenfalls kommt es darauf an, ob während der Gewinnführung Bauern gezogen werden oder etwas geschlagen wird, und ggfs., ob es alternative Gewinnführungen gibt, um die 50-Züge-Regel zu umgehen.

Go Bearbeiten

Gegeben:

Endliche Knotenmenge $V$
Menge von Kanten $E\subseteq \{(a,b)\in V^{2}\,|\,a\neq b\}$
Anfangsbelegung: $f_{0}:V\rightarrow C$ mit $C=\{-1,0,1\}$

$f_{i}:V\rightarrow C$ mit $i\in \mathbb {Z}$ bezeichnet für ein gegebenes $i$ eine Belegung der Knoten mit Steinen der Spieler. Dabei bedeutet $1$ einen schwarzen und $-1$ einen weißen Stein und $0$ einen unbesetzten Knoten. $f_{i}$ mit $i\geq 0$ ist die Belegung nach $i$ Zügen. Zwei Belegungen sind gleich ( $f_{i}=f_{k}$ ), wenn $\forall n\in V:f_{i}(n)=f_{k}(n)$ .

Für jede Belegung $f_{i}$ mit $i\in \mathbb {Z}$ sei

L_{i}:=\{n\in V\,|\,f_{i}(n)=0\}

die Menge der unbesetzten Knoten,

F_{i,1}:=\{n\in V\setminus L_{i}\,|\,\exists m\in L_{i}:(m,n)\in E\}

,

F_{i,j}:=\{n\in V\,|\,\exists m\in F_{i,j-1}:(m,n)\in E\wedge f_{i}(m)=f_{i}(n)\}

mit

j\in \{2,3,4,\cdots \}

,

F_{i}:=\bigcup _{j=1,2,\cdots }F_{i,j}

die Menge der Steine (also der besetzten Knoten), die eine Freiheit haben.

Die beiden Spieler ziehen abwechselnd. Der Spieler, der nach $i$ Zügen am Zug ist, kann entweder passen, dann ist $f_{i+1}=f_{i}$ , oder er setzt auf den Knoten $m_{i}\in L_{i}$ seiner Wahl, und das führt zu der vorläufigen Belegung

f_{-i-1}(n)={\begin{cases}(-1)^{i}&{\text{wenn}}\;n=m_{i}\\f_{i}(n)&{\text{wenn}}\;n\neq m_{i}\end{cases}}

Regelvarianten für die erlaubten Züge:

Auf jeden Knoten in $L_{i}$ darf gesetzt werden (außer die Ko-Regel verbietet es, siehe unten).
Man darf nicht so setzen, dass $m_{i}\notin F_{-i-1}$ und $\forall n\in V:f_{i}(n)\neq (-1)^{i+1}\vee n\in F_{-i-1}$ , das heißt $m_{i}$ hat keine Freiheit, aber alle gegnerischen Steine haben eine Freiheit.
Man darf nicht so setzen, dass $m_{i}\notin F_{-i-1}$ .
Man darf nicht so setzen, dass nach der Behandlung von Steinen ohne Freiheit (siehe unten) noch Steine auf dem Brett sind (Belegung $f_{i+1}$ ), die keine Freiheit haben.

Regelvarianten für die Behandlung von Steinen ohne Freiheit:

Es werden alle Steine ohne Freiheit entfernt, d. h. wenn $n\notin F_{-i-1}$ , dann ist $f_{i+1}(n)=0$ .
Gegnerische Steine ohne Freiheit werden entfernt; wenn es danach eigene Steine ohne Freiheit gibt, werden auch diese entfernt.
Eigene Steine ohne Freiheit werden entfernt; wenn es danach gegnerische Steine ohne Freiheit gibt, werden auch diese entfernt.
Gegnerische Steine ohne Freiheit werden zu eigenen Steinen.

Für $n\in F_{-i-1}$ gilt $f_{i+1}(n)=f_{i}(n)$ .

Ko-Regel: man darf nicht so setzen, dass die entstehende Belegung $f_{i}$ gleich einer früheren Belegung mit dem gleichen Spieler am Zug ist, also $\exists k\in \{0,1,\cdots ,i-1\}:(i-k)\equiv 0({\bmod {2}})\wedge f_{k}=f_{i}$ .