diff options
| -rw-r--r-- | tictactoe.c | 301 | ||||
| -rw-r--r-- | tictactoe.py | 131 |
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 |