initial commitHEADmaster

2 files changed, 432 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
diff --git a/tictactoe.py b/tictactoe.py
new file mode 100644
index 0000000..f6b2c70
--- /dev/null
+++ b/tictactoe.py
@@ -0,0 +1,131 @@
+import random
+
+board = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
+wincombs = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6))
+player1 = 'x'
+player2 = 'o'
+
+def render(board):
+    print(f'''
+ {board[0]} │ {board[1]} │ {board[2]} 
+───┼───┼───
+ {board[3]} │ {board[4]} │ {board[5]} 
+───┼───┼───
+ {board[6]} │ {board[7]} │ {board[8]}''')
+
+def evaluate(board):
+    for wincomb in wincombs:
+        if board[wincomb[0]] == board[wincomb[1]] == board[wincomb[2]] == player1:
+            return 1
+        if board[wincomb[0]] == board[wincomb[1]] == board[wincomb[2]] == player2:
+            return -1
+    if all(cell in {player1, player2} for cell in board):
+        return 0
+
+def askmove(board):
+    for _ in range(3):      # 3 attempts
+        userinput = input('\nWhere do you want to place your x? > ')
+        if userinput in {'1', '2', '3', '4', '5', '6', '7', '8', '9'}:
+            idx = int(userinput) - 1
+            if board[idx] not in {player1, player2}:
+                return idx
+        print('\nInvalid input')
+        return askmove(board)
+    exit(0)
+
+def emptycells(board):
+    for cell in board:
+        if cell not in {player1, player2}:
+            yield cell
+
+def checkposition(board):
+    eval = evaluate(board)
+    if eval is not None:
+        render(board)
+        if eval == 0:
+            print('\nDRAW\n')
+        if eval == 1:
+            print(f'\n{player1} won the game!\n')
+        if eval == -1:
+            print(f'\n{player2} won the game!\n')
+        exit(0)
+
+def minimax(board, ismax, alpha = -float('inf'), beta = float('inf')):
+
+    eval = evaluate(board)
+    if eval is not None:
+        return eval
+    
+    if ismax:
+        bestvalue = -float('inf')
+        for cell in emptycells(board):
+            idx = int(cell) - 1
+            board[idx] = player1
+            minimaxvalue = minimax(board, False, alpha, beta)
+            board[idx] = cell
+            if minimaxvalue > bestvalue:
+                bestvalue = minimaxvalue
+                alpha = max(alpha, bestvalue)
+                if alpha >= beta:
+                    break
+    else:
+        bestvalue = float('inf')
+        for cell in emptycells(board):
+            idx = int(cell) - 1
+            board[idx] = player2
+            minimaxvalue = minimax(board, True, alpha, beta)
+            board[idx] = cell
+            if minimaxvalue < bestvalue:
+                bestvalue = minimaxvalue
+                beta = min(beta, bestvalue)
+                if alpha >= beta:
+                    break
+    return bestvalue
+
+def bestmoves(board, ismax):
+    bestmovelist = []
+    if ismax:
+        bestvalue = -float('inf')
+        for cell in emptycells(board):
+            idx = int(cell) - 1
+            board[idx] = player1
+            minimaxvalue = minimax(board, False)
+            board[idx] = cell
+            if minimaxvalue == bestvalue:
+                bestmovelist.append(cell)
+            elif minimaxvalue > bestvalue:
+                bestvalue = minimaxvalue
+                bestmovelist = [cell]
+    else:
+        bestvalue = float('inf')
+        for cell in emptycells(board):
+            idx = int(cell) - 1
+            board[idx] = player2
+            minimaxvalue = minimax(board, True)
+            board[idx] = cell
+            if minimaxvalue == bestvalue:
+                bestmovelist.append(cell)
+            elif minimaxvalue < bestvalue:
+                bestvalue = minimaxvalue
+                bestmovelist = [cell]
+    return bestmovelist
+    
+import time
+
+if __name__ == '__main__':
+    while True:
+        starttime = time.time()
+        bestmoves_list = bestmoves(board, False)
+        computermove = random.choice(bestmoves_list)
+        exectime = time.time() - starttime
+        print('exectime >', exectime)
+        input()
+        render(board)
+        usermove = askmove(board)
+        board[usermove] = player1
+        checkposition(board)
+        bestmoves_list = bestmoves(board, False)
+        computermove = random.choice(bestmoves_list)
+        idx = int(computermove) - 1
+        board[idx] = player2
+        checkposition(board)
\ No newline at end of file