/*

	LED_Matrix_TTT4.C - An AI version of Tic-Tac-Toe, played on a 4x4x4 LED matrix
        powered by an Arduino

    Copyright (C) 2011  Jeffrey R. Gilmour, Ph.D.

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <Sprite.h>
#include <Matrix.h>
#include <MsTimer2.h>	// Uses pins 3 & 11, so DON'T USE those

const int loadPin = 4;
const int clockPin = 5;
const int dataPin = 6;

Matrix myMatrix = Matrix(dataPin, clockPin, loadPin);

#define FALSE 0
#define TRUE !FALSE
boolean OLedsOn = TRUE;

char cube0[4][4][4], cube1[4][4][4], cube2[4][4][4], cube3[4][4][4], human_symbol='X', comp_symbol='O';

const int period = 200;

const int numRows = 2;
const int rowPins[numRows] = { 7, 8 };		// Keypad pins 1 & 2, attached to Arduino pins 7 & 8

const int numCols = 3;
const int colPins[numCols] = { 9, 10, 12 };	// Keypad pins 5, 6 & 7

const int debounceTime = 200;

const char keymap[numRows][numCols] = {		// USE PINS 1, 2, 5, 6, 7 on keypad
	{ '1', '2', '3' },
	{ '4', '5', '6' }
};


char key = 0;

int state = 0, state1x = 5, state1y = 5, state1z = 5;
int	bestmovex, bestmovey, bestmovez;

char getKey() {
	key = 0;	

	for (int column = 0; column < numCols; column++) {
		digitalWrite(colPins[column], LOW);
		for (int row = 0; row < numRows; row++) {
			if(digitalRead(rowPins[row]) == LOW) {
				delay(debounceTime);
				while(digitalRead(rowPins[row]) == LOW) ;
				key = keymap[row][column];
			}
		}
		digitalWrite(colPins[column], HIGH);
	}
	
	return key;
}

char check(char board[4][4]) {

	int i;

	for (i=0;i<4;i++)		/* check rows */
		if (board[i][0]==board[i][1] &&
		   board[i][0]==board[i][2] &&
		   board[i][0]==board[i][3]) if (board[i][0]!=' ')
		   	return board[i][1];
	
	for (i=1;i<=4;i++)		/* check columns */
		if (board[0][i]==board[1][i] &&
		   board[0][i]==board[2][i] &&
		   board[0][i]==board[3][i]) if (board[0][i]!=' ')
		   	return board[1][i];

	/* test diagonals */
	if (board[0][0]==board[1][1] && board[1][1]==board[2][2] &&
	   board[2][2]==board[3][3] && board[0][0]!=' ')
		return board[1][1];

	if (board[0][3]==board[1][2] && board[1][2]==board[2][1] &&
	   board[2][1]==board[3][0] && board[0][3]!=' ')
		 return board[1][2];

	return ' ';
}

void disp_LED_cube(void) {

	if (state == 0) {		// Default display of all moves
		for (int z=0;z<4;z++)
			for (int y=0;y<4;y++)
				for (int x=0;x<4;x++) {
					if (OLedsOn) {
						if (cube0[x][y][z] == 'O') {
							if (z == 0) {
								myMatrix.write(y, x, LOW);
							} else if (z == 1) {
								myMatrix.write(y, x+4, LOW);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, LOW);
							} else if (z == 3) {
								myMatrix.write(y+4, x, LOW);
							}
						}
					} else {
						if (cube0[x][y][z] != ' ') {
							if (z == 0) {
								myMatrix.write(y, x, HIGH);
							} else if (z == 1) {
								myMatrix.write(y, x+4, HIGH);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, HIGH);
							} else if (z == 3) {
								myMatrix.write(y+4, x, HIGH);
							}
						}
					}
				}
		OLedsOn = !OLedsOn;
	}

	if (state == 1) {	// setting up player's move
		myMatrix.clear();
		if (state1z < 5) {

						if (state1z == 0) {
							myMatrix.write(state1y, state1x, HIGH);
						} else if (state1z == 1) {
							myMatrix.write(state1y, state1x+4, HIGH);
						} else if (state1z == 2) {
							myMatrix.write(state1y+4, state1x+4, HIGH);
						} else if (state1z == 3) {
							myMatrix.write(state1y+4, state1x, HIGH);
						}


		} else
		if (state1y < 5) {
				for (int z=0;z<4;z++)
						if (z == 0) {
							myMatrix.write(state1y, state1x, HIGH);
						} else if (z == 1) {
							myMatrix.write(state1y, state1x+4, HIGH);
						} else if (z == 2) {
							myMatrix.write(state1y+4, state1x+4, HIGH);
						} else if (z == 3) {
							myMatrix.write(state1y+4, state1x, HIGH);
						}
		} else
		if (state1x < 5) {		
				for (int z=0;z<4;z++)
					for (int y=0;y<4;y++) {
						if (z == 0) {
							myMatrix.write(y, state1x, HIGH);
						} else if (z == 1) {
							myMatrix.write(y, state1x+4, HIGH);
						} else if (z == 2) {
							myMatrix.write(y+4, state1x+4, HIGH);
						} else if (z == 3) {
							myMatrix.write(y+4, state1x, HIGH);
						}
					}
		}
	}
	
	if (state == 3) {		// blinking last computer move
	
		if (OLedsOn) {
			if (bestmovez == 0) {
				myMatrix.write(bestmovey, bestmovex, LOW);
			} else if (bestmovez == 1) {
				myMatrix.write(bestmovey, bestmovex+4, LOW);
			} else if (bestmovez == 2) {
				myMatrix.write(bestmovey+4, bestmovex+4, LOW);
			} else if (bestmovez == 3) {
				myMatrix.write(bestmovey+4, bestmovex, LOW);
			}
		} else {
			if (bestmovez == 0) {
				myMatrix.write(bestmovey, bestmovex, HIGH);
			} else if (bestmovez == 1) {
				myMatrix.write(bestmovey, bestmovex+4, HIGH);
			} else if (bestmovez == 2) {
				myMatrix.write(bestmovey+4, bestmovex+4, HIGH);
			} else if (bestmovez == 3) {
				myMatrix.write(bestmovey+4, bestmovex, HIGH);
			}
		}
		OLedsOn = !OLedsOn;
	}

	if (state == 4) {		// computer "thinking"
		myMatrix.clear();
		for (int z=0;z<4;z++)
			for (int y=0;y<4;y++)
				for (int x=0;x<4;x++) {
					if (OLedsOn) {
						if (cube3[x][y][z] == 'O') {
							if (z == 0) {
								myMatrix.write(y, x, LOW);
							} else if (z == 1) {
								myMatrix.write(y, x+4, LOW);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, LOW);
							} else if (z == 3) {
								myMatrix.write(y+4, x, LOW);
							}
						}
					} else {
						if (cube3[x][y][z] != ' ') {
							if (z == 0) {
								myMatrix.write(y, x, HIGH);
							} else if (z == 1) {
								myMatrix.write(y, x+4, HIGH);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, HIGH);
							} else if (z == 3) {
								myMatrix.write(y+4, x, HIGH);
							}
						}
					}
				}
		OLedsOn = !OLedsOn;
	}

}


char check_cube(char cube[4][4][4]) {
	
	int x, y, z, n=0;
	char done, board[4][4];

	for (z=0;z<4;z++) {	/* boards in Z direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][y][z];
		done=check(board);
		if (done!=' ') return done;
	}

	for (z=0;z<4;z++) {	/* boards in Y direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][z][y];
		done=check(board);
		if (done!=' ') return done;
	}

	for (z=0;z<4;z++) {	/* boards in X direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[z][y][x];
		done=check(board);
		if (done!=' ') return done;
	}

	/* 3D diagonal 1 */
	if (cube[0][0][0]==cube[1][1][1] && cube[0][0][0]==cube[2][2][2]
		&& cube[0][0][0]==cube[3][3][3] && cube[0][0][0]!=' ')
		return cube[0][0][0];

	/* 3D diagonal 2 */
	if (cube[0][0][3]==cube[1][1][2] && cube[0][0][3]==cube[2][2][1]
		&& cube[0][0][3]==cube[3][3][0] && cube[0][0][3]!=' ')
		return cube[0][0][3];

	/* 3D diagonal 3 */
	if (cube[3][0][0]==cube[2][1][1] && cube[3][0][0]==cube[1][2][2]
		&& cube[3][0][0]==cube[0][3][3] && cube[3][0][0]!=' ')
		return cube[3][0][0];

	/* 3D diagonal 4 */
	if (cube[0][3][0]==cube[1][2][1] && cube[0][3][0]==cube[2][1][2]
		&& cube[0][3][0]==cube[3][0][3] && cube[0][3][0]!=' ')
		return cube[0][3][0];
	
	for (z=0;z<4;z++)	/* if no spaces are empty, game is a draw */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				if (cube[x][y][z]==' ') n++;
	if (n==0) {
		// Game is a draw - how to communicate to player?
		loop();
	}

	return done;
}

void copy_cube(char b2[4][4][4], char b1[4][4][4]) {

	int x,y,z;

	for (z=0;z<4;z++)
		for (y=0;y<4;y++) 
			for (x=0;x<4;x++) b2[x][y][z]=b1[x][y][z];
	
}

void get_computer_move(void) {

	long int	s0=-100000, s1, s2;
	int		test=0, x1, y1, z1, x2, y2, z2, x3, y3, z3, NoGood, NoGood2;
	int		score;
	char	done;

	state = 4;		// computer "thinking" LED display

	for (z1=0;z1<4;z1++) 
	    for (y1=0;y1<4;y1++) 
		for (x1=0;x1<4;x1++) {

		    s1=100000;
		    NoGood=FALSE;

		    if (cube0[x1][y1][z1]==' ') {
			copy_cube(cube1,cube0);
			cube1[x1][y1][z1]=comp_symbol;
			
			done = check_cube(cube1);	// Computer has WON!
			if (done==comp_symbol) {
				bestmovex = x1;
				bestmovey = y1;
				bestmovez = z1;

				state = 3;		// blinking last move of computer
				while (getKey() == 0) ;
				state = 0;

				copy_cube(cube0,cube1);

				while (getKey() == 0) ;
				loop();

			}

			for (z2=0;z2<4 && !NoGood;z2++)
			    for (y2=0;y2<4 && !NoGood;y2++)
					for (x2=0;x2<4 && !NoGood;x2++) {
					   	
				    	s2=-100000;
				    	NoGood2=FALSE;

					    if (cube1[x2][y2][z2]==' ') {
							copy_cube(cube2,cube1);
							cube2[x2][y2][z2]=human_symbol;

							for (z3=0;z3<4 && !NoGood2;z3++)
							    for (y3=0;y3<4 && !NoGood2;y3++)
									for (x3=0;x3<4 && !NoGood2;x3++) {
								    	if (cube2[x3][y3][z3]==' '){
											copy_cube(cube3,cube2);
											cube3[x3][y3][z3]=comp_symbol;
							   	 			score=score_cube(cube3);
											if (s2<score) {
										    	s2=score;
										    	if (s2>s1) NoGood2=TRUE;
											}
								    	}
									}
					   		if (s1>s2) {
					   		   	s1=s2;
					   		   	if (s1<s0) NoGood=TRUE;
							}
					    }
			}

			if (s0<s1) {
			    s0=s1;
			    bestmovex=x1;
			    bestmovey=y1;
			    bestmovez=z1;
			}
		    }
		}

	cube0[bestmovex][bestmovey][bestmovez]=comp_symbol;

	myMatrix.clear();
	state = 3;					// blinking last move of computer
	while (getKey() == 0) ;		// wait until player has pressed a button, then display regular cube
	state = 0;
}

int score_cube(char cube[4][4][4]) {

	int scores=0, x, y, z, tally_comp=0, tally_human=0;
	int comp[5]={0,0,0,0,0}, human[5]={0,0,0,0,0};
	char board[4][4];
	
	for (z=0;z<4;z++) {	/* boards in Z direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][y][z];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* boards in Y direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][z][y];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* boards in X direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[z][y][x];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* 3D diagonal 1 */
		tally_comp+=(cube[z][z][z]==comp_symbol);
		tally_human+=(cube[z][z][z]==human_symbol);
	}
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 2 */
		tally_comp+=(cube[3-z][z][z]==comp_symbol);
		tally_human+=(cube[3-z][z][z]==human_symbol);
	}
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 3 */
		tally_comp+=(cube[z][3-z][z]==comp_symbol);
		tally_human+=(cube[z][3-z][z]==human_symbol);
	}
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 4 */
		tally_comp+=(cube[z][z][3-z]==comp_symbol);
		tally_human+=(cube[z][z][3-z]==human_symbol);
	}	
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	scores+=comp[1]-3*human[1]+7*comp[2]-15*human[2]+31*comp[3]-63*human[3]+127*comp[4]-1000*human[4];
	return scores;

}

int score(char board[4][4]) {

	int x, y, tally_comp=0, tally_human=0, comp[5]={0,0,0,0,0}, human[5]={0,0,0,0,0};
	
	for (y=0;y<4;y++) {						/* Rows */
		for (x=0;x<4;x++) {
			tally_comp+=(board[x][y]==comp_symbol);
			tally_human+=(board[x][y]==human_symbol);
		}

		if (tally_comp>0 && tally_human>0) {
			tally_comp=0;
			tally_human=0;
		}
	
		comp[tally_comp]++;
		human[tally_human]++;
		
		tally_comp=0;
		tally_human=0;
	}

	for (x=0;x<4;x++) {						/* Columns */
		for (y=0;y<4;y++) {
			tally_comp+=(board[x][y]==comp_symbol);
			tally_human+=(board[x][y]==human_symbol);
		}

		if (tally_comp>0 && tally_human>0) {
			tally_comp=0;
			tally_human=0;
		}
	
		comp[tally_comp]++;
		human[tally_human]++;
		
		tally_comp=0;
		tally_human=0;
	}
	
	for (y=0;y<4;y++) {						/* Down diagonal */
		tally_comp+=(board[y][y]==comp_symbol);
		tally_human+=(board[y][y]==human_symbol);
	}
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}
	
	comp[tally_comp]++;
	human[tally_human]++;
	
	tally_comp=0;
	tally_human=0;
	
	for (y=0;y<4;y++) {						/* Up diagonal */
		tally_comp+=(board[3-y][y]==comp_symbol);
		tally_human+=(board[3-y][y]==human_symbol);
	}
	
	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}
	
	comp[tally_comp]++;
	human[tally_human]++;

	y=comp[1]-3*human[1]+7*comp[2]-15*human[2]+31*comp[3]-63*human[3]+127*comp[4]-1000*human[4];
	/* Needs to be the same evaluation function as in 'score_cube' function */
	return y;

}


void init_cube (void) {

	int x,y,z;
	
	for(z=0;z<4;z++)
		for(y=0;y<4;y++)
			for(x=0;x<4;x++) cube0[x][y][z]=' ';
}

void get_player_move(void) {

	int x,y,z;

	while (getKey() == 0) ;
	
	state = 1;
	state1x = 5;
	state1y = 5;
	state1z = 5;

	do {
		while (getKey() == 0) ;
		if (key < '5') 
			state1x = (key - '0') - 1;
	} while (key != '5' || state1x > 3 );
	x = state1x;

	do {
		while (getKey() == 0) ;
		if (key < '5') 
			state1y = (key - '0') - 1;
	} while (key != '5' || state1y > 3 );
	y = state1y;

	do {
		while (getKey() == 0) ;
		if (key < '5') 
			state1z = (key - '0') - 1;
	} while (key != '5' || state1z > 3 );
	z = state1z;

	if (cube0[x][y][z]!=' ') {			// Invalid move - redo entry
		get_player_move();
	}

	cube0[x][y][z]=human_symbol;
	state = 0;
}

void setup() {

	for (int row = 0; row < numRows; row++) {
		pinMode(rowPins[row], INPUT);
		digitalWrite(rowPins[row], HIGH);
	}
	for (int column = 0; column < numCols; column++) {
		pinMode(colPins[column], OUTPUT);
		digitalWrite(colPins[column], HIGH);
	}
}

void loop() {
	char done, Buf[12];
	int x,y,z;

	state = 1;	// Pre-game cube LED flashing
	done = ' ';

	myMatrix.clear();

	init_cube();
	MsTimer2::set(period, disp_LED_cube);
	MsTimer2::start();
	
	while (getKey() == 0) ;			// Press 1 to go first
	state = 0;		// Normal display of cube LED 
	if (key != '1') {
		human_symbol='O';
		comp_symbol='X';
		get_computer_move();
	}

	do {
		state = 0;
		get_player_move();
		done=check_cube(cube0);
		if (done != ' ') break;
		get_computer_move();
		done=check_cube(cube0);
	} while (done==' ');
	
	if (done==human_symbol) ;			// Player has WON! - how to communicate?
	else ;								// Compute has WON! - how to communicate?
	
}