1. //Tic-tac-toe playing AI. Exhaustive tree-search. Do what you want with the code.
  2. //Matthew Steel 2009, www.www.repsilat.com
  3.  
  4. #include <stdio.h>
  5.  
  6. char gridChar(int i) {
  7.     switch(i) {
  8.         case -1:
  9.             return 'X';
  10.         case 0:
  11.             return ' ';
  12.         case 1:
  13.             return 'O';
  14.     }
  15. }
  16.  
  17. void draw(int b[9]) {
  18.     printf(" %c | %c | %c\n",gridChar(b[0]),gridChar(b[1]),gridChar(b[2]));
  19.     printf("---+---+---\n");
  20.     printf(" %c | %c | %c\n",gridChar(b[3]),gridChar(b[4]),gridChar(b[5]));
  21.     printf("---+---+---\n");
  22.     printf(" %c | %c | %c\n",gridChar(b[6]),gridChar(b[7]),gridChar(b[8]));
  23. }
  24.  
  25. int win(const int board[9]) {
  26.     //determines if a player has won, returns 0 otherwise.
  27.     unsigned wins[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
  28.     int i;
  29.     for(i = 0; i < 8; ++i) {
  30.         if(board[wins[i][0]] != 0 &&
  31.            board[wins[i][0]] == board[wins[i][1]] &&
  32.            board[wins[i][0]] == board[wins[i][2]])
  33.             return board[wins[i][2]];
  34.     }
  35.     return 0;
  36. }
  37.  
  38. int minimax(int board[9], int player) {
  39.     //How is the position like for player (their turn) on board?
  40.     int winner = win(board);
  41.     if(winner != 0) return winner*player;
  42.    
  43.     int move = -1;
  44.     int score = -2;//Losing moves are preferred to no move
  45.     int i;
  46.     for(i = 0; i < 9; ++i) {//For all moves,
  47.         if(board[i] == 0) {//If legal,
  48.             board[i] = player;//Try the move
  49.             int thisScore = -minimax(board, player*-1);
  50.             if(thisScore > score) {
  51.                 score = thisScore;
  52.                 move = i;
  53.             }//Pick the one that's worst for the opponent
  54.             board[i] = 0;//Reset board after try
  55.         }
  56.     }
  57.     if(move == -1) return 0;
  58.     return score;
  59. }
  60.  
  61. void computerMove(int board[9]) {
  62.     int move = -1;
  63.     int score = -2;
  64.     int i;
  65.     for(i = 0; i < 9; ++i) {
  66.         if(board[i] == 0) {
  67.             board[i] = 1;
  68.             int tempScore = -minimax(board, -1);
  69.             board[i] = 0;
  70.             if(tempScore > score) {
  71.                 score = tempScore;
  72.                 move = i;
  73.             }
  74.         }
  75.     }
  76.     //returns a score based on minimax tree at a given node.
  77.     board[move] = 1;
  78. }
  79.  
  80. void playerMove(int board[9]) {
  81.     int move = 0;
  82.     do {
  83.         printf("\nInput move ([0..8]): ");
  84.         scanf("%d", &move);
  85.         printf("\n");
  86.     } while (move >= 9 || move < 0 && board[move] == 0);
  87.     board[move] = -1;
  88. }
  89.  
  90. int main() {
  91.     int board[9] = {0,0,0,0,0,0,0,0,0};
  92.     //computer squares are 1, player squares are -1.
  93.     printf("Computer: O, You: X\nPlay (1)st or (2)nd? ");
  94.     int player=0;
  95.     scanf("%d",&player);
  96.     printf("\n");
  97.     unsigned turn;
  98.     for(turn = 0; turn < 9 && win(board) == 0; ++turn) {
  99.         if((turn+player) % 2 == 0)
  100.             computerMove(board);
  101.         else {
  102.             draw(board);
  103.             playerMove(board);
  104.         }
  105.     }
  106.     switch(win(board)) {
  107.         case 0:
  108.             printf("A draw. Ho hum.\n");
  109.             break;
  110.         case 1:
  111.             draw(board);
  112.             printf("You lose.\n");
  113.             break;
  114.         case -1:
  115.             printf("You win. Inconceivable!\n");
  116.             break;
  117.     }
  118. }
  119.