# TicTacToe with MiniMax algorithm

I just got into C++ a few days ago and decided to make a MiniMax based TicTacToe game, I don't really know much about the conventions and best uses of the C++ language so I'd really appreciate any kind of feedback.

Brief summary:

• Board: has all the information pertinent to the game. Is used by the main method to paint the window and by the Brain to decide which move to make.
• Brain: Container for the MiniMax algorithm with helper methods. The Board is passed as a pointer to the Brain during construction (I don't know how wise this is but it's how I did things in Java).
• Main: mainly contains functions to draw the board and get inputs from the user. Spacebar clears the board, F1 asks for a move, click performs a move.

Board.h - Most of the comments are not in the header files

#ifndef BOARD_H_
#define BOARD_H_
#include <vector>

typedef enum {empty, x, o} cellState; // The 3 possible states a cell can be in

class Board {
public:
Board();

static const unsigned NUMBER_OF_CELLS = 9;
static const unsigned CELLS_PER_ROW = 3;

Board getClone();
cellState getCell(int n);
std::vector<unsigned> getLegalMoves();

int getWinner();
bool isGameOver();
bool isXTurn();

void applyMove(unsigned m);
void clear();

void print();

private:

std::vector<cellState> cells;
cellState winner;
bool xToMove;
bool gameOver;

void setMark(int p, cellState m);
void update();
void xWon();
void oWon();
void draw();
};

#endif


Board.cpp

#include <iostream>
#include "Board.h"

Board::Board() {
clear();
}

void Board::clear() {  // Resets the game
cells.clear();
for (unsigned i = 0; i < NUMBER_OF_CELLS; i++)
cells.push_back(empty);
winner = empty;
xToMove = true;
gameOver = false;
}

cellState Board::getCell(int n) { // Returns the contents of a cell
return cells.at(n);
}

void Board::setMark(int p, cellState m) { // Sets the contents of a cell
if (getCell(p) != empty || m == empty)
return;
cells.erase(cells.begin()+p);
cells.insert(cells.begin()+p, m);
update();
}

std::vector<unsigned> Board::getLegalMoves() { // Gets a vector of all the empty cells
std::vector<unsigned> moves;

for (unsigned i = 0; i < NUMBER_OF_CELLS; i++)
if (getCell(i) == empty)
moves.push_back(i);
return moves;
}

Board Board::getClone() { // Returns a clone of this board object
Board clone;
for (unsigned i = 0; i < NUMBER_OF_CELLS; i++) {
clone.setMark(i, getCell(i));
}
return clone;
}

void Board::xWon() { // X won the game
winner = x;
gameOver = true;
}

void Board::oWon() { // O won the game
winner = o;
gameOver = true;
}

void Board::draw() { // The game is drawn
gameOver = true;
}

bool Board::isGameOver() {
return gameOver;
}

bool Board::isXTurn() {
return xToMove;
}

int Board::getWinner() { // Returns the winner. x = 1; o = -1; draw = 0
return winner == x? 1 : winner == o? -1 : 0;
}

void Board::update() { // Checks if there is a winner or if the game is drawn
xToMove = !xToMove;

bool xWin;
bool oWin;

// Helper for loop to offset the horizontal and vertical searches
for (unsigned firstOffset = 0; firstOffset < CELLS_PER_ROW; firstOffset++) {

xWin = true;
oWin = true;

// Checks horizontally
for (unsigned totalOffset = firstOffset*CELLS_PER_ROW;
totalOffset < firstOffset*CELLS_PER_ROW+CELLS_PER_ROW; totalOffset++) {
if(getCell(totalOffset) != x)
xWin = false;
if(getCell(totalOffset) != o)
oWin = false;
}

if (xWin) {
xWon();
return;
}

if  (oWin) {
oWon();
return;
}

xWin = true;
oWin = true;

// Checks vertically
for (unsigned totalOffset = firstOffset; totalOffset < firstOffset+7 ; totalOffset+=CELLS_PER_ROW) {

if(getCell(totalOffset) != x)
xWin = false;
if(getCell(totalOffset) != o)
oWin = false;
}

if (xWin) {
xWon();
return;
}

if  (oWin) {
oWon();
return;
}
}

int step = 4;
// Helper for loop which tells the nested loop which diagonal to check
for (unsigned start = 0; start < CELLS_PER_ROW; start+=2) {

xWin = true;
oWin = true;

// Checks a diagonal
for (unsigned check = 0; check < CELLS_PER_ROW; check++) {
if (getCell(start+(check*step)) != x)
xWin = false;
if (getCell(start+(check*step)) != o)
oWin = false;
}
if (xWin) {
xWon();
return;
}
if (oWin) {
oWon();
return;
}
step = 2;
}

draw();
}
}

void Board::applyMove(unsigned p) { // Sets the mark on the specified cell based on the current turn

if (p >= NUMBER_OF_CELLS || isGameOver())
return;

if (xToMove)
setMark(p, x);
else setMark(p, o);
}

void Board::print() { // Prints the board to the console for bugtesting purposes
std::cout << "---------" << std::endl;
for (unsigned i = 0; i < CELLS_PER_ROW; i++) {
for (unsigned j = 0; j < CELLS_PER_ROW; j++)
switch (getCell(i*CELLS_PER_ROW+j)) {
case x:
std::cout << " X ";
break;
case o:
std::cout << " O ";
break;
default:
std::cout << " - ";
}
std::cout << std::endl;
}
}


Brain.h

#ifndef BRAIN_H_
#define BRAIN_H_
#include "Board.h"

class Brain {

public:
Brain(Board* b);

int getBestMove();
void setBoard(Board* b); // Method not yet implemented, not needed for this small project

private:
Board* board;

int miniMax(Board b, unsigned move);
int min(std::vector<int> v);
int max(std::vector<int> v);
};

#endif


Brain.cpp

#include "Brain.h"

Brain::Brain(Board* b) {
board = b; // Board which will be used when calling getBestMove()
}

int Brain::getBestMove() { // "Main" method which calls all the others in order to return the best move
// based on which turn it is

std::vector<unsigned> availableMoves = board->getLegalMoves();
if (availableMoves.size() == 0)
return 0;

std::vector<int> moveScore;
// For each available move a score is assigned
for (unsigned i = 0; i < availableMoves.size(); i++)
moveScore.push_back(miniMax(board->getClone(), availableMoves.at(i)));

// And based on which turn it is the one with the highest/lowest score is returned
if(board->isXTurn())
return availableMoves.at(max(moveScore));
else return availableMoves.at(min(moveScore));
}

int Brain::miniMax(Board b, unsigned move) { // Classic MiniMax algorithm

b.applyMove(move);
if (b.isGameOver())
return b.getWinner(); // If the game is over the value is returned (1, 0, -1)

// Otheriwse for each other legal move miniMax is called again
std::vector<unsigned> availableMoves = b.getLegalMoves();
if (b.isXTurn()) { // X is the Maximizing player
int max = -1;
for (unsigned i = 0; i < availableMoves.size(); i++) {
int score = miniMax(b, availableMoves.at(i));
if (score > max)
max = score;
}
return max;

} else { // O is the minimixing player
int min = 1;
for (unsigned i = 0; i < availableMoves.size(); i++) {
int score = miniMax(b, availableMoves.at(i));
if (score < min)
min = score;
}
return min;
}
}

int Brain::min(std::vector<int> v) { // Helper method which returns the index of the lowest value in a vector
if (v.size() == 1)
return 0;

int minValue = v.at(0);
int minIndex = 0;
for (unsigned i = 1; i < v.size(); i++)
if (minValue > v.at(i)) {
minValue = v.at(i);
minIndex = i;
}

return minIndex;
}

int Brain::max(std::vector<int> v) { // Helper method which returns the index of the highest value in a vector
if (v.size() == 1)
return 0;

int maxValue = v.at(0);
int maxIndex = 0;
for (unsigned i = 1; i < v.size(); i++)
if (maxValue < v.at(i)) {
maxValue = v.at(i);
maxIndex = i;
}

return maxIndex;
}


Main

#include <iostream>
#include <math.h>
#include <SFML/Graphics.hpp>
#include "Board.h"
#include "Brain.h"

using namespace sf;
using std::cout;
using std::endl;

void drawBoard(RenderWindow &window, Board &board);
void drawBG(RenderWindow &window);
sf::Color getBGColor(unsigned cell);
int translateCoords(Vector2i &v);

unsigned cellWidth;
unsigned cellHeight;

const sf::Color light (55, 55, 55);
const sf::Color dark (33, 33, 33);
const sf::Color red(90, 100, 200);
const sf::Color blue(180, 40, 40);

int main() {

Board board;
Brain brain(&board);

RenderWindow window (VideoMode(400, 400), "Tic Tac Toe");
window.setKeyRepeatEnabled(false);

cellWidth = window.getSize().x / Board::CELLS_PER_ROW;
cellHeight = window.getSize().y / Board::CELLS_PER_ROW;

while (window.isOpen()) {

sf::Event event;
while (window.pollEvent(event)) {

switch (event.type) {

case sf::Event::Closed:
window.close();
break;

case sf::Event::Resized:
//              cellWidth = window.getSize().x / Board::CELLS_PER_ROW; Bugged
//              cellHeight = window.getSize().y / Board::CELLS_PER_ROW;  To fix
break;

case sf::Event::KeyPressed:
if (event.key.code == sf::Keyboard::Space) // Space = Resets the board
board.clear();
else if (event.key.code == sf::Keyboard::F1) // F1 = Asks for a move
board.applyMove(brain.getBestMove());
break;

case sf::Event::MouseButtonReleased:  // Click == Applies a move
if (event.mouseButton.button == sf::Mouse::Left) {
Vector2i mousePos = sf::Mouse::getPosition(window);
board.applyMove(translateCoords(mousePos));
}
break;

default:
break;
}
}

window.clear();
drawBG(window);
drawBoard(window, board);
window.display();
}

return 0;
}

int translateCoords(Vector2i &v) {  // Function needed to translate window coordinates to game coordinates
int x = floor((v.x) / cellWidth);
int y = floor((v.y) /cellHeight);
return (int)(x + y * Board::CELLS_PER_ROW);
}

sf::Color getBGColor(unsigned cell) {  // Helper function to draw the background checkered pattern
return cell / Board::CELLS_PER_ROW % 2 == cell % Board::CELLS_PER_ROW % 2 ? dark : light;
}

void drawBG(RenderWindow &window) {  // Draws the background checkered pattern
sf::RectangleShape rect(sf::Vector2f(cellWidth, cellHeight));
for (unsigned i = 0; i < Board::NUMBER_OF_CELLS; i++) {
rect.setPosition(i%Board::CELLS_PER_ROW*cellWidth, i/Board::CELLS_PER_ROW*cellHeight);
rect.setFillColor(getBGColor(i));
window.draw(rect);
}
}

void drawBoard(RenderWindow &window, Board &board) {  // Draws the board based on where the naughts and crosses are
// To make things simple the crosses are actually squares

sf::CircleShape circle(cellWidth/2);
circle.setFillColor(red);
sf::RectangleShape rect(sf::Vector2f(cellWidth, cellHeight));
rect.setFillColor(blue);
for (unsigned i = 0; i < Board::NUMBER_OF_CELLS; i++) {
switch (board.getCell(i)) {
case x:
rect.setPosition(i%Board::CELLS_PER_ROW*cellWidth, i/Board::CELLS_PER_ROW*cellHeight);
window.draw(rect);
break;
case o:
window.draw(circle);
break;
default:
break;
}
}
}

• In C++, if you want to pass ownership of resources of the object to another object, you can move construct from it. – Incomputable Apr 15 '17 at 18:56

# Don't use raw pointers, make ownership semantics clear

class Brain {

public:
Brain(Board* b);

int getBestMove();
void setBoard(Board* b); // Method not yet implemented, not needed for this small project

private:
Board* board;
// ...
};


Your Brain class uses a raw pointer to reference a current Board it is supposed to work with. Raw pointers leave us unclear about their ownership and who's responsible for the memory management.

You should rather use a smart pointer like std::unique_ptr<Board> (indicates ownership is transferred to the Brain class), std::shared_ptr<Brain> (indicates ownership is shared) or std::weak_ptr<Brain> (indicates Brain doesn't own that reference). I'll give a sample using std::shared_ptr:

class Brain {

public:
Brain(std::shared_ptr<Board> b);

int getBestMove();
void setBoard(std::shared_ptr<Board> b);

private:
std::shared_ptr<Board> board;
// ...
};


# Don't pass complex objects by value

int min(std::vector<int> v);
int max(std::vector<int> v);


You should use const references for these parameters:

int min(const std::vector<int>& v);
int max(const std::vector<int>& v);


Modern compilers may elide copies for these parameters, though semantics will be more clear and prevent you from accidentally changing those parameters inside the function.

# Use const correctness

Since the min() or max() functions never change the state of the Brain class, these should be declared as const member functions:

int min(std::vector<int> v) const;
int max(std::vector<int> v) const;


In fact those functions don't even rely on any state stored in Brain, thus these shouldn't be class members at all but free functions. Best choice would be to use the already existing std::min_element() and std::max_element() functions from the standard library instead.

# Prefer operator[] over at() to access container elements by index

The std::vector<T>::at() function introduces bounds checking and will throw an exception if the requested index is out of bounds.

That's nice for debugging purposes with unchecked size beforehand.

For performance reasons you should prefer to do size checks beforehand and use the operator[] overload of the container class at all.

• Thank you very much, will make sure to implement your suggestions in my next project. – Daniel Apr 17 '17 at 15:06