Ergebnis 1 bis 1 von 1

Baum-Darstellung

  1. #1
    Der mit Anatidaephobie Avatar von blackberry
    Registriert seit
    11.07.2008
    Beiträge
    2.350

    Standard [C] TicTacToe (mit ncurses)

    Hi,

    habe mal ncurses ausprobiert.

    Bedienung:
    Einfach starten und mit den Pfeiltasten navigieren.
    Markierungen setzt man mit ENTER, oder durch drücken der Zahlen 0 bis 8.
    Zum Verlassen einfach die Leertaste drücken.

    Das Spiel neu starten kann man nicht direkt (war mir zu doof die paar Zeilen auch noch zu tippen), also muss man eben das Spiel mit der Leertaste beenden und nochmal starten.

    Der Code:

    oder:
    http://pastie.org/2532868

    Compilieren einfach via GCC. Oben im Sourcecode ist auch noch der Inhalt für ein Makefile im Kommentar, wenn jemand lieber so compiliert.

    Über den Code:
    Das Feld wird in einem int gespeichert. Dabei werden pro Zelle im Feld je zwei Bits genutzt. Die Werte sehen so aus:
    Code:
    0 = 00b: Zelle ist frei
    1 = 01b: Zelle enthält ein "X"
    2 = 10b: Zelle enthält ein "O"
    3 = 11b: wird nicht benutzt
    Die Felder sind wie folgt durchnummeriert:
    Code:
    0 1 2
    3 4 5
    6 7 8
    Das Makro um den Wert auszulesen sieht so aus:
    #define GETPLAYER(state, fieldid) (((state) >> (2 * fieldid)) & 3)

    Will man eine Markierung setzen macht man das mit diesem Makro:
    #define SETPLAYER(state, fieldid, player) state = ((state) & ~(3 << (2 * (fieldid)))) | ((player) << (2 * (fieldid)))
    Dabei ist das Makro im Prinzip komplizierter als notwenig, da es die Bits an der Stelle erst alle auf 0 setzt und dann erst den Wert setzt. Das verhindert, dass man irgendwie "X"(=01b) und "O"(=10b) mischt und dann auf den nicht genutzen Zustand kommt (=11b). Im Prinzip wird dieser Fall aber bereits durch die Programmlogik abgefangen (man kann nicht auf bereits gesetzte Felder setzen)...

    Der Aufwand mit den Bits scheint zwar überdimensioniert, jedoch vereinfacht sich das Überprüfen gewisser Gewinnsituationen erheblich.
    Die Funktion "checkwin" nimmt das Feld als Parameter und ruft "checkwin_player" zwei mal auf. Diese Funktion prüft jeweils, ob ein gewisser Spieler gewonnen hat (darum zwei mal -- jeweils für X und O). Dabei wird das Spielfeld noch einmal komprimiert: ist auf dem i-ten Feld eine Markierung von dem Spieler, der gerade geprüft wird, dann wird das i-te Bit in einem weiteren int auf 1 gesetzt (i=0,...,8).
    Nun kann man alle möglichen Gewinnkombinationen in Form von Bitmasken realisieren und dann prüfen, ob die entsprechenden Markierungen gesetzt sind:
    if ((checkstate & winarr[i]) == winarr[i])
    checkstate ist hier das Feld mit den gesetzten Bits und winarr[i] durchläuft alle möglichen Bitkombinationen:
    Code:
    unsigned int winarr[] = {
    	// horizontally
    	7, 56, 448,
    	// vertically
    	73, 146, 292,
    	// across
    	84, 273
    };
    Beispielsweise ist 84 = 001010100b und entspricht also dem Feld:
    Code:
    _ _ Z
    _ Z _
    Z _ _
    (Reihenfolge beachten!)

    Vielleicht noch kurz zur "KI":
    Der Zug wird in 3 Schritten entschieden (wobei nach dem ersten und zweiten Schritt bereits abgebrochen werden kann):
    1: es wird geprüft, ob die KI sofort gewinnen kann -- wenn ja wird natürlich sofort dieser Zug genutzt
    2: es wird geprüft, ob der Gegner sofort gewinnen könnte -- wenn ja wird natürlich sofort der Zug des Gegners blockiert
    3: ist weder 1 noch 2 erfolgreich, so wird eine Wertigkeitstabelle angelegt. Auf die freie Zelle mit der höchsten Wertigkeit wird gesetzt (haben mehrere Zellen die gleiche Wertigkeit, so wird auf die erste von diesen gesetzt).

    Die Bewertung erfolgt so:
    Das mittlere Feld bekommt von Haus aus eine Wertigkeit von 1 und alle anderen eine von 0 (von der Mitte aus hat man natürlich die meisten Optionen).
    Nun wird das Feld anhand der bereits gelegten Steine bewertet. Jedes Feld, das Benutzt werden kann, um zu gewinnen bzw. vom Gegner genutzt werden kann um zu gewinnen wird von der Wertigkeit um 2 erhöht.
    Hat man also dieses Feld:
    Code:
    _ _ _
    _ _ _
    X _ _
    so erhält man als Wertigkeitstabelle:
    Code:
    2 0 2
    2 3 0
    # 2 2
    ^--- "#" soll hier ein besetztes Feld andeuten;
         diese werden von der KI logischer Weise nicht
         für Züge in Erwägung gezogen)
    Dies resultiert also in einem Zug auf die Mitte:
    Code:
    _ _ _
    _ O _
    X _ _
    Im nächsten Schritt setzen wir vielleicht mal auf auf die erste Zelle:
    Code:
    X _ _
    _ O _
    X _ _
    Dies resultiert in:
    Code:
    # 4 4
    6 # 2
    # 4 6 (hoffentlich habe ich mich hier nicht verrechnet ^-^)
    Also wird links neben die Mitte gesetzt (weil höchste Wertung =6 und dies das erste Feld mit dieser Wertung ist):
    Code:
    O _ _
    O O _
    X _ _
    Wie man sieht ist hier kein Zufall involviert (also auch nicht, wenn mehrere Felder die gleiche Wertigkeit erhalten) und die KI handelt immer gleich.
    Dass das im Prinzip auch wieder suboptimal ist wird sofort klar, wenn man die Kombination der Züge auf 7, 2, 3, 8, 6 betrachtet, die immer zu einem Sieg führen (wer das ändern will: die Auswahl des Zuges nach der Wertigkeit geht ab Zeile 130 los).


    MfG. blackberry
    Geändert von blackberry (13.12.2011 um 18:18 Uhr) Grund: Tippfehler korrigiert: 'Zelle enthält ein "="' zu 'Zelle enthält ein "O"'

    PDFTT cr3w a.E. — ReiDC0Re, lindor, Sera, berry
    please do feed the trolls crew and elk
    Ehrenwerte Mitglieder im Ruhestand: OpCodez, SFX.
    "Was sich blackberry gerade denkt" — Vorsicht! Frei laufender Wahnsinn!
    Zitat von fuckinghot19: "PS: Blackberry ist auf FH der Trollkönig ^^."
    An dieser Stelle danke ich all meinen Fans und Hatern gleichermaßen ^.^

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •