TicTacToe with MiniMax algorithm

Question

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;
 unsigned movesMade;
 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;
 movesMade = 0;
}
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
 // Also updates the turn
 xToMove = !xToMove;
 movesMade++;
 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;
 }
 if (movesMade == NUMBER_OF_CELLS) {
 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.setOrigin(circle.getRadius(), circle.getRadius());
 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:
 circle.setPosition(i%Board::CELLS_PER_ROW*cellWidth+circle.getRadius(), i/Board::CELLS_PER_ROW*cellHeight+circle.getRadius());
 window.draw(circle);
 break;
 default:
 break;
 }
 }
}

• Incomputable: In C++, if you want to pass ownership of resources of the object to another object, you can move construct from it.

Answer 1

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.

• Daniel: Thank you very much, will make sure to implement your suggestions in my next project.