Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

basically I am attempting to make a a efficient/smallish C game of Tic-Tac-Toe. I have implemented everything other then the AI for the computer so far. my squares are basically structs in an array with an assigned value based on the square. For example

s[1].value = 1;

therefore it's a x, and then a value of 3 would be a o. My question is whats the best way to create a semi-decent game playing AI for my tic-tac-toe game? I don't really want to use minimax, since It's not what I need. So how do I avoid a a lot of if statments and make it more efficient.

Here is the rest of my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

struct state{ // defined
    int state; // 0 is tie, 1 is user loss, 2 is user win, 3 is ongoing game
    int moves;
};

struct square{ // one square of the board
    int value; // 1 is x, 3 is o
    char sign; // no space used
};

struct square s[9]; //set up the struct
struct state gamestate = {0,0}; //nothing

void setUpGame(){ // setup the game
    int i = 0;
    for(i = 0; i < 9; i++){
        s[i].value = 0;
        s[i].sign = ' ';
    }
    gamestate.moves=0;
    printf("\nHi user! You're \"x\"! I'm \"o\"! Good Luck :)\n");
}

void displayBoard(){// displays the game board
    printf("\n %c | %c | %c\n", s[6].sign, s[7].sign, s[8].sign);
    printf("-----------\n");
    printf(" %c | %c | %c\n", s[3].sign, s[4].sign, s[5].sign);
    printf("-----------\n");
    printf(" %c | %c | %c\n\n", s[0].sign, s[1].sign, s[2].sign);
}

void getHumanMove(){ // get move from human
    int i;
    while(1){
        printf(">>:");
        char line[255]; // input the move to play
        fgets(line, sizeof(line), stdin);
            while(sscanf(line, "%d", &i) != 1) { //1 match of defined specifier on input line
            printf("Sorry, that's not a valid move!\n");
            fgets(line, sizeof(line), stdin);
        }
        if(s[i-1].value != 0){printf("Sorry, That moves already been taken!\n\n");continue;}
        break;
    }
    s[i-1].value = 1;
    s[i-1].sign = 'x';
    gamestate.moves++;
}

int sum(int x, int y, int z){return(x*y*z);}

void getCompMove(){ // get the move from the computer

}

void checkWinner(){ // check the winner
    int i;
    for(i = 6; i < 9; i++){ // check cols
        if((sum(s[i].value,s[i-3].value,s[i-6].value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
        if((sum(s[i].value,s[i-3].value,s[i-6].value)) == 1){printf("The Winner is x!\n");gamestate.state=2;}   
    }
    for(i = 0; i < 7; i+=3){ // check rows
        if((sum(s[i].value,s[i+1].value,s[i+2].value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
        if((sum(s[i].value,s[i+1].value,s[i+2].value)) == 1){printf("The Winner is x!\n");gamestate.state=2;}
    }
    if((sum(s[0].value,s[4].value,s[8].value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
    if((sum(s[0].value,s[4].value,s[8].value)) == 1){printf("The Winner is x!\n");gamestate.state=2;}
    if((sum(s[2].value,s[4].value,s[6].value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
    if((sum(s[2].value,s[4].value,s[6].value)) == 1){printf("The Winner is x!\n");gamestate.state=2;}
}

void playGame(){ // start playing the game
    gamestate.state = 3; //set-up the gamestate
    srand(time(NULL));
    int temp = (rand()%2) + 1;
    if(temp == 2){ // if two comp goes first
        temp = (rand()%2) + 1;
        if(temp == 2){
            s[4].value = 2; s[4].sign = 'o';
            gamestate.moves++;
        }else{
            s[2].value = 2; s[2].sign = 'o';
            gamestate.moves++;
        }
    } 
    displayBoard();
    while(gamestate.state == 3){
        if(gamestate.moves<10);
            getHumanMove();
        if(gamestate.moves<10);
            getCompMove();
        checkWinner();
        if(gamestate.state == 3 && gamestate.moves==9){
            printf("The game is a tie :p\n");
            break;
        }
        displayBoard();
    }
}

int main(int argc, const char *argv[]){
    printf("Welcome to Tic Tac Toe\nby The Elite Noob\nEnter 1-9 To play a move, standard numpad\n1 is bottom-left, 9 is top-right\n");
    while(1){ // while game is being played
        printf("\nPress 1 to play a new game, or any other number to exit;\n>>:");
        char line[255]; // input whether or not to play the game
        fgets(line, sizeof(line), stdin);
        int choice; // user's choice about playing or not   
        while(sscanf(line, "%d", &choice) != 1) { //1 match of defined specifier on input line
            printf("Sorry, that's not a valid option!\n");
            fgets(line, sizeof(line), stdin);
        }
        if(choice == 1){
            setUpGame(); // set's up the game
            playGame(); // Play a Game
        }else {break;} // exit the application
    }
    printf("\nThank's For playing!\nHave a good Day!\n");
    return 0;
}
share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

So you want the human to have a chance to win?

Then play the move that blocks a winning line, or if there isn't one, play a move at random. Perhaps weight the centre for 3 and the corners for 2, with the edges at 1, but if what you want is an opponent you can beat, you don't want to be to clever.

share|improve this answer
    
ok then, thanks, but how would that look in code, really sorry, just don't know how to implement it properly in my code. –  Link Mar 7 '12 at 1:22
    
The AI should aim to draw, not to win. –  Bernard Mar 7 '12 at 1:28
    
ok, so basically I just need to block off any possible wins? And if none exist, just choose some random point to play? That should be strongish enough AI correct? –  Link Mar 7 '12 at 1:29
    
Actually, I think I got it, will finish up tomorrow, but seems like it worked :) accepted! –  Link Mar 7 '12 at 1:52
    
Yes, that should give the illusion of a human novice player. –  Bill Michell Mar 7 '12 at 9:30
add comment

3x3 Tic Tac Toe is a small enough game that one could relatively easily enumerate all the possible board positions and identify the correct next move for each. If one wanted to tackle something a little bigger like 4x4x4, which allows the first player to force a win but not always easily, a good approach would be to combine heuristics with a min-max algorithm. A reasonably good heuristic would, for each of the possible winning lines, identify it as being empty, as being blocked, or as having 1-4 player marks by the person who just moved, or 1-3 marks by the other player. Each of those nine possibilities would be assigned a score value (4 marks by the person who just moved move being a really huge score value, and 3 marks by the person about to move being a not-quite-as-big negative value (so if a move would create a four-in-a-row, that would leave a good board position for the person who just moved even if the other player had an unblocked three, but otherwise leaving an unblocked three by the opponent would be very bad). A simple score-based approach would work by testing each possible move, computing how favorable the board position would be afterward, and selecting the move that yields the most favorable position. Such an approach would work decently, but would not play optimally.

To make the computer play better, use what's called a min-max algorithm. To find the "level 0" score for a possible move, simply score the board that would result after the move. To find the "level n" score for a possible move, determine which possible following move by the opponent would yield the best "level n-1" score (for the opponent). The "level n" score is that best "level n-1" score, with the sign reversed.

Min-max algorithms can work very well for many types of turn-based games. The biggest problem with them is that they can be very slow unless some steps are taken to ensure efficiency. Among other things, simple algorithms will often end up examining board positions many dozens of times, if not hundreds. They will also spend a lot of time evaluating in depth the possible countermoves for moves which should be recognized as lacking any merit. Additionally, simple algorithms will often score each board position "from scratch". Making a playable game requires tackling all three problems: keep track of what positions have been analyzed and what scores they've received; rather than using a depth-first search to evaluate every possible move at e.g. level 5, use a cross between a breadth-first search and a priority queue, so that the best-seeming moves get evaluated first. Finally, use an "incremental" data structure that allows rapid scoring. For example, in addition to holding the 64 squares of the board, keep counters for each of the possible 16+16+16+24+8 possible winning lines tallying up how many of each player's markers are on the line. Adding or removing a piece would then require incrementing or decrementing the counts for the winning lines on which the piece appears, rather than having to recompute all of them.

share|improve this answer
add comment

If one represents X as +1 and O as -1 on a 3x3 matrix, a necessary move is one where the absolute value of the sum of the values on the line is 2. An unnecessary play is into the 3rd spot where the value is 0.

Thus, takes the state of the board, and examines each line and places the empty spots on that line in one of three lists:

  1. necessary
  2. ok
  3. unnecessary

Then the algorithm picks a random play from one of the lists in order of necessity. An improvement for slightly more intelligent play would be to bias this selection based on the number of times the play exists in the list (this will cause it to tend to play to the center (4 possible lines) and corners (3 possible lines) over the edges (2 possible lines).

O | X |
--+---+--
  | X |
--+---+--
  |   |

Would become:

    1  2  0  1
    |  |  | /
T  -1| 1 |  - 0
   --+---+--
C    | 1 |  - 1
   --+---+--
B    |   |  - 0
    L  c  R \ 0

In this situation, the empty spot in the center column would be played in because its value is 2. As this is O to play, this would be a block.

The full set of moves and grouping for this board state would be:

Necessary:
  Bc (1)
Ok:
  TR (1)
  CL (2)
  CR (1)
  BL (2)
Unnecessary:
  TR (2)
  CR (1)
  BL (1)
  Bc (1)
  BR (3)

Note that a single cell may very well fall into multiple groupings (Bottom Center Bc is both necessary to play to win/block, but it is also unnecessary to play on the bottom row as it will not contribute to a winning or blocking play on that row).

The key here is that it identifies the obvious plays but doesn't do any look ahead for what board position is strongest later (it doesn't have any preference to play the known strategies for winning with X or forcing a draw with O). It will attempt to block or win obvious setups - if you don't block it when its placed two on a line, it will attempt to win (unless you also have a win possible in which case it may decide to block rather than win).

Note that this is almost a byproduct of detecting the winning conditions for the board, as that would have a row, column, or diagonal that has an absolute value of its values of 3.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.