Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

repsilat

By: a guest on Oct 18th, 2009  |  syntax: C  |  size: 2.74 KB  |  views: 70  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }