Lektion 15 - Tic-Tac-Toe, Computer unschlagbar? 2

Erstellt von Frithjof Thu, 25 Oct 2007 23:03:00 GMT

Dein Computer verliert noch häufig beim Tic-Tac-Toe. Das wollen wir mit dieser Lektion ändern. Du machst ihn zu einem stärkeren Gegner, der bei der Wahl seiner Züge auch den aktuellen Spielstand mit berücksichtigt. Wo er mit dem nächsten Zug gewinnen kann, wird er es tun, andernfalls sucht er sich gute Felder für seine Züge aus.

In Lektion 14 führten wir die Methode computer_zug ein. Zunächst mit den beiden Strategien naiver Zug und Zufallszug (die man eigentlich gar nicht als Strategien bezeichnen kann). An dieser Stelle fügst du heute eine neue Strategie intelligenter_zug hinzu. Innerhalb dieser Methode werden wir einige der Spielstrategien implementieren, die den Computer (fast) unschlagbar machen.

Tic-Tac-Toe ist ein aus Sicht des Computers recht einfaches Spiel, verglichen etwa mit Schach. Theoretisch wäre es für den Computer möglich, zu jedem aktuellen Spielstand den optimalen Zug zu wählen, der ihn vor dem Verlieren bewahrt, also höchstens für ihn mit einem Unentschieden endet. Dazu müsste er alle Spielausgänge berechnen, die vom aktuellen Spielstand aus möglich sind, je nachdem, welcher Zug als nächstes gewählt werden würde. Allerdings ist dieses Vorgehen nicht ganz so einfach zu implementieren wie es sich anhört. Und gerade weil Tic-Tac-Toe ein recht einfaches Spiel ist, reicht es aus, ein paar Regeln zu implementieren, die den Computer ausreichend stark machen. Wir werden folgende Regeln implementieren:

  1. Kannst du 3 Steine in einer Reihe setzen, dann tue es.
  2. Kann dein Gegner 3 Steine in einer Reihe setzen, dann verhindere es indem du deinen Stein in diese Reihe setzt.
  3. Ist die Mitte noch frei, dann setzte in die Mitte.
  4. Hat der Gegner einen Stein in einer Ecke und ist die gegenüberliegende Ecke noch frei, dann setze in diese freie Ecke.
  5. Ist eine Ecke frei, dann setze in die Ecke.

Ist der Computer an der Reihe, geht er alle Regeln in obiger Reihenfolge durch und wählt entsprechend der ersten zutreffenden Regel seinen Zug. Hat er sich am Ende der letzten Regel immer noch nicht für einen Zug entscheiden können, so macht er schließlich einen Zufallszug.

Regel 1: Gewinne!

Hier ist die Methode intelligenter_zug mit der Implementierung der ersten Regel. Der Computer versucht zu gewinnen. Falls das nicht geht, macht er einen Zufallszug.

Um zu entscheiden, ob er überhaupt gewinnen kann, muss er für jede Reihe nachschauen, ob dort Felder von ihm besetzt sind, ob es genau 2 sind und ob das dritte Feld frei ist (also nicht schon vom Gegner besetzt ist). Das Ermitteln der besetzten und freien Felder einer Reihe übernimmt die Methode reihen_status. Sie liefert die Liste der freien Felder in einer Reihe (maximal 3 Felder können in einer Reihe frei sein) und einen Hash, der für jeden Spieler eine Liste mit den von ihm besetzten Feldern in der Reihe festhält.


def computer_zug(zuege, spieler, wer)
  #naiver_zug(zuege, spieler, wer)
  #zufalls_zug(zuege, spieler, wer)
  intelligenter_zug(zuege, spieler, wer)
end

# Implementiert einige Regeln, mit deren Hilfe man sehr wahrscheinlich
# nicht verliert.
#  zuege   - Liste der Züge
#  spieler - Liste mit beiden Spielern
#  wer     - Index in der Spielerliste, der angibt, wer gerade am Zug ist
def intelligenter_zug(zuege, spieler, wer)
  reihen = [
    [1, 2, 3], [4, 5, 6], [7, 8, 9],
    [1, 4, 7], [2, 5, 8], [3, 6, 9],
    [1, 5, 9], [3, 5, 7],
  ]

  zug = nil

  # 1. Regel: Zuerst nach einer Gewinnsituation suchen
  for reihe in reihen
    besetzt, frei = reihen_status(zuege, reihe)

    # Wenn der aktuelle Spieler in einer Reihe bereits zwei Felder
    # besetzt hält und das dritte frei ist, dann natürlich das nehmen
    if (frei.size == 1) and (besetzt[spieler[wer][0]].size == 2)
      zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
      break # nicht weitersuchen
    end
  end

  # Andernfalls Zufallszug machen
  if zug.nil?
    zug = zufalls_zug(zuege, spieler, wer)
  end

  zug
end

# Bestimmt den Status einer Reihe in der aktuellen Spielsituation. 
# Rückgabewerte sind eine Liste der besetzten und der freien Felder.
# Die Liste der besetzten Felder ist aufgeteilt nach Spielern und
# in einem Hash nach folgender Form organisiert:
#
#  besetzt = {
#    :o => Liste der von O besetzten Felder, 
#    :x => Liste der von X besetzten Felder
#  }
#   
def reihen_status(zuege, reihe)
  # Welche Felder sind noch frei?
  frei_alle = freie_felder(zuege)
  frei = []
  for feld in reihe
    if frei_alle.include?(feld)
      frei << feld
    end
  end

  # Welche Felder sind vom wem besetzt? Da ist etwas mehr zu tun.
  besetzt = {:o => [], :x => []}
  for zug in zuege
    # Liegt der zug in der fraglichen Reihe?
    feld = nummer_aus_spalte_zeile(zug[1], zug[2])
    if reihe.include?(feld)
      # Wer besetzt es?
      if zug[0] == :x
        # X besetzt das Feld, nehme das Feld in die Besetztliste von X auf
        besetzt[:x] << feld
      elsif zug[0] == :o
        # O besetzt das Feld, nehme das Feld in die Besetztliste von O auf
        besetzt[:o] << feld
      end
    end
  end
  [besetzt, frei]
end

Regel 2: Lass den Gegner nicht gewinnen!

Die zweite Regel versucht zu verhindern, dass der Gegner in seinem nächsten Zug eine Reihe mit seinen 3 Steinen vervollständigt und gewinnt. Im Prinzip ist hier genau das gleiche zu tun wie in Regel 1 nur mit dem Unterschied, dass die Prüfung der zwei besetzten Felder natürlich für den Gegner erfolgt.


...
  if zug.nil?
    # 2. Regel: Suche dann nach den Reihen, in denen der Gegner bereits
    # genau 2 Felder besetzt hat und das dritte Feld noch frei ist.
    for reihe in reihen
      besetzt, frei = reihen_status(zuege, reihe)

      # Gefährlich, wenn Gegner zwei besetzt hält. Wie in der vorherigen
      # Lektion gelernt, erhält man zum Index des aktuellen Spielers
      # in der Spielerliste den Index des Gegners mit der Bitoperation 1^wer
      if (frei.size == 1) and (besetzt[spieler[1^wer][0]].size == 2)
        # Jetzt muss der Spieler unbedingt das eine freie Feld besetzen!
        # Andernfalls kann der Gegner im nächsten Zug gewinnen.
        zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
        break # nicht weitersuchen
      end
    end
  end
...

Regel 3: Spiel die Mitte!

Die Mitte ist immer das Feld mit der Nummer 5. Das ist also ziemlich einfach zu implementieren. Wenn Feld 5 frei ist, dann nimmt der Computer dieses.


...
  # 3. Regel: Immer in die Mitte setzten, falls dort frei ist
  if zug.nil?
    frei  = freie_felder(zuege)
    mitte = 5
    if frei.include?(mitte)
      zug = [spieler[wer][0], nummer_in_spalte_zeile(mitte)].flatten
    end
  end
...

Regel 4: Spiel die gegenüberliegende Ecke!

Am kompliziertesten scheint es, eine dem Gegner gegenüberliegende freie Ecke zu identifizieren.

Hier bestimmen wir zunächst alle Ecken, die vom Gegner besetzt werden und merken uns dies für jede Ecke (Felder 1, 3, 7 oder 9) in einem Hash, wobei 0 bedeuten soll, die Ecke ist frei, und 1 bedeutet sie ist vom Gegner besetzt.

Dann prüfen wir für alle besetzten Ecken, ob die gegenüberliegende Ecke frei ist und wählen die erste dieser Ecken für den Computer als seinen Zug aus.


...
  # 4. Regel: Verteidige gegenüberliegende Ecke
  frei  = freie_felder(zuege)
  ecken = {
    1 => 0, # links oben
    3 => 0, # rechts oben
    7 => 0, # links unten
    9 => 0  # rechts unten
  }
  for z in zuege
    feld = nummer_aus_spalte_zeile(z[1], z[2])
    # Gegner besetzt die Ecke, wenn:
    #   feld ist eine Ecke  und  Gegner besetzt sie
    if (ecken[feld] != nil) and (z[0] == spieler[1^wer][0])
      # Markiere Ecke als vom Gegner besetzt
      ecken[feld] = 1
    end
  end

  if zug.nil?
    # Wenn Ecke 1 besetzt, dann setze auf 9, oder umgekehrt (sofern frei).
    # Wenn Ecke 3 besetzt, dann setze auf 7, oder umgekehrt (sofern frei).
    gegen_ecken = [[1, 9], [9, 1], [3, 7], [7, 3]]
    for ecken_paar in gegen_ecken
      if (ecken[ecken_paar[0]] > 0) and (frei.include?(ecken_paar[1]))
        zug = [spieler[wer][0], nummer_in_spalte_zeile(ecken_paar[1])].flatten
        break # nicht weitersuchen
      end
    end
  end
...

Regel 5: Spiel eine Ecke!

Die letzte Regel sucht in allen Ecken nach der ersten freien und verwendet diese für den Zug des Computers.


...
  # 5. Regel: Setze in irgendeine freie Ecke.
  # Verwende Variablen 'frei' und 'ecken' von oben
  if zug.nil?
    for ecke in ecken.keys
      if frei.include?(ecke)
        zug = [spieler[wer][0], nummer_in_spalte_zeile(ecke)].flatten
        break # nicht weitersuchen
      end
    end
  end
...

Hier nochmals die gesamte Methode intelligenter_zug:


# Implementiert einige Regeln, mit deren Hilfe man sehr wahrscheinlich
# nicht verliert.
#  zuege   - Liste der Züge
#  spieler - Liste mit beiden Spielern
#  wer     - Index in der Spielerliste, der angibt, wer gerade am Zug ist
def intelligenter_zug(zuege, spieler, wer)
  reihen = [
    [1, 2, 3], [4, 5, 6], [7, 8, 9], 
    [1, 4, 7], [2, 5, 8], [3, 6, 9], 
    [1, 5, 9], [3, 5, 7],
  ]

  zug = nil

  # 1. Regel: Zuerst nach einer Gewinnsituation suchen
  for reihe in reihen
    besetzt, frei = reihen_status(zuege, reihe)

    # Wenn der aktuelle Spieler in einer Reihe bereits zwei Felder
    # besetzt hält und das dritte frei ist, dann natürlich das nehmen
    if (frei.size == 1) and (besetzt[spieler[wer][0]].size == 2)
      zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
      break # nicht weitersuchen
    end
  end

  if zug.nil?
    # 2. Regel: Suche dann nach den Reihen, in denen der Gegner bereits
    # genau 2 Felder besetzt hat und das dritte Feld noch frei ist.
    for reihe in reihen
      besetzt, frei = reihen_status(zuege, reihe)

      # Gefährlich, wenn Gegner zwei besetzt hält. Wie in der vorherigen
      # Lektion gelernt, erhält man zum Index des aktuellen Spielers
      # in der Spielerliste den Index des Gegners mit der Bitoperation 1^wer
      if (frei.size == 1) and (besetzt[spieler[1^wer][0]].size == 2)
        # Jetzt muss der Spieler unbedingt das eine freie Feld besetzen!
        # Andernfalls kann der Gegner im nächsten Zug gewinnen.
        zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
        break # nicht weitersuchen
      end
    end
  end

  # 3. Regel: Immer in die Mitte setzten, falls dort frei ist
  if zug.nil?
    frei  = freie_felder(zuege)
    mitte = 5
    if frei.include?(mitte)
      zug = [spieler[wer][0], nummer_in_spalte_zeile(mitte)].flatten
    end
  end

  # 4. Regel: Verteidige gegenüberliegende Ecke
  frei  = freie_felder(zuege)
  ecken = {
    1 => 0, # links oben
    3 => 0, # rechts oben
    7 => 0, # links unten
    9 => 0  # rechts unten
  }
  for z in zuege
    feld = nummer_aus_spalte_zeile(z[1], z[2])
    # Gegner besetzt die Ecke, wenn:
    #   feld ist eine Ecke  und  Gegner besetzt sie
    if (ecken[feld] != nil) and (z[0] == spieler[1^wer][0])
      # Markiere Ecke als vom Gegner besetzt
      ecken[feld] = 1
    end
  end

  if zug.nil?
    # Wenn Ecke 1 besetzt, dann setze auf 9, oder umgekehrt (sofern frei).
    # Wenn Ecke 3 besetzt, dann setze auf 7, oder umgekehrt (sofern frei).
    gegen_ecken = [[1, 9], [9, 1], [3, 7], [7, 3]]
    for ecken_paar in gegen_ecken
      if (ecken[ecken_paar[0]] > 0) and (frei.include?(ecken_paar[1]))
        zug = [spieler[wer][0], nummer_in_spalte_zeile(ecken_paar[1])].flatten
        break # nicht weitersuchen
      end
    end
  end

  # 5. Regel: Setze in irgendeine freie Ecke.
  # Verwende Variablen 'frei' und 'ecken' von oben
  if zug.nil?
    for ecke in ecken.keys
      if frei.include?(ecke)
        zug = [spieler[wer][0], nummer_in_spalte_zeile(ecke)].flatten
        break # nicht weitersuchen
      end
    end
  end

  # Andernfalls Zufallszug machen
  if zug.nil?
    zug = zufalls_zug(zuege, spieler, wer)
  end

  zug
end

Peter und Livia

Peter: Was bedeutet das komische flatten?

...
  zug = [spieler[wer][0], nummer_in_spalte_zeile(ecke)].flatten
...

Livia: Das ist ein Befehl für eine Liste (oder Array) und bedeutet zu deutsch verflachen. Damit kannst du eine verschachtelte Liste (eine Liste, die andere Listen als Elemente enthält) zu einer einzigen Liste verflachen, die nur noch Elemente enthält, die selbst keine Listen sind.

Zum Beispiel ist liste eine Liste mit 4 Elementen, von denen das vierte Element selbst wieder eine Liste aus 4 Elemente ist, bei der wiederum das vierte Element eine Liste, nun aber nur mit 3 Elementen ist:


...
  liste  = [1, 2, 3, [eins, zwei, drei, ["Sonne", "Mond", "Sterne"]]]
  liste_flach = liste.flatten
...

Die verflachte Liste liste_flach besteht nun also aus 9 Elementen:


...
  [1, 2, 3, eins, zwei, drei, "Sonne", "Mond", "Sterne"]
...
Trackbacks

Verwenden Sie den folgenden Link zur Rückverlinkung von Ihrer eigenen Seite:
http://www.rubykids.de/trackbacks?month=10&year=2007&article_id=computer-gewinnt&day=26

Meine Nachricht

Einen Kommentar hinterlassen

  1. aspire about 1 year later:
    der computer ist noch unschlagbar, wenn man anfängt: -Kreuz oben link -Kreuz unten rechts -Kreuz unten links Und schon hat man gewonnen :/
  2. Cracer over 2 years later:
    Tolles Tutorial, mir ist allerdings aufgefallen, das dieser Alghorhytmus eine kleine Schwachstelle hat: Wenn ich beginne und zuerst in eine Ecke setze, setzt das Programm in die Mitte. Wenn ich nun in die gegenüberliegende Ecke setze, setzt das Programm in eine freie Ecke (oder habe ich das falsch verstanden?). Ich setzt nun logischerweise in die verbleibende Ecke, weil das Programm sonst 3 in der Diagonalen hätte. Nun habe ich aber 2 Möglichkeiten um das Spiel zu gewinnen, das Programm verhindert die Eine und ich kann nun 3 in einer Reihe setzen. Möglicher Ablauf (x ist der Spieler, o der Computer): x auf 1, o auf 5, x auf 9, o auf 3, x auf 7, o auf 4 oder 8, x auf 8 oder 4, Spiel zu Ende). Verbesserungsvorschlag: Nach dem 3. Zug (natürlich nur bei dieser Spielweise) muss der Computer auf eine ganze Zahl zwischen 2 und 8 setzen. Cracer
Comments