MORTAL2000 · January 5, 2018 15:06 · Jan 5, 2018
diff --git a/TicTacToe-minimax-SFML.cpp b/TicTacToe-minimax-SFML.cpp
@@ -0,0 +1,429 @@
+#include <SFML/Graphics.hpp>
+#include <iostream>
+#include <memory>
+#include <map>
+#include <string>
+#include <vector>
+#include <array>
+#include <random>
+#include <stdexcept>
+#include <cassert>
+
+namespace
+{
+	const sf::Vector2i WINDOW_SIZE(640, 480);
+	const unsigned NUMBER_OF_PLAYERS = 2;
+	const unsigned DIM = 3;
+	const float SIZE = 70.f;
+	const sf::Vector2f START_POINT(WINDOW_SIZE.x * 0.5f - DIM * SIZE * 0.5f, WINDOW_SIZE.y * 0.5f - DIM * SIZE * 0.5f);
+}
+
+enum struct Player : unsigned
+{
+	None,
+	User,
+	Computer
+};
+
+template <typename Resource> static
+void centerOrigin(Resource& resource)
+{
+	sf::FloatRect bounds = resource.getLocalBounds();
+	resource.setOrigin(std::floor(bounds.left + bounds.width / 2.f), std::floor(bounds.top + bounds.height / 2.f));
+}
+
+class Tile : public sf::RectangleShape, private sf::NonCopyable
+{
+public:
+	Tile() = default;
+
+	void setOwner(Player player)
+	{
+		mOwner = player;
+	}
+
+	Player getOwner() const
+	{
+		return mOwner;
+	}
+
+private:
+	Player mOwner = Player::None;
+};
+
+class World : private sf::NonCopyable
+{
+	struct Move
+	{
+		unsigned x = 0;
+		unsigned y = 0;
+	};
+
+public:
+	explicit World(sf::RenderTarget& outputTarget);
+
+	bool isFull() const;
+	bool isWinner(Player player) const;
+	bool applyMove(Player player, sf::Uint32 row, sf::Uint32 column) const;
+	bool applyAl(Player player) const;
+	void draw();
+
+private:
+	Move minimax() const;
+	int minSearch(int level) const;
+	int maxSearch(int level) const;
+
+private:
+	sf::RenderTarget& mTarget;
+	mutable unsigned mRemain;
+	mutable std::array<Tile, DIM * DIM> mTiles;
+};
+
+World::World(sf::RenderTarget& outputTarget)
+	: mTarget(outputTarget)
+	, mTiles()
+	, mRemain(DIM * DIM)
+{
+	sf::Vector2f startPosition(START_POINT);
+
+	for (unsigned i = 0; i < DIM; ++i)
+	{
+		for (unsigned j = 0; j < DIM; ++j)
+		{
+			unsigned index = j * DIM + i;
+
+			mTiles[index].setSize(sf::Vector2f(SIZE, SIZE));
+			mTiles[index].setPosition(startPosition);
+			mTiles[index].setOutlineThickness(2.f);
+			mTiles[index].setFillColor(sf::Color::Black);
+			mTiles[index].setOutlineColor(sf::Color::White);
+
+			startPosition.x += SIZE;
+		}
+
+		startPosition.y += SIZE;
+		startPosition.x = START_POINT.x;
+	}
+}
+
+void World::draw()
+{
+	for (const auto& tile : mTiles)
+	{
+		mTarget.draw(tile);
+	}
+}
+
+bool World::applyMove(Player player, sf::Uint32 row, sf::Uint32 column) const
+{
+	unsigned index = row + DIM * column;
+
+	if ((index > mTiles.size()) || (mTiles[index].getOwner() != Player::None) || row >= DIM || column >= DIM)
+	{
+		return false;
+	}
+
+	--mRemain;
+
+	mTiles[index].setOwner(player);
+
+	switch (player)
+	{
+	case Player::User:
+		mTiles[index].setFillColor(sf::Color::Blue);
+		break;
+	case Player::Computer:
+		mTiles[index].setFillColor(sf::Color::Red);
+		break;
+	}
+
+	return true;
+}
+
+bool World::isFull() const
+{
+	return (mRemain == 0);
+}
+
+bool World::applyAl(Player player) const
+{
+	Move move = minimax();
+	return applyMove(player, move.x, move.y);
+}
+
+World::Move World::minimax() const
+{
+	static int level = 0;
+	int score = std::numeric_limits<int>::max();
+	Move move;
+
+	for (unsigned i = 0; i < DIM; i++)
+	{
+		for (unsigned j = 0; j < DIM; j++)
+		{
+			unsigned index = j * DIM + i;
+
+			if (mTiles[index].getOwner() == Player::None)
+			{
+				mTiles[index].setOwner(Player::Computer);
+				--mRemain;
+
+				int temp = maxSearch(level);
+
+				if (temp < score)
+				{
+					score = temp;
+					move.x = i;
+					move.y = j;
+				}
+
+				mTiles[index].setOwner(Player::None);
+				++mRemain;
+			}
+		}
+	}
+
+	return move;
+}
+
+int World::maxSearch(int level) const
+{
+	if (isWinner(Player::User)) { return 10; }
+	else if (isWinner(Player::Computer)) { return -10; }
+	else if (isFull()) { return 0; }
+
+	int score = std::numeric_limits<int>::min();
+
+	for (unsigned i = 0; i < DIM; i++)
+	{
+		for (unsigned j = 0; j < DIM; j++)
+		{
+			unsigned index = j * DIM + i;
+
+			if (mTiles[index].getOwner() == Player::None)
+			{
+				mTiles[index].setOwner(Player::User);
+				--mRemain;
+
+				score = std::max(score, minSearch(level + 1) - level);
+
+				mTiles[index].setOwner(Player::None);
+				++mRemain;
+			}
+		}
+	}
+
+	return score;
+}
+
+int World::minSearch(int level) const
+{
+	if (isWinner(Player::User)) { return 10; }
+	else if (isWinner(Player::Computer)) { return -10; }
+	else if (isFull()) { return 0; }
+
+	int score = std::numeric_limits<int>::max();
+
+	for (unsigned i = 0; i < DIM; i++)
+	{
+		for (unsigned j = 0; j < DIM; j++)
+		{
+			unsigned index = j * DIM + i;
+
+			if (mTiles[index].getOwner() == Player::None)
+			{
+				mTiles[index].setOwner(Player::Computer);
+				--mRemain;
+
+				score = std::min(score, maxSearch(level + 1) + level);
+
+				mTiles[index].setOwner(Player::None);
+				++mRemain;
+			}
+		}
+	}
+
+	return score;
+}
+
+bool World::isWinner(Player player) const
+{  
+	// 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 &= mTiles[i*DIM + j].getOwner() == player;
+			colwin &= mTiles[j*DIM + i].getOwner() == player;
+		}
+		if (colwin || rowwin)
+			return true;
+	}
+
+	// check for diagonal wins
+	bool diagwin = true;
+	for (unsigned i = 0; i < DIM; ++i)
+		diagwin &= mTiles[i*DIM + i].getOwner() == player;
+
+	if (diagwin)
+		return true;
+
+	diagwin = true;
+	for (unsigned i = 0; i < DIM; ++i)
+		diagwin &= mTiles[i*DIM + (DIM - i - 1)].getOwner() == player;
+
+	return diagwin;
+}
+
+class Game : private sf::NonCopyable
+{
+public:
+	Game();
+	void run();
+
+private:
+	void processEvents();
+	void update();
+	void render();
+
+	sf::RenderWindow mWindow;
+
+	sf::Font mFont;
+	sf::Text mText;
+	sf::Text mTitle;
+
+	World mWorld;
+	std::array<Player, NUMBER_OF_PLAYERS> mPlayers;
+};
+
+Game::Game()
+	: mWindow(sf::VideoMode(WINDOW_SIZE.x, WINDOW_SIZE.y), "Tic Tac Toe - SFML")
+	, mFont()
+	, mText()
+	, mTitle()
+	, mWorld(mWindow)
+	, mPlayers({ { Player::User, Player::Computer } })
+{
+	mWindow.setVerticalSyncEnabled(true);
+
+	if (!mFont.loadFromFile("Sansation.ttf"))
+		throw std::runtime_error("Failed to load font");
+
+	mText.setFont(mFont);
+	mText.setStyle(sf::Text::Bold);
+	mText.setCharacterSize(20);
+	mText.setFillColor(sf::Color::White);
+	mText.setPosition(30.f, mWindow.getSize().y - 50.f);
+	centerOrigin(mText);
+
+	mTitle.setString("Colourful Tic Tac Toe");
+	mTitle.setFont(mFont);
+	mTitle.setStyle(sf::Text::Bold);
+	mTitle.setCharacterSize(30);
+	mTitle.setFillColor(sf::Color::White);
+	mTitle.setPosition(mWindow.getSize().x * 0.5f, 50.f);
+	centerOrigin(mTitle);
+}
+
+void Game::run()
+{
+	while (mWindow.isOpen())
+	{
+		processEvents();
+		update();
+		render();
+	}
+}
+
+void Game::processEvents()
+{
+	sf::Event event;
+
+	while (mWindow.pollEvent(event))
+	{
+		if (event.type == sf::Event::Closed)
+			mWindow.close();
+	}
+}
+
+void Game::update()
+{
+	static bool winner = false;
+	static bool tie = false;
+	static unsigned index = 0;
+
+	if (tie || winner) return;
+
+	switch (mPlayers[index])
+	{
+	case Player::User:
+		if (sf::Mouse::isButtonPressed(sf::Mouse::Left))
+		{
+			const sf::Vector2i& position = sf::Mouse::getPosition(mWindow);
+
+			if (position.x > START_POINT.x &&
+				position.y > START_POINT.y &&
+				position.x < (START_POINT.x + (DIM*SIZE)) &&
+				position.y < (START_POINT.y + (DIM*SIZE)))
+			{
+				unsigned row = static_cast<unsigned>((position.y - START_POINT.y) / SIZE);
+				unsigned col = static_cast<unsigned>((position.x - START_POINT.x) / SIZE);
+
+				if (mWorld.applyMove(Player::User, row, col)) {
+					winner = mWorld.isWinner(Player::User);
+					if (!winner) {
+						index ^= 1;
+					}
+				}
+			}
+		}
+		break;
+	case Player::Computer:
+		if (mWorld.applyAl(Player::Computer)) {
+			winner = mWorld.isWinner(Player::Computer);
+			if (!winner) {
+				index ^= 1;
+			}
+		}
+		break;
+	}
+
+	if (winner)
+	{
+		mText.setString("The Winner: " + std::string((mPlayers[index] == Player::User) ? "Blues" : "Reds"));
+		return;
+	}
+
+	tie = mWorld.isFull();
+
+	if (tie)
+	{
+		mText.setString("*** Tie ***");
+		return;
+	}
+}
+
+void Game::render()
+{
+	mWindow.clear();
+	mWorld.draw();
+	mWindow.draw(mTitle);
+	mWindow.draw(mText);
+	mWindow.display();
+}
+
+int main()
+{
+	try
+	{
+		Game game;
+		game.run();
+	}
+	catch (std::runtime_error& e)
+	{
+		std::cout << "\nException: " << e.what() << std::endl;
+		return 1;
+	}
+}