//	Os and Xs - (c) 2024 Andrew Lea

#include <stdio.h>
#include <stdbool.h>

#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");
}