Shall we play a game? Tic-Tac-Toe mal anders

Für die einen ist es nichts weiter als Drei Gewinnt. Den anderen zaubert es ein nostalgisches Schmunzeln ins Gesicht, während sie an Joshua, die einsichtige KI aus dem Klassiker War Games denken. Für mich ist Tic-Tac-Toe ein schönes Beispiel dafür, wie unterschiedlich Softwareentwickler Strategien zur Lösung eines Problems entwickeln.

Für Tic-Tac-Toe gibt es 255.169 verschiedene Spielverläufe, von denen 131.185 mit einem Sieg des ersten Spielers enden, 77.904 mit einem Sieg des zweiten Spielers und 46.080 mit einem Unentschieden. (Quelle: Wikipedia)

Während die Anzahl an Spielverläufen somit übersichtlich ist, gestaltet sich die Entwicklung eines Tic-Tac-Toes in z.B. C# sogar noch einfacher, wenn es nur als Zweispieler (ohne selbst-lernende KI) gedacht ist. Doch während sich die meisten gleich als erstes die Frage danach stellen, wie sie das Spielbrett visualisieren und die Interaktion mit dem Spieler gestalten sollen (Windows Forms, HTML, WPF,…) ist dieses Spiel aus meiner Sicht einfach zu gut dafür geeignet, um sich über TDD Gedanken zu machen, als dass man es ignorieren könnte.

Klar. Ein Gameboard ist schnell entworfen und nach der Überlegung, dass es nicht mehr als neun Felder gibt, sind auch die ersten Tests schnell geschrieben.

GameBoardTests.cs

[TestClass]
public class GameBoardTests
{
  private GameBoard board = null;

  [TestInitialize]
  public void TestInitialize()
  {
    this.board = new GameBoard(null);
  }

  [TestMethod]
  [TestCategory("GameBoard")]      
  public void Fail_If_Greater_Than_Max()
  {
    Action action = () => board.Set(9);
    action.ShouldThrow<ArgumentOutOfRangeException>();
  }

  [TestMethod]
  [TestCategory("GameBoard")]
  public void Fail_If_Less_Than_Min()
  {
    Action action = () => board.Set(-1);
    action.ShouldThrow<ArgumentOutOfRangeException>();
  }
}
  

 

(Für die Prüfung erwarteter Exceptions kommt hier übrigens das Paket FluentAssertions zum Einsatz.)

GameBoard.cs

public class GameBoard
{
  public void Set(int pos)
  {
    if (pos < 0 || pos > 8) throw new ArgumentOutOfRangeException("The gameboard only consists of nine fields. Please set a new coin only on positions from zero to eight.");
  }
}       
  

 

Doch nun kommt schon die Frage: Angenommen, ein Spieler entscheidet sich für ein gültiges Feld. Wie genau soll das gespeichert werden? Und dann gleich die nächste Frage: Wie genau soll der Code ermitteln, ob jemand gewonnen hat?

Während nahezu jede Beispielimplementierung von Tic-Tac-Toe an dieser Stelle mit einem zweidimensionalen Array arbeitet und für die Gewinnermittlung verschachtelte If-Then-Else Abfragen nutzt, schlage ich einfach mal folgende Datentypen für die Verwaltung des Spielbrettes und der Gewinner-Kombinationen vor:

GameBoard.cs

private int board = 0;
private int[] winningCombinations = { 448, 56, 7, 292, 146, 73, 273, 84 };
  

 

Mehr braucht es eigentlich nicht. Genial, oder?

Die Idee ist im Prinzip recht simpel: Das Tic-Tac-Toe Spielfeld besteht aus 9 Feldern. Es ist also problemlos möglich, die Felder binär zu repräsentieren (000 000 000). Damit ließen sich auch die Gewinnerkombinationen einfach festlegen:

  • Horizontal: 111 000 000, 000 111 000, 000 000 111
  • Vertikal: 100 100 100, 010 010 010, 001 001 001
  • Diagonal: 100 010 001, 001 010 100

Mehr gibt es nicht. Umgerechnet in Dezimalwerte ergibt sich daraus die Liste von Zahlen wie oben im Array winningCombinations dargestellt.

Das ist in sofern pfiffig, als dass sich mit nur einer Schleife herausfinden lässt, ob ein Gewinner vorliegt. Dazu muss einfach nur über das obige Array iteriert und der jeweilige Wert mit dem Spielbrett bitverknüpft werden. Fertig.

Wer mitgedacht hat, wird spätestens jetzt sagen: Ja, aber! Es gibt zwei Spieler. Daraus ergeben sich drei Zustände und ein Bit kann nur zwei Zustände haben:

  • Feld unbesetzt
  • Feld von Spieler 1 besetzt
  • Feld von Spieler 2 besetzt

Ich sage: Richtig. Also speichern wir einfach für jeden Spieler in dem Integer ein separates Spielbrett. Das ergibt somit 18 Bit und ist problemlos abbildbar (Dezimal 262.143). Worauf nun lediglich geachtet werden muss, ist beim abwechselnden Setzen von X und O durch Spieler 1 und Spieler 2 a) das korrekte Spielbrett innerhalb des Integers zu erwischen und b) darin wiederum das korrekte Feld. Das ermöglichen Bit-Shift Operationen:

GameBoard.cs

public enum Player
{
  Player1,
  Player2
};

private int GetPosition(int pos, Player player){
  return (1 << (int)player * 9) << pos;
}
  

 

Die Frage von oben, wie sich denn nun die gewählten Felder der jeweiligen Spieler in der Integer Variablen festhalten lassen, ist damit leicht beantwortet:

GameBoard.cs

public void Set(int pos)
{  
  if (pos < 0 || pos > 8) throw new ArgumentOutOfRangeException("The gameboard only consists of nine fields. Please set a new coin only on positions from zero to eight.");

  this.board |= this.GetPosition(pos, this.ActivePlayer);
}
  

 

Da dieser Artikel mehr auf die etwas ungewöhnliche Art, ein Tic-Tac-Toe Spielbrett in C# abzubilden abzielt und weniger auf den testgetriebenen Ansatz, kommt an dieser Stelle der Hinweis: Bevor es zu dieser Implementierung gekommen ist, wurden zunächst Tests für das Setzen von Feldern, der Prüfung, ob ein Feld bereits belegt wurde und dann irgendwann das Prüfen verschiedener Gewinner-Konstellationen implementiert. Abschließend wurde der Spielverlauf selbst mittels Strategie-Muster entworfen und getestet.

Wichtig hierbei war natürlich die Entkopplung von Abhängigkeiten (wie z.B. Benutzereingabe und Bildschirmausgabe).

Um aber noch kurz zu zeigen, wie einfach basierend auf der hier vorgestellten Methode das Prüfen auf einen Gewinner ist, der Vollständigkeit halber noch der dazugehörige Code:

GameBoard.cs

public bool CheckWinner()
{
  foreach (int winningCombination in this.winningCombinations)
  {
    if (this.IsMatch(winningCombination))
    {
      return true;
    }
  }
  return false;
}

private bool IsMatch(int combination)
{
  return (this.board & combination << 9) == combination << 9 || // Check if player 2 won
    (this.board & combination ) == combination; // Check if player 1 won
}
  

 

Spannend, oder? Falls sich jemand für die Solution interessiert, lohnt sich ein entsprechender Kommentar. Auch der TDD Ansatz lässt sich hier ganz gut demonstrieren: In der ersten Iteration gab es noch zwei Integer-Variablen für die Repräsentation der Spielfelder für beide Spieler (und natürlich eine Menge Unit-Tests). Im Anschluss wurde der Game Code refaktorisiert, so dass nur noch eine Integer Variable wie oben gezeigt notwendig war. Die bestehenden Unit Tests konnten zeigen, dass die Logik (von außen betrachtet) dadurch keinen Schaden genommen hat.

Und so soll es schließlich ja auch sein.

Smile 

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading

Über die Autoren

Christian Jacob ist Leiter des Geschäftsbereiches Softwarearchitektur und -entwicklung und zieht als Trainer im Kontext der .NET Entwicklung sowie ALM-Themen Projekte auf links.

Marcus Jacob fokussiert sich auf die Entwicklung von Office-Addins sowie Windows Phone Apps und gilt bei uns als der Bezwinger von Windows Installer Xml.

Martin Kratsch engagiert sich für das Thema Projektmanagement mit dem Team Foundation Server und bringt mit seinen Java- und iOS-Kenntnissen Farbe in unser ansonsten von .NET geprägtes Team.

Aktuelle Kommentare

Comment RSS