tic tac toe with bitboard, negamax and alpha-beta pruning

tictactoe.c

/* 
 * 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;
}