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 = ' ';
    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(" %c | %c | %c\n", s[3].sign, s[4].sign, s[5].sign);
    printf(" %c | %c | %c\n\n", s[0].sign, s[1].sign, s[2].sign);

void getHumanMove(){ // get move from human
    int i;
        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;}
    s[i-1].value = 1;
    s[i-1].sign = 'x';

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
    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';
            s[2].value = 2; s[2].sign = 'o';
    while(gamestate.state == 3){
        if(gamestate.state == 3 && gamestate.moves==9){
            printf("The game is a tie :p\n");

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;
  • 1
    Start with a national defense AI... Oct 21, 2015 at 10:28

4 Answers 4


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.

Obviously, the AI should play a winning move if there is one.

  • ok then, thanks, but how would that look in code, really sorry, just don't know how to implement it properly in my code.
    – Rivasa
    Mar 7, 2012 at 1:22
  • The AI should aim to draw, not to win.
    – Bernard
    Mar 7, 2012 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?
    – Rivasa
    Mar 7, 2012 at 1:29
  • Actually, I think I got it, will finish up tomorrow, but seems like it worked :) accepted!
    – Rivasa
    Mar 7, 2012 at 1:52
  • Yes, that should give the illusion of a human novice player. Mar 7, 2012 at 9:30

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.


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:

  Bc (1)
  TR (1)
  CL (2)
  CR (1)
  BL (2)
  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.


Trivial, Basic, Simple concept of AI for Tic-tac-toe, which was my 1st test for my AI prototype years ago.


  • N x N cells. N=3 => 9 cells
  • Every cell can have 3 states (Empty, 0, 1). Game has 3ˇ9 = 19683 states
  • Player must choose 1 cell

AI input: State of the game (1 of 81 states)

  • 15 bits for combinations of the state (log2(3ˇ9))
  • Not: using 2 bits per cell state, 9x2 is 18 bits

AI Output: Cell (move)

  • Use 3 bits (use 1 of 8 free cells) - yes 9th cell wont be chosen, but we have 9 free cells only in first iteration and only if we start and in this moment it has the same meaning as cell[0]
  • Not: using 9 bits (1 bit per cell)
  • Not: using 4 bits (4-bit index of the cell)

AI Feedback: Game won or lost (1 bit)

AI internal

  • int fbs[MAX_STATES][MAX_MOVES]; // feedbacks
  • void Feedback(fb) { fbs[lastState][lastMove] += f; }
  • U32 Output(state) {
  • try random move every N_RAND'th time (rand() % N_RAND == 0)
    • return lastMove = rand() % MAX_MOVES;
  • Find max(fbs[lastState][m=0..MAX_MOVES])
    • if found, return m; // risk with this to try opponents other moves.
    • else, force random
  • lastState = state; lastMove = m;

Notes: (you can skip those)

  • As rotations have same meaning, there are less meaningful states and could use less bits for those. But we may want AI to "find" those "meaningfulnesses" out by itself and optimize itself later
  • Output: Index of free cells (other outputs are impossible)
    • on 2nd iteration we can have as much as 5 options (log(5)>2bits), so 3b output is good.
    • There are less meaningful outputs (at 1st iteration: center, corner, side) - could have output as index of meaningful outputs
  • The impossible and not meaningful moves will be ignored later after "training" by weighting them down (as bad moves) automatically AI.
  • Could use 4 bit feedback for (lost/won in N steps)
  • If state not found - could interpolate from similar states instead of trying random
  • [State][Move] combined are 15+3 18b or less. So you have 157464 or less state-move combinations.
  • Using 1B resolution/precision for feedback is would use 157KB or RAM (if you move to more complex games, optimizing memory usage becomes you main job). It is wasting as you only wanna sort ~5 possible moves by their fb, so 3b would be enough, but with "arithmetical coding" it's still a big waste of 3rd bit. In the trained and optimized model just 1 bit is enough as you only want the best moves (1) and worse moves' feedback should go to (0) (RAM: 20KB), or just write down the best 3b moves for 19683 state (7.4KB), can be compressed better...
  • To make it smarter, you could add aging to the feedbacks, so that if game rules change, it (or should we call she) would start winning sooner.
  • Wiki: "138 terminal board positions"
    • Can do only 4-5 moves at max before ending in 1 of those 138 positions, means we have less than 5x138 decisions to make, means the best answers are <259B of data (possibly around 100B). Good AI would optimize its RAM usage from 157KB to 0.1KB. The best AI would zip this info probably to <30 bytes and use 157KB RAM for much greater problems.

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