tictactoe

commit 812bd5d20a182ea1b6e3cb5dbc8a06ce7b203106
parent d02b840e2bfabd7475676f9c669a535e7c91f8a5
Author: Wilson Gheen <wilson@wilsonrgheen.com>
Date:   Tue, 20 Dec 2022 16:40:21 -0600

WIP: Added the beginning of an unbeatable minimax AI. Stops moving altogether if it can't win

Diffstat:
M
tictactoe.c
 | 
7
++-----
M
tictactoe.h
 | 
88
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----

2 files changed, 85 insertions(+), 10 deletions(-)
diff --git a/tictactoe.c b/tictactoe.c
@@ -1,9 +1,6 @@
 #include <stdint.h>
 #include <stdio.h>
-#define TB_IMPL
-#include <termbox.h>
 
-#include "../life/print_box.h"
 #include "tictactoe.h"
 
 #define SIDE_BY_SIDE 1
@@ -24,7 +21,7 @@ static void print_board(char *board) {
 
 char play(char (*get_move)(char*, char), char (*get_move_2)(char*, char)) {
     struct tb_event ev;
-    char board[9] = "         ";
+    char board[10] = "         ";
     char winner = 0;
     char player = 'O';
     if(get_move_2 == NULL)
@@ -47,7 +44,7 @@ char play(char (*get_move)(char*, char), char (*get_move_2)(char*, char)) {
 int main(void) {
     struct tb_event ev;
     tb_init();
-    char winner = play(get_winning_move_else_block_else_random, NULL);
+    char winner = play(get_move_minimax, get_move_from_human);
     if(winner)
         print_msg("%c wins.", winner);
     else
diff --git a/tictactoe.h b/tictactoe.h
@@ -3,6 +3,8 @@
 #include <string.h>
 #include <time.h>
 
+#include "../life/print_box.h"
+
 #define SCRATCH_BOARD "XXOOOXXOX"
 #define X_WINS_COLUMN "XXOXOOXOX"
 #define X_WINS_DIAG   "XOO XOOXX"
@@ -17,15 +19,18 @@
 
 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) {
     if (!srand_seeded) {
         time_t seed = time(NULL);
         FILE *f = fopen("seed", "w");
         if(f) {
-            fprintf(f, "%d\n", seed);
+            fprintf(f, "%ld\n", seed);
             fclose(f);
         }
+        else
+            puts("Failed to open file");
         srand(seed);
         srand_seeded = 1;
     }
@@ -128,17 +133,21 @@ char get_move_from_human(char *board, char player) {
     board[n-1] = player;
     return get_winner_or_winning_moves(board, NULL);
 }
-char get_random_move(char *board, char player) {
-    int legal_moves[9];
+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;
-    board[legal_moves[get_rand(lm_ind)]] = player;
+    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[9] = "";
+    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;
@@ -168,3 +177,72 @@ char get_winning_move_else_random(char *board, char player) {
 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] = "";
+    get_winner_or_winning_moves(board, winning_moves);
+    int his_wm_cnt = 0;
+    int i;
+    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;
+        }
+        /* `player` can't block both moves, so it's a loss */
+        if(winning_moves[i] == OPPONENT && ++his_wm_cnt > 1) {
+            struct move m = {.move_ind = i, .winner = OPPONENT};
+            return m;
+        }
+    }
+    i = 0;
+    for(int empties=0; i < 9; i++)
+        if(board[i] == ' ' && ++empties > 2) break;
+    if(i >= 9) {
+        /* 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.) */
+        struct move m = {.move_ind = -1, .winner = 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 */
+    while(lm_cnt-->0) {
+        if(moves[lm_cnt].winner == 0) {
+            struct move ret = moves[lm_cnt];
+            free(moves);
+            ret.move_ind = legal_moves[lm_cnt];
+            return ret;
+        }
+    }
+    struct move ret = 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);
+}