1. Dashboard
  2. Forum
    1. Unerledigte Themen
  3. Mitglieder
    1. Letzte Aktivitäten
    2. Benutzer online
    3. Team-Mitglieder
    4. Trophäen
    5. Mitgliedersuche
  4. Tutorial Bereich
  • Anmelden
  • Registrieren
  • Suche
Dieses Thema
  • Alles
  • Dieses Thema
  • Dieses Forum
  • Seiten
  • Forum
  • Lexikon
  • Erweiterte Suche
  1. Informatik Forum
  2. Webmaster & Internet
  3. Entwicklung

tictactoe KI

  • downforme
  • 17. November 2005 um 16:54
  • Unerledigt
  • downforme
    3
    downforme
    Mitglied
    Punkte
    90
    Beiträge
    13
    • 17. November 2005 um 16:54
    • #1

    Hi!
    Ich hab folgendes Problem:
    Für meinen TicTacToe-gametree verwende ich die klasse TTTTreeNode mit folgenden Funktionen:

    Code
    void TTTTreeNode::init(char cCurrentplayer) { 
        TTTBoard* pBoard; 
        TTTTreeNode* pTTTTreeNode; 
        // wechsle Spieler 
        this->cPlayer = (cCurrentplayer==PLAYER_1)?PLAYER_2:PLAYER_1; 
        // Spiel zu Ende, keine weiteren Kinder 
        if (this->board->isFilled()) return; 
        if (this->board->isWon()) return; 
        // sonst 
        for (int iy=0; iy<BOARD_Y;++iy) { 
            for (int ix=0; ix<BOARD_X;++ix) { 
                pTTTTreeNode = NULL; 
                // dieser Zug wurde noch nicht gemacht 
                if (this->board->getField(ix, iy)==NULL) { 
                    // neues Board, identisch mit eigenem Board 
                    pBoard = new TTTBoard(this->board); 
                    // setze Spieler 
                    pBoard->setStone(this->cPlayer, ix, iy); 
                    // neuer Knoten mit dem Board zu diesem Zug 
                    pTTTTreeNode = new TTTTreeNode(pBoard); 
                    // initialiesere Kindknoten 
                    pTTTTreeNode->init(this->cPlayer); 
                } 
                this->attach(((iy*BOARD_Y)+ix), pTTTTreeNode); 
            } 
        } 
    } 
     
     
    int TreeNode::count() { 
        int count = 1; 
        for (unsigned int i=0; i<this->successors.size();++i) { 
            if (this->successors[i]!=NULL) count = count + this->successors[i]->count(); 
        } 
        return count; 
    }
    Alles anzeigen


    Die Maximale Anzahl aller möglichen Knoten in TTT sind imho 9! (= 362.880)
    Da ja einige Knoten schon früher keine Nachfolger mehr haben, wel sie gewonnene Spielzüge enthalten, sollte die Anzahl der tatsächlichen Knoten noch etwas darunter liegen.
    Auf Symetrie und andere Optimierung verzichte ich einstweilen.
    Wenn ich init() jetzt von meinem wurzelknoten mit einem leeren board aus aufrufe, wir ein Baum aufgebaut der aus 549946 Knoten besteht.
    Also entweder meine count()-Methode ist falsch, oder in der init() klappt was nicht.
    Kann mir wer sagen wo der Fehler liegt?

  • linken_harmy
    1
    linken_harmy
    Gast
    • 17. November 2005 um 17:19
    • #2

    Hoi, also wir haben neulich einen Spieltheorie Algorithmus zu TicTacToe besprochen und daraufhin das berühmte 8-Schiebe-Puzzle implementiert, das ungefähr die selben Ideen verwendet.. Die Zahl 362880 stimmt zwar, aber es ist glaub ich nicht sehr zu empfehlen, den Spielbaum komplett am Beginn aufzubauen, auch wenn du auf Optimierung verzichtest, wenn du von Anfang an den Baum komplett aufbaust wird das Optimieren danach um so schwerer.. Beim 8 Puzzle habe ich einen Algorithmus verwendet, der bisherige Züge beim Baumaufbau ausschliesst, vielleicht solltest du dir ein paar Methoden zurecht legen, die dir während dem Spiel auf n < 5 Ebenen den möglichen Spielbaum aufbaut. Eine genaue Lösung zu deinem Problem weiss ich jetzt nicht, aber die count methode an sich sieht nicht wirklich falsch aus würd ich sagen,.. durchsteppen mit debug wird halt recht schwer bei 362880 zyklen,.. aber du könntest mal ein paar läufe durchmachen und schauen ob er am anfang schon was unterschlägt, dafür solltest du aber eine eingerückte formatierung deines codes verwenden damit du optimal die ergebnisse nach zeilen analysieren kannst,.. bei dem if in ::count() mein ich,... sorry, ausser den paar tips kann ich dir nicht wirklich helfen,...

  • downforme
    3
    downforme
    Mitglied
    Punkte
    90
    Beiträge
    13
    • 17. November 2005 um 17:25
    • #3

    eigentlich gehts um den minmax algorithmus.
    die aufgabenstellung lautet zuerst den kompletten spielebaum aufzubauen.
    bei tictactoe ist der speicherverbrauch noch (halbwegs) vertretbar.

    362880 zyklen sind sicher zu viel, aber 15 hab ich mit zettel und bleistift gemacht, und dabei keinen fehler entdecken können.

  • downforme
    3
    downforme
    Mitglied
    Punkte
    90
    Beiträge
    13
    • 18. November 2005 um 05:46
    • #4

    habs rausgefunden:
    der baum besteht naturlich nicht aus 9! sondern aus
    9 +
    9*8 +
    9*8*7 +
    .... +
    9!
    maximal möglichen knoten

  • Maximilian Rupp 27. Dezember 2024 um 12:06

    Hat das Thema aus dem Forum Programmieren nach Entwicklung verschoben.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden

Benutzer online in diesem Thema

  • 1 Besucher

Rechtliches

Impressum

Datenschutzerklärung