thumb

Benutzer:Megatherium/Bildfehlertheorie
Benutzer:Megatherium/Canon FD
Benutzer:Megatherium/Kram
Benutzer:Megatherium/Test
Benutzer:Megatherium/Pendel
Pellsche Gleichung
7. Sinfonie (Bruckner)
ImageJ
IPython

Zugbasiertes Spiel

Bearbeiten

Ein zugbasiertes Spiel ist ein 9-Tupel   mit:

  • Anzahl der Spieler  , den Zufallsspieler nicht mitgezählt
  • Menge der Spielzustände  
  • Startzustand  
  • Endzustände  , sei  
  • Menge der Ansichten  
  • Spielerfunktion  , die den Spieler am Zug bestimmt.
  • Sichtfunktion  , die festlegt, welche Information über den aktuellen Spielzustand jeder Spieler erhält.
  • Übergangsfunktion  , die aus dem alten Zustand und dem Zug den neuen Zustand bestimmt.
  • Gewinnfunktion  , die jedem Spieler einen Gewinn zuweist.

Zu Beginn erhält jeder Spieler   den Gewinn  . Wenn der nach   Zügen vorliegende Zustand   Element von   ist, dann wählt der Spieler   den nächsten Zug  . Dabei bezeichnet   den Zufallsspieler, der seinen Zug unabhängig von den bisherigen Zügen   bis   und gleichverteilt wählt, d. h. es gilt  . Der nächste Zustand ist dann  , und Spieler   erhält den Gewinn  . Der gesamte Gewinn von Spieler   nach   Zügen ist also  .

Das Tupel   und die Zuordnung der Werte von   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   bekommt Spieler   den Funktionswert   mitgeteilt. Er erfährt auch seinen Gewinn  . Weitere Information über den Spielverlauf erhalten die Spieler nicht.

Mit der Zugmenge   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   in Teilintervalle dargestellt werden, und in einer reellen Zahl können mehrere (sogar abzählbar unendlich viele) reelle Zahlen codiert werden.

  • endliches Spiel:   ist endlich
  • zyklusfreies Spiel: ein früherer Spielzustand kann nicht wiederholt werden,  
  • zufallsfreies Spiel:  
  • Spiel mit zufallsfreiem Verlauf:  
  • Spiel mit perfekter Information: für jeden Spieler   ist die Abbildung   injektiv
  • endloses Spiel:  
  • Konstantsummenspiel:  

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 - -
                 
                 
                 
                 
                 
                 
                 
                 
                 


         
         
         
         
         

Vorlage:Goban


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   aller Spielsituationen  , 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   entsteht immer eine Situation, die ebenfalls in   liegt.

Bestimme eine Indexfunktion  , 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   können auf den gleichen Index   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  , 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   ergibt sich durch Begrenzen der Figurenzahl. Mit   Steinen sind grob   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.

Gegeben:

  • Endliche Knotenmenge  
  • Menge von Kanten  
  • Anfangsbelegung:   mit  

  mit   bezeichnet für ein gegebenes   eine Belegung der Knoten mit Steinen der Spieler. Dabei bedeutet   einen schwarzen und   einen weißen Stein und   einen unbesetzten Knoten.   mit   ist die Belegung nach   Zügen. Zwei Belegungen sind gleich ( ), wenn  .

Für jede Belegung   mit   sei

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

Die beiden Spieler ziehen abwechselnd. Der Spieler, der nach   Zügen am Zug ist, kann entweder passen, dann ist  , oder er setzt auf den Knoten   seiner Wahl, und das führt zu der vorläufigen Belegung

 

Regelvarianten für die erlaubten Züge:

  1. Auf jeden Knoten in   darf gesetzt werden (außer die Ko-Regel verbietet es, siehe unten).
  2. Man darf nicht so setzen, dass   und  , das heißt   hat keine Freiheit, aber alle gegnerischen Steine haben eine Freiheit.
  3. Man darf nicht so setzen, dass  .
  4. Man darf nicht so setzen, dass nach der Behandlung von Steinen ohne Freiheit (siehe unten) noch Steine auf dem Brett sind (Belegung  ), die keine Freiheit haben.

Regelvarianten für die Behandlung von Steinen ohne Freiheit:

  1. Es werden alle Steine ohne Freiheit entfernt, d. h. wenn  , dann ist  .
  2. Gegnerische Steine ohne Freiheit werden entfernt; wenn es danach eigene Steine ohne Freiheit gibt, werden auch diese entfernt.
  3. Eigene Steine ohne Freiheit werden entfernt; wenn es danach gegnerische Steine ohne Freiheit gibt, werden auch diese entfernt.
  4. Gegnerische Steine ohne Freiheit werden zu eigenen Steinen.

Für   gilt  .

Ko-Regel: man darf nicht so setzen, dass die entstehende Belegung   gleich einer früheren Belegung mit dem gleichen Spieler am Zug ist, also  .