From d475ede435018fc0a9289b1396c6891b7b22c72d Mon Sep 17 00:00:00 2001 From: root Date: Wed, 9 Jul 2025 15:24:51 +0200 Subject: initial commit --- tictactoe.c | 301 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 301 insertions(+) create mode 100644 tictactoe.c (limited to 'tictactoe.c') 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 +#include +#include +#include +#include +#include +#include + +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 -- cgit v1.2.3