initial commitHEADmaster

1 files changed, 301 insertions, 0 deletions

diff --git a/tictactoe.c b/tictactoe.c
new file mode 100644
index 0000000..1fa48ef
--- /dev/null
+++ b/tictactoe.c
@@ -0,0 +1,301 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <unistd.h>
+#include <termios.h>
+#include <time.h>
+
+typedef struct 
+{
+    uint16_t bm; 
+    char icon;
+} Player;
+
+typedef struct
+{
+    Player max_player;
+    Player min_player;
+} Board;
+
+const uint16_t wincombs[8] = {
+        0b111000000, 0b000111000, 0b000000111, 0b100100100, 
+        0b010010010, 0b001001001, 0b100010001, 0b001010100};
+
+void render(Board *board);
+uint8_t askmove(Board *board, char *player); 
+uint8_t evaluate(Board *board);
+void checkposition(Board *board);
+uint8_t minimax_alpha_beta(Board *board, bool ismax, uint8_t alpha, uint8_t beta);
+uint8_t best_move(Board *board, bool ismax);
+unsigned int random_number(unsigned int limit);
+
+int main(void) 
+{
+    Board activeBoard = {
+        .max_player = {.bm = 0b000000000, .icon = 'x'}, 
+        .min_player = {.bm = 0b000000000, .icon = 'o'}
+    };
+    uint8_t user_move;
+    uint8_t computer_move;
+
+    time_t time = clock();
+    computer_move = best_move(&activeBoard, false);
+    time = clock() - time;
+
+    double exec_time = ((double) time) / CLOCKS_PER_SEC;
+    printf("bestmove function took %f seconds\n", exec_time);
+    int scanvar;
+    scanf("%d", &scanvar);
+
+    while (true) {
+        checkposition(&activeBoard);
+        render(&activeBoard);
+        user_move = askmove(&activeBoard, &activeBoard.max_player.icon);
+        activeBoard.max_player.bm ^= 0b100000000 >> user_move;
+        checkposition(&activeBoard);
+        computer_move = best_move(&activeBoard, false);
+        activeBoard.min_player.bm ^= 0b100000000 >> computer_move;
+    }
+    return 0;
+}
+
+void render(Board *board) 
+{
+    uint8_t i;
+    uint16_t wincomb;
+    uint16_t color_bm = 0b000000000;
+
+    for (i = 0; i < 8; i++) {
+        wincomb = wincombs[i];
+        if ((wincomb & board->max_player.bm) == wincomb || (wincomb & board->min_player.bm) == wincomb) {
+            color_bm |= wincomb;
+        }
+    }
+    printf(
+        "\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n───┼───┼───\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n───┼───┼───\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n", 
+        (0b100000000 & color_bm) ? "\x1b[7m" : "", 
+        (0b100000000 & board->max_player.bm) ? board->max_player.icon : (0b100000000 & board->min_player.bm) ? board->min_player.icon : '1', 
+        (0b010000000 & color_bm) ? "\x1b[7m" : "", 
+        (0b010000000 & board->max_player.bm) ? board->max_player.icon : (0b010000000 & board->min_player.bm) ? board->min_player.icon : '2', 
+        (0b001000000 & color_bm) ? "\x1b[7m" : "", 
+        (0b001000000 & board->max_player.bm) ? board->max_player.icon : (0b001000000 & board->min_player.bm) ? board->min_player.icon : '3', 
+        (0b000100000 & color_bm) ? "\x1b[7m" : "", 
+        (0b000100000 & board->max_player.bm) ? board->max_player.icon : (0b000100000 & board->min_player.bm) ? board->min_player.icon : '4', 
+        (0b000010000 & color_bm) ? "\x1b[7m" : "", 
+        (0b000010000 & board->max_player.bm) ? board->max_player.icon : (0b000010000 & board->min_player.bm) ? board->min_player.icon : '5', 
+        (0b000001000 & color_bm) ? "\x1b[7m" : "", 
+        (0b000001000 & board->max_player.bm) ? board->max_player.icon : (0b000001000 & board->min_player.bm) ? board->min_player.icon : '6', 
+        (0b000000100 & color_bm) ? "\x1b[7m" : "", 
+        (0b000000100 & board->max_player.bm) ? board->max_player.icon : (0b000000100 & board->min_player.bm) ? board->min_player.icon : '7', 
+        (0b000000010 & color_bm) ? "\x1b[7m" : "", 
+        (0b000000010 & board->max_player.bm) ? board->max_player.icon : (0b000000010 & board->min_player.bm) ? board->min_player.icon : '8', 
+        (0b000000001 & color_bm) ? "\x1b[7m" : "", 
+        (0b000000001 & board->max_player.bm) ? board->max_player.icon : (0b000000001 & board->min_player.bm) ? board->min_player.icon : '9'
+    );
+}
+
+uint8_t askmove(Board *board, char *player)
+{
+    static struct termios term_settings;
+    char c;
+    uint16_t empty_cells = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
+    uint8_t i;
+    uint16_t cell_bm;
+
+    /* changing term settings for special input */
+    tcgetattr(STDIN_FILENO, &term_settings);
+    term_settings.c_lflag ^= ICANON | ECHO;
+    tcsetattr(STDIN_FILENO, TCSANOW, &term_settings);
+
+    printf("\nWhere do you want to place your %c?\n", *player);
+
+    while ((c = getc(stdin)) != EOF) {
+        for (i = 0; i < 9; i++) {
+            cell_bm = 0b100000000 >> i;
+            if (empty_cells & cell_bm && c - '1' == i) {
+
+                /* restoring old term settings */
+                term_settings.c_lflag ^= ICANON | ECHO;
+                tcsetattr(STDIN_FILENO, TCSANOW, &term_settings);
+
+                return i;
+            }
+        }
+    }
+    exit(0);
+}
+
+uint8_t evaluate(Board *board) 
+{
+    uint8_t i;
+    uint16_t wincomb;
+
+    /* 
+    0 -> position not terminal
+    1 reserved for -infinity
+    2 -> player2 wins
+    3 -> draw = noone wins
+    4 -> player1 wins
+    5 reserved for infinity
+    */
+
+    for (i = 0; i < 8; i++) {
+        wincomb = wincombs[i];
+        if ((wincomb & board->max_player.bm) == wincomb) {
+            return 4;
+        }
+        if ((wincomb & board->min_player.bm) == wincomb) {
+            return 2;
+        }
+    }
+    if ((board->max_player.bm | board->min_player.bm) == 0b111111111) {
+        return 3;
+    }
+    return 0;
+}
+
+void checkposition(Board *board)
+{
+    uint8_t eval = evaluate(board);
+    uint16_t color_bm;
+    uint8_t i;
+    uint16_t wincomb;
+
+    if (eval) {
+        render(board);
+        if (eval == 3) {
+            printf("\nDRAW\n\n");
+        } else if (eval == 4) {
+            printf("\n%c won the game!\n\n", board->max_player.icon);
+        } else if (eval == 2) {
+            printf("\n%c won the game!\n\n", board->min_player.icon);
+        }
+        exit(0);
+    }
+}
+
+uint8_t minimax_alpha_beta(Board *board, bool ismax, unsigned char alpha, unsigned char beta)
+{
+    uint16_t empty_cells_bm = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
+    uint8_t eval = evaluate(board);
+    uint8_t bestvalue;
+    uint8_t i;
+    uint16_t cell_bm;
+    uint8_t minimax_value;
+
+    if (eval) {
+        return eval;
+    }
+
+    if (ismax) {
+        bestvalue = 1;
+        for (i = 0; i < 9; i++) {
+            cell_bm = 0b100000000 >> i;
+            if (cell_bm & empty_cells_bm) {
+                board->max_player.bm ^= cell_bm;
+                minimax_value = minimax_alpha_beta(board, false, alpha, beta);
+                board->max_player.bm ^= cell_bm;
+                if (minimax_value > bestvalue) {
+                    bestvalue = minimax_value;
+                    if (bestvalue > alpha) {
+                        alpha = bestvalue;
+                    }
+                    if (alpha >= beta) {
+                        break;
+                    }
+                }
+            }
+        }
+    } else {
+        bestvalue = 5;
+        for (i = 0; i < 9; i++) {
+            cell_bm = 0b100000000 >> i;
+            if (cell_bm & empty_cells_bm) {
+                board->min_player.bm ^= cell_bm;
+                minimax_value = minimax_alpha_beta(board, true, alpha, beta);
+                board->min_player.bm ^= cell_bm;
+                if (minimax_value < bestvalue) {
+                    bestvalue = minimax_value;
+                    if (bestvalue < beta) {
+                        beta = bestvalue;
+                    }
+                    if (alpha >= beta) {
+                        break;
+                    }
+                }
+            }
+        }
+    }
+    return bestvalue;
+}
+
+uint8_t best_move(Board *board, bool ismax) 
+{
+    uint8_t bestvalue;
+    uint8_t i;
+    uint16_t cell_bm;
+    uint16_t empty_cells_bm = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
+    uint8_t minimax_value;
+    uint8_t cell_values[9];
+    uint8_t ctr = 0;
+    uint8_t choice;
+
+    if (ismax) {
+        bestvalue = 1;
+        for (i = 0; i < 9; i++) {
+            cell_bm = 0b100000000 >> i;
+            if (cell_bm & empty_cells_bm) {
+                board->max_player.bm ^= cell_bm;
+                minimax_value = minimax_alpha_beta(board, !ismax, 1, 5);
+                board->max_player.bm ^= cell_bm;
+                if (minimax_value == bestvalue) {
+                    cell_values[i] = minimax_value;
+                    ++ctr;
+                } else if (minimax_value > bestvalue) {
+                    bestvalue = minimax_value;
+                    cell_values[i] = minimax_value;
+                    ctr = 1;
+                }
+            }
+        }
+    } else {
+        bestvalue = 5;
+        for (i = 0; i < 9; i++) {
+            cell_bm = 0b100000000 >> i;
+            if (cell_bm & empty_cells_bm) {
+                board->min_player.bm ^= cell_bm;
+                minimax_value = minimax_alpha_beta(board, !ismax, 1, 5);
+                board->min_player.bm ^= cell_bm;
+                if (minimax_value == bestvalue) {
+                    cell_values[i] = minimax_value;
+                    ++ctr;
+                } else if (minimax_value < bestvalue) {
+                    bestvalue = minimax_value;
+                    cell_values[i] = minimax_value;
+                    ctr = 1;
+                }
+            }
+        }
+    }
+    choice = random_number(ctr);
+    for (i = 0; i < 9; i++) {
+        if (cell_values[i] == bestvalue) {
+            if (!choice) {
+                return i;
+            } else {
+                --choice;
+            }
+        }
+    }
+    return 0b11111111;
+}
+
+unsigned int random_number(unsigned int limit)
+{
+    srand(time(0));
+    return rand() % limit;
+}
+
+/* python exectime > 0.066766 */
+/* C exectime > 0.003077 */
\ No newline at end of file