#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <sstream>
#include <windows.h>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <cstdio>
#include <ctime>
#include <cmath>

using namespace std;

void cls( HANDLE hConsole ) {
   COORD coordScreen = { 0, 0 };    // home for the cursor 
   DWORD cCharsWritten;
   CONSOLE_SCREEN_BUFFER_INFO csbi; 
   DWORD dwConSize;
    // Get the number of character cells in the current buffer. 
   if( !GetConsoleScreenBufferInfo( hConsole, &csbi ))
      return;
   dwConSize = csbi.dwSize.X * csbi.dwSize.Y;
   // Fill the entire screen with blanks.
   if( !FillConsoleOutputCharacter( hConsole, (TCHAR) ' ',
      dwConSize, coordScreen, &cCharsWritten ))
      return;
   // Get the current text attribute.
   if( !GetConsoleScreenBufferInfo( hConsole, &csbi ))
      return;
   // Set the buffer's attributes accordingly.
   if( !FillConsoleOutputAttribute( hConsole, csbi.wAttributes,
      dwConSize, coordScreen, &cCharsWritten ))
      return;
   // Put the cursor at its home coordinates.
   SetConsoleCursorPosition( hConsole, coordScreen );
}
	/* Code for clearing console
    HANDLE hStdout;
    hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
    cls(hStdout); */
void coutcommand( HANDLE hConsole ) {
   COORD coordScreen = { 0, 23 };    // home for the cursor 
   SetConsoleCursorPosition( hConsole, coordScreen );
}

vector <string> taunts;
vector <string> tauntstrash;
vector <string> victories;
vector <string> victoriestrash;
vector <string> losses;
vector <string> lossestrash;

void initiatemsgs() {
	taunts.push_back("\nI'm gonna win! :P\n");
	taunts.push_back("\nHehehe...\n");
	taunts.push_back("\nLooks like you're done.\n");
	taunts.push_back("\nYou should probably forfeit now.\n");
	victories.push_back("\nI WIN!!\n");
	victories.push_back("\nVictory is mine!\n");
	victories.push_back("\nMaybe you should try a lower difficulty! XD\n");
	victories.push_back("\nIt appears I have won.\n");
	losses.push_back("\nYOU WIN!! :D\n");
	losses.push_back("\nAwww, I lost. :(\n");
	losses.push_back("\nNicely done. Good game.\n");
	losses.push_back("\nI want a rematch! >.<\n");
	tauntstrash.push_back("\nThanks for the free win.\n");
	tauntstrash.push_back("\nThat move was probably a mistake.\n");
	tauntstrash.push_back("\nYou should probably use your brain next time.\n");
	tauntstrash.push_back("\nLOL really?\n");
	victoriestrash.push_back("\nConfucius say: you suck at this game.\n");
	victoriestrash.push_back("\n...are you dumb or something?\n");
	victoriestrash.push_back("\nGo back to tic-tac-toe.\n");
	victoriestrash.push_back("\nSuck it noob.\n");
	lossestrash.push_back("\nI bet you cheated.\n");
	lossestrash.push_back("\nI was just going easy on you.\n");
	lossestrash.push_back("\nI gave you the win cause I felt bad for you.\n");
	lossestrash.push_back("\nI blame my crappy programmer.\n");
	
}

string taunt(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*taunts.size()));
	return taunts[select];
}
string victory(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*victories.size()));
	return victories[select];
}
string loss(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*losses.size()));
	return losses[select];
}
string taunttrash(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*tauntstrash.size()));
	return tauntstrash[select];
}
string victorytrash(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*victoriestrash.size()));
	return victoriestrash[select];
}
string losstrash(int diff) {
	time_t result = time(NULL);
	double whoa = sin(result);
	unsigned int select = floor(abs(whoa*lossestrash.size()));
	return lossestrash[select];
}

struct Triple;

struct Cell {
        int x;
        int y;
        int z;
        bool fill;
        int color;
        int shape;
        vector<Triple *> groups;

        Cell() {
        }
        Cell(int a, int b, int c) {
                x = a;
                y = b;
                z = c;
                fill = false;
                color = 0;
                shape = 0;
        }

        void place(int c, int s);

        void remove();

        void addGroup(Triple *k) {
                groups.push_back(k);
        }
        void display() {
                cout << "Cell (" << x << ", " << y << ", " << z << ")\n";
                if (fill) cout << "Occupied by (" << color << ", " << shape << ")\n";
                else cout << "Empty\n";
        }

        void showGroups();
		int emptygroups();
};

struct Triple {
        int id;
        Cell *a;
        Cell *b;
        Cell *c;

		/*	0 - Empty (0 cells filled)
			1 - Initialized (1 cell filled)
			2, danger = true - Danger (2 cells filled, group can be completed)
			2, danger = false - Dead (2 cells filled, group cannot win)
			3, danger = true - Completed (3 cells filled, win)
			3, danger = false - Dead (3 cells filled, group cannot win) */
        int status;
		/*	If initialized, refers to where the cell occupies. If in danger, refers to last open cell.
			a - 1, b - 2, c - 3 */
        int atkcell;
		// If group can be completed by color, refers to color required to complete
        int atkcolor;
		// If group can be completed by shape, refers to shape required to complete
        int atkshape;
		// If at least 2 cells are filled, and group can still be completed/has been completed
        bool danger;
		// Coordinates of winning move for a danger group
		int xwin, ywin, zwin;

        Triple() {
        }
        Triple(Cell *cell1, Cell *cell2, Cell *cell3, int num) {
                id = num;
                a = cell1;
                b = cell2;
                c = cell3;
                status = 0;
                atkcolor = 0;
                atkshape = 0;
				danger = false;
        }

        void fill(int x, int y, int z, int col, int sh) {
				xwin = 0;
				ywin = 0;
				zwin = 0;
                if (status == 0) {
                        status++;
                        if ((a->x == x) && (a->y == y) && (a->z == z)) atkcell = 1;
                        else if ((b->x == x) && (b->y == y) && (b->z == z)) atkcell = 2;
                        else if ((c->x == x) && (c->y == y) && (c->z == z)) atkcell = 3;
                        atkcolor = col;
                        atkshape = sh;
                }
                else if (status == 1) {
                        status++;
                        if ((col == atkcolor) || (sh == atkshape)) danger = true;
						if (col != atkcolor) atkcolor = 0;
						else atkcolor = col;
						if (sh != atkshape) atkshape = 0;
						else atkshape = sh;
						if (danger) {
							if (!a->fill) {
								atkcell = 1;
								xwin = a->x;
								ywin = a->y;
								zwin = a->z;
							}
							else if (!b->fill) {
								atkcell = 1;
								xwin = b->x;
								ywin = b->y;
								zwin = b->z;
							}
							else if (!c->fill) {
								atkcell = 1;
								xwin = c->x;
								ywin = c->y;
								zwin = c->z;
							}
						}
                }
				else if (status == 2) {
						status++;
						if (!danger || !(col == atkcolor || sh == atkshape)) {
							danger = false;
							atkcolor = 0;
							atkshape = 0;
						}
						atkcell = 0;
				}
        }

        void display() {
                cout << "Group " << id << ": (" << a->x << "," << a->y << "," << a->z << ") (" << b->x << "," << b->y << "," << b->z << ") (" << c->x << "," << c->y << "," << c->z << ") \n";
                cout << "Status: ";
                if (status == 0) cout << "empty\n";
                else if (status == 1) cout << "initialized, with attacking piece (" << atkcolor << ", " << atkshape << ")\n";
                else if (status >= 2 && !danger) cout << "dead\n";
                else if (status == 2 && danger) {
                        cout << "danger, with win on (";
						if (atkcolor == 0) cout << "-";
						else cout << atkcolor;
						cout << ", ";
						if (atkshape == 0) cout << "-";
						else cout << atkshape;
						cout << ")\n";
				}
				else if (status == 3 && danger) cout << "completed\n";
        }
		
        void checkStatus() {
                int filled = 0;
                int full[3] = { 0, 0, 0 };
                if (a->fill) {
					filled++;
					full[0]++;
				}
                if (b->fill) {
					filled++;
					full[1]++;
				}
                if (c->fill) {
					filled++;
					full[2]++;
				}

                if (filled == 0) {
                        atkcell = 0;
                        status = 0;
                        atkcolor = 0;
                        atkshape = 0;
                        danger = false;
                }
                else if (filled == 1) {
                        status = 1;
                        danger = false;
                        if (full[0] == 1) {
                                atkcell = 1;
                                atkcolor = a->color;
                                atkshape = a->shape;
                        }
                        else if (full[1] == 1) {
                                atkcell = 2;
                                atkcolor = b->color;
                                atkshape = b->shape;
                        }
                        else if (full[2] == 1) {
                                atkcell = 3;
                                atkcolor = c->color;
                                atkshape = c->shape;
                        }
                }
                else if (filled == 2) {
                        status = 2;
                        danger = false;
						if (full[0] == 0) atkcell = 1;
						else if (full[1] == 0) atkcell = 2;
						else if (full[2] == 0) atkcell = 3;
                        if (a->color == b->color) {
							atkcolor = a->color;
							danger = true;
						}
						else if (b->color == c->color) {
							atkcolor = b->color;
							danger = true;
						}
						else if (a->color == c->color) {
							atkcolor = a->color;
							danger = true;
						}
                        if (a->shape == b->shape) {
							atkshape = a->shape;
							danger = true;
						}
						else if (b->shape == c->shape) {
							atkshape = b->shape;
							danger = true;
						}
						else if (a->shape == c->shape) {
							atkshape = a->shape;
							danger = true;
						}
						if (!danger) {
							atkcell = 0;
							atkshape = 0;
							atkcolor = 0;
						}
                }
				else if (filled == 3) {
						status = 3;
						danger = false;
						atkcell = 0;
						if ((a->color == b->color) && (b->color == c->color)) {
							danger = true;
							atkcolor = a->color;
						}
						if ((a->shape == b->shape) && (b->shape == c->shape)) {
							danger = true;
							atkshape = a->shape;
						}
						atkcell = 0;
						if (!danger) {
							atkcolor = 0;
							atkshape = 0;
						}
				}
        }
};

void Cell::showGroups() {
        for (unsigned int k = 0; k<groups.size(); k++) groups[k]->display();
}
void Cell::place(int c, int s) {
        color = c;
        shape = s;
        fill = true;
        for (unsigned int k = 0; k<groups.size(); k++) groups[k]->fill(x, y, z, c, s);
}
void Cell::remove() {
        color = 0;
        shape = 0;
        fill = false;
        for (unsigned int k = 0; k<groups.size(); k++) groups[k]->checkStatus();
}
int Cell::emptygroups() {
	int count = 0;
	for (unsigned int k = 0; k<groups.size(); k++) {
		if (groups[k]->status == 0) count++;
	}
	return count;
}

struct Move {
	int x, y, z, c, s;
	double payout;
	Move() {
	}
	Move(int a, int b, int d, int e, int f) {
		x = a;
		y = b;
		z = d;
		c = e;
		s = f;
		payout = 0;
	}
	Move(int a, int b, int d, int e, int f, double pay) {
		x = a;
		y = b;
		z = d;
		c = e;
		s = f;
		payout = pay;
	}
	~Move() {
	}
};

string hex(int k) {
	switch (k) {
		case -1:
		return "-";
		case 0:
		return "0";
		case 1:
		return "1";
		case 2:
		return "2";
		case 3:
		return "3";
		case 4:
		return "4";
		case 5:
		return "5";
		case 6:
		return "6";
		case 7:
		return "7";
		case 8:
		return "8";
		case 9:
		return "9";
		case 10:
		return "A";
		case 11:
		return "B";
		case 12:
		return "C";
		case 13:
		return "D";
		case 100:
		return "W";
		default:
		return "0";
	}
}

struct Board {

        Cell* cell[3][3][3];
        Triple* group[49];
        int board[3][3][3][2];
        int piececount[4][4];
		int atkspace[3][3][3][2][3];
		HANDLE hStdout;		
		bool gameend;
		bool playerfirst;
		int difficulty;
		bool trashtalk;
		
		int next[5];
		ofstream savedata;
		ifstream preset;
		bool solution;
		
		vector<Move *> maxnode;
		vector<Move *> safe;
		vector<Move *> empty;

        Board() {
                for (int x = 0; x < 3; x++) {
                        for (int y = 0; y < 3; y++) {
                                for (int z = 0; z < 3; z++) cell[x][y][z] = new Cell(x, y, z);
                        }
                }
				hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
				playerfirst = true;
				difficulty = 5;
				trashtalk = false;
				memset( piececount, 0, sizeof( piececount ));
                int count = 0;
                for (int x = 0; x < 3; x++) {
                        group[count] = new Triple(cell[x][0][0], cell[x][1][1], cell[x][2][2], count);
                        count++;
                        group[count] = new Triple(cell[0][x][0], cell[1][x][1], cell[2][x][2], count);
                        count++;
                        group[count] = new Triple(cell[0][0][x], cell[1][1][x], cell[2][2][x], count);
                        count++;
                        group[count] = new Triple(cell[x][0][2], cell[x][1][1], cell[x][2][0], count);
                        count++;
                        group[count] = new Triple(cell[0][x][2], cell[1][x][1], cell[2][x][0], count);
                        count++;
                        group[count] = new Triple(cell[0][2][x], cell[1][1][x], cell[2][0][x], count);
                        count++;
                        for (int y = 0; y < 3; y++) {
                                group[count] = new Triple(cell[x][y][0], cell[x][y][1], cell[x][y][2], count);
                                count++;
                                group[count] = new Triple(cell[x][0][y], cell[x][1][y], cell[x][2][y], count);
                                count++;
                                group[count] = new Triple(cell[0][x][y], cell[1][x][y], cell[2][x][y], count);
                                count++;
                        }
                }
                group[count] = new Triple(cell[0][0][0], cell[1][1][1], cell[2][2][2], count);
                count++;
                group[count] = new Triple(cell[0][0][2], cell[1][1][1], cell[2][2][0], count);
                count++;
                group[count] = new Triple(cell[0][2][0], cell[1][1][1], cell[2][0][2], count);
                count++;
                group[count] = new Triple(cell[0][2][2], cell[1][1][1], cell[2][0][0], count);
                for (int k = 0; k < 49; k++) {
                        group[k]->a->addGroup(group[k]);
                        group[k]->b->addGroup(group[k]);
                        group[k]->c->addGroup(group[k]);
                }
        }

		void togglefirst() {
			if (playerfirst) playerfirst = false;
			else playerfirst = true;
		}
		void trashtoggle() {
			if (trashtalk) trashtalk = false;
			else trashtalk = true;
		}
		void diffchange(int diff) {
			difficulty = diff;
		}
		void load() {
			reset();
			ifstream preset("board.txt");
			string line;
			
			for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
					if ( getline (preset,line) );
					if (atoi(line.substr(1,1).c_str()) != 0) move(0,y,z,atoi(line.substr(1,1).c_str()),atoi(line.substr(2,1).c_str()));
					if (atoi(line.substr(4,1).c_str()) != 0) move(1,y,z,atoi(line.substr(4,1).c_str()),atoi(line.substr(5,1).c_str()));
					if (atoi(line.substr(7,1).c_str()) != 0) move(2,y,z,atoi(line.substr(7,1).c_str()),atoi(line.substr(8,1).c_str()));
				}
				if (getline(preset,line));
			}
			if (getline(preset,line)) difficulty = atoi(line.c_str());
			preset.close();
		}
		void save() {
			savedata.open ("board.txt");
            for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
						for (int x = 0; x < 3; x++) savedata << "\t" << cell[x][y][z]->color << cell[x][y][z]->shape;
						savedata << "\n";
				}
				if (z != 2) savedata << "\n";
			}
			savedata << difficulty;
			savedata.close();
		}

		bool fullcheck() {
			for (int a = 1; a <= 3; a++) {
				for (int b = 1; b <= 3; b++) {
					if (piececount[a][b] != 3) {
						return false;
						break;
					}
				}
			}
			return true;
		}
		bool emptycheck() {
			for (int a = 1; a <= 3; a++) {
				for (int b = 1; b <= 3; b++) {
					if (piececount[a][b] != 0) {
						return false;
						break;
					}
				}
			}
			return true;
		}
		
        void move(int x, int y, int z, int a, int b) {
			if (!cell[x][y][z]->fill) {
                cell[x][y][z]->place(a, b);
                piececount[a][b]++;
			}
        }
        void remove(int x, int y, int z) {
				piececount[cell[x][y][z]->color][cell[x][y][z]->shape]--;
                cell[x][y][z]->remove();
        }

		void display() {
				cls(hStdout);
				cout << "Board:\t\t\t\tPiececount:\n\n";
                for (int z = 0; z < 3; z++) {
						for (int y = 0; y < 3; y++) {
                                for (int x = 0; x < 3; x++) cout << "\t" << cell[x][y][z]->color << cell[x][y][z]->shape;
								cout << "\t\t" << z+1 << y+1 << ": " << piececount[z+1][y+1] << "\n";
                        }
						if (z != 2) cout << "\n";
                }
				cout << "\nType \"quit\" to leave game.\n";
		}
		void reset() {
                for (int x = 0; x < 3; x++) {
                        for (int y = 0; y < 3; y++) {
                                for (int z = 0; z < 3; z++) {
									if (cell[x][y][z]->fill) remove(x, y, z);
								}
                        }
                }
		}
		void countpiece() {
                for (int c = 1; c <= 3; c++) {
                        for (int s = 1; s <= 3; s++) piececount[c][s] = 0;
                }			
                for (int x = 0; x < 3; x++) {
                        for (int y = 0; y < 3; y++) {
                                for (int z = 0; z < 3; z++) {
                                        if ((cell[x][y][z]->color != 0) && (cell[x][y][z]->shape != 0)) {
                                                piececount[cell[x][y][z]->color][cell[x][y][z]->shape]++;
                                        }
                                }
                        }
                }			
		}
		void checkallgroups() {
			for (int k=0; k < 49; k++) {
				group[k]->checkStatus();
			}
		}
		int win() {
			int wincount = 0;
			for (int k = 0; k < 49; k++) {
				if (group[k]->status == 3 && group[k]->danger) wincount++;
			}
			return wincount;
		}

		void play() {
			if (!playerfirst && emptycheck() ) randomfirstmove();
			gameend = false;
			string system;
			system = "Type cell coordinate as a 3-digit number, each digit from 0-2.\n";
			do {
				string input;
				cls(hStdout);
				display();
				cout << system;
				coutcommand(hStdout);
				cout << "Command: ";
				cin >> input;
				bool valid = true;
				int x,y,z,c,s;
				// If input is "quit" leave game
				if (input == "quit") {
					save();
					break;
				}
				// Check if input string is a valid move and convert to integer
				if (input.size() != 3) valid = false;
				else {
					if (input.substr(0,1) != "0" && input.substr(0,1) != "1" && input.substr(0,1) != "2") valid = false;
					else if (input.substr(1,1) != "0" && input.substr(1,1) != "1" && input.substr(1,1) != "2") valid = false;
					else if (input.substr(2,1) != "0" && input.substr(2,1) != "1" && input.substr(2,1) != "2") valid = false;
					else {
						int celli;
						celli = atoi(input.c_str());
						x = (celli-celli%100)/100;
						y = (celli-x*100-celli%10)/10;
						z = celli-x*100-y*10;
					}
				}
				
				// If input is invalid
				if ( !valid ) system = "Type cell coordinate as a 3-digit number, each digit from 0-2.\nNot a valid coordinate.\n";
				else if ( valid && cell[x][y][z]->fill) {
					valid = false;
					system = "Type cell coordinate as a 3-digit number, each digit from 0-2.\nCell already filled.\n";
				}
				// If input is correct make move
				else {
					system = "Type piece as a 2-digit number, each digit from 1-3.\n";
					cls(hStdout);
					display();
					cout << system;
					coutcommand(hStdout);
					cout << "Command: ";
					cin >> input;
					if (input == "quit") {
						save();
						break;
					}
					// Check if input is valid piece and convert to integer
					if (input.size() != 2) valid = false;
					else {
						if (input.substr(0,1) != "1" && input.substr(0,1) != "2" && input.substr(0,1) != "3") valid = false;
						else if (input.substr(1,1) != "1" && input.substr(1,1) != "2" && input.substr(1,1) != "3") valid = false;
						else {
							int piece;
							piece = atoi(input.c_str());
							c = (piece-piece%10)/10;
							s = piece-c*10;
						}
					}
					if ( !valid ) system = "Type cell coordinate as a 3-digit number, each digit from 0-2.\nNot a valid piece.\n";
					else if (valid && piececount[c][s] >= 3) {
						valid = false;
						system = "Type cell coordinate as a 3-digit number, each digit from 0-2.\nPiece limit reached.\n";
					}
					else {
						move(x,y,z,c,s);
						if (win() >= 1) {
							if (trashtalk) system = loss(difficulty);
							else system = losstrash(difficulty);
							gameend = true;
						}
						else if (fullcheck()) {
							system = "\nDraw. Nobody wins.\n";
							gameend = true;
						}
						// If game hasn't ended yet, computer's turn
						if (!gameend) {
							stringstream ss;
							string s = ss.str();
							string temp1;
							cout << "Thinking...";
							clock_t start;
							double duration;
							start = std::clock();
							
							getnextmove();
							move(next[0],next[1],next[2],next[3],next[4]);
							
							duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
							
							ss << "I took " << duration << " seconds to think.\n";
							ss << "I placed " << next[3] << next[4] << " at (" << next[0] << ", " << next[1] << ", " << next[2] << ").\n";
							temp1 = ss.str();
														
							// Check for win condition or full board
							if (win() >= 1 ) {
								if (trashtalk) system = "\n" + temp1 + victorytrash(difficulty);
								else system = "\n" + temp1 + victory(difficulty);
								gameend = true;
							}
							else if (fullcheck()) {
								system = "\n" + temp1 + "\nDraw. Nobody wins.\n";
								gameend = true;
							}
							// If game hasn't ended and computer is going to win, gloat
							if (!gameend) {
								system = "Type piece as a 2-digit number, each digit from 1-3.\n" + temp1;
								if (maxnode.size() > 0) {
									if (trashtalk) system = system + taunttrash(difficulty);
									else system = system + taunt(difficulty);
								}
							}
						}
					}
				}
			} while (!gameend);
			cls(hStdout);
			display();
			cout << system;
			coutcommand(hStdout);
		}
		
		void randomfirstmove() {
			time_t result = time(NULL);
			unsigned int x,y,z,c,s;
			double whoa = sin(result);
			x = floor(abs(whoa*3));
			whoa = sin(13109*whoa);
			y = floor(abs(whoa*3));
			whoa = sin(2042*whoa);
			z = floor(abs(whoa*3));
			whoa = sin(8992*whoa);
			c = floor(abs(whoa*3))+1;
			whoa = sin(11099*whoa);
			s = floor(abs(whoa*3))+1;
			move(x,y,z,c,s);
		}
		
		// solver functions
		
		// Immediate one move win search
		void findwin() {
			int gid = 0;
			solution = false;
			// for each group...
			for (gid = 0; gid < 49; gid++) {
				// check if group is one move from winning
				if (group[gid]->status == 2 && group[gid]->danger) {
					// check if there exists a piece that can be played
					for (int cs = 1; cs <= 3; cs++) {
						if ((group[gid]->atkcolor != 0 && piececount[group[gid]->atkcolor][cs] != 3) || (group[gid]->atkshape != 0 && piececount[cs][group[gid]->atkshape] != 3)) {
							if (group[gid]->atkcolor != 0) {
								next[3] = group[gid]->atkcolor;
								next[4] = cs;
							}
							else {
								next[3] = cs;
								next[4] = group[gid]->atkshape;
							}
							solution = true;
						}
					}
					if (solution) break;
				}
			}
			// if there exists a piece that can win, find the piece
			if (solution) {
				next[0] = group[gid]->xwin;
				next[1] = group[gid]->ywin;
				next[2] = group[gid]->zwin;
			}
		}
		/* Alternate algorithm to find winning move using the attack space
		void findwin() {
			resetatkspace();
			findatkspace();
			int x, y, z, t, n;
			bool winexists = false;
			for (x = 0; x < 3; x++) {
				for (y = 0; y < 3; y++) {
					for (z = 0; z < 3; z++) {
						for (t = 0; t < 2; t++) {
							for (n = 0; n < 3; n++) {
								if (atkspace[x][y][z][t][n] == 100) {
									winexists = true;
									break;
								}
							}
						}
					}
				}
			}
			// Insert checking piececount for valid move
			
		} */
		
		void resetatkspace() {
			memset( atkspace, 0, sizeof( atkspace ));
		}
		void findatkspace() {
			resetatkspace();
			for (int x = 0; x < 3; x++) {
				for (int y = 0; y < 3; y++) {
					for (int z = 0; z < 3; z++) {
						for (unsigned int k = 0; k < cell[x][y][z]->groups.size(); k++) {
							if (cell[x][y][z]->groups[k]->status == 1) {
								atkspace[x][y][z][0][cell[x][y][z]->groups[k]->atkcolor-1]++;
								atkspace[x][y][z][1][cell[x][y][z]->groups[k]->atkshape-1]++;
							}
						}
					}
				}
			}
			for (unsigned int k = 0; k < 49; k++) {
				if (group[k]->status == 2 && group[k]->danger) {
					if (group[k]->atkcolor != 0) {
						atkspace[group[k]->xwin][group[k]->ywin][group[k]->zwin][0][group[k]->atkcolor-1] = 100;
					}
					if (group[k]->atkshape != 0) {
						atkspace[group[k]->xwin][group[k]->ywin][group[k]->zwin][1][group[k]->atkshape-1] = 100;
					}
				}
			}
			for (int a = 1; a <= 3; a++) {
				bool allgone = true;
				for (int b = 1; b <= 3; b++) {
					if (piececount[a][b] != 3) {
						allgone = false;
						break;
					}
				}
				if (allgone) {
					for (int x = 0; x < 3; x++) {
						for (int y = 0; y < 3; y++) {
							for (int z = 0; z < 3; z++) {
								atkspace[x][y][z][0][a-1] = -1;
							}
						}
					}
				}
				allgone = true;
				for (int b = 1; b <= 3; b++) {
					if (piececount[b][a] != 3) {
						allgone = false;
						break;
					}
				}
				if (allgone) {
					for (int x = 0; x < 3; x++) {
						for (int y = 0; y < 3; y++) {
							for (int z = 0; z < 3; z++) {
								atkspace[x][y][z][1][a-1] = -1;
							}
						}
					}
				}
			}
		}
		int atkspaceopening() {
			findatkspace();
			int count = 0;
			for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
					for (int x = 0; x < 3; x++) {
						if (!cell[x][y][z]->fill) {
							for (int c = 0; c < 3; c++) {
								if (atkspace[x][y][z][0][c] == 0) {
									for (int s = 0; s < 3; s++) {
										if (atkspace[x][y][z][1][s] == 0) {
											count++;
										}
									}
								}
							}
						}
					}
				}
			}
			return count;
		}

		// Recursive version of atkspaceopening method
		int atkspacesolve(int maxdepth, int depth, double payout) {
			findatkspace();
			int node = 0;
			double payouttotal = 0;
			int nodecount = 0;
			bool open = false;
			bool allforced = true;
			if ( fullcheck() ) {
				this->solution = false;
				return 0;
			}
			for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
					for (int x = 0; x < 3; x++) {
						if (!cell[x][y][z]->fill) {
							for (int c = 0; c < 3; c++) {
								if (atkspace[x][y][z][0][c] == 0) {
									for (int s = 0; s < 3; s++) {
										if (atkspace[x][y][z][1][s] == 0) {
											if (piececount[c+1][s+1] < 3) {
												open = true;
												if (depth >= maxdepth) {
													this->solution = false;
													payout = 1;
													return 0;
												}
												nodecount++;
												move(x,y,z,c+1,s+1);
												
												node = atkspacesolve(maxdepth, depth+1, payout);
												if (node == 0) payouttotal = payouttotal + payout;
												else if (node == 1) payouttotal = payouttotal + payout*20;
												if (depth == 2 && piececount[c+1][s+1] != 3) {
													if (node == 1) maxnode.push_back(new Move(x,y,z,c+1,s+1));
													else if (node == 0) safe.push_back(new Move(x,y,z,c+1,s+1,payout));
													else if (node == -1) empty.push_back(new Move(x,y,z,c+1,s+1,payout));
												}
												
												// print results
												/* int maxdisplaydepth = 9;
												if (depth <= maxdisplaydepth) {
													if (depth > 2) {
														for (int k = 2; k < depth; k++) {
															results << "\t";
															// cout << "\t";
														}
													}
													if (node == 1) {
														results << "Max-node: (";
														// cout << "Max-node: (";
													}
													else if (node == -1) {
														results << "Min-node: (";
														// cout << "Min-node: (";
													}
													else {
														results << "Dead-node: (";
														// cout << "Dead-node: (";
													}
													results << x << ", " << y << ", " << z << ") [" << c+1 << ", " << s+1 << "]";
													// cout << x << ", " << y << ", " << z << ") [" << c+1 << ", " << s+1 << "]";
													if (node == 1 && this->solution) {
														results << " found solution";
														// cout << " found solution";
													}
													else if (node == -1 && !this->solution) {
														results << " no solution";
														// cout << " no solution";
													}
													if (depth == maxdisplaydepth && maxdepth > maxdisplaydepth) {
														results << " depth=" << maxdisplaydepth;
														// cout << " depth=" << maxdisplaydepth;
													}
													results << "\n";
													// cout << "\n";
												}

												*/
												
												remove(x,y,z);
												findatkspace();
												if (!this->solution) allforced = false;
												if (this->solution && node == 1) {
													payout = payouttotal/nodecount;
													return -1;
												}
												else if (!this->solution && node == -1) {
													payout = payouttotal/nodecount;
													return 0;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
			if ((node == -1 && allforced) || !open) {
				this->solution = true;
				return 1;
			}
			this->solution = false;
			payout = 1;
			return 0;
		}
		void findsolution(int maxdepth) {			
			this->solution = false;
			if ( atkspacesolve(maxdepth, 2, 0) );
		}
		
		void clearmoves() {
			for (unsigned int k = 0; k < empty.size(); k++) {
				delete empty[k];
			}
			for (unsigned int k = 0; k < safe.size(); k++) {
				delete safe[k];
			}
			for (unsigned int k = 0; k < maxnode.size(); k++) {
				delete maxnode[k];
			}
			empty.clear();
			safe.clear();
			maxnode.clear();
		}
		void findemptymoves() {
			for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
					for (int x = 0; x < 3; x++) {
						if (!cell[x][y][z]->fill) {
							for (int c = 1; c <= 3; c++) {
								for (int s = 1; s <= 3; s++) {
									if (piececount[c][s] != 3) {
										double threats = 0;
										for (unsigned int k = 0; k < cell[x][y][z]->groups.size(); k++) {
											if (cell[x][y][z]->groups[k]->atkcolor == c || cell[x][y][z]->groups[k]->atkshape == s) threats = threats+1;
										}
										empty.push_back(new Move(x,y,z,c,s,20-threats));
									}
								}
							}
						}
					}
				}
			}
		}
		void findsafemoves() {
			findatkspace();
			for (int z = 0; z < 3; z++) {
				for (int y = 0; y < 3; y++) {
					for (int x = 0; x < 3; x++) {
						if (!cell[x][y][z]->fill) {
							for (int c = 0; c < 3; c++) {
								if (atkspace[x][y][z][0][c] == 0) {
									for (int s = 0; s < 3; s++) {
										if (atkspace[x][y][z][1][s] == 0) {
											if (piececount[c+1][s+1] != 3) safe.push_back(new Move(x,y,z,c+1,s+1));
										}
									}
								}
							}
						}
					}
				}
			}
		}
		void selectmove() {
			int payout = 0;
			vector<int> indices;
			if (maxnode.size() != 0) {
				next[0] = maxnode[0]->x;
				next[1] = maxnode[0]->y;
				next[2] = maxnode[0]->z;
				next[3] = maxnode[0]->c;
				next[4] = maxnode[0]->s;
			}
			else if (safe.size() != 0) {
				for (unsigned int k = 0; k < safe.size(); k++) {
					if (safe[k]->payout >= payout) payout = safe[k]->payout;
				}
				for (unsigned int k = 0; k < safe.size(); k++) {
					if (safe[k]->payout == payout) indices.push_back(k);
				}
				time_t result = time(NULL);
				double whoa = sin(result);
				unsigned int select = floor(abs(whoa*indices.size()));
				
				if (select == indices.size()) select--;
				next[0] = safe[select]->x;
				next[1] = safe[select]->y;
				next[2] = safe[select]->z;
				next[3] = safe[select]->c;
				next[4] = safe[select]->s;
			}
			else {
				for (unsigned int k = 0; k < empty.size(); k++) {
					if (empty[k]->payout >= payout) payout = empty[k]->payout;
				}
				for (unsigned int k = 0; k < empty.size(); k++) {
					if (empty[k]->payout == payout) indices.push_back(k);
				}
				time_t result = time(NULL);
				double whoa = sin(result);
				unsigned int select = floor(abs(whoa*indices.size()));
	
				if (select == indices.size()) select--;
				next[0] = empty[select]->x;
				next[1] = empty[select]->y;
				next[2] = empty[select]->z;
				next[3] = empty[select]->c;
				next[4] = empty[select]->s;
			}
		}
		// Full AI algorithm to finding next move
		void getnextmove() {
			// Reset all variables
			solution = false;
			for (int k = 0; k < 5; k++) next[k] = 0;
			clearmoves();
			// Check for immediate win
			findwin();
			// If win does not exist
			if (!solution) {
				// Count attack space openings
				// If openings do not exist
				if ( !atkspaceopening() || difficulty == 0 ) {
					// Find empty moves
					findemptymoves();
					// Make a random move, preferably putting the least number of groups in danger
					selectmove();
				}
				// If openings exist
				else {
					findemptymoves();
					// Find number of safe moves
					findsafemoves();
					// Early game - too many possible moves to depth search, random safe move is picked
					if (difficulty == 1 || safe.size() > 32) {
						selectmove();
					}
					// Mid game - shallow depth search to avoid early min-nodes
					else if (difficulty == 2 || difficulty == 3) {
						findsolution(3);
						if (difficulty == 2) {
							for (unsigned int k = 1; k <= maxnode.size(); k++) {
								delete maxnode[k];
							}
							maxnode.clear();
						}
					}
					else if (safe.size() > 15) {
						if (difficulty == 4) findsolution(4);
						else if (difficulty == 5) findsolution(6);
						selectmove();
					}
					// Late game - deep search to look for solved configurations
					else {
						// Call recursive solve for k moves, k depending on difficulty
						// Recursive solve should list out all maxnode, safe, and empty moves, as well as their payoffs
						if (difficulty == 4) findsolution(6);
						else if (difficulty == 5) findsolution(11);
						// Select best move
						selectmove();
					}
				}
			}
		}

};

void intro() {
	cout << "--------------------------------------------------------------------------------";
	cout << "|                                    Sanga                                     |";
	cout << "--------------------------------------------------------------------------------\n";
	cout << "\tSelect:\n\n";
	cout << "\t\thelp - How to Play\n";
	cout << "\t\tnew - New game\n";
	cout << "\t\tload - Continue\n";
	cout << "\t\toptions - Options\n";
	cout << "\t\tquit - Quit\n";
	cout << "\n\n\nCoded by CosmoVibe v1.0";
}

void helpmenu() {
	cout << "What is Sanga?\n\n";
	cout << "Sanga is loosely translated to \"three\" in Chinese. It is a version of 3D\n";
	cout << "tic-tac-toe designed by Chi Ni. Attempts to raise money to make the game failed,";
	cout << "but this program implements the basic game in the console with a decently\n";
	cout << "strong AI. Good luck!\n\n";
	cout << "How to Play Sanga\n\n";
	cout << "The player that connects 3 pieces in any straight line of the same color OR\n";
	cout << "shape. Each piece has 1 of 3 colors, and 1 of 3 shapes. This game, being played\n";
	cout << "on the console, colors and shapes are labeled from 1 to 3.\n\n";
	cout << "The board is displayed during the game, showing each cell of the cube.\n";
	cout << "Empty cells will be displayed as \"00\".\n\n";
	cout << "Coordinates are as follows: For each 3x3 block, x is 0 to 2 from left to right,\n";
	cout << "y is 0 to 2 from top to bottom, and z refers to the 3x3 block from top to\n";
	cout << "bottom.\n\n";
	cout << "The piececount is also displayed. A piece of a particular color and shape can\n";
	cout << "only be played a maximum of 3 times.\n";
	
}

void optionsmenu(bool playerfirst, int difficulty, bool trashtalk) {
	cout << "\nOptions Menu:\n\n";
	cout << "\tdiff - Current difficulty: " << difficulty << "\n";
	cout << "\tfirst - (Toggle) ";
	if (playerfirst) cout << "Player";
	else cout << "Computer";
	cout << " goes first\n";
	cout << "\ttrash - (Toggle) Trashtalking: ";
	if (trashtalk) cout << "ON\n";
	else cout << "OFF\n";
	cout << "\tback - Go back to main menu.\n";
}

void difficultymenu(int difficulty) {
	cout << "\nSelect Difficulty:\n\n";
	cout << "Current difficulty: " << difficulty << "\n\n";
	cout << "Difficulty descriptions:\n";
	cout << "0 - Computer only takes immediate wins.\n";
	cout << "1 - Computer avoids giving and takes immediate wins.\n";
	cout << "2 - Computer avoids being trapped and takes immediate wins.\n";
	cout << "3 - Computer avoids being trapped and tries to trap the player.\n";
	cout << "4 - Computer searches deeper once much of the board has been filled.\n";
	cout << "5 - Computer attempts deep search within reasonable computation times.\n";
	cout << "\nType \"back\" to cancel.\n";
}

int main() {
		initiatemsgs();
        Board* sanga = new Board();
		HANDLE hStdout;
		hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
		string input;
		string system = "";

		// Main menu
		do {
			cls(hStdout);
			intro();
			cout << system;
			coutcommand(hStdout);
			system = "";
			cout << "Command: ";
			cin >> input;
			if (input == "quit" || input == "q") break;
			
			// New game
			else if (input == "new") {
				sanga->reset();
				sanga->play();
				if (sanga->gameend) {
					cout << "Input any command to continue...";
					cin >> input;
				}
			}

			// Load game
			else if (input == "load") {
				sanga->load();
				sanga->play();
				if (sanga->gameend) {
					cout << "Input any command to continue...";
					cin >> input;
				}
			}

			// Help Menu
			else if (input == "help") {
				cls(hStdout);
				helpmenu();
				coutcommand(hStdout);
				cout << "Input any command to continue...";
				cin >> input;
			}
			
			// Options Menu
			else if (input == "options") {
				do {
					string input2;
					cls(hStdout);
					optionsmenu(sanga->playerfirst, sanga->difficulty, sanga->trashtalk);
					cout << system;
					coutcommand(hStdout);
					cout << "Command: ";
					system = "";
					cin >> input2;
					if (input2 == "back") break;
					else if (input2 == "first") sanga->togglefirst();
					else if (input2 == "diff") {
						do {
							string input3;
							cls(hStdout);
							difficultymenu(sanga->difficulty);
							cout << system;
							coutcommand(hStdout);
							cout << "Command: ";
							system = "";
							cin >> input3;
							if (input3 == "0" || input3 == "1" || input3 == "2" || input3 == "3" || input3 == "4" || input3 == "5") {
								int diff = atoi(input3.c_str());
								sanga->diffchange(diff);
								break;
							}
							else if (input3 == "back") break;
							else system = "\nCommand not recognized.";
						} while (true);
					}
					else if (input2 == "trash") sanga->trashtoggle();
					else if (input2 == "back") break;
					else {
						system = "\nCommand not recognized.";
					}
				} while (true);
			}
			

			// Invalid syntax
			else {
				system = "\nCommand not recognized.";
			}
			
		} while (true);
        return 0;
}