// PIC-TAC-TOE, 0/1/2 Player Tic-Tac-Toe in a PIC16F874 microcontroller
// EC331 Final Project, Fall 2000
// Colin Hill and Peter Haugen

#include <pic.h>

// keypad codes for 0-f
const unsigned char codes[16] = {0xee,0xde,0xbe,0x7e,0xed,0xdd,0xbd,0x7d,0xeb,0xdb,0xbb,0x7b,0xe7,0xd7,0xb7,0x77};

// keypad remappings for the board keys
const unsigned char remaps[16] = {0,1,2,0xff,3,4,5,0xff,6,7,8,0xff,0xc,0xd,0xe,0xf};

// bitmasks for eight possible winning states
const unsigned int winstates[8] = {0x007,0x038,0x1c0,0x049,0x092,0x124,0x111,0x054};

// board score table (easier than taking a power)
const int scores[4] = {0,10,100,1000};

// function to read the state of the keypad
// returns 0xff if no key pressed or 0-0xf
// for the remapped key code
char readpad(void) {
	unsigned int i;
	unsigned char read;

	// assert low bits
	TRISD = 0xf0;
	PORTD = 0x00;

	// debounce delay
	for(i=0;i<5000;i++) ;
	read = PORTD;

	// assert high bits
	TRISD = 0x0f;
	PORTD = 0x00;

	// debounce delay
	for(i=0;i<5000;i++) ;

	// assemble code
	read |= PORTD;

	// check and remap
	for(i=0;i<16;i++) if (read == codes[i]) return remaps[i];

	// default, no key pressed
	return 0xff;
}

// red and green board bitfields and used mask
unsigned int board[2], mask;

// turn indicator and player count variables
unsigned char turn, players;

void showboard(void) {
	// show majority of red board
	PORTA = board[0] & 0xff;
	// show majority of green board
	PORTB = board[1] & 0xff;
	// show the rest of the boards and the turn indicator
	PORTC = ((board[0] & 0x100) >> 8)|((board[1] & 0x100) >> 7)|
		(turn << 7)|((turn^1) << 6)|((board[1] & 0x08) >> 1);
	PORTE = ((board[0] & 0xc0) >> 6) | ((board[0] & 0x10) >> 2); 
}

// setup a new game given the selected key
void newgame(int pad) {
	if (pad == 0xc) {
		// clear the boards and set the turn to red
		board[0] = board[1] = mask = turn = 0;
		// no human players
		players = 0;
	} else if (pad == 0xd) {
		// clear the boards and set the turn to green (PIC moves)
		board[0] = board[1] = mask = 0;
		// one human player
		players = 1; turn = 1;
	} else if (pad == 0xe) {
		// clear the boards and set the turn to red
		board[0] = board[1] = mask = turn = 0;
		// one human player
		players = 1;
	} else if (pad == 0xf) {
		// clear the boards and set the turn to red
		board[0] = board[1] = mask = turn = 0;
		// two human players
		players = 2;
	}
}

// check for a win, if so, flash the winning combination
// then, wait for a key press and reset the game.
// returns 1 if there is a win, 0 otherwise
int checkwin(void) {
	unsigned int i, j, k, t = board[turn];
	unsigned char pad;
	for(i=0;i<8;i++) { // check each of the winning bitmasks
		j = winstates[i];
		if ((t & j) == j) { // win?
			// if it's a win, wait for a key to be released
			do pad = readpad(); while (pad != 0xff);
			do {
				// flash the winning move by
				// xoring the mask on the board
				showboard();
				board[turn] ^= j;
				for(k=0;k<50000;k++) ;
				showboard();
				board[turn] ^= j;
				for(k=0;k<50000;k++);
				pad = readpad();
				// until there is a newgame key pressed
			} while ((pad < 0xc)||(pad > 0xf));
			// initiate the new game
			newgame(pad);
			// return 1 for a win
			return 1;
		}
	}
	// no win, return 0
	return 0;
}

// take a move from the keypad for the player and handle new game keys
void playermove(void) {
	unsigned char pad;
	unsigned int i, j;

	// wait until no key is pressed
	do pad = readpad(); while (pad != 0xff);
	// wait until a new key is pressed
	do pad = readpad(); while (pad == 0xff);
	// wait for the release
	while (readpad() != 0xff) ;
	// if it's a valid square
	if (pad < 9) {
		// if there is no mark in that square
		if (!(mask & (1 << pad))) {
			// set the mask and the board square
			mask |= (1 << pad);
			board[turn] |= (1 << pad);
			// check for a win . . if no, switch the turn
			if (checkwin()) {
			} else turn ^= 1;
		} else {
			// there already is a mark there
			// save the boards
			int ob1 = board[0];
			int ob2 = board[1];
			// flash the square yellow by setting the square
			// both red and green
			board[0] |= (1 << pad);
			board[1] |= (1 << pad);
			showboard();
			for(j=0;j<5;j++)
				for(i=0;i<20000;i++) ;
			// restore the board
			board[0] = ob1;
			board[1] = ob2;
		}
	} else newgame(pad); // pad > 9, must be a newgame
}

// PIC's initial opening move
int opening = 5;

// score the board state for the current color and return the value
int scoreboard() {
	int score = 0;
	unsigned char i, j, me, them;

	// check each winning state
	for(i=0;i<8;i++) {
		me = them = 0; // initialize counters
		
		for(j=0;j<9;j++) { // for each square in the mask
			int m = (1 << j);
			if (winstates[i] & m) {
				// increment counters if there is a mark there
				if (board[turn] & m) me++;
				if (board[turn^1] & m) them++;
			}
		}

		// change scores if and only if there are marks of a
		// single color in this winning combination, otherwise
		// the score is irrelevant because it can't result in a
		// win anyway
		if (them == 0) score += scores[me];
		if (me == 0) score -= scores[them];
	}
	// return the score
	return score;
}

// pick a move for the current color and make it
// note: the opening is randomized because with
// the scoring mechanism, the algorithm will always
// pick the middle square
void picmove() {
	unsigned char i, j, pos;
	int max = -10000, min, score; // initialize maximum to some arbitrary low value
	for(i=0;i<9;i++) {
		// for each square that is empty
		if (!(mask & (1 << i))) {
			// try to move here
			board[turn] ^= (1 << i);
			mask ^= (1 << i);
			// initialize minimum to some arbitrary large integer
			min = 10000;

			// now, anticipate responses
			for(j=0;j<9;j++) {
				// for each additional square that's empty
				if (!(mask & (1 << j))) {
					// move the opponent here
					board[turn^1] ^= (1 << j);
					// minimize the response score
					if (scoreboard() < min) min = scoreboard();
					// restore the board
					board[turn^1] ^= (1 << j);
				}
			}

			// accumulate this score				
			score = scoreboard()+min;

			// maximize the total score
			if (score > max) {
				max = score;
				// save the position
				pos = i;
			}
			// restore board state
			board[turn] ^= (1 << i);
			mask ^= (1 << i);
		}
	}
	// ok, a move is selected . . . now make the move

	// if this is not the opening
	if (mask != 0) {
		// make the computer selected move
		board[turn] |= (1 << pos);
		mask |= (1 << pos);
	} else {
		// use the opening move
		board[turn] |= (1 << opening);
		mask |= (1 << opening);
		// cycle the opening to make it interesting
		opening = (opening+4)%9;
	}
	
	// check for wins, if not, flip the turn
	if (checkwin()) {
	} else turn ^= 1;
}

// check for a draw . . if there is one, wait for a keypress
// and reset the game
void checkstale() {
	unsigned char pad;
	unsigned int k, b1 = board[0], b2 = board[1];

	// check for a full board mask
	if (mask != 0x1ff) return;

	// wait for the pad to not have a key pressed	
	do pad = readpad(); while (pad != 0xff);
	do {
		// flash the while board
		showboard();
		board[0] ^= b1;
		board[1] ^= b2;
		for(k=0;k<50000;k++) ;
		showboard();
		// restore the board
		board[0] ^= b1;
		board[1] ^= b2;
		for(k=0;k<50000;k++);
		pad = readpad();
		// wait for a new game key
	} while ((pad < 0xc)||(pad > 0xf));

	// reset the game
	newgame(pad);
}

// main program goes here
void main(void) {
	// default, one player, player goes first
	players = 1;
	// initialize port tristate registers
	TRISA = TRISB = TRISC = TRISE = 0;
	TRISD = 0xff;
	board[0] = board[1] = mask = turn = 0;

	// main game loop
	for(;;) {
		// show the board
		showboard();

		// if there are two players, always have the player move next
		if (players == 2) {
			playermove();
		} else if (players == 1) {
			// if there is one player, have the computer move green
			if (turn == 0) playermove();
			else picmove();
		} else {
			// no players, computer always moves
			picmove();
		}
		// check for a draw
		checkstale();
	}
}