Skip to content

Instantly share code, notes, and snippets.

@ggorlen

ggorlen/tictactoe.c

Created Sep 13, 2020
Embed
What would you like to do?
tic tac toe with bitboard, negamax and alpha-beta pruning
/*
* tic tac toe with bitboard, negamax and alpha-beta pruning
*
* todo:
* - variants
* - transposition table
*
* ref:
* - http://libfbp.blogspot.com/2017/05/tic-tac-toe-bitboards.html
*/
#include <stdbool.h>
#include <stdio.h>
#define ull unsigned long long
static ull wins[] = {
0x7, // 0b000000111,
0x38, // 0b000111000,
0x1c0, // 0b111000000,
0x124, // 0b100100100,
0x92, // 0b010010010,
0x49, // 0b001001001,
0x111, // 0b100010001,
0x54 // 0b001010100
};
typedef struct {
ull board; // 0b00000000ooooooooo000000xxxxxxxxx
unsigned int ply;
} tictactoe;
tictactoe tttcpy(const tictactoe *ttt) {
tictactoe cpy;
cpy.board = ttt->board;
cpy.ply = ttt->ply;
return cpy;
}
int tttdraw(const tictactoe *ttt) {
return ttt->ply > 8;
}
int tttwon(const tictactoe *ttt) {
int i;
if (ttt->ply > 3) {
for (i = 0; i < 8; i++) {
if ((wins[i] & ttt->board) == wins[i] ||
(wins[i] & ttt->board >> 16) == wins[i]) {
return true;
}
}
}
return false;
}
void tttinit(tictactoe *ttt) {
ttt->board = 0;
ttt->ply = 0;
}
int tttmove(tictactoe *ttt, unsigned int square) {
if (square >= 0 && square <= 8 &&
~ttt->board & (1/*ull ?*/ << (square + 16)) &&
~ttt->board & (1 << square)) {
ttt->board |= 1 << (square + (ttt->ply & 1 ? 16 : 0));
ttt->ply++;
return true;
}
return false;
}
void tttprint(const tictactoe *ttt) {
int i;
puts("");
for (i = 0; i < 9; i++) {
if (ttt->board & 1 << i) {
printf(" x");
}
else if (ttt->board & (1 << (i + 16))) {
printf(" o");
}
else {
printf(" %d", i + 1);
}
if (i % 3 == 2) { puts(""); }
}
puts("");
}
ull tttmoves(const tictactoe *ttt) {
return ttt->board >> 16 | ttt->board;
}
int _nega(tictactoe ttt, int depth, int a, int b, int *best_move) {
if (tttwon(&ttt)) { return -1; }
if (tttdraw(&ttt)) { return 0; }
int i;
int best_val = -2;
ull moves = tttmoves(&ttt);
for (i = 0; i < 9; i++) {
if (~moves >> i & 1) {
tictactoe cpy = tttcpy(&ttt);
tttmove(&cpy, i);
int child_val = -_nega(cpy, depth + 1, -b, -a, best_move);
if (child_val > a) { a = child_val; }
if (best_val < child_val) {
best_val = child_val;
if (depth == 0) { *best_move = i; }
}
}
if (a >= b) { break; }
}
return best_val;
}
int negamax(const tictactoe *ttt) {
int best_move;
_nega(*ttt, 0, -2, 2, &best_move);
return best_move;
}
int main() {
char c;
int d;
int i = 0;
tictactoe ttt;
tttinit(&ttt);
printf("Choose 'x' or 'o': ");
while (!scanf("%c", &c));
if (c == 'x') {
tttprint(&ttt);
i++;
}
for (;;) {
if (i & 1) {
printf("Enter cell number ('q' to quit): ");
if (!scanf("%d", &d)) { break; }
if (!tttmove(&ttt, d - 1)) { continue; }
}
else {
tttmove(&ttt, negamax(&ttt));
}
tttprint(&ttt);
if (tttwon(&ttt)) {
printf(ttt.ply & 1 ? "x" : "o");
puts(" wins");
break;
}
else if (tttdraw(&ttt)) {
puts("draw");
break;
}
i++;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment