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.

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

I made this same game, and i just used a ton of if statements lol

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

---

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.

Quote:

---

Originally Posted by Cpro

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.

>> 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.

What if you filter rotated and mirror states?