1 # Copyright (C) 2007 www.rubykids.de
  2 # tictactoe.rb
  3
  4 # Methode, die das Spielfeld im Ausgabebereich 'out' ausgibt
  5 # und dabei auch die in 'zuege' angegebenen Züge mit ausgibt.
  6 # Ist für ein Feld noch kein Zug erfolgt, dann wird die
  7 # Nummer des Feldes ausgegeben. Die Felder sind dabei von
  8 # links nach rechts und oben nach unten von 1 bis 9 fortlaufend
  9 # nummeriert.
 10 def spielfeld(out, zuege)
 11   out.puts  "/-----------\\" 
 12   out.print "| " 
 13
 14   print_zeile(out, 1, zuege)
 15
 16   out.puts " |" 
 17   out.puts  "|---|---|---|" 
 18   out.print "| " 
 19
 20   print_zeile(out, 2, zuege)
 21
 22   out.puts " |" 
 23   out.puts  "|---|---|---|" 
 24   out.print "| " 
 25
 26   print_zeile(out, 3, zuege)
 27
 28   out.puts " |" 
 29   out.puts "\\-----------/" 
 30 end
 31
 32 # Methode zum Ausgeben einer einzigen Zeile im Ausgabebereich 'out'.
 33 # Welche Zeile ausgegeben werden soll ist in 'zeile' übergeben.
 34 # Die Liste der Züge in 'zuege' brauchen wir hier, um das richtige
 35 # Symbol (X oder O) später in den Feldern ausgeben zu können,
 36 # oder die Nummer des Feldes.
 37 def print_zeile(out, zeile, zuege)
 38   spalte = 1
 39   1.upto(3) do 
 40     print_feld(spalte, zeile, zuege)
 41     out.print " | " unless spalte == 3
 42     spalte += 1
 43   end
 44 end
 45
 46 # Methode, die ein bestimmtes Feld ausgibt. Entweder wird
 47 # das Symbol für den Spieler ausgegeben, der das Feld besetzt hat,
 48 # oder es wird die laufende Nummer des Feldes ausgegeben.
 49 def print_feld(spalte, zeile, zuege)
 50   res = (spalte-1)*1 + (zeile-1)*3 + 1
 51   for z in zuege do
 52     if z[1] == spalte and z[2] == zeile
 53       res = (z[0] == :x ? "X" : "O")
 54       break
 55     end
 56   end
 57   print res
 58 end
 59
 60 # Methode zum Hinzufügen eines Zuges.
 61 def zug_hinzu(wer, spalte, zeile, zuege)
 62   # Nicht erlauben, wenn das Feld schon besetzt ist
 63   erlaubt = true
 64   zuege.each do |zug|
 65     if zug[1] == spalte and zug[2] == zeile
 66       # Einen Zug für diese Feld gibt es schon
 67       erlaubt = false
 68       break
 69     end
 70   end
 71   # Ein Zug besteht aus einer kleinen Liste mit genau 3 Elementen:
 72   # 1. Element 'wer': gibt den Spieler an, entweder :x oder :o
 73   # 2. Element 'spalte': die Spalte, in der der Zug gesetzt werden soll
 74   # 3. Element 'zeile': die Zeile, in die der Zug gesetzt werden soll
 75   zuege << [wer, spalte, zeile] if erlaubt
 76   erlaubt
 77 end
 78
 79 # Bestimmt aus der Nummer eines Feldes die Spalte und Zeile
 80 # Angenommen Spalte und Zeilen würden von 0 bis 2 gezählt werden.
 81 # Dann ergeben sich folgende Formeln:
 82
 83 # Spalte, Zeile => Nummer => Formel
 84 # ----------------------------------------
 85 # 0,0           => 1      => 0*1 + 0*3 + 1
 86 # 1,0           => 2      => 1*1 + 0*3 + 1
 87 # 2,0           => 3      => 2*1 + 0*3 + 1
 88 # 0,1           => 4      => 0*1 + 1*3 + 1
 89 # 1,1           => 5      => 1*1 + 1*3 + 1
 90 # 2,1           => 6      => 2*1 + 1*3 + 1
 91 # 0,2           => 7      => 0*1 + 2*3 + 1
 92 # 1,2           => 8      => 1*1 + 2*3 + 1
 93 # 2,2           => 9      => 2*1 + 2*3 + 1
 94 def nummer_in_spalte_zeile(num)
 95   spalte = ((num-1) % 3)
 96   zeile = (((num + 2 ) / 3 ) - 1)
 97   [spalte+1, zeile+1]
 98 end
 99
100 # Berechnet die Feldnummer aus gegebener Spalte und Zeile
101 # Tabelle für Zuordnung siehe oben bei Methode nummer_in_spalte_zeile.
102 def nummer_aus_spalte_zeile(spalte, zeile)
103   nummer = 0
104   nummer = (spalte-1)*1 + (zeile-1)*3 + 1 unless (spalte.nil? or zeile.nil?)
105   nummer
106 end
107
108 # Stellt fest, ob es einen Gewinner gibt
109 def the_winner_is(zuege)
110   reihen = [
111     [1, 2, 3],
112     [4, 5, 6],
113     [7, 8, 9],
114
115     [1, 4, 7],
116     [2, 5, 8],
117     [3, 6, 9],
118
119     [1, 5, 9],
120     [3, 5, 7],
121   ]
122
123
124   # Variable für den Gewinner
125   the_winner = nil
126
127   # Für beide Spieler testen
128   for spieler in [:o, :x]
129     felder_besetzt = []
130
131     for zug in zuege
132       if zug[0] == spieler
133         feld = nummer_aus_spalte_zeile(zug[1], zug[2])
134         felder_besetzt << feld
135       end
136     end
137
138     # In felder_besetzt stehen die Felder, die vom aktuellen Spieler
139     # belegt sind. Die können wir nun für alle Reihen testen.
140     for reihe in reihen
141       gewonnen = true
142       for feld in reihe
143         # gewonnen wird falsch (false), wenn das aktuelle Feld der
144         # Reihe nicht besetzt ist.
145         gewonnen = (gewonnen and felder_besetzt.include?(feld))
146         break if gewonnen == false # in der Reihe kein Gewinn mehr
147       end
148       if gewonnen
149         the_winner = spieler
150         break # Gewinner gefunden, aufhören weiter zu suchen
151       end
152     end
153
154     # Wenn es einen Gewinner gibt, für den nächsten gar nicht erst
155     # mehr versuchen, denn dieser kann nicht auch gleichzeitig
156     # gewonnen haben, das hätten wir beim vorherigen Zug bereits
157     # bemerkt.
158     break if the_winner != nil
159   end
160
161   the_winner
162 end
163
164
165 # Schaut nach, ob das Spiel schon aus ist
166 def ist_beendet?(zuege)
167   alle_zuege_gemacht = zuege.nil? ? false : zuege.size >= 9
168   gewinner = the_winner_is(zuege)
169   # Zwei Rückgabewerte in einer Liste:
170   # Erster Wert: gibt an (true, false), ob das Spiel aus ist
171   # Zweiter Wert: der Gewinner (oder nil, falls es keinen gibt)
172   [(alle_zuege_gemacht or (gewinner != nil)), gewinner]
173 end
174
175 # Lässt 2 Spieler miteinander spielen
176 def play_2_spieler(out, ein, zuege)
177   spieler = [[:o, 'O'], [:x, 'X']]
178   wer = 0
179   ergebnis = [false, nil]
180   while true
181     zug_okay = false
182     until zug_okay
183       out.print "#{spieler[wer][1]} ist am Zug: "
184       nummer = ein.gets.to_i
185       break if nummer == 0
186       spalte, zeile = nummer_in_spalte_zeile(nummer)
187       zug_okay = zug_hinzu(spieler[wer][0], spalte, zeile, zuege)
188     end
189     spielfeld(out, zuege)
190     ergebnis = ist_beendet?(zuege)
191     beendet = ergebnis[0]
192     break if (beendet or !zug_okay)
193     wer += 1
194     wer %= 2
195   end
196   # Rückgabewerte: der aktuelle Spieler, falls er der Gewinner ist.
197   gewinner = ergebnis[1]
198   if gewinner != nil
199     return spieler[wer]
200   else
201     return nil
202   end
203 end
204
205 def zufalls_zug(zuege, spieler, wer)
206   frei = freie_felder(zuege)
207   zug = [wer, 0, 0]
208   if frei.size > 0
209     jetzt = Time.now
210     sekunden = jetzt.sec
211     index = sekunden % frei.size
212     spalte, zeile = nummer_in_spalte_zeile(frei[index])
213     zug = [wer, spalte, zeile]
214   end
215   zug
216 end
217
218 def naiver_zug(zuege, spieler, wer)
219   frei = freie_felder(zuege)
220   zug = nil
221   if frei.size > 0
222     # Nehme das erste freie Feld
223     spalte, zeile = nummer_in_spalte_zeile(frei[0])
224     zug = [wer, spalte, zeile]
225   end
226   zug
227 end
228
229 def freie_felder(zuege)
230   frei = [1, 2, 3, 4, 5, 6, 7, 8, 9]
231   for zug in zuege
232     nummer = nummer_aus_spalte_zeile(zug[1], zug[2])
233     frei.delete(nummer)
234   end
235   frei
236 end
237
238 # Bestimmt den Status einer Reihe in der aktuellen Spielsituation.
239 # Rückgabewerte sind eine Liste der besetzten und der freien Felder.
240 # Die Liste der besetzten Felder ist aufgeteilt nach Spielern und
241 # in einem Hash nach folgender Form organisiert:
242 #
243 #  besetzt = {
244 #    :o => Liste der von O besetzten Felder,
245 #    :x => Liste der von X besetzten Felder
246 #  }
247 #  
248 def reihen_status(zuege, reihe)
249   # Welche Felder sind noch frei?
250   frei_alle = freie_felder(zuege)
251   frei = []
252   for feld in reihe
253     if frei_alle.include?(feld)
254       frei << feld
255     end
256   end
257   
258   # Welche Felder sind vom wem besetzt? Da ist etwas mehr zu tun.
259   besetzt = {:o => [], :x => []}
260   for zug in zuege
261     # Liegt der zug in der fraglichen Reihe?
262     feld = nummer_aus_spalte_zeile(zug[1], zug[2])
263     if reihe.include?(feld)
264       # Wer besetzt es?
265       if zug[0] == :x
266         # X besetzt das Feld, nehme das Feld in die Besetztliste von X auf
267         besetzt[:x] << feld
268       elsif zug[0] == :o
269         # O besetzt das Feld, nehme das Feld in die Besetztliste von O auf
270         besetzt[:o] << feld
271       end
272     end
273   end
274   [besetzt, frei]
275 end
276
277 # Implementiert einige Regeln, mit deren Hilfe man sehr wahrscheinlich
278 # nicht verliert.
279 #  zuege   - Liste der Züge
280 #  spieler - Liste mit beiden Spielern
281 #  wer     - Index in der Spielerliste, der angibt, wer gerade am Zug ist
282 def intelligenter_zug(zuege, spieler, wer)
283   reihen = [
284     [1, 2, 3],
285     [4, 5, 6],
286     [7, 8, 9],
287
288     [1, 4, 7],
289     [2, 5, 8],
290     [3, 6, 9],
291
292     [1, 5, 9],
293     [3, 5, 7],
294   ]
295   
296   zug = nil
297   
298   # 1. Regel: Zuerst nach einer Gewinnsituation suchen
299   for reihe in reihen
300     besetzt, frei = reihen_status(zuege, reihe)
301     
302     # Wenn der aktuelle Spieler in einer Reihe bereits zwei Felder
303     # besetzt hält und das dritte frei ist, dann natürlich das nehmen
304     if (frei.size == 1) and (besetzt[spieler[wer][0]].size == 2)
305       zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
306       break # nicht weitersuchen
307     end
308   end
309   
310   if zug.nil?
311     # 2. Regel: Suche dann nach den Reihen, in denen der Gegner bereits
312     # genau 2 Felder besetzt hat und das dritte Feld noch frei ist.
313     for reihe in reihen
314       besetzt, frei = reihen_status(zuege, reihe)
315         
316       # Gefährlich, wenn Gegner zwei besetzt hält. Wie in der vorherigen
317       # Lektion gelernt, erhält man zum Index des aktuellen Spielers
318       # in der Spielerliste den Index des Gegners mit der Bitoperation 1^wer
319       if (frei.size == 1) and (besetzt[spieler[1^wer][0]].size == 2)
320         # Jetzt muss der Spieler unbedingt das eine freie Feld besetzen!
321         # Andernfalls kann der Gegner im nächsten Zug gewinnen.
322         zug = [spieler[wer][0], nummer_in_spalte_zeile(frei[0])].flatten
323         break # nicht weitersuchen
324       end
325     end
326   end
327   
328   # 3. Regel: Immer in die Mitte setzten, falls dort frei ist
329   if zug.nil?
330     frei  = freie_felder(zuege)
331     mitte = 5
332     if frei.include?(mitte)
333       zug = [spieler[wer][0], nummer_in_spalte_zeile(mitte)].flatten
334     end
335   end
336   
337   # 4. Regel: Verteidige gegenüberliegende Ecke
338   frei  = freie_felder(zuege)
339   ecken = {
340     1 => 0, # links oben
341     3 => 0, # rechts oben
342     7 => 0, # links unten
343     9 => 0  # rechts unten
344   }
345   for z in zuege
346     feld = nummer_aus_spalte_zeile(z[1], z[2])
347     # Gegner besetzt die Ecke, wenn:
348     #   feld ist eine Ecke  und  Gegner besetzt sie
349     if (ecken[feld] != nil) and (z[0] == spieler[1^wer][0])
350       # Markiere Ecke als vom Gegner besetzt
351       ecken[feld] = 1
352     end
353   end
354   
355   if zug.nil?
356     # Wenn Ecke 1 besetzt, dann setze auf 9, oder umgekehrt (sofern frei).
357     # Wenn Ecke 3 besetzt, dann setze auf 7, oder umgekehrt (sofern frei).
358     gegen_ecken = [[1, 9], [9, 1], [3, 7], [7, 3]]
359     for ecken_paar in gegen_ecken
360       if (ecken[ecken_paar[0]] > 0) and (frei.include?(ecken_paar[1]))
361         zug = [spieler[wer][0], nummer_in_spalte_zeile(ecken_paar[1])].flatten
362         break # nicht weitersuchen
363       end
364     end
365   end
366
367   # 5. Regel: Setze in irgendeine freie Ecke.
368   # Verwende Variablen 'frei' und 'ecken' von oben
369   if zug.nil?
370     for ecke in ecken.keys
371       if frei.include?(ecke)
372         zug = [spieler[wer][0], nummer_in_spalte_zeile(ecke)].flatten
373         break # nicht weitersuchen
374       end
375     end
376   end
377
378   # Andernfalls Zufallszug machen
379   if zug.nil?
380     zug = zufalls_zug(zuege, spieler, wer)
381   end
382   
383   zug
384 end
385
386 def computer_zug(zuege, spieler, wer)
387   #naiver_zug(zuege, spieler, wer)
388   #zufalls_zug(zuege, spieler, wer)
389   intelligenter_zug(zuege, spieler, wer)
390 end
391
392 # Lässt 1 Spieler gegen den Computer spielen
393 def play_gegen_computer(out, ein, zuege)
394   spieler = [[:o, 'O'], [:x, 'X']]
395   ergebnis = [false, nil]
396
397   wer = nil
398   out.print "Was spielst du, X oder O? "
399   eingabe = ein.gets.downcase.chomp
400   wer = (eingabe == 'x') ? 1 : 0
401
402   out.print "Los geht's! Du spielst #{spieler[wer][1]}, und ich #{spieler[1^wer][1]}!"
403   out.puts " Du faengst an."
404
405   while true
406     # Der menschliche Spieler zuerst
407     zug_okay = false
408     until zug_okay
409       out.print "#{spieler[wer][1]} ist am Zug: "
410       nummer = ein.gets.to_i
411       break if nummer == 0
412       spalte, zeile = nummer_in_spalte_zeile(nummer)
413       zug_okay = zug_hinzu(spieler[wer][0], spalte, zeile, zuege)
414     end
415     spielfeld(out, zuege)
416     ergebnis = ist_beendet?(zuege)
417     beendet = ergebnis[0]
418     break if (beendet or !zug_okay)
419     wer += 1
420     wer %= 2
421
422     # Gleich den Zug des Computers anschließen
423     zug_okay = false
424     until zug_okay
425       out.puts "\nJetzt bin ich dran!"
426       zug = computer_zug(zuege, spieler, wer)
427       break if zug.nil?
428       out.puts "Ich setze auf das Feld #{nummer_aus_spalte_zeile(zug[1], zug[2])}."
429       zug_okay = zug_hinzu(spieler[wer][0], zug[1], zug[2], zuege)
430     end
431     spielfeld(out, zuege)
432     ergebnis = ist_beendet?(zuege)
433     beendet = ergebnis[0]
434     break if (beendet or !zug_okay)
435     wer += 1
436     wer %= 2
437   end
438   # Rückgabewerte: der aktuelle Spieler, falls er der Gewinner ist.
439   gewinner = ergebnis[1]
440   if gewinner != nil
441     return spieler[wer]
442   else
443     return nil
444   end
445 end
446