Posted my first attempt at Tic-Tac-Toe a second ago here. Got a lot of great and helpful responses. The main things I took away from these responses was to use spell check, and to keep things simple. Wanted to give it a second go before moving on to something a bit bigger.
Learned about the Minimax algorithm from this article. It doesn't work exactly like I'd hope but I can't tell if it's just the pitfalls of the algorithm or my code.
I'm grateful for any critique or pointers.
tictactoe.h
#ifndef TICTACTOE
#define TICTACTOE
#include <bitset>
#include <iostream>
#include <vector>
enum class BoardValue{ none, o, x};
class Board
{
public:
Board() = default;
Board(const Board& board): o_bits(board.o_bits), x_bits(board.x_bits) {};
BoardValue at(int index) const;
bool check_tie() const;
bool check_win(bool) const;
bool place(int, bool);
std::vector<int> possible_moves() const;
private:
std::bitset<9> o_bits{};
std::bitset<9> x_bits{};
std::bitset<9> filled_bits() const{ return o_bits | x_bits; }
};
class AI
{
public:
AI(bool o) : is_o(o) {};
int best_move(const Board&);
private:
int minimax(const Board&, int, bool);
int choice{};
bool is_o; //is the ai playing as 'O'
};
#endif
tictactoe.cpp
#include "tictactoe.h"
#include <bitset>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>
BoardValue Board::at(int index) const{
if(index < 0 || 8 < index) throw std::out_of_range{ "Index out of Board range" };
if(filled_bits().test(index) == true)
{
return (o_bits.test(index) ? BoardValue::o : BoardValue::x);
}
else return BoardValue::none;
}
bool Board::check_tie() const
{
std::bitset<9> full_board{ "111111111" };
if( full_board == (filled_bits() & full_board) ) return true;
return false;
}
bool Board::check_win(bool o) const
{
const std::bitset<9>& bits = o ? o_bits : x_bits; //bits to be checked
//diagonals
if(bits.test(4) != false) //if middle is not taken no diagonals will pass
{
std::bitset<9> forward_diagonal{ "100010001" }; //bits of '\'
std::bitset<9> backward_diagonal{ "001010100" }; //bits of '/'
if(forward_diagonal == (bits & forward_diagonal)) return true;
if(backward_diagonal == (bits & backward_diagonal)) return true;
}
//columns and rows
std::bitset<9> col_check{ "001001001" }; //bits of the first column/row
std::bitset<9> row_check{ "000000111" };
for(int i = 0; i < 3; ++i) // loop for all 3 columns and rows
{
if(col_check == (bits & col_check)) return true;
if(row_check == (bits & row_check)) return true;
col_check = col_check << 1; //move over a column/row over
row_check = row_check << 3;
}
return false;
}
//returns false if index is occupied
bool Board::place(int index, bool o)
{
if(at(index) != BoardValue::none) return false;
std::bitset<9>& bits = o ? o_bits : x_bits; //bits to be changed
bits.set(index);
return true;
}
//returns indexes of free spaces
//all returned indexes will return true when used in place(int,bool)
std::vector<int> Board::possible_moves() const
{
const std::bitset<9> bits = filled_bits();
std::vector<int> moves{};
//loop through each bit and add the index of the ones that are 0 to possible_moves
for(int i = 0; i < 9; ++i)
{
if( bits.test(i) == false)
{
moves.push_back(i);
}
}
return moves;
}
int AI::best_move(const Board& board)
{
minimax(board, 0, true);
return choice;
}
int AI::minimax(const Board& position, int depth, bool maxPlayer)
{
//check position game state and return score if game is lost, won, or tied
if(position.check_win(!is_o)) //AI loses
{
return depth - 10;
}
else if(position.check_win(is_o)) //AI wins
{
return 10 - depth;
}
else if(position.check_tie())
{
return 0;
}
//do minimax calculation
if(maxPlayer)
{
int max_move{};
int max_move_score{ std::numeric_limits<int>::min()};
for(int move : position.possible_moves())
{
Board possible_position{ position };
possible_position.place(move, is_o);
int score = minimax(possible_position, ++depth, false);
if ( score > max_move_score )
{
max_move = move;
max_move_score = score;
}
}
choice = max_move;//last call to this will be at first call to minimax() from best_move()
return max_move_score; //return max score
}
else
{
int min_move{};
int min_move_score{ std::numeric_limits<int>::max()};
for(int move : position.possible_moves())
{
Board possible_position{ position };
possible_position.place(move, !is_o);
int score = minimax(possible_position, ++depth, true);
if ( score < min_move_score )
{
min_move = move;
min_move_score = score;
}
}
return min_move_score; //return max score
}
}
main.cpp
#include "tictactoe.h"
#include <array>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
int ask_player_input()
{
bool retry{ false };
int index{};
std::cout << "It's your turn. Where do you want to go(e.g. A1 B3 C2)? ";
do{
if(retry)
{
std::cout << "No, no, no! Input a letter followed by a number: ";
}
retry = false; //reset retry
std::string input;
std::cin >> input;
if(input.size() < 2)
{
retry = true;
continue;
}
//letter input
int col_input{};
switch(input.at(0))
{
case 'A':
case 'a':
col_input = 0;
break;
case 'B':
case 'b':
col_input = 1;
break;
case 'C':
case 'c':
col_input = 2;
break;
default:
retry = true;
continue;
}
//number input
int row_input = input.at(1) - '0'; //converts char '2' to int 2
if(--row_input < 0 || 3 < row_input)
{
retry = true;
continue;
}
index = col_input * 3 + row_input;
} while( retry );
return index;
}
bool ask_turn() //ask who will go first if return true O goes first
{
bool turn{};
std::string input;
std::cout << "Who do you want to be?(X or O)? ";
for(bool valid_input{false}; !valid_input;)
{
std::cin >> input;
switch(input.front()) //input cannot be null at this point
{
case 'x':
case 'X':
valid_input = true;
turn = false;
break;
case '0':
case 'o':
case 'O':
valid_input = true;
turn = true;
break;
default:
std::cout << "Invalid input! Try X or O :";
}
}
return turn;
}
std::ostream& print_board(std::ostream& os,const Board& board)
{
os << " |A|B|C\n";
for(int row = 0; row < 3; ++row)
{
os << std::string( 8, '-') << '\n';
os << row + 1 << '|';
for(int col = 0; col < 3; ++col)
{
char follow_char{ col == 2 ? '\n' : '|' };
char place_char{};
//determine character to print for this board place on the board
BoardValue place_value = board.at(col * 3 + row);
if(place_value == BoardValue::none) place_char = ' ';
else place_char = place_value == BoardValue::o ? 'O' : 'X';
os << place_char << follow_char;
}
}
os << '\n';
return os;
}
std::ostream& operator<<(std::ostream& os,const Board& board)
{
return print_board(os, board);
}
int main(){
std::default_random_engine e{ static_cast<long unsigned int>(time(NULL)) };
bool turn{ e() % 2 };
bool player_turn{ ask_turn() };
Board board{};
AI ai{ !player_turn };
if(turn != player_turn)//player first, turns will be flipped at start of game loop
{
std::cout << "You go first!\n" << board;
}
else
{
std::cout << "Computer gets to go first this time. Good luck!\n";
}
while(board.check_win(turn) == false && board.check_tie() == false)
{
turn = !turn;
if(turn == player_turn)
{
bool input_valid{false};
while(input_valid == false)
{
int input;
input = ask_player_input();
input_valid = board.place(input, turn);
if( input_valid == false )
std::cout << "That place is take! Try again...\n";
}
}
else //AI turn
{
int best_move = ai.best_move(board);
board.place( best_move, turn);
std::cout << board;
//print AI turn
std::array<char,3> col_chars = { 'A', 'B', 'C' };
char col_input = col_chars.at( best_move % 3 );
int row_input = ((best_move + 1) / 3) + 1;
std::cout << "Computer picks " << col_input << row_input << '\n';
}
}
std::cout << board;
if(board.check_tie())
{
std::cout << "Looks like its a tie...\n";
}
else
{
std::cout << (turn == player_turn ? "You won!" : "The computer wins..." ) << '\n';
}
}
