Results 1 to 4 of 4

Thread: tictactoe KI

  1. #1
    downforme's Avatar
    Title
    Master
    Join Date
    May 2002
    Posts
    165
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    12
    Thanked in
    5 Posts

    Question tictactoe KI

    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; 
    }

    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?

  2. #2
    linken_harmy
    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,...

  3. #3
    downforme's Avatar
    Title
    Master
    Join Date
    May 2002
    Posts
    165
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    12
    Thanked in
    5 Posts
    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.

  4. #4
    downforme's Avatar
    Title
    Master
    Join Date
    May 2002
    Posts
    165
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    12
    Thanked in
    5 Posts
    habs rausgefunden:
    der baum besteht naturlich nicht aus 9! sondern aus
    9 +
    9*8 +
    9*8*7 +
    .... +
    9!
    maximal möglichen knoten

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •