tictactoe

tictactoe.h (8985B)

---

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <time.h>
 
 #include "./print_box.h"
 
 #define SCRATCH_BOARD "XXOOOXXOX"
 #define X_WINS_COLUMN "XXOXOOXOX"
 #define X_WINS_DIAG   "XOO XOOXX"
 #define X_WINS_ROW    " OOOXOXXX"
 #define O_WINS_COLUMN "OOXOXXOX "
 #define O_WINS_DIAG   "OXXOOXX O"
 #define O_WINS_ROW    " XXXOXOOO"
 
 #define scase(s1, s2)    if (!strcmp(s1, s2))
 
 #define OPPONENT    (player == 'O' ? 'X' : 'O')
 
 static char  the_desired_board[32];
 static _Bool srand_seeded = 0;
 struct move { int move_ind; char winner; };
 
 static int get_rand(int max_excl) {
 #ifndef UNIT_TEST
     FILE *urandom = fopen("/dev/urandom", "r");
     if(urandom) {
         int rnd = 0;
         size_t z = fread(&rnd, sizeof(int), 1, urandom);
         fclose(urandom);
         if(z) {
             if(rnd < 0) rnd *= -1;
             return rnd % max_excl;
         }
     }
 #endif
     /* fallback if somehow we can't open urandom or read 4 bytes from it */
     if (!srand_seeded) {
         time_t seed = time(NULL);
         /* save seed for later in case of bugs, so they're reproducible */
         FILE *seed_file = fopen("seed", "w");
         if(seed_file) {
             fprintf(seed_file, "%ld\n", seed);
             fclose(seed_file);
         }
         srand(seed);
         srand_seeded = 1;
     }
     return rand() % max_excl;
 }
 char get_winner_or_winning_moves(char *b, char *winning_moves) {
     char center = b[4];
     _Bool add_to_wm = 0; 
     /* Check status of squares on either side of center: row, column and diagonal */
     for(int i=-4; i < 0; i++) {
         int sq1 = 4+i;
         int sq3 = 4-i;
         if(b[sq1] == b[sq3] && b[sq1] != ' ') {
             if(b[sq1] == center)
                 return center;
             if(center == ' ')
                 add_to_wm = 1;
         }
         if(winning_moves == NULL) continue;
         if(add_to_wm) {
             /* Normally means `w...[4] = b[s...]`, but allows us
              * to detect later on if it is a winning move for both */
             winning_moves[4] |= b[sq1];
             add_to_wm = 0;
         }
         else if(center == ' ') continue;
         else if((b[sq1] == center) ^ (b[sq3] == center)) {
             if(b[sq1] == ' ')
                 winning_moves[sq1] |= center;
             else if(b[sq3] == ' ')
                 winning_moves[sq3] |= center;
         }
     }
     for(int i=1; i <= 7; i+=2){
         /* (i+1)&4 -> side column, else upper or lower row */
         int distance = ((i+1) & 4) ? 3 : 1;
         int sq1 = i - distance;
         int sq3 = i + distance;
         if(b[sq1] == b[sq3] && b[sq1] != ' ') {
             if(b[sq1] == b[i])
                 return b[i];
             if(b[i] == ' ')
                 add_to_wm = 1;
         }
         if(winning_moves == NULL) continue;
         if(add_to_wm) {
             winning_moves[i] |= b[sq1];
             add_to_wm = 0;
         }
         else if(b[i] == ' ') continue;
         else if((b[sq1] == b[i]) ^ (b[sq3] == b[i])) {
             if(b[sq1] == ' ')
                 winning_moves[sq1] |= b[i];
             else if(b[sq3] == ' ')
                 winning_moves[sq3] |= b[i];
         }
     }
     return 0;
 }
 
 void set_board(char *board_name) {
     scase(board_name, "scratch_board")
         strcpy(the_desired_board, SCRATCH_BOARD);
     scase(board_name, "x_wins_column")
         strcpy(the_desired_board, X_WINS_COLUMN);
     scase(board_name, "x_wins_diag")
         strcpy(the_desired_board, X_WINS_DIAG);
     scase(board_name, "x_wins_row")
         strcpy(the_desired_board, X_WINS_ROW);
     scase(board_name, "o_wins_column")
         strcpy(the_desired_board, O_WINS_COLUMN);
     scase(board_name, "o_wins_diag")
         strcpy(the_desired_board, O_WINS_DIAG);
     scase(board_name, "o_wins_row")
         strcpy(the_desired_board, O_WINS_ROW);
 }
 
 char get_move_preset_board(char *board, char player) {
     char *desired_board = the_desired_board;
     for(int i=0; i < 9; i++) {
         if(desired_board[i] == player && board[i] == ' ') {
             board[i] = player;
             return get_winner_or_winning_moves(board, NULL);
         }
     }
     return 0;
 }
 char get_these_moves(char *board, char player) {
     /* Automate any specific sequence of moves, for debugging */
     static int moves[9] = {1, 2, 5, 6, 7,};
     static int m = 0;
     board[moves[m++]] = player;
     return 0;
 }
 char get_move_from_human(char *board, char player) {
     int n;
     print_msg("%c's move? [1-9]: ", player);
     tb_present();
     scanf("%d", &n);
     board[n-1] = player;
     return get_winner_or_winning_moves(board, NULL);
 }
 static int get_legal_moves(char *board, int legal_moves[]) {
     int lm_ind = 0;
     for(int i=0; i < 9; i++)
         if(board[i] == ' ')
             legal_moves[lm_ind++] = i;
     return lm_ind;
 }
 char get_random_move(char *board, char player) {
     int legal_moves[9];
     int lm_cnt = get_legal_moves(board, legal_moves);
     board[legal_moves[get_rand(lm_cnt)]] = player;
     return get_winner_or_winning_moves(board, NULL);
 }
 static char try_make_winning_move(char *board, char player, _Bool block_opponent) {
     char all_winning_moves[10] = "";
     get_winner_or_winning_moves(board, all_winning_moves);
     int my_winning_moves_inds[5], his_winning_moves_inds[5];
     int mwm_ind_ind = 0, hwm_ind_ind = 0;
     for(int i=0; i < 9; i++) {
         /* Get all possible winning moves, including optionally the opponent's;
          * add indices of each to an array ... */
         if((all_winning_moves[i] & player) == player)
             my_winning_moves_inds[mwm_ind_ind++] = i;
         else if(block_opponent && all_winning_moves[i] == OPPONENT)
             his_winning_moves_inds[hwm_ind_ind++] = i;
     }
     /* ...then choose one at random, mine if possible, else the opponent's (if opted for) */
     if(mwm_ind_ind) {
         board[my_winning_moves_inds[get_rand(mwm_ind_ind)]] = player;
         return player;
     }
     if(hwm_ind_ind) {
         board[his_winning_moves_inds[get_rand(hwm_ind_ind)]] = player;
         /* N.B. This will not be reached if the move is a winning move for both players */
         return 0;
     }
     return get_random_move(board, player);
 }
 char get_winning_move_else_random(char *board, char player) {
     return try_make_winning_move(board, player, 0);
 }
 char get_winning_move_else_block_else_random(char *board, char player) {
     return try_make_winning_move(board, player, 1);
 }
 static struct move minimax_best_move(char *board, char player, int *legal_moves, int lm_cnt) {
     char winning_moves[10] = "";
     int i;
     get_winner_or_winning_moves(board, winning_moves);
     int his_wm_cnt = 0;
     int blocking_move = -1;
     for(i=0; i < 9; i++) {
         /* As good as won */
         if((winning_moves[i] & player) == player) {
             struct move m = {.move_ind = i, .winner = player};
             return m;
         }
         if(winning_moves[i] == OPPONENT) {
             his_wm_cnt++;
             blocking_move = i;
         }
     }
     if(lm_cnt <= 2) {
         /* If there's <= 2 moves remaining, and no opportunity
          * to win next turn, it's a draw. If the opponent has
          * exactly one winning move, we will block it.
          * If more than one, opponent wins. */
         struct move m;
         m.winner   = his_wm_cnt > 1 ? OPPONENT      : 0;
         m.move_ind = his_wm_cnt > 0 ? blocking_move : legal_moves[0]; 
         return m;
     }
 
     struct move *moves = malloc(sizeof(struct move) * lm_cnt);
     for(i=0; i < lm_cnt; i++) {
         char new_board[10];
         int *new_legal_moves = malloc(sizeof(int) * 9);
         memcpy(new_board, board, 10);
         memcpy(new_legal_moves, legal_moves, 9 * sizeof(int));
         new_board[legal_moves[i]] = player;
         /* Just move the array to point to lm...[1] */
         if(i == 0)
             new_legal_moves++;
         else if(i < lm_cnt - 1)
             for(int j=i+1; j < lm_cnt; j++)
                 new_legal_moves[j-1] = legal_moves[j];
         moves[i] = minimax_best_move(new_board, OPPONENT, new_legal_moves, lm_cnt - 1);
         /* Just get first definite win */
         if(moves[i].winner == player) {
             struct move ret = {legal_moves[i], player};
             free(moves);
             return ret;
         }
     }
     /* No wins -- try for a draw */
     int scratch_moves[9];
     int sm_cnt = 0;
     while(lm_cnt-->0)
         if(moves[lm_cnt].winner == 0)
             scratch_moves[sm_cnt++] = legal_moves[lm_cnt];
     struct move ret;
     if(sm_cnt) {
         ret.winner = 0;
         ret.move_ind = scratch_moves[get_rand(sm_cnt)];
     }
     else {
         ret.winner = OPPONENT;
         ret.move_ind = legal_moves[0]; //whatever
     }
     free(moves);
     return ret;
 }
 char get_move_minimax(char *board, char player) {
     int legal_moves[9];
     int lm_cnt = get_legal_moves(board, legal_moves);
     int best_move = minimax_best_move(board, player, legal_moves, lm_cnt).move_ind;
     board[best_move] = player;
     return get_winner_or_winning_moves(board, NULL);
 }