What's the best/most efficent way to create a semi-intelligent AI for a tic tac toe game?

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.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; //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.sign, s.sign, s.sign);
printf("-----------\n");
printf(" %c | %c | %c\n", s.sign, s.sign, s.sign);
printf("-----------\n");
printf(" %c | %c | %c\n\n", s.sign, s.sign, s.sign);
}

void getHumanMove(){ // get move from human
int i;
while(1){
printf(">>:");
char line; // 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.value,s.value,s.value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
if((sum(s.value,s.value,s.value)) == 1){printf("The Winner is x!\n");gamestate.state=2;}
if((sum(s.value,s.value,s.value)) == 8){printf("The Winner is o!\n");gamestate.state=1;}
if((sum(s.value,s.value,s.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.value = 2; s.sign = 'o';
gamestate.moves++;
}else{
s.value = 2; s.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; // 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;
}
• Start with a national defense AI... – Mason Wheeler Oct 21 '15 at 10:28

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 '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? – Rivasa Mar 7 '12 at 1:29
• Actually, I think I got it, will finish up tomorrow, but seems like it worked :) accepted! – Rivasa 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

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:

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.

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

Game

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

protected by gnatSep 24 '18 at 8:54

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?