#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

struct gomoku {
	char board[19][19];
	char player1;
	char cpu;
};


char check_win(char board[19][19]) {
	char lop;
	for (int r = 0; r < 14; r++) {
		for (int c = 0; c < 14; c++) {
			if (board[r][c] != '.'  ) {
				lop = board[r][c];

				if (board[r+1][c] == lop){
					if (board[r+2][c] == lop){
						if (board[r+3][c] == lop){
							if (board[r+4][c] == lop){
								if (board[r+5][c] == lop){
									return board[r][c];
								}
							}
						}
					}
				}

				if (board[r][c+1] == lop){
					if (board[r][c+1] == lop){
						if (board[r][c+1] == lop){
							if (board[r][c+1] == lop){
								if (board[r][c+1] == lop){
									return board[r][c];
								}
							}
						}
					}
				}

				if (board[r+1][c+1] == lop){
					if (board[r+1][c+1] == lop){
						if (board[r+1][c+1] == lop){
							if (board[r+1][c+1] == lop){
								if (board[r+1][c+1] == lop){
									return board[r][c];
								}
							}
						}
					}
				}

			}
		}
	}

	return 0;
}


int negamax(char board[19][19], char player1, char player2,int negamaxno) {

	int best_move_score = -9999;
	int score_for_this_move = 0;
	if (negamaxno>100){
		return 0;
	}
	//If player 1 wins, then the score is high (good for player1)
	if (check_win(board) == player1)
		return 1000;

	//If player 2 loses, then the score is low (bad for player1)
	else if (check_win(board) == player2)
		return -1000;

	for (int r = 0; r < 19; r++) {
		for (int c = 0; c < 19; c++) {
			if (board[r][c] == '.') {
				board[r][c] = player1; //Try test move.
				score_for_this_move = -(negamax(board, player2, player1,negamaxno+1));
				board[r][c] = '.'; //Put back test move.
				if (score_for_this_move >= best_move_score) {
					best_move_score = score_for_this_move;
				}
			}
		}
	}

	if (best_move_score == -9999 || best_move_score == 0)
		return 0;

	else if (best_move_score < 0)
		return best_move_score + 1;

	else if (best_move_score > 0)
		return best_move_score - 1; //As the game goes longer, and the recursion goes deeper, the moves near the end are less favorable than in the beginning.

}


int main() {
	gomoku game;
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < 19; j++) {
			game.board[i][j] = '.';
		}
	}
	cout << "Hello, I am the computer you will be playing." << endl;
	cout << "If you chose x's, I will be o's. If you chose o's, I will be x's." << endl;
	cout << "If you chose neither x or o, I will default to x." << endl << endl;
	while (1) {
		string choice;
		cout << "Player 1" << ": What would you like your character to be? ";
		cin >> choice;
		if (choice.size() > 1) {
			cout << "You inputted more than one character. Please try again." << endl;
			continue;
		}
		cout << endl;
		game.player1 = choice[0];
		break;
	}

	if (game.player1 == 'x' || game.player1 == 'X')
		game.cpu = 'o';

	else
		game.cpu = 'x';


	for (int i = 0; i < 19; i++) {
		cout << endl;
		for (int j = 0; j < 19; j++) {
		cout << "  ";
		cout << game.board[i][j];
		}
	}
	cout << endl;

	int moves = 0;


	while (moves < 361) {

		while (1) {
			string string_row, string_col;
			int row = 0, col = 0;
			while (1) {
				cout << "Where would you like to play? " << endl << "Enter the row: ";
				cin >> string_row;
				row = atoi(string_row.c_str());

				if (row >= 1 && row <= 19)
					break;
					cout << "You need to enter a row on the board (between 1 and 19, inclusive)." << endl;
			}

			while (1) {
				cout << "Enter the column: ";
				cin >> string_col;
				col = atoi(string_col.c_str());

				if (col >= 1 && col <= 19)
					break;
					cout << "You need to enter a column on the board (between 1 and 19, inclusive)." << endl;
			}
			if (game.board[row-1][col-1] == '.') {
				game.board[row-1][col-1] = game.player1;
				break;
			}
			else
				cout << "Someone already played there." << endl << endl;
		}

		moves++;
		for (int i = 0; i < 19; i++) {
			cout << endl;
			for (int j = 0; j < 19; j++) {
				cout << "  ";
				cout << game.board[i][j];
			}
		}
		cout << endl << endl;
		if (moves == 361)
			break;
		int best_move_score = -9999;
		int best_move_row = -9999;
		int best_move_col = -9999;
		int score_for_this_move = 0;
			for (int r = 0; r < 361; r++) {
				for (int c = 0; c < 361; c++) {
					if (game.board[r][c] == '.') {
						game.board[r][c] = game.player1; //Try test move.
						int negamaxno=0;
						score_for_this_move = -(negamax(game.board, game.cpu, game.player1,negamaxno));
						game.board[r][c] = '.'; //Put back test move.
						if (score_for_this_move >= best_move_score) {
							best_move_score = score_for_this_move;
							best_move_row = r;
							best_move_col = c;
						}
					}
				}
			}
		game.board[best_move_row][best_move_col] = game.cpu;
		if (check_win(game.board)) {
			cout << game.cpu << " won!" <<endl;
			exit(1);
		}
		moves++;
		for (int i = 0; i < 361; i++) {
			cout << endl;
			for (int j = 0; j < 361; j++) {
				cout << "  ";
				cout << game.board[i][j];
			}
		}
		cout << endl;
	}
	cout << "Cat's game!" << endl;

	return 0;
}