// Os and Xs - (c) 2024 Andrew Lea
#include
#include
#define and && // We define logical 'and' and 'or' to
#define or || // distinguish from the bit-twiddlers.
// === Board ===
typedef unsigned int BitBoard; // 9 bits used as a list of squares.
typedef struct { BitBoard Os; // One bit-boards for each player,
BitBoard Xs; } Board; // that can easily be "or'd" together.
static const BitBoard FirstSq = 0b1, LastSq = 0b100000000, FullBoard = 0b111111111;
#define NO_LINES 8
static const BitBoard Lines[NO_LINES] = {0b100010001, 0b001010100, // Diagonal
0b000000111, 0b000111000, 0b111000000, // Horizontal
0b001001001, 0b010010010, 0b100100100 };// Vertical
static bool line(const BitBoard brd) { // Return true if there is a line.
for (unsigned l = 0; l < NO_LINES; l++)
if ((Lines[l] & brd) == Lines[l]) // Examine each candidate in turn.
return true;
return false; // No line, so return false.
}
// === Moves ===
typedef unsigned int MoveSet; // A set of moves: multiple bits set.
typedef unsigned int Move; // A single move: only one bit set.
// Move generator: returns a set of possible (empty) moves from this position.
static MoveSet possMoves(const Board b) { return FullBoard & ~(b.Os | b.Xs); }
static unsigned movesExamined[10] = { 0 }; // ... at each depth
// Return a new board after this move has been made
static Board makeMove(Board brd, const Move mv, const bool x, const unsigned depth) {
movesExamined[depth] += 1;
if (x)
brd.Xs |= mv;
else
brd.Os |= mv;
return brd;
}
// === Dynamic Evaluation ===
static Move report(const Move mv, const int score) {
printf("\t[%d]", __builtin_ffs(mv)); // show this move as a square
for (unsigned d = 1; d <= 9 and movesExamined[d]; d++) {
printf("\t%d: %d", d, movesExamined[d]);
movesExamined[d] = 0;
}
printf("\tscore: %d\n", score);
return mv; // Just as a convenience
}
static int maxMoveValue(const Board brd, const unsigned depth);
// Returns lowest, ie most "devestating", score O can acheive
static int minMoveValue(const Board brd, const unsigned depth) {
const MoveSet candidates = possMoves(brd);
if (candidates == 0) // Any moves possible?
return 0; // ...no, so its a draw
int minScore = 1000; // +'infinity'
for (Move mv = FirstSq; mv <= LastSq; mv <<= 1)
if (mv & candidates) { // Try each candidate move
const Board b = makeMove(brd, mv, false, depth);
if (line(b.Os))
return -100; // can immediately make a line
const int score = maxMoveValue(b, depth+1);
if (score < 0)
return score; // O can indirectly make a line
if (score < minScore)
minScore = score; // Note 'worst so far'
}
return minScore; // The 'worst' we can find
}
// Returns highest scoring X can acheive
static int maxMoveValue(const Board brd, const unsigned depth) {
const MoveSet candidates = possMoves(brd);
if (candidates == 0) // Any moves possible?
return 0; // ... no, so its a draw
int maxScore = -1000; // -'infinity'
for (Move mv = FirstSq; mv <= LastSq; mv <<= 1)
if (mv & candidates) { // Try each candidate move
const Board b = makeMove(brd, mv, true, depth);
if (line(b.Xs))
return +100; // X can directly make a line
const int score = minMoveValue(b, depth+1);
if (score > 0)
return score; // can indirectly make a line
if (score > maxScore)
maxScore = score; // Note 'best so far'
}
return maxScore; // The 'best' we can find
}
static Move minOmove(const Board brd) { // Find minimising move for O
Move bestMove = 0; int minScore = 1000;
const MoveSet candidates = possMoves(brd); // Get all the possible moves
for (Move mv = FirstSq; mv <= LastSq; mv <<= 1)
if (mv & candidates) {
const Board b = makeMove(brd, mv, false, 1);
if (line(b.Os)) // Can immediately make a line
return report(mv, -100);
const int score = maxMoveValue(b, 2);
if (score < minScore) {
bestMove = mv;
minScore = score;
}
report(mv, score);
}
if (minScore < 0) printf("O is going to win.\n");
return bestMove;
}
static Move maxXmove(const Board brd) { // Find maximising move for X
Move bestMove = 0; int maxScore = -1000;
const MoveSet candidates = possMoves(brd); // Get all the possible moves
for (Move mv = FirstSq; mv <= LastSq; mv <<= 1)
if (mv & candidates) {
const Board b = makeMove(brd, mv, true, 1);
if (line(b.Xs))
return report(mv, 100); // Can immediately make a line
const int score = minMoveValue(b, 2);
if (score > maxScore) {
bestMove = mv;
maxScore = score;
}
report(mv, score);
}
if (maxScore > 0) printf("X is going to win.\n");
return bestMove;
}
// === I/O ===
static char piece(const Board b, const Move sq) { // Returns O or X for
return b.Os & sq ? 'O' : (b.Xs & sq ? 'X' : ' '); // this board position
}
static void displayBoard(const Board b) {
for (Move q = FirstSq; q < LastSq; q <<= 3) {
printf("\t\t%c | %c | %c\n", piece(b, q), piece(b, q*2), piece(b, q*4));
if (q <= 0b100000)
printf("\t\t--+---+--\n");
}
}
static Move askMove(const MoveSet unAvailable) { // Request and validate move
int m = 0;
do {printf("Your move [1..9] > ");
scanf("%d", & m);
} while (m < 1 or m > 9 or ((1 << (m-1)) & unAvailable));
return 1 << (m-1);
}
// === Game ===
int main(int argc, char * argv[]) {
Board game; game.Os = 0; game.Xs = 0;
printf("\nO&X\n\n1 | 2 | 3\n--+---+--\n4 | 5 | 6\n--+---+--\n7 | 8 | 9\n");
for (unsigned turn = 1; turn <= 9; turn++) {
printf("\n%d: %c's turn\n", turn, turn % 2 ? 'X' : 'O');
const Move mv = turn % 2 ? askMove(~possMoves(game)): minOmove(game);
game = makeMove(game, mv, turn % 2, 0);
displayBoard(game);
if (line(game.Xs) or line(game.Os))
return printf("%c wins!\n", turn % 2 ? 'X' : 'O');
}
printf("Draw\n");
}