Lektion 14 - Tic-Tac-Toe gegen den Computer

Erstellt von Frithjof Tue, 16 Oct 2007 20:24:00 GMT

Dein Computer gehorcht dir bisher prima bei der Ausführung des Rubyprogramms Tic-Tac-Toe. Er fühlt sich aber etwas einsam, weil er nicht wirklich mitspielen darf. Das wollen wir in dieser Lektion ändern – der Computer darf Tic-Tac-Toe spielen! Er wird in dieser Lektion aber noch kein Profi werden. Wir sind zufrieden, wenn er überhaupt mitspielt, auch wenn man ihn noch sehr gut besiegen kann.

Schauen wir uns an, wo wir den Computer als Gegner mit einbeziehen können. Die Methode play_2_spieler sorgt bisher dafür, dass zwei Spieler miteinander spielen können. Der Methode ist aber eigentlich ziemlich egal, ob die Eingaben für die Züge von einem menschlichen Spieler kommen, oder von einem Computerprogramm bestimmt werden. Du definierst dir also eine weitere Methode play_gegen_computer und änderst sie in geeigneter Weise ab.


# Lässt 1 Spieler gegen den Computer spielen
def play_gegen_computer(out, ein, zuege)
  spieler = [[:o, 'O'], [:x, 'X']]
  ergebnis = [false, nil]

end

Die Methode play_gegen_computer erhält beim Aufruf neben der Aus- und Eingabe die Liste der (noch leeren) Züge. Sie definiert dann die beiden Spieler in der Variablen spieler und das Ergebnis in der Variablen ergebnis wie bisher auch.

Es fehlt noch die Variable wer, die den aktuellen Spieler festlegt bzw. am Anfang den Spieler bestimmt, der mit dem Spiel beginnen darf. Beim Spiel gegen den Computer müssten wir festlegen, mit welchen Steinen (X oder O) der Computer spielen soll. Du fügst dafür eine Abfrage an den menschlichen Spieler ein und fragst ihn, mit welchem Stein er spielen möchte. Den anderen nimmt dann zwangsläufig der Computer. Wir legen außerdem fest, dass der menschliche Spieler immer anfangen darf.


# Lässt 1 Spieler gegen den Computer spielen
def play_gegen_computer(out, ein, zuege)
  spieler = [[:o, 'O'], [:x, 'X']]
  ergebnis = [false, nil]

  wer = nil
  out.print "Was spielst du, X oder O? " 
  eingabe = ein.gets.downcase.chomp
  wer = (eingabe == 'x') ? 1 : 0

  out.puts "Los geht's! Du spielst #{spieler[wer][1]}, und ich #{spieler[1^wer][1]}!" 
  out.puts "Du fängst an." 
end
Das Abfragen nach dem Spielstein erfolgt also in der Zeile:

  ...
  eingabe = ein.gets.downcase.chomp
  ...

ein ist die Eingabekonsole, auf der der menschliche Spieler etwas eintippt, gets holt sich die eingetippte Zeichenkette, downcase verwandelt die Eingabe in Kleinbuchstaben und chomp schneidet das unsichtbare Zeichen für die Entertaste ab.

Bis jetzt weißt du im Rubyprogramm aber immer noch nicht, ob der Spieler nun X (oder x) oder O (oder o) eingegeben hat. Das findest du erst mit der nächsten Zeile heraus:


  ...
  eingabe = ein.gets.downcase.chomp
  wer = (eingabe == 'x') ? 1 : 0
  ...

Mit dem ternären Operator entscheidest du, mit welchem Stein der menschliche Spieler nun tatsächlich anfängt. Hat er X (oder x) eingetippt, dann erhält er den Stein X, in allen anderen Fällen, also egal ob er O (oder o) oder irgendeine andere Zeichenkette eingetippt hat, erhält er den Stein O.

Na prima, jetzt wissen wir, mit welchem Stein der menschliche Spieler beginnt und können nun in die Spielschleife eintreten. Dort darf der menschliche Spieler zuerst seinen Zug eingeben, der Zug wird gemacht und das neue Spielfeld ausgeben. Danach macht sofort der Computer weiter mit seinem Zug. Und hier wird es dann spannend. Schauen wir uns also die fertige Methode play_gegen_computer an:


# Lässt 1 Spieler gegen den Computer spielen
def play_gegen_computer(out, ein, zuege)
  spieler = [[:o, 'O'], [:x, 'X']]
  ergebnis = [false, nil]

  wer = nil
  out.print "Was spielst du, X oder O? " 
  eingabe = ein.gets.downcase.chomp
  wer = (eingabe == 'x') ? 1 : 0

  out.puts "Los geht's! Du spielst #{spieler[wer][1]}, und ich #{spieler[1^wer][1]}!" 
  out.puts "Du fängst an." 

  while true
    # Der menschliche Spieler zuerst
    zug_okay = false
    until zug_okay
      out.print "#{spieler[wer][1]} ist am Zug: " 
      nummer = ein.gets.to_i
      break if nummer == 0
      spalte, zeile = nummer_in_spalte_zeile(nummer)
      zug_okay = zug_hinzu(spieler[wer][0], spalte, zeile, zuege)
    end
    spielfeld(out, zuege)
    ergebnis = ist_beendet?(zuege)
    beendet = ergebnis[0]
    break if (beendet or !zug_okay)
    wer += 1
    wer %= 2

    # Gleich den Zug des Computers anschließen
    zug_okay = false
    until zug_okay
      out.puts "\nJetzt bin ich dran!" 
      zug = computer_zug(zuege, wer)
      out.puts "Ich setze auf das Feld #{nummer_aus_spalte_zeile(zug[1], zug[2])}." 
      break if zug.nil?
      zug_okay = zug_hinzu(spieler[wer][0], zug[1], zug[2], zuege)
    end
    spielfeld(out, zuege)
    ergebnis = ist_beendet?(zuege)
    beendet = ergebnis[0]
    break if (beendet or !zug_okay)
    wer += 1
    wer %= 2
  end
  # Rückgabewerte: der aktuelle Spieler, falls er der Gewinner ist.
  gewinner = ergebnis[1]
  if gewinner != nil
    return spieler[wer]
  else
    return nil
  end
end

Der Rubycode für das Durchführen des Computerzuges ähnelt dem für den menschlichen Spieler ziemlich. Aber es gibt doch einige Unterschiede.

Die entscheidende Stelle ist


  ...
  zug = computer_zug(zuege, wer)
  ...

Hier wird eine Methode computer_zug aufgerufen, die die aktuelle Liste der Züge und den aktuellen Spielstein des Computers erhält. In dieser Methode kannst du dann eine beliebige Spielstrategie des Computers entwickeln. Ich zeige dir gleich zwei mögliche einfache Strategien, aber zunächst nehmen wir mal an, die Methode liefert uns einen Zug in der Form einer kleinen Liste


  [wer, spalte, zeile]

Der Computerzug liefert uns also nicht die Feldnummer, sondern gleich die Spalte und Zeile für die Platzierung des Spielsteins. Die Feldnummer ist ja vornehmlich zur erleichterten Eingabe für den menschlichen Spieler gedacht gewesen.

Nachdem der Computerzug erfolgreich hinzugefügt, das Spielfeld erneut ausgegeben und der nächste Spieler bestimmt wurde, ist der menschliche Spieler wieder am Zug, sofern das Spiel noch nicht vorbei ist (keine freien Felder mehr, oder jemand hat gewonnen).

Spielstrategien für den Computer

Schauen wir uns also nun wie besprochen ein paar Spielstrategien für den Computer an.


def computer_zug(zuege, wer)
  naiver_zug(zuege, wer)
end

def naiver_zug(zuege, wer)
  frei = freie_felder(zuege)
  zug = nil
  if frei.size > 0
    # Nehme das erste freie Feld
    spalte, zeile = nummer_in_spalte_zeile(frei[0])
    zug = [wer, spalte, zeile]
  end
  zug
end

def freie_felder(zuege)
  frei = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  for zug in zuege
    nummer = nummer_aus_spalte_zeile(zug[1], zug[2])
    frei.delete(nummer)
  end
  frei
end

Der Naive Zug

Die Methode computer_zug ruft die Methode naiver_zug auf, die sich ziemlich dumm anstellt. Sie nimmt nämlich einfach das nächste freie Feld. Dabei geht sie wie folgt vor.

Sie bestimmt zuerst die freien Felder mit Hilfe der Methode freie_felder.

  ...
  frei = freie_felder(zuege)
  ...
Wenn es mindestens ein freies Feld gibt, beschafft sie sich die Feldnummer des ersten Feldes, daraus die Spalte und Zeile und bildet damit die kleine Liste, die den Zug beschreibt.

  ...
  if frei.size > 0
    # Nehme das erste freie Feld
    spalte, zeile = nummer_in_spalte_zeile(frei[0])
    zug = [wer, spalte, zeile]
  end
  ...

Was meinst du, wie oft der Computer mit dieser Strategie gewinnt? Ich denke kaum, der menschliche Spieler braucht sich nicht sehr anzustengen, um zu gewinnen. Außerdem würde der menschliche Spieler nach ein paar Runden bemerken, dass der Computer immer auf das erst beste freie Feld setzt.

Wir brauchen eine andere Strategie.

Der Zufallszug

Damit der menschliche Spieler nicht so leicht die Spielstrategie des Computers durchschaut, müssen wir ein wenig Zufall mit ins Spiel bringen. Das ist zwar auch noch keine wirklich gute Strategie für den Computer, um zu gewinnen, aber immerhin, tut er wenigstens so.

Du kommentierst also zunächst den Aufruf der naiven Methode aus und rufst die neue Methode zufalls_zug auf.

Moment mal! Aber wie soll der Computer eine zufällige Entscheidung treffen? Soll er seine Augen schließen und mit dem Finger auf irgendein (freies) Feld zeigen? Wie geht das? Du hast bisher keinen Rubybefehl für den Zufall kennen gelernt. Im richtigen Leben gibt es viele Möglichkeiten, den Zufall entscheiden zu lassen: man wirft eine Münze, wer vorher auf Kopf gesetzt hat, gewinnt genau dann, wenn die Münze mit der Kopfseite oben zu liegen kommt. Oder du hast Stöckchen, von denen eines besonders kurz ist. Wer dieses zieht, gilt als der vom Zufall auserwählte.

Aber das hilft uns alles nicht weiter. Das Problem ist die Entscheidung für einen von mehreren möglichen Werten. Angenommen wir haben eine Liste der freien Felder vom aktuellen Spielstand. Der Computer müsste sich für einen Index in der Liste entscheiden. Beim naiven Zug nahm er immer den ersten Index 0. Wie bringen wir ihn dazu, mal den Index 0, mal den Index 3 oder 9 zu nehmen?

Ich zeige dir im folgenden meine Idee. Du kannst dir aber gerne auch eine andere Lösung überlegen. Der Zufallszug hier funktioniert so:


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

def zufalls_zug(zuege, wer)
  frei = freie_felder(zuege)
  zug = [wer, 0, 0]
  if frei.size > 0
    jetzt = Time.now
    sekunden = jetzt.sec
    index = sekunden % frei.size
    spalte, zeile = nummer_in_spalte_zeile(frei[index])
    zug = [wer, spalte, zeile]
  end
  zug
end
  1. Der Computer (das heißt das Rubyprogramm) bestimmt zuerst wieder die freien Felder.
  2. Dann schaut es nach der aktuellen Uhrzeit! Heh? Was hat die Uhrzeit mit dem Zufall zu tun? Die Idee ist, bei der Uhrzeit nur auf die Sekunden zu achten. Wenn du zu einem beliebigen Zeitpunkt auf deine Uhr schaust, ist es sehr unwahrscheinlich, dass du zweimal dieselbe Sekundenanzeige siehst. Erst wenn du genau nach einer Minute wieder auf die Uhr schaust, wird die selbe Sekunde angezeigt.
  3. Der Computer bestimmt also aus der aktuellen Uhrzeit nur die Sekunden.
  4. Dann teilt der die Sekunden durch die Anzahl der freien Felder und merkt sich von dieser Division nur den Rest. Der Rest ist immer kleiner als das wodurch man dividiert (Divisor).
  5. Somit kann der Computer diesen Rest als Index für die Liste der freien Felder ansehen.

Der Computer hat nun eine sehr einfache Möglichkeit, eine Zufallsentscheidung zwischen mehreren Möglichkeiten zu treffen. Es reicht allein die Uhrzeit.

Probiere die beiden Strategien, die naive und die mit Zufall, ein wenig aus, indem du abwechselnd eine Runde spielst und dabei jeweils die entsprechende Zeile in der Methode computer_zug aus- bzw. einkommentierst.

Bei dem Zufallszug hast du als menschlicher Spieler das Gefühl, der Computer denkt sich etwas bei seinen Zügen, weil du kein Muster erkennst. In Wahrheit denkt er sich natürlich überhaupt nichts. Es ist immer noch keine gute Strategie für ihn, um oft zu gewinnen.

Du kannst ja gerne eigene Strategien entwickeln. In der nächsten Lektion schauen wir uns gemeinsam eine bessere an. Aber für heute ist es denke ich genug.

Peter und Livia

Peter: Mir ist in der Methode play_gegen_computer folgende Zeile aufgefallen.

  ...
  out.puts "Los geht's! Du spielst #{spieler[wer][1]}, und ich #{spieler[1^wer][1]}!" 
  ...
Da verstehe ich nicht, was das mit dem kleinen Dach ^ zu bedeuten hat?

Livia: Das ist ein Bit-Operator. Er heißt XOR, was eXklusives OdeR bedeutet, also entweder oder. 1^wer wird also 1, nur dann, wenn wer gleich 0 ist. Es wird 0 genau dann und nur dann, wenn wer 1 ist. Somit kann man leicht zu einem gegebenen Spieler immer den anderen Spieler angeben.

Trackbacks

Verwenden Sie den folgenden Link zur Rückverlinkung von Ihrer eigenen Seite:
http://www.rubykids.de/trackbacks?month=10&year=2007&article_id=lektion-14-tic-tac-toe-gegen-den-computer&day=16

Meine Nachricht

Einen Kommentar hinterlassen

Comments