uttt/uttt.c

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <curses.h>
#include <signal.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <string.h>
#include <errno.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdarg.h>

struct ut_state
{
	char tiles[9][9];
	char boards[3][3];
	int playBoard;
	char player;
};
const struct ut_state ut_initial = {
		.boards = {0},
		.tiles = {0},
		.playBoard = -1,
		.player = 'X',
};
struct ut_move
{
	char r, c;
};
struct ut_game
{
	char l;
	struct ut_move moves[81];
};

const char HELP_TEXT[] = "\
Usage: uttt (--local | --agent | --host | --join)\n\
\n\
  --local  play local game\n\
  --agent  play against AI agent\n\
  --host   host game at 127.0.0.1:6669\n\
  --join   join game at 127.0.0.1:6669\n\
";

const char arg_local[] = "--local";
const char arg_agent[] = "--agent";
const char arg_host[] = "--host";
const char arg_join[] = "--join";

const char PLAY_BOARDS[][14] = {
	"top left", "top middle", "top right",
	"middle left", "middle", "middle right",
	"bottom left", "bottom middle", "bottom right",
	"all boards",
};

char ut_turn(char player)
{
	switch(player)
	{
		case 'X': return 'O';
		case 'O': return 'X';
		default: return '\0';
	}
}

#define T(r, c) (tiles[offset + stride * r + c])
char ut_winnerBoard(const char *tiles, int offset, int stride) {

	// whoreizontal wins
	for (int y = 0; y < 3; y++)
	{
		char tile = T(y, 0);
		if (tile == '\0') {continue;}
		if (tile == T(y, 1) && tile == T(y, 2)) {return tile;}
	}

	// vertical wins
	for (int x = 0; x < 3; x++)
	{
		char tile = T(0, x);
		if (tile == '\0') {continue;}
		if (tile == T(1, x) && tile == T(2, x)) {return tile;}
	}

	// diagonalz
	char tile = T(1, 1);
	if (tile != '\0')
	{
		if (tile == T(0, 0) && tile == T(2, 2)) {return tile;}
		if (tile == T(2, 0) && tile == T(0, 2)) {return tile;}
	}

	for(int y = 0; y < 3; y++)
	{
		for(int x = 0; x < 3; x++)
		{
			if(T(y, x) == '\0') {return '\0';} // in progress
		}
	}
	return ' '; // draw
}
char ut_winner(const struct ut_state *state)
{
	return ut_winnerBoard((char *)state->boards, 0, 3);
}

int ut_move(struct ut_state *new_state, const struct ut_state *old_state, struct ut_move m)
{
	// bad move - out of bounds
	if(m.r < 0 || m.r >= 9 || m.c < 0 || m.c >= 9) {return 1;}

	// state->playBoard == -1 means all boards playable; otherwise only one board is playable
	if (old_state->playBoard != -1 && old_state->playBoard != 3 * (m.r / 3) + (m.c / 3)) {return 1;}

	// bad move - tile is occupied
	if(old_state->tiles[m.r][m.c] != '\0') {return 1;}

	// bad move - board is finished
	if(old_state->boards[m.r / 3][m.c / 3] != '\0') {return 1;}

	// just check if move valid
	if(!new_state) {return 0;}

	// copy old_state->{tiles,boards} to new_state->{tiles,boards}
	memmove(new_state->tiles, old_state->tiles, sizeof(old_state->tiles));
	memmove(new_state->boards, old_state->boards, sizeof(old_state->boards));

	// do move
	new_state->tiles[m.r][m.c] = old_state->player;
	new_state->boards[m.r / 3][m.c / 3] = ut_winnerBoard((char *)new_state->tiles, 27 * (m.r / 3) + 3 * (m.c / 3), 9);

	//  next play board - if next play board is not playable, play any board
	new_state->playBoard = new_state->boards[m.r % 3][m.c % 3] == '\0' ? 3 * (m.r % 3) + (m.c % 3) : -1;

	new_state->player = ut_turn(old_state->player);
	return 0;
}


int curs_line;
void ut_curserase(void)
{
	curs_line = 0;
	erase();
}
void ut_cursprint(const char *str, int n)
{
	mvaddnstr(curs_line, 0, str, n);
	int y, x;
	getyx(stdscr, y, x);
	curs_line = y;
}
int ut_writefill(int fd, const char *x, size_t l)
{
	while(l > 0)
	{
		int r = write(fd, x, l);
		if(r < 0)
		{
			if(errno == EAGAIN || errno == EWOULDBLOCK || errno == EINTR) {continue;}
			else {return 1;}
		}
		x += r; l -= r;
	}
	return 0;
}
#define MAX_LINE 128
int ut_cursprintf(const char *restrict format, ...)
{
	char line[MAX_LINE];
	va_list ap;
	va_start(ap, format);
	int n = vsnprintf(line, MAX_LINE, format, ap);
	va_end(ap);
	if(n < 0 || n > MAX_LINE - 1) {return -1;}
	ut_cursprint(line, n);
	return n;
}
int ut_dprintf(int fd, const char *restrict format, ...)
{
	char line[MAX_LINE];
	va_list ap;
	va_start(ap, format);
	int n = vsnprintf(line, MAX_LINE, format, ap);
	va_end(ap);
	if(n < 0 || n > MAX_LINE - 1) {return -1;}
	if(ut_writefill(fd, line, n)) {return -1;}
	return n;
}

void ut_drawBoard(void (*mvch)(void*, int, int, char), void *arg, const char *tiles, int offset, int stride, int iy, int ix, char winner, bool highlight)
{
	// 7x7 board display
	/*
	 * X|X|X
	 * -+-+-
	 * X|X|X
	 * -+-+-
	 * X|X|X
	*/
	for(int r = 0; r < 3; r++) // tiles
		for(int c = 0; c < 3; c++)
			mvch(arg, iy + 2 * r + 1, ix + 2 * c + 1, T(r, c) != '\0' ? T(r, c) : ' ');
	//char info = winner != '\0' ? winner : highlight ? '*' : ' ';
	for(int r = 0; r < 3; r++) // |
		for(int c = 0; c < 2; c++)
			mvch(arg, iy + 2 * r + 1, ix + 2 * c + 1 + 1, '|');
	for(int r = 0; r < 2; r++) // -
		for(int c = 0; c < 3; c++)
			mvch(arg, iy + 2 * r + 1 + 1, ix + 2 * c + 1, '-');
	for(int r = 0; r < 2; r++) // +
		for(int c = 0; c < 2; c++)
			mvch(arg, iy + 2 * r + 1 + 1, ix + 2 * c + 1 + 1, highlight ? '*' : '+');
	for(int r = 0; r < 7; r++) // | boundary
		for(int c = 0; c < 2; c++)
			mvch(arg, iy + r, ix + 6 * c, winner != '\0' ? winner : ' ');
	for(int r = 0; r < 2; r++) // - boundary
		for(int c = 0; c < 7; c++)
			mvch(arg, iy + 6 * r, ix + c, winner != '\0' ? winner : ' ');
}
#define DTILES_Y 21
#define DTILES_X 21
void ut_drawTiles(void (*mvch)(void*, int, int, char), void *arg, const struct ut_state *state, bool numbers, struct ut_move lm)
{
	for(int r = 0; r < 3; r++)
		for(int c = 0; c < 3; c++)
			ut_drawBoard(mvch, arg, (char *)state->tiles,
				    27 * r + 3 * c, 9,
				    7 * r, 7 * c,
				    state->boards[r][c],
				    state->boards[r][c] == '\0' && (state->playBoard == -1 || state->playBoard == 3 * r + c));
	if(numbers)
	{
		for(int b = 0; b < 3; b++)
			for(int c = 0; c < 3; c++)
				mvch(arg, 0, 7 * b + 2 * c + 1, '0' + 3 * b + c);
		for(int b = 0; b < 3; b++)
			for(int r = 0; r < 3; r++)
				mvch(arg, 7 * b + 2 * r + 1, 0, '0' + 3 * b + r);
	}
	if(lm.r >= 0 && lm.r < 9 && lm.c >= 0 && lm.c < 9)
		mvch(arg, 7 * (lm.r / 3) + 2 * (lm.r % 3) + 1,
			  7 * (lm.c / 3) + 2 * (lm.c % 3) + 1,
			  state->tiles[lm.r][lm.c] == 'X' ? '%' : '0');
}
#define DBOARDS_Y 7
#define DBOARDS_X 7
void ut_drawBoards(void (*mvch)(void*, int, int, char), void *arg, const struct ut_state *state)
{
	ut_drawBoard(mvch, arg, (char *)state->boards,
		    0, 3,
		    0, 0,
		    '\0', false);
}

void ut_cursmvchc(void *arg, int y, int x, char c)
{
	bool colorized;
	if(colorized = has_colors())
	{
		color_set((c == 'X' || c == '%') ? 1 :
			  (c == 'O' || c == '0') ? 2 : 0, NULL);
	}
	bool bold;
	if(c == '%' || c == '0')
	{
		bold = true;
		attr_on(A_BOLD, NULL);
	}
	mvaddch(curs_line + y, x, c);
	if(bold) {attr_off(A_BOLD, NULL);}
	if(colorized) {color_set(0, NULL);}
}
void ut_tmvch(void *arg, int y, int x, char c)
{
	((char (*)[DTILES_X])arg)[y][x] = c;
}
void ut_bmvch(void *arg, int y, int x, char c)
{
	((char (*)[DBOARDS_X])arg)[y][x] = c;
}

int dtiles_line;
void ut_cursdraw(const struct ut_state *state, const struct ut_game *game)
{
	ut_cursprintf("Turn: %c  Play board: %s\n", (int)state->player, PLAY_BOARDS[(state->playBoard + 10) % 10]);
	dtiles_line = curs_line;
	ut_drawTiles(ut_cursmvchc, NULL, state, false, (game && game->l > 0) ? game->moves[game->l - 1] : (struct ut_move){-1, -1});
	curs_line += DTILES_Y;
	//ut_drawBoards(ut_cursmvchc, NULL, state);
}
void ut_sockdraw(const struct ut_state *state, const struct ut_game *game, int fd)
{
	ut_dprintf(fd, "Turn: %c\nPlay board: %s\n", (int)state->player, PLAY_BOARDS[(state->playBoard + 10) % 10]);
	char dtiles[DTILES_Y][DTILES_X];
	ut_drawTiles(ut_tmvch, dtiles, state, true, (game && game->l > 0) ? game->moves[game->l - 1] : (struct ut_move){-1, -1});
	for(int r = 0; r < DTILES_Y; r++)
	{
		ut_dprintf(fd, "%.*s\n", DTILES_X, dtiles[r]);
	}
}

void ut_cursmove(const struct ut_move m)
{
	ut_cursprintf("%d,%d", (int)m.c, (int)m.r);
}
void ut_cursgame(const struct ut_game *game)
{
	for(int i = 0; i < game->l; i++)
	{
		ut_cursmove(game->moves[i]);
		if(i + 1 < game->l)
		{
			ut_cursprintf(" ");
		}
	}
	ut_cursprintf("\n");
}
void ut_sockmove(const struct ut_move m, int fd)
{
	ut_dprintf(fd, "%d,%d\n", (int)m.c, (int)m.r);
}

int ut_readfill(int fd, char *x, size_t l)
{
	while(l > 0)
	{
		int r = read(fd, x, l);
		if(r < 0)
		{
			//printf("ut_readfill read:%d errno=%d\n", r, errno);
			if(errno == EAGAIN || errno == EWOULDBLOCK || errno == EINTR) {continue;}
			else {return 1;}
		}
		else if(r == 0) {return 2;}
		x += r; l -= r;
	}
	return 0;
}

int ut_cursgetmove(const struct ut_state *state, struct ut_move *m)
{
#define P(r, c, d) ((state->playBoard == -1 || state->playBoard == 3 * (r / 3) + (c / 3)) && \
	            (state->boards[r / 3][c / 3] == '\0' || d % 3 == 1))
	MEVENT event;
	ut_cursprintf("Select move with arrow keys or mouse.\n");
	if(m->r < 0 || m->r >= 9 || m->c < 0 || m->c >= 9)
	{
		m->r = 4; m->c = 4;
	}
	else if(state->playBoard == -1)
	{
		m->r = 3 * (m->r / 3) + 1;
		m->c = 3 * (m->c / 3) + 1;
	}
	else
	{
		m->r = 3 * (state->playBoard / 3) + 1;
		m->c = 3 * (state->playBoard % 3) + 1;
	}
	for(;;)
	{
		/*if(state->boards[m->r / 3][m->c / 3] != '\0')
		{
			m->r = 3 * (m->r / 3) + 1;
			m->c = 3 * (m->c / 3) + 1;
		}*/
		move(dtiles_line + (7 * (m->r / 3) + 1) + (2 * (m->r % 3)),
		     (7 * (m->c / 3) + 1) + (2 * (m->c % 3)));
		refresh();
		switch(getch())
		{
			case KEY_MOUSE:
				if(getmouse(&event) == OK && (event.bstate & BUTTON1_CLICKED))
				{
					event.y -= dtiles_line;
					if(event.y < 0 || event.y >= 21) {break;}
					if(event.x < 0 || event.x >= 21) {break;}
					m->r = (event.y % 7 - 1) / 2 + 3 * (event.y / 7);
					m->c = (event.x % 7 - 1) / 2 + 3 * (event.x / 7);
					if(((event.y % 7) - 1) % 2 != 0) {break;}
					if(((event.x % 7) - 1) % 2 != 0) {break;}
					return 0;
				}
				break;
			case 'k':  /* FALLTHROUGH */
			case 'w':  /* FALLTHROUGH */
			case KEY_UP:
				//m->r = (((m->r - 1) % 9) + 9) % 9;
				for(int i = 0; i < 9 + 1; i++)
				{
					m->r = (m->r + 9 - 1) % 9;
					if(P(m->r, m->c, m->r)) {break;}
				}
				break;
			case 'h':  /* FALLTHROUGH */
			case 'a':  /* FALLTHROUGH */
			case KEY_LEFT:
				//m->c = (((m->c - 1) % 9) + 9) % 9;
				for(int i = 0; i < 9 + 1; i++)
				{
					m->c = (m->c + 9 - 1) % 9;
					if(P(m->r, m->c, m->c)) {break;}
				}
				break;
			case 'j':  /* FALLTHROUGH */
			case 's':  /* FALLTHROUGH */
			case KEY_DOWN:
				//m->r = (m->r + 1) % 9;
				for(int i = 0; i < 9 + 1; i++)
				{
					m->r = (m->r + 1) % 9;
					if(P(m->r, m->c, m->r)) {break;}
				}
				break;
			case 'l':  /* FALLTHROUGH */
			case 'd':  /* FALLTHROUGH */
			case KEY_RIGHT:
				//m->c = (m->c + 1) % 9;
				for(int i = 0; i < 9 + 1; i++)
				{
					m->c = (m->c + 1) % 9;
					if(P(m->r, m->c, m->c)) {break;}
				}
				break;
			case ' ':  /* FALLTHROUGH */
			case '\r': /* FALLTHROUGH */
			case KEY_ENTER:
				return 0;
			case ERR:  /* FALLTHROUGH */
			default:
				break;
		}
	}
#undef P
}


int ut_ignore_line(int sock) {
	char byte;
	for (int i = 0; i < 128; i++) {
		if (ut_readfill(sock, &byte, 1)) {
			return 1;
		}
		if (byte == '\n') {return 0;}
	}
	return 2;
}

int ut_sockgetmove(const struct ut_state *state, int sock, struct ut_move *m, bool readable) {
	int index = 0;
	char byte;
	while (true) {
		if (ut_readfill(sock, &byte, 1)) {return 1;}
		// allow \r\n
		if (index == 3 && byte == '\r') {
			if (ut_readfill(sock, &byte, 1)) {return 1;}
		}
		if (index == 0 && byte == '|') {
			if (ut_ignore_line(sock)) {return -1;}
		} else if (index == 0) {
			m->c = byte - 0x30;
		} else if (index == 2) {
			m->r = byte - 0x30;
		} else if (index == 1 && byte != ',' || index == 3 && byte != '\n') {
			ut_cursprintf("Partner sent malformed coords - retrying\n");
			if (ut_ignore_line(sock)) {return 2;}
			if (readable) {
				ut_dprintf(sock, "Invalid coordinates. Try again: ");
			}
			index = 0;
			continue;
		}
		index++;
		if (index == 4) {break;}
	}
	//printf("x=%d y=%d\n", (int)m->c, (int)m->r);
	return 0;
}

int ut_local_game(struct ut_state *state, struct ut_game *game) {
	for(;;)
	{
		struct ut_move m = {4, 4};
		ut_curserase();
		ut_cursdraw(state, game);
		char w = ut_winner(state);
		if(w)
		{
			if(w == ' ')
			{
				ut_cursprintf("Draw!\n");
			}
			else
			{
				ut_cursprintf("%c wins!\n", (int)w);
			}
			break;
		}
		if(ut_cursgetmove(state, &m)) {continue;}
		if(ut_move(state, state, m)) {continue;}
		game->moves[game->l++] = m;
	}
	return 0;
}

int ut_network_game(struct ut_state *state, struct ut_game *game, int sock, char player, bool readable) {
	while (true) {
		struct ut_move m = {4, 4};
		ut_curserase();
		ut_cursdraw(state, game);
		if (readable) ut_sockdraw(state, game, sock);
		char w = ut_winner(state);
		if(w)
		{
			if(w == ' ')
			{
				ut_cursprintf("Draw!\n");
				if (readable) {ut_dprintf(sock, "\nDraw!\n");}
				close(sock);
			}
			else
			{
				ut_cursprintf("%c wins!\n", (int)w);
				if (readable) {ut_dprintf(sock, "\n%c wins!\n", (int)w);}
				close(sock);
			}
			break;
		}
		if (state->player == player) {
			if (readable) {ut_dprintf(sock, "Waiting for game partner ...\n");}
			if(ut_cursgetmove(state, &m)) {continue;}
			ut_sockmove(m, sock);
		} else {
			ut_cursprintf("Waiting for game partner ...\n");
			refresh();
			if (readable) {
				// line feed aligns game board each turn
				ut_dprintf(sock, "\nPlace token %c in position x,y: ", (int)ut_turn(player));
			}
			int err = ut_sockgetmove(state, sock, &m, readable);
			if(err != 0)
			{
				ut_cursprintf("received ");
				ut_cursmove(m);
				ut_cursprintf("\n");
			}
			if (err == 1) {
				ut_cursprintf("Connection closed.\n");
				return 1;
			}
			else if (err == 2) {
				ut_cursprintf("Partner sent too much data - exiting\n");
				return 1;
			}
		}
		if (readable) {ut_dprintf(sock, "\n");}
		if (ut_move(state, state, m)) {continue;}
		game->moves[game->l++] = m;
	}
	return 0;
}

char ut_random_player(void) {
	char player;
	int random = open("/dev/urandom", O_RDONLY);
	if (read(random, &player, 1) < 0) {return -1;}
	player = (player % 2 == 0) ? 'X' : 'O';
	return player;
}

int ut_host_game(struct ut_state *state, struct ut_game *game) {
	int sock = socket(AF_INET, SOCK_STREAM, 0);
	if (sock == -1) {
		ut_cursprintf("error %d\n", errno);
		return 1;
	}
	const struct sockaddr_in addr = {
		.sin_family = AF_INET,
		.sin_port = htons(6669),
		.sin_addr = { .s_addr = htonl(0x7f000001) },
	};
	setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, &(int){1}, sizeof(int));
	if (bind(sock, (struct sockaddr*)&addr, sizeof(addr)) == -1) {
		ut_cursprintf("error %d\n", errno);
		return 1;
	}
	if (listen(sock, 128) == -1) {
		ut_cursprintf("error %d\n", errno);
		return 1;
	}
	ut_cursprintf("Waiting for game partner at 127.0.0.1:6669 ...\n");
	refresh();
	int conn = accept(sock, NULL, NULL);
	if (conn == -1) {
		ut_cursprintf("error %d\n", errno);
		return 1;
	}
	close(sock);

	// decide X or O
	char player;
	if ((player = ut_random_player()) < 0) {return 1;}

	// check to determine readable
	char byte;
	ut_dprintf(conn, "| Press enter to start.\n");
	if (ut_readfill(conn, &byte, 1)) {
		ut_cursprintf("Connection closed.\n");
		return 1;
	}
	bool readable = (byte != '\0');
	if (byte != '\n') {
		int err = ut_ignore_line(conn);
		if (err == 1) {
			ut_cursprintf("Connection closed.\n");
			return 1;
		} else if (err == 2) {
			ut_cursprintf("Partner sent too much data - exiting\n");
			return 1;
		}
	}

	// tell partner X or O
	ut_dprintf(conn, "%c\n", (int)ut_turn(player));
	if (readable) {
		ut_dprintf(conn, "You play as: %c\n\n", ut_turn(player));
	}

	return ut_network_game(state, game, conn, player, readable);
}

int ut_join_game(struct ut_state *state, struct ut_game *game) {
	int sock = socket(AF_INET, SOCK_STREAM, 0);
	if (sock == -1) {
		ut_cursprintf("error %d\n", errno);
		return 1;
	}
	const struct sockaddr_in addr = {
		.sin_family = AF_INET,
		.sin_port = htons(6669),
		.sin_addr = { .s_addr = htonl(0x7f000001) },
	};
	ut_cursprintf("Connecting to game host at 127.0.0.1:6669 ...\n");
	refresh();
	if(connect(sock, (struct sockaddr*)&addr, sizeof(addr)) == -1)
	{
		ut_cursprintf("error %d\n", errno);
		return 1;
	}

	// tell host to deactivate readable
	ut_writefill(sock, "\0\n", 2);

	// host decides X or O
	char player[2];
	for (int i = 0; i < 10; i++) {
		int r = ut_readfill(sock, player, 1);
		ut_ignore_line(sock);
		if (*player == '|') {
			continue;
		}
		if (r == 2) {ut_cursprintf("Connection closed.\n");}
		if (r != 0) {return 1;}
		break;
	}
	if (*player != 'X' && *player != 'O') {
		ut_cursprintf("Host is retarded.\n");
		return 1;
	}

	return ut_network_game(state, game, sock, *player, false);
}

int ut_agentgetmove(const struct ut_state *state, const struct ut_game *game, struct ut_move *move);
int ut_agent_game(struct ut_state *state, struct ut_game *game) {
	char player;
	if ((player = ut_random_player()) < 0) {return 1;}
	for(;;)
	{
		struct ut_move m = {4, 4};
		ut_curserase();
		ut_cursdraw(state, game);
		char w = ut_winner(state);
		if(w)
		{
			if(w == ' ')
			{
				ut_cursprintf("Draw!\n");
			}
			else
			{
				ut_cursprintf("%c wins!\n", (int)w);
			}
			break;
		}
		if (state->player == player) {
			if(ut_cursgetmove(state, &m)) {continue;}
		} else {
			ut_cursprintf("Waiting for AI agent ...\n");
			refresh();
			if(ut_agentgetmove(state, game, &m))
			{
				ut_cursprintf("Agent failed - exiting\n");
				return 1;
			}
		}
		if(ut_move(state, state, m)) {continue;}
		game->moves[game->l++] = m;
	}
	return 0;
}


void finish(int sig)
{
//	putchar('\n');
	endwin();
	// other cleanup
	exit(0);
}
void waitfinish(int sig)
{
	ut_cursprintf("\nPress any key to exit.");
	refresh();
	mousemask(0, NULL);
	getch();
	finish(sig);
}
void begin(void)
{
	signal(SIGINT, finish);
	initscr();
	keypad(stdscr, TRUE);
	nonl(); // \r instead of \r\n
	cbreak();
	noecho();
	mousemask(BUTTON1_CLICKED, NULL);
	if (has_colors())
	{
		start_color();
		init_pair(1, COLOR_RED,     COLOR_BLACK);
		init_pair(2, COLOR_BLUE,    COLOR_BLACK);
	}
}

int main(int argc, char **argv) {

	struct ut_state state = ut_initial;
	struct ut_game game = {0};
	if (argc != 2) {
		printf(HELP_TEXT);
		return 1;
	} else if (strncmp(argv[1], arg_local, sizeof(arg_local)) == 0) {
		begin();
		waitfinish(ut_local_game(&state, &game));
	} else if (strncmp(argv[1], arg_agent, sizeof(arg_agent)) == 0) {
		begin();
		waitfinish(ut_agent_game(&state, &game));
	} else if (strncmp(argv[1], arg_host, sizeof(arg_host)) == 0) {
		begin();
		waitfinish(ut_host_game(&state, &game));
	} else if (strncmp(argv[1], arg_join, sizeof(arg_join)) == 0) {
		begin();
		waitfinish(ut_join_game(&state, &game));
	} else {
		printf(HELP_TEXT);
		return 1;
	}
	return 0;
}


int ut_boardValue(const char *tiles, int offset, int stride)
{
	// could change this too..
	int value = 0;
	for(int r = 0; r < 3; r++)
		for(int c = 0; c < 3; c++)
			value += (T(r, c) == 'X') ? 1 : (T(r, c) == 'O') ? -1 : 0;
	return value;
}
#define UT_VALUEMAX 81
#define UT_VALUEMIN (-81)
int ut_value(const struct ut_state *state)
{
	int value = 0;

	// game is won
	char winner = ut_winner(state);
	if(winner != '\0')
	{
		return (winner == 'X') ? UT_VALUEMAX : (winner == 'O') ? UT_VALUEMIN : 0;
	}

	// weight each board: 2x if taken, 2x if blank but would lead to a 2-of-3
	// line (for X or O), 1x otherwise
	/*char importance[3][3] = {1};
	for(int r = 0; r < 3; r++) {
		for(int c = 0; c < 3; c++) {
			char board = state->boards[r][c];
			if (board == '\0') {
				char b1, b2;
				// horizontal
				b1 = state->boards[r][(c+1)%3];
				b2 = state->boards[r][(c+2)%3];
				if (b2 < b1) { char tmp = b1; b1 = b2; b2 = tmp; }
				if (b1 == '\0' && b2 != '\0') importance[r][c] = 2;
				// vertical
				b1 = state->boards[(r+1)%3][c];
				b2 = state->boards[(r+2)%3][c];
				if (b2 < b1) { char tmp = b1; b1 = b2; b2 = tmp; }
				if (b1 == '\0' && b2 != '\0') importance[r][c] = 2;
				// diagonals
				if (r == c) {
					b1 = state->boards[(r+1)%3][(c+1)%3];
					b2 = state->boards[(r+2)%3][(c+2)%3];
					if (b2 < b1) { char tmp = b1; b1 = b2; b2 = tmp; }
					if (b1 == '\0' && b2 != '\0') importance[r][c] = 2;
				}
				if (r == 2 - c) {
					b1 = state->boards[(r+1)%3][(c+2)%3];
					b2 = state->boards[(r+2)%3][(c+1)%3];
					if (b2 < b1) { char tmp = b1; b1 = b2; b2 = tmp; }
					if (b1 == '\0' && b2 != '\0') importance[r][c] = 2;
				}
			}
			else if (board == 'X') importance[r][c] = 2;
			else if (board == 'O') importance[r][c] = 2;
		}
	}*/

	// game is in progress
	for(int r = 0; r < 3; r++) {
		for(int c = 0; c < 3; c++) {
			char board = state->boards[r][c];
			int board_value;
			if (board == '\0') {
				// board is in progress
				board_value = ut_boardValue((char *)state->tiles, 27 * r + 3 * c, 9);
			} else {
				// board is won
				board_value = (board == 'X') ? 9 : (board == 'O') ? -9 : 0;
			}
			value += board_value/* * importance[r][c]*/;
		}
	}

	return value;
}

int ut_alphabetaq(int (*value)(const struct ut_state *state), const struct ut_state *state, struct ut_move move, int depth, int a, int b)
{
	struct ut_state next;
	if(ut_move(&next, state, move)) {return (state->player == 'X') ? UT_VALUEMIN - 1 : UT_VALUEMAX + 1;}

	char winner = ut_winner(&next);
	if(winner != '\0')
	{
		return (winner == 'X') ? UT_VALUEMAX : (winner == 'O') ? UT_VALUEMIN : 0;
	}
	else if(depth <= 0) {return value(&next);}


	int q;
	if(next.player == 'X')
	{
		q = UT_VALUEMIN - 1;
		for(int r = 0; r < 9; r++)
		for(int c = 0; c < 9; c++)
		{
			struct ut_move next_move = (struct ut_move){r, c};
			int next_q = ut_alphabetaq(value, &next, next_move, depth - 1, a, b);
			if(next_q > q) {q = next_q;}
			if(q > b) {return q;}
			a = q > a ? q : a;
		}
	}
	else
	{
		q = UT_VALUEMAX + 1;
		for(int r = 0; r < 9; r++)
		for(int c = 0; c < 9; c++)
		{
			struct ut_move next_move = (struct ut_move){r, c};
			int next_q = ut_alphabetaq(value, &next, next_move, depth - 1, a, b);
			if(next_q < q) {q = next_q;}
			if(q < a) {return q;}
			b = q < b ? q : b;
		}
	}
	return q;
}

struct ut_move ut_minimax(int (*value)(const struct ut_state *state), const struct ut_state *state, int depth)
{
	struct ut_move best_move = {-1, -1};
	int best_q = (state->player == 'X') ? UT_VALUEMIN - 1 : UT_VALUEMAX + 1;
	for(int r = 0; r < 9; r++)
	for(int c = 0; c < 9; c++)
	{
		struct ut_move move = (struct ut_move){r, c};
		int q = ut_alphabetaq(value, state, move, depth - 1, UT_VALUEMIN - 1, UT_VALUEMAX + 1);
		if((state->player == 'X') ? q > best_q : q < best_q)
		{
			best_q = q;
			best_move = move;
		}
	}
	return best_move;
}

struct ut_statevalue
{
	unsigned char tilesxo[21];
	char value;
};
struct ut_statevalue ut_rolloutCache[16777216];
void ut_statetokey(struct ut_statevalue *sv, const struct ut_state *state)
{
	memset(sv->tilesxo, 0, sizeof(sv->tilesxo));
	char *tiles = (char *)state->tiles;
	for(int i = 0; i < sizeof(state->tiles); i++)
		sv->tilesxo[i / 4] |= ((tiles[i] == 'X') ? (1 << ((i % 4) * 2)) : 0) |
			              ((tiles[i] == 'O') ? (1 << ((i % 4) * 2 + 1)) : 0);
}
unsigned long ut_keytoidx(struct ut_statevalue *sv)
{
	//djb2 hash
	unsigned long hash = 5831;
	for(int i = 0; i < sizeof(sv->tilesxo); i++)
	{
		hash = ((hash << 5) + hash) ^ sv->tilesxo[i];
	}
	return hash % (sizeof(ut_rolloutCache) / sizeof(ut_rolloutCache[0]));
}
int ut_memValue(int value, const struct ut_state *state)
{
	struct ut_statevalue sv;
	sv.value = value;
	ut_statetokey(&sv, state);
	ut_rolloutCache[ut_keytoidx(&sv)] = sv;
	return value;
}
int ut_getValue(const struct ut_state *state, int *value)
{
	struct ut_statevalue sv;
	ut_statetokey(&sv, state);
	struct ut_statevalue *entry = &ut_rolloutCache[ut_keytoidx(&sv)];
	if(memcmp(sv.tilesxo, entry->tilesxo, sizeof(sv.tilesxo))) {return 1;}
	*value = entry->value;
	return 0;
}

#define UT_RDEPTH 2
#define UT_RTURNS 36
int ut_rollout(const struct ut_state *state)
{
	// memoization
	int value;
	if(!ut_getValue(state, &value)) {return value;}

	struct ut_state rstate = *state;
	int moves = 0;
	char winner;
	while((winner = ut_winner(&rstate)) == '\0' && moves < UT_RTURNS)
	{
		if(ut_move(&rstate, &rstate,
			   ut_minimax(ut_value, &rstate, UT_RDEPTH)))
		{
			return 0;
		}
		moves++;
	}
	return ut_memValue((winner == 'X') ? (UT_VALUEMAX - moves) :
		           (winner == 'O') ? (UT_VALUEMIN + moves) :
		           (winner == ' ') ? 0 : ut_value(&rstate), state);
}

#define UT_DEPTH 4
int ut_agentgetmove(const struct ut_state *state, const struct ut_game *game, struct ut_move *move)
{
	*move = ut_minimax(ut_rollout, state, UT_DEPTH);
	return (move->r < 0 || move->r >= 9 || move->c < 0 || move->c >= 9);
}