markusberg.de

Dieses Projekt ist im Modul "Algorithmen und Datenstrukturen" im Studiengang "Bachelor Multimedia Engineering" entstanden und implementiert einige Algorithmen für die Spiele "Tic, Tac, Toe" und "UNO".

Tic Tac Toe

Zum Einstieg in die Programmierung in Matlab wird zunächst das bekannte Tic Tac Toe entwickelt, bevor es an die Programmierung von UNO geht. Dabei wird sich zunächst auf ein 3x3 Spielfeld beschränkt (wird später erweitert), welches durch eine Matrix repräsentiert wird, in der gesetzte Spielsteine durch eine 1 und freie Felder durch eine 0 dargestellt werden.

Die Ermittelung, ob jemand gewonnen hat, erfolgt über folgenden Algorithmus:

for n=1:feld_groesse %Spaltendurchlauf
 for m=1:feld_groesse %Zeilendurchlauf
  if F(m,n)==1
   if (F(m+1,n)==1 & F(m-1,n)==1) | %Spalte
    (F(m,n-1)==1 & F(m,n+1)==1) | %Zeile
    (F(m-1,n-1)==1 & F(m+1,n+1)==1) | %Diagonale
    (F(m-1,n+1)==1 & F(m+1,n-1)==1) %Diagonale
       gewonnen=1;
   end
  end
 end
end


In diesem Spiel sind die Varianten "Mensch gegen Mensch", "Mensch gegen Computer" und "Computer gegen Computer" möglich. In der grafischen Oberfläche wird jedoch nur die Variante "Mensch gegen Computer" umgesetzt. Die anderen Varianten sind per Konsole spielbar.

Um gegen den Computer spielen zu können, wird folgende einfache KI entwickelt - Grundgedanke ist folgender Entscheidungsfindungsprozess (Wo soll ich setzen?):

• Kann ich gewinnen? Wenn ja, Spielstein setzen! Wenn nein, weiter…
• Kann mein Gegenspieler gewinnen? Wenn ja, verhindern! Wenn nein, weiter…
• Gibt es einen Stein in der Spielfeldmitte? Wenn nein, setzen! Wenn ja, weiter…
• Ist das mein Stein in der Spielfeldmitte? Wenn nein, setze auf nächstes freies Feld! Wenn ja, weiter…
• Setze Stein auf freies Feld, wo das Feld gegenüber (vertikal, horizontal, diagonal) der Mitte nicht mit einem gegnerischen Stein besetzt ist. Wenn nicht möglich, setze auf nächstes freies Feld

UNO

Das Spiel wurde nach den Standardregeln programmiert: Eine Karte darf auf die Andere gelegt werden, wenn sie die gleiche Farbe oder die gleiche Zahl hat. Wenn eine +2 oder +4 Karte gespielt wurde, müssen entsprechend viele Karten aufgenommen (+2 auf +2 legen, ohne zuvor Karten aufgenommen zu haben, ist nach Standardspielregeln nicht erlaubt) und es darf keine Karte abgelegt werden.

UNO besteht aus 108 Karten:

• 2 x Zahlen 0..9 (0 nur einmal) / Farbe = 76 Karten
• 2 x Aussetzen/ Farbe = 8 Karten
• 2 x Rundendreher/ Farbe = 8 Karten
• 2 x 2 Aufnehmen (+2) / Farbe = 8 Karten
• 4 x Farbwahl = 4 Karten
• 4 x 4 Aufnehmen (+4) berechtigt auch zur Farbwahl = 4 Karten

Die Karten werden wie folgt codiert:

Farben:

• 1 rot
• 2 gelb
• 3 blau
• 4 grün
• 5 Farbwahl

Zahlen:

• 0..9 Zahlenkarte
• 10 Rundendreher
• 11 aussetzen
• 12 +2
• 13 Farbwahlkarte
• 14 Farbwahl

Zuerst werden alle Karten durch eine Schleife in eine Matrix geschrieben: Karten [Zahl,Farbe]. Anschließend werden die Karten gemischt, indem eine zweite Matrix (Stapel) erstellt wird, welche die Zeilennummern der ersten Matrix in zufälliger Reihenfolge enthält. Die Matrix Stapel enthält also „Zeiger“ (Zeilennummern) auf die Matrix Karten. Das „Mischen“ selbst entsteht über das Erzeugen von Zufallszahlen im Bereich 1..108, wobei keine Zahl doppelt vorkommen darf.

Die Hand des Spielers wird durch BubbleSort sortiert. Die Wertigkeit der Karte bezüglich der Reihenfolge wird wie folgt ermittelt: Farbe und Zahl werden zu einer Zahl zusammengefügt:
farbezahl=Karten(spieler,2)*100+Karten(spieler,1);…und anschließend sortiert: z.B. Farbe=2, Zahl=9 -> 209 (primäre Sortierung anhand der Hunderterstelle, sekundäre Sortierung anhand der Zehner- und Einerstelle. Es wird also zuerst nach der Farbe sortiert und innerhalb der Farbe nach der Zahl).

Die Karten in der GUI werden durch das Überlagern von Bildern erstellt.
Beispiel: Die Karten "Aussetzen" und "Rundendreher" gibt es in jeder Farbe. Theoretisch wären also 8 Bilder notwendig. Dies kann jedoch auf 6 bzw. eigentlich 2 Bilder (4 Farbkarten die sowieso gebraucht werden, 2 Masken) reduziert werden, wenn man eine Maske auf die Grundkarten (die 4 Farbkarten) legt. Dazu wird das Maskenbild als Negativ gespeichert. Nach Abzug der Maske vom Originalbild der Farbkarte entsteht ein neues Bild. Im Negativ sind die Bereiche, die keinen Einfluss auf das neue Bild haben sollen schwarz. Sie haben also den Farbwert 0 und haben bei einer Subtraktion keine Wirkung. Die andersfarbigen Werte werden vom Originalbild (das an dieser Stelle den Farbwert weiß (255) besitzt) abgezogen. Nun ist aus zwei Bildern ein Neues entstanden.

Anschließend werden Funktionen zur Ermittelung des Gewinners, zum Spielen von Karten (inkl. Sonderkarten), zum Aufnehmen von Karten sowie vier verschiedene KIs entwickelt.