# TicTacToe Logic

I've started to write a small Tic-Tac-Toe game. I am pretty sure everyone knows how this game works so I don't have to explain that part. I've decided to represent the grid using 2 bitsets which allows for an easy grid evaluation. I just want to hear some thoughts on this code regarding style and my solution in general. Keep in mind that this isn't a finished game yet, it's just the logic component which works as expected if you manually do all the stuff in main.

#include <algorithm>
#include <array>
#include <bitset>
#include <exception>
#include <iostream>
#include <limits>
#include <map>
#include <utility>

using Turn = std::bitset<1u>; // std::bitset for convenience

struct Grid
{
using PlayerBitset = std::bitset<9u>;

Turn turn;

PlayerBitset x;
PlayerBitset o;
};

enum class GridState
: std::uint16_t
{
VictoryX    = 0x0,
VictoryO    = 0x1,
Draw        = 0x2,
Unspecified = 0x3
};

constexpr std::array<PlayerBitmask, 8u> victoryMasks{ 0x007, 0x038, 0x049, 0x054, 0x092, 0x111, 0x124, 0x1c0 };

GridState CheckGrid(const Grid& grid) noexcept
{
if(grid.turn[0u]) {
return GridState::VictoryX;
}
}
}
else {
return GridState::VictoryO;
}
}
}

if(grid.x.count() + grid.o.count() >= 9u) {
return GridState::Draw;
}
else {
return GridState::Unspecified;
}
}

using Move = std::uint16_t;
using MoveSet = std::bitset<9u>;

MoveSet GetPossibleMoves(const Grid& grid) noexcept
{
return ~(grid.x ^ grid.o);
}

void MakeMove(const Move move, Grid& grid)
{
if(GetPossibleMoves(grid).test(move)) { // Throws std::out_of_range if move does not correspond to a valid position within the bitset
if(grid.turn[0u]) {
grid.x[move] = true;
}
else {
grid.o[move] = true;
}
grid.turn.flip();
}
else {
throw std::invalid_argument("Invalid move.");
}
}

std::int16_t AlphaBeta(const Grid& grid, std::int16_t alpha, std::int16_t beta, std::uint16_t depth) noexcept
{
switch(CheckGrid(grid)) {
case GridState::VictoryX :
{
return depth - 10u;
}

case GridState::VictoryO :
{
return 10u - depth;
}

case GridState::Draw :
{
return 0u;
}

case GridState::Unspecified :
{
auto moveSet{ GetPossibleMoves(grid) };

if(!grid.turn[0u]) {
for(auto i{ 0u }; i < moveSet.size(); ++i) {
if(moveSet[i]) {
Grid g{ grid };
MakeMove(i, g);

auto utility{ AlphaBeta(g, alpha, beta, (depth + 1u)) };

if(utility > alpha) {
alpha = utility;
}

if(alpha >= beta) {
return alpha;
}
}
}
return alpha;
} // if
else {
for(auto i{ 0u }; i < moveSet.size(); ++i) {
if(moveSet[i]) {
Grid g{ grid };
MakeMove(i, g);

auto utility{ AlphaBeta(g, alpha, beta, (depth + 1u)) };

if(utility < beta) {
beta = utility;
}

if(alpha >= beta) {
return beta;
}
}
}
return beta;
} // else
}
} // switch
}

Move GetBestMove(const Grid& grid) noexcept
{
auto moveSet{ GetPossibleMoves(grid) };

std::multimap<std::int16_t, Move> results;

for(auto i{ 0u }; i < moveSet.size(); ++i) {
if(moveSet[i]) {
Grid g{ grid };
MakeMove(i, g);

results.emplace(AlphaBeta(g, std::numeric_limits<std::int16_t>::min(), std::numeric_limits<std::int16_t>::max(), 0u), i);
}
}
return std::max_element(results.cbegin(), results.cend())->second;
}


One thing I noticed, you've got the same loop in each branch of a conditional(if-else). It would be cleaner and easier to understand and maintain to have one loop with different conditionals in it.

for(auto& mask : victoryMasks) {
return GridState::VictoryX;
}
return GridState::VictoryO;
}
}


Has another thought about maintaining the original logic and still improving cleanliness and maintenance. Put the loop into a function that returns a bool and takes a PlayerBitset as a parameter:

bool CheckForVictory(PlayerBitset player)
{
return true;
}
}
return false;
}

if(grid.turn[0u]) {
if(CheckForVictory(grid.x){
return GridState::VictoryX;
}
}
else {
if(CheckForVictory(grid.o){
return GridState::VictoryO;
}
}


You can follow this same pattern anywhere you see major duplications of your code.

• I also thought of that, but wouldn't that increases the number of checks made during the algorithm by alot? I mean this code even checks the grid for a VictoryO even if it's impossible that he won this round. May 23, 2017 at 16:30
– user33306
May 23, 2017 at 19:45
• When if(grid.turn[0u] && (mask & grid.x) == mask)isn't true it still checks the first condition for the elseif, which isn't the case in my original design. :) I know this has like zero to none impact on the performance, but it's still the better way I think. May 23, 2017 at 21:16
– user33306
May 25, 2017 at 3:00
• That's a nice idea, I am going to add that one. :) May 25, 2017 at 14:10

Just some small nitpicks:

First, in GetPossibleMoves you might want to change the xor operation to an or operation. Reasoning: If by any chance the same bit is set in both grid.x and grid.o, you would return the move corresponding to that bit as possible. Granted, by proper execution of your code this scenario is unlikely, but I've experienced worse. (On the other hand, if that scenario really happens, you might be screwed anyways.)

Second, I have no idea what AlphaBeta does based on its name. Maybe change it to something more fitting (like CalculateGridScore)?

Third, you define the Turn type as std::bitset<1u> and justify it in a comment as "for convenience". If that matters for some reason outside of the code presented, fine, but as given I'd be very tempted to exchange it for a bool, or better, an enum.

• I also considered the following: enum class Turn : bool { X = true, O = false }; and then an overloaded ! operator to flip the turn in a convenient way. A simple bool might have done the job as well. AlphaBeta is Alpha-Beta-Pruning, an optimized version of minimax. May 23, 2017 at 10:06
• as said, those were just small nitpicks ;) Thanks for the explanation on AlphaBeta, I appreciate that. That said, I rather have my function names tell me what they do instead of how they are doing their job, but YMMV. May 23, 2017 at 23:46