TicTacToe AI matchbox thing from 28/7/2020, working state unknown

matchbox-ttt.c

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

/* board state storage:
 *  pstate -> whether X or O owns a given board part
 *  bstate -> which parts of the board are set
 */

#define LGET(s, i)			((s >> (i)) & 1)
#define LSET(s, i)			s |= (1 << (i))

#define CGET(s, x, y)		LGET(s, (x) + (y)*3)
#define CSET(s, x, y)		LSET(s, (x) + (y)*3)

#define CTOL(x, y)			((x) + (y)*3)

#define PDEFAULT			10

#define LSETALL				0b111111111
#define LSETNONE			0b000000000

#define MATCHPATTERN(m, p)	(((m) & (p)) == (p))

typedef struct
{
	uint16_t pstate;
	uint16_t bstate;
} boardstate_t;

typedef struct
{
	boardstate_t state;
	int alteration;
} board_t;

typedef struct
{
	int id;
	boardstate_t state;
	int possibilities[9];
} matchbox_t;

typedef struct
{
	int id;
	int ishuman;
	int moves[10];
	int moved[10];
} player_t;

typedef struct
{
	int id;
	matchbox_t *list;
	int count;
} ai_t;

ai_t ais[2] =
{
	{0, NULL, 0},
	{1, NULL, 0},
};

uint16_t vflipstate(uint16_t s)
{
	uint16_t sp0, sp1, sp2;

	sp0 = (s & 0b001001001) << 2;
	sp1 = (s & 0b010010010);
	sp2 = (s & 0b100100100) >> 2;
	return sp0 | sp1 | sp2;
}

uint16_t hflipstate(uint16_t s)
{
	uint16_t sp0, sp1, sp2;

	sp0 = (s & 0b000000111) << 6;
	sp1 = (s & 0b000111000);
	sp2 = (s & 0b111000000) >> 6;
	return sp0 | sp1 | sp2;
}

uint16_t rotstate(uint16_t s)
{
	uint16_t r = 0;
	int x, y;

	for (x = 0; x < 3; x++)
		for (y = 0; y < 3; y++)
			if (CGET(s, x, y))
				CSET(r, 2 - y, x);

	return r;
}

int mod(int n, int m)
{
	int r;

	r = n % m;

	if (n < 0)
		r += m;

	return r;
}

void
boardstate_flip(boardstate_t *state, int flip)
{

	if (flip & 0b01)
	{
		state->bstate = hflipstate(state->bstate);
		state->pstate = hflipstate(state->pstate);
	}
	if (flip & 0b10)
	{
		state->bstate = vflipstate(state->bstate);
		state->pstate = vflipstate(state->pstate);
	}
}

void
boardstate_rotate(boardstate_t *state, int rotate)
{
	int i;

	for (i = 0; i < rotate; i++)
	{
		state->bstate = rotstate(state->bstate);
		state->pstate = rotstate(state->pstate);
	}
}

void
board_restore(board_t *board)
{
	int rotate, flip;

	flip = board->alteration & 0b11;
	rotate = (board->alteration >> 2) & 0b11;

	if (rotate)
		boardstate_rotate(&board->state, 4 - rotate);
	if (flip)
		boardstate_flip(&board->state, flip);

	board->alteration = 0;
}

void
board_mutate(board_t *board, int alteration)
{
	int rotate, flip;

	board->alteration = alteration & 0b1111;

	flip = board->alteration & 0b11;
	rotate = (board->alteration >> 2) & 0b11;

	boardstate_flip(&board->state, flip);
	boardstate_rotate(&board->state, rotate);
}

int
board_matchstate(board_t *board, boardstate_t *state)
{
	int i;
	board_t cboard;

	for (i = 0; i <= 0b1111; i++)
	{
		memcpy(&cboard, board, sizeof(*board));
		board_mutate(&cboard, i);

		if (cboard.state.pstate != state->pstate)
			continue;
		if (cboard.state.bstate != state->bstate)
			continue;

		board_mutate(board, i);
		return 1;
	}

	return 0;
}

matchbox_t *
matchboxcreate(ai_t *ai, board_t *board)
{
	int i;
	matchbox_t *matchbox;

	ai->count++;
	ai->list = realloc(ai->list,
		ai->count * sizeof(matchbox_t));
	if (!ai->list)
	{
		printf("FATAL: ALLOCATION FAILED\n");
		printf("SIZE %d\n", ai->count * sizeof(matchbox_t));
		exit(0);
	}

	matchbox = &ai->list[ai->count - 1];

	matchbox->id = ai->count - 1;
	memcpy(&matchbox->state, &board->state, sizeof(matchbox->state));
	for (i = 0; i < 9; i++)
		matchbox->possibilities[i] = PDEFAULT;

	return matchbox;
}

matchbox_t *
matchboxfind(ai_t *ai, board_t *board)
{
	int i;

	for (i = 0; i < ai->count; i++)
		if (board_matchstate(board, &ai->list[i].state))
			return &ai->list[i];

	return matchboxcreate(ai, board);
}

const char *
getplayername(int playerid)
{
	return (playerid) ? "X" : "O";
}

void
computerturn(int round, boardstate_t *state, player_t *player)
{
	board_t cboard;
	matchbox_t *matchbox;
	int i, nrand, nmax = 0;

	memset(&cboard, 0, sizeof(cboard));
	memcpy(&cboard.state, state, sizeof(cboard.state));

	matchbox = matchboxfind(&ais[player->id], &cboard);

	for (i = 0; i < 9; i++)
		if (!LGET(cboard.state.bstate, i))
			nmax += matchbox->possibilities[i];

	for (i = nmax ? 9 : 0; i < 9; i++)
		if (!LGET(cboard.state.bstate, i))
			nmax += ++matchbox->possibilities[i];

	nrand = rand() % nmax;

	for (i = 0; i < 9; i++)
	{
		if (LGET(cboard.state.bstate, i))
			continue;
		if (!matchbox->possibilities[i])
			continue;
		nrand -= matchbox->possibilities[i];
		if (nrand <= 0)
			break;
	}
	i %= 9;

	if (player->id)
		LSET(cboard.state.pstate, i);
	LSET(cboard.state.bstate, i);

	player->moves[round] = matchbox->id;
	player->moved[round] = i;

	board_restore(&cboard);

	memcpy(state, &cboard.state, sizeof(*state));
}

void
computerlearn(player_t *player, int winner)
{
	matchbox_t *matchbox;
	int i = 0, chosen;

	for (i = 0; i < 10; i++)
	{
		if (player->moves[i] == -1)
			continue;

		matchbox = &ais[player->id].list[player->moves[i]];
		chosen = player->moved[i];

		if (winner == player->id)
			matchbox->possibilities[chosen] += 2;
		else if (winner == 2)
			matchbox->possibilities[chosen]++;
		else if (matchbox->possibilities[chosen] > 0)
			matchbox->possibilities[chosen]--;
	}
}

void
humanturn(int round, boardstate_t *board, player_t *player)
{
	char str[256];
	int x = 0, y = 0, okay = 0;

	while (!okay)
	{
		printf("%s TURN.\n", getplayername(player->id));
		printf("TYPE X, Y COORDINATES:\n");
		fflush(stdout);

		fgets(str, sizeof(str), stdin);

		okay = 1;
		okay &= sscanf(str, "%d, %d", &x, &y) == 2;
		okay &= (x >= 0) && (y >= 0);
		okay &= (x <= 2) && (y <= 2);

		if (okay)
			okay &= CGET(board->bstate, x, y) != 1;

		if (!okay)
			printf("ERROR.\n\n");
	}

	if (player->id)
		CSET(board->pstate, x, y);

	CSET(board->bstate, x, y);
}

void
turn(int round, boardstate_t *board, player_t *player)
{
	if (player->ishuman)
		humanturn(round, board, player);
	else
		computerturn(round, board, player);
}

void
draw(int round, boardstate_t *board)
{
	int y, x;

	printf("\033[2J\033[H");
	printf("\nROUND %d:\n\n", round);

	for (y = 0; y < 3; y++)
	{
		for (x = 0; x < 3; x++)
		{
			printf(" %s %c",
				((CGET(board->bstate, x, y)) ?
					getplayername(CGET(board->pstate, x, y)) :
					" "),
				((x < 2) ?
					'|' :
					'\n'));
		}
		if (y < 2)
			printf("---+---+---\n");
	}

	printf("\n\n");
	fflush(stdout);
}

int
gameend(boardstate_t *board, int *winner)
{
	int i, playerset;

	for ((*winner) = 0; (*winner) < 2; (*winner)++)
	{
		playerset = board->pstate;
		playerset ^= (*winner) ? LSETNONE : LSETALL;
		playerset &= board->bstate;

		if (MATCHPATTERN(playerset, 0b100010001))
			return 2;
		if (MATCHPATTERN(playerset, 0b001010100))
			return 2;

		for (i = 0; i < 3; i++)
		{
			int row = board->pstate >> (3 * i);
			if (MATCHPATTERN(playerset >> (i * 3), 0b111))
				return 2;
			if (MATCHPATTERN(playerset >> i, 0b1001001))
				return 2;
		}
	}

	return (board->bstate == LSETALL);
}

void
drawwinstatus(int winner)
{
	const char *s;

	if (winner < 2)
		s = getplayername(winner);
	else
		s = "NONE";

	printf("WINNER: %s.\n", s);
}

void
play(int playercount)
{
	player_t players[2];
	boardstate_t board;
	int playerid, round, winner, i, j;

	playerid = 0;
	round = 0;
	memset(&board, 0, sizeof(board));
	memset(&players, 0, sizeof(players));

	for (i = 0; i < 2; i++)
	{
		players[i].id = i;
		if (playercount > i) 
			players[i].ishuman = 1;
		else
		{
			for (j = 0; j < 10; j++)
				players[i].moves[j] = -1;
		}
	}

	do
	{
		if (playercount)
			draw(round, &board);
		turn(round, &board, &players[playerid]);

		playerid ^= 1;
		round++;
	} while(!gameend(&board, &winner));

	draw(round, &board);
	drawwinstatus(winner);
	
	for (i = 0; i < 2; i++)
		if (!players[i].ishuman)
			computerlearn(&players[i], winner);
		
	//printf("COUNT AI 0: %d\n", ais[0].count);
	//printf("COUNT AI 1: %d\n", ais[1].count);
}

int getplayerscount(char *str)
{
	if ((*str == '0') || !strcmp(str, "ZERO"))
		return 0;
	if ((*str == '1') || !strcmp(str, "ONE"))
		return 1;
	if ((*str == '2') || !strcmp(str, "TWO"))
		return 2;

	return 0;
}


int main()
{
	int playerscount, run, i;
	char str[256];

	srand(time(NULL));

	while(1)
	{
		printf("\033[2J\033[H");
		printf("NUMBER OF PLAYERS?\n");
		fgets(str, sizeof(str), stdin);

		playerscount = getplayerscount(str);

		if (!playerscount)
		{
			printf("HOW MANY TIMES?\n");
			fgets(str, sizeof(str), stdin);
			run = atoi(str);
		}
		else
			run = 1;

		for (i = 0; i < run; i++)
		{
			play(playerscount);

			if (!playerscount)
			{
				printf("\n\nPLAYED: %d / %d\n", i + 1, run);
				//usleep(5000);
			}
		}

		printf("\n\nFINISHED. PLAY AGAIN?\n");
		fgets(str, sizeof(str), stdin);
		if (*str != 'Y')
			break;
	}

	return 0;
}

#if 0
int main()
{
	int i;
	srand(time(NULL));

	board_t board;
	memset(&board, 0, sizeof(board));

	CSET(board.state.bstate, 0, 0);
	CSET(board.state.bstate, 1, 0);
	CSET(board.state.bstate, 1, 2);
	CSET(board.state.bstate, 2, 2);
	CSET(board.state.pstate, 1, 0);

	for (i = 0; i <= 0b1111; i++)
	{
		int rotate = i >> 2;
		int flip  = i & 0b11;

		printf("\nhflip: %d\n", !!(flip & 0b01));
		printf("vflip: %d\n", !!(flip & 0b10));
		printf("angle: %d\n\n", rotate * 90);
		
		board_mutate(&board, i);
		draw(-1, &board.state);
	}

	board_restore(&board);
		draw(-1, &board.state);

	return 0;
}
#endif