Thread: tic-tac-toe computer

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    tic-tac-toe computer

    I'm making a tic-tac-toe program. Player vs computer. I have most of the programming working, and I am now working on the computer's moves. I'm looking for the best way to go about this. The only way i can figure, is working out all the possible combinations of X's and O's in the tic-tac-toe square, and programming a move for every possible combination.
    Ex:
    Code:
    if(firstsquare = x & secondsquare = x)
         have the computer mark third square O.
    
    else if(first square = x & fourthsquare = x)
         have the computer mark the seventh square o.
    
    ...
    Is this the only way to do this (there would be ALOT of combinations to program)? Or is there a better way?

    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    The way you're imagining is perhaps sort of like the minimax technique. Search around for that if you like. Basically, the program calculates all the possible ways that the game might end, and moves based on which endings are best for it.

    There are lots of threads about this around. A recent one: http://cboard.cprogramming.com/showthread.php?t=103715
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User Terran's Avatar
    Join Date
    May 2008
    Location
    Nashua, NH
    Posts
    100
    I made this same game, and i just used a ton of if statements lol
    Sorry, but i'm a Code::Blocks man now.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Since there are so many tic-tac-toe programs floating around at the moment, I thought I'd post this one.

    Note that it's really old, so it's probably not very well written. I never finished writing it, either. Plus the interface isn't the best. But still, you might be interested in the AI. Check out aiopponent::move().

    [edit] I forgot to mention that I don't know how good this AI is. I made it up myself. I don't remember if I found a way to beat it or not, but I think I did. Try it yourself.

    It doesn't do any planning or anything. I'd probably call it a moderately tough AI. [/edit]

    Code:
    #include <iostream>
    #include <string>
    #include <cctype>
    
    using std::cout;
    using std::cin;
    using std::endl;
    
    using std::string;
    
    using std::tolower;
    
    class tttboard {
    private:
        char board[3][3];
    public:
        static const char NOBODY = ' ', PLAYER1 = 'X', PLAYER2 = 'O';
    
        tttboard();
        void init_board();
        void display();
        void set(int x, int y, char c);
        char get(int x, int y) const;
    };
    
    tttboard::tttboard() {
        init_board();
    }
    
    void tttboard::init_board() {
        for(int x = 0; x < 3; x ++) {
            for(int y = 0; y < 3; y ++) {
                board[x][y] = NOBODY;
            }
        }
    }
    
    void tttboard::display() {
        cout << endl;
    
        for(int y = 0; y < 3; y ++) {
            for(int x = 0; x < 3; x ++) {
                cout << board[x][y];
                if(x < 2) cout << '|';
            }
            
            cout << endl;
            if(y < 2) cout << "-+-+-\n";
        }
    }
    
    void tttboard::set(int x, int y, char c) {
        board[x][y] = c;
    }
    
    char tttboard::get(int x, int y) const {
        return board[x][y];
    }
    
    class opponent {
    private:
        string name;
    protected:
        char c;
        void set_name(string name, char c);
    public:
        virtual void move(const tttboard &board, int &xpos, int &ypos) = 0;
        string get_name() { return name; }
    };
    
    void opponent::set_name(string name, char c) {
        this->name = name + " (" + c + ")";
        this->c = c;
    }
    
    class aiopponent : public opponent {
    private:
        int two(char c, char x, char y, char z);
    public:
        aiopponent(string name, char c);
        void move(const tttboard &board, int &xpos, int &ypos);
    };
    
    aiopponent::aiopponent(string name, char c) {
        set_name(name, c);
    }
    
    /* Extremely simple AI that picks the next available spot.
    void aiopponent::move(const tttboard &board, int &xpos, int &ypos) {
        for(int x = 0; x < 3; x ++) {
            for(int y = 0; y < 3; y ++) {
                if(board.get(x, y) == tttboard::NOBODY) {
                    xpos = x, ypos = y;
                    cout << "AI picks position (" << x << ',' << y << ")\n";
                    return;
                }
            }
        }
    }*/
    
    int aiopponent::two(char c, char x, char y, char z) {
        if(x == c && y == c && z == tttboard::NOBODY) return 3;
        if(x == c && y == tttboard::NOBODY && z == c) return 2;
        if(x == tttboard::NOBODY && y == c && z == c) return 1;
        
        return 0;
    }
    
    void aiopponent::move(const tttboard &board, int &xpos, int &ypos) {
        int r;
        char ic;// = (c == tttboard::PLAYER1 ? tttboard::PLAYER2 : tttboard::PLAYER1);
        
        if(c == tttboard::PLAYER1) ic = tttboard::PLAYER2;
        else ic = tttboard::PLAYER1;
    
        /* Look for winning spots */
        for(int x = 0; x < 3; x ++) {
            if((r = two(c, board.get(0, x), board.get(1, x), board.get(2, x)))) {
                ypos = x, xpos = r-1;
                return;
            }
            
            if((r = two(c, board.get(x, 0), board.get(x, 1), board.get(x, 2)))) {
                xpos = x, ypos = r-1;
                return;
            }
        }
        
        if((r = two(c, board.get(0, 0), board.get(1, 1), board.get(2, 2)))) {
            xpos = r-1, ypos = r-1;
            return;
        }
        
        if((r = two(c, board.get(2, 0), board.get(1, 1), board.get(0, 2)))) {
            xpos = 3-r, ypos = r-1;
            return;
        }
        
        /* Block losing spots */
        for(int x = 0; x < 3; x ++) {
            if((r = two(ic, board.get(0, x), board.get(1, x), board.get(2, x)))) {
                ypos = x, xpos = r-1;
                return;
            }
            
            if((r = two(ic, board.get(x, 0), board.get(x, 1), board.get(x, 2)))) {
                xpos = x, ypos = r-1;
                return;
            }
        }
        
        if((r = two(ic, board.get(0, 0), board.get(1, 1), board.get(2, 2)))) {
            xpos = r-1, ypos = r-1;
            return;
        }
        
        if((r = two(ic, board.get(2, 0), board.get(1, 1), board.get(0, 2)))) {
            xpos = 3-r, ypos = r-1;
            return;
        }
        
        /* Pick the middle if it's available */
        if(board.get(1, 1) == tttboard::NOBODY) {
            xpos = 1, ypos = 1;
            return;
        }
        
        /* Take a corner if we don't have one yet */
        if(board.get(0, 0) != c && board.get(2, 0) != c 
            && board.get(0, 2) != c && board.get(2, 2) != c) {
            
            if(board.get(0, 0) == tttboard::NOBODY) {
                xpos = 0, ypos = 0;
                return;
            }
            if(board.get(2, 0) == tttboard::NOBODY) {
                xpos = 2, ypos = 0;
                return;
            }
            if(board.get(0, 2) == tttboard::NOBODY) {
                xpos = 0, ypos = 2;
                return;
            }
            if(board.get(2, 2) == tttboard::NOBODY) {
                xpos = 2, ypos = 2;
                return;
            }
        }
        
        /* Pick the next available spot */
        for(int x = 0; x < 3; x ++) {
            for(int y = 0; y < 3; y ++) {
                if(board.get(x, y) == tttboard::NOBODY) {
                    xpos = x, ypos = y;
                    return;
                }
            }
        }
    }
    
    class humanopponent : public opponent {
    public:
        humanopponent(char c);
        void move(const tttboard &board, int &xpos, int &ypos);
    };
    
    humanopponent::humanopponent(char c) {
        cout << "\nEnter your name: ";
        string name;
        cin >> name;
        set_name(name, c);
    }
    
    void humanopponent::move(const tttboard &board, int &xpos, int &ypos) {
        for(;;) {
            cout << "Enter column (x-axis) number (1-3): ";
            while(!(cin >> xpos) || xpos <= 0 || xpos > 3) {
                // !!!
                cin.clear();
                cout << ": ";
            }
            
            cout << "Enter row (y-axis) number (1-3): ";
            while(!(cin >> ypos) || ypos <= 0 || ypos > 3) {
                cin.clear();
                cout << ": ";
            }
            
            xpos --, ypos --;
            
            if(board.get(xpos, ypos) != tttboard::NOBODY) {
                cout << "That spot's already taken\n";
                continue;
            }
            
            break;
        }
    }
    
    class ttt {
    private:
        tttboard board;
        opponent *player[2];
        int turn;
    
    public:
        ttt();
        ~ttt();
        bool new_game();
        void play_game();
        int game_done();
    };
    
    ttt::ttt() : turn(0) {
        player[0] = player[1] = 0;
    }
    
    ttt::~ttt() {
        for(int x = 0; x < 2; x ++) {
            if(player[x]) delete player[x];
        }
    }
    
    bool ttt::new_game() {
        cout << "\nNew game\nEnter the type of player #1 ([A]I/[H]uman/[Q]uit): ";
        
        char one;
        for(;;) {
            if(!(cin >> one)) {
                cin.clear();
                continue;
            }
            
            one = tolower(one);
            if(one == 'q') return false;
            if(one == 'a' || one == 'h') break;
        }
        
        cout << "Enter the type of player #2 ([A]I/[H]uman/[Q]uit): ";
        
        char two;
        for(;;) {
            if(!(cin >> two)) {
                cin.clear();
                continue;
            }
            
            two = tolower(two);
            if(two == 'q') return false;
            if(two == 'a' || two == 'h') break;
        }
        
        if(one == 'h') player[0] = new humanopponent(tttboard::PLAYER1);
        else {
            player[0] = new aiopponent(
                "AI for player #1", tttboard::PLAYER1);
        }
        
        if(two == 'h') player[1] = new humanopponent(tttboard::PLAYER2);
        else {
            player[1] = new aiopponent(
                "AI for player #2", tttboard::PLAYER2);
        }
        
        turn = 0;
        play_game();
    
        return true;
    }
    
    void ttt::play_game() {
        int x, y, won;
        char again;
        
        do {
            board.init_board();
            
            while(!(won = game_done())) {
                board.display();
                cout << player[turn]->get_name() << endl;
                player[turn]->move(board, x, y);
                cout << player[turn]->get_name() << " picked position "
                    << x+1 << ", " << y+1 << endl;
                board.set(x, y, turn ? tttboard::PLAYER2 : tttboard::PLAYER1);
                turn = !turn;
            }
            
            board.display();
            cout << "Game over. ";
            
            switch(won) {
            case -1: cout << "Tie."; break;
            case 1: cout << player[0]->get_name() << " won!"; break;
            case 2: cout << player[1]->get_name() << " won!"; break;
            }
            
            cout << endl;
            
            cout << "Another round? ";
            cin >> again;
        } while(tolower(again) == 'y');
    }
    
    int ttt::game_done() {
        int n, flag = 0;
    
        for(int x = 0; x < 3 && !flag; x ++) {
            for(int y = 0; y < 3 && !flag; y ++) {
                if(board.get(x, y) == tttboard::NOBODY) flag = 1;
            }
        }
        
        if(!flag) return -1;
        
        for(int x = 0; x < 3; x ++) {
            if((n = board.get(x, 0)) != tttboard::NOBODY) {
                if(n == board.get(x, 1) && n == board.get(x, 2)) {
                    return n == tttboard::PLAYER1 ? 1 : 2;
                }
            }
        }
        
        for(int y = 0; y < 3; y ++) {
            if((n = board.get(0, y)) != tttboard::NOBODY) {
                if(n == board.get(1, y) && n == board.get(2, y)) {
                    return n == tttboard::PLAYER1 ? 1 : 2;
                }
            }
        }
        
        if((n = board.get(0, 0)) != tttboard::NOBODY) {
            if(n == board.get(1, 1) && n == board.get(2, 2)) {
                return n == tttboard::PLAYER1 ? 1 : 2;
            }
        }
        
        if((n = board.get(2, 0)) != tttboard::NOBODY) {
            if(n == board.get(1, 1) && n == board.get(0, 2)) {
                return n == tttboard::PLAYER1 ? 1 : 2;
            }
        }
        
        return 0;
    }
    
    int main() {
        cout << "ttt45 by DWK\n"
            "Simple Tic-Tac-Toe game.\n";
    
        ttt tictactoe;
        
        while(tictactoe.new_game());
    
        return 0;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Thank you all for the input. I'll probably go with a buch of if statements, since i've already started that way. But, i'll also look into that minimax technique to see how it works, as it seems to be the most efficient.

    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by Cpro View Post
    Thank you all for the input. I'll probably go with a buch of if statements, since i've already started that way. But, i'll also look into that minimax technique to see how it works, as it seems to be the most efficient.

    Thanks.
    "bunch of if statements?" Eeewww, gross. Why not instead build an array of games with the next best possbile move. Coming up with the way to store that data would be the challenge, but once you've figured out it's just a matter of finding your game in the array and choosing the pre-programmed move.

    My major gripe with games like this is it's boring to play. When I wrote my tic-tac-toe I set it up to learn. You'll bet it a time or 10, but then it won't do that again. Much more "fun" IMHO.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    >> Why not instead build an array of games with the next best possbile move.

    Some very intelligent game engines use game trees like this, however, they don't completely solve the problem. It's not space efficient. If you complete the game tree for tic-tac-toe you would discover that there are 362,000+ layouts. The game tree complexity for tic-tac-toe is 26,830 leaf nodes. You would need at least some problem solving rather than just a big tree of game states.

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    What if you filter rotated and mirror states?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. Tic Tac Toe Comp Move help
    By swgh in forum C++ Programming
    Replies: 5
    Last Post: 09-24-2008, 11:05 AM
  3. Tic Tac Toe... so close...
    By SlayerBlade in forum C Programming
    Replies: 14
    Last Post: 10-10-2005, 08:58 PM
  4. Tic Tac Toe AI help please...
    By Rune Hunter in forum Game Programming
    Replies: 12
    Last Post: 11-05-2004, 04:24 PM
  5. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM