TicTacToe-minimax_alpha_beta.cpp

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <limits>

class Game
{
	enum class Player
	{
		none = '-',
		human = 'X',
		computer = 'O'
	};

	struct Move
	{
		unsigned x = 0;
		unsigned y = 0;
	};

	static const unsigned DIM = 4;

	Player board[DIM][DIM];
	unsigned remained;

public:
	Game() : remained(DIM * DIM)
	{
		for (unsigned i = 0; i < DIM; i++)
		{
			for (unsigned j = 0; j < DIM; j++)
			{
				board[i][j] = Player::none;
			}
		}
	}

	void play()
	{
		unsigned turn = 0;
		bool exit = false;

		printBoard();
		std::cout << "Enter your move in coordinate form[row, col]. ex: 02\n";

		do
		{
			// human move
			if (turn == 0)
			{
				getHumanMove();

				if (checkWin(Player::human))
				{
					std::cout << "Human Wins\n";
					exit = true;
				}
			}
			else
			{
				std::cout << "\nComputer Move: ";

				Move aimove = minimax();

				std::cout << aimove.x << aimove.y << "\n";

				board[aimove.x][aimove.y] = Player::computer;
				remained--;

				if (checkWin(Player::computer))
				{
					std::cout << "Computer Wins\n";
					exit = true;
				}
			}

			if (isTie())
			{
				std::cout << "\n*** Tie ***\n";
				exit = true;
			}

			turn ^= 1;
			printBoard();

		} while (!exit);
	}

private:
	void printBoard()
	{
		for (unsigned i = 0; i < DIM; i++)
		{
			std::cout << "\n|";
			for (unsigned j = 0; j < DIM; j++)
			{
				std::cout << std::setw(3) << static_cast<char>(board[i][j]) << std::setw(3) << " |";
			}
		}
		std::cout << "\n\n";
	}

	bool isTie()
	{
		return remained == 0;
	}

	bool checkWin(Player player)
	{
		// check for row or column wins
		for (unsigned i = 0; i < DIM; ++i)
		{
			bool rowwin = true;
			bool colwin = true;
			for (unsigned j = 0; j < DIM; ++j)
			{
				rowwin &= board[i][j] == player;
				colwin &= board[j][i] == player;
			}
			if (colwin || rowwin)
				return true;
		}

		// check for diagonal wins
		bool diagwin = true;
		for (unsigned i = 0; i < DIM; ++i)
			diagwin &= board[i][i] == player;

		if (diagwin)
			return true;

		diagwin = true;
		for (unsigned i = 0; i < DIM; ++i)
			diagwin &= board[DIM - i - 1][i] == player;

		return diagwin;
	}


	Move minimax()
	{
		int score = std::numeric_limits<int>::max();
		Move move;
		int level = 0;

		for (unsigned i = 0; i < DIM; i++)
		{
			for (unsigned j = 0; j < DIM; j++)
			{
				if (board[i][j] == Player::none)
				{
					board[i][j] = Player::computer;
					remained--;

					int temp = maxSearch(level, std::numeric_limits<int>::min(), std::numeric_limits<int>::max());

					if (temp < score)
					{
						score = temp;
						move.x = i;
						move.y = j;
					}

					board[i][j] = Player::none;
					remained++;
				}
			}
		}

		return move;
	}

	int maxSearch(int level, int alpha, int beta)
	{
		if (checkWin(Player::human)) { return 10; }
		else if (checkWin(Player::computer)) { return -10; }
		else if (isTie()) { return 0; }

		int score = std::numeric_limits<int>::min();

		for (unsigned i = 0; i < DIM; i++)
		{
			for (unsigned j = 0; j < DIM; j++)
			{
				if (board[i][j] == Player::none)
				{
					board[i][j] = Player::human;
					remained--;

					score = std::max(score, minSearch(level + 1, alpha, beta) - level);
					alpha = std::max(alpha, score);

					board[i][j] = Player::none;
					remained++;

					if (beta <= alpha) return alpha;
					if (level >= 6) return score;
				}
			}
		}

		return score;
	}

	int minSearch(int level, int alpha, int beta)
	{
		if (checkWin(Player::human)) { return 10; }
		else if (checkWin(Player::computer)) { return -10; }
		else if (isTie()) { return 0; }

		int score = std::numeric_limits<int>::max();

		for (unsigned i = 0; i < DIM; i++)
		{
			for (unsigned j = 0; j < DIM; j++)
			{
				if (board[i][j] == Player::none)
				{
					board[i][j] = Player::computer;
					remained--;

					score = std::min(score, maxSearch(level + 1, alpha, beta) + level);
					beta = std::min(beta, score);

					board[i][j] = Player::none;
					remained++;

					if (beta <= alpha) return beta;
					if (level >= 6) return score;
				}
			}
		}

		return score;
	}

	void getHumanMove()
	{
		bool fail = true;
		unsigned x = -1, y = -1;

		do
		{
			std::cout << "Your Move: ";

			char c;
			std::cin >> c;
			x = c - '0';
			std::cin >> c;
			y = c - '0';

			fail = board[x][y] != Player::none;

			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

		} while (fail);

		board[x][y] = Player::human;
		remained--;
	}
};

int main()
{
	Game tictactoe;
	tictactoe.play();
	std::cin.ignore();
}