TicTacToe Logic

Question

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
};

using PlayerBitmask = std::bitset<9u>;

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

GridState CheckGrid(const Grid& grid) noexcept
{
    if(grid.turn[0u]) {
        for(auto& mask : victoryMasks) {
            if((mask & grid.x) == mask) {
                return GridState::VictoryX;
            }
        }
    }
    else {
        for(auto& mask : victoryMasks) {
            if((mask & grid.o) == mask) {
                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;
}

Answer 1

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) {
    if(grid.turn[0u] && (mask & grid.x) == mask) {
        return GridState::VictoryX;
    }
    elseif(!grid.turn[0u] && (mask & grid.o) == mask) {
         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)
{
    for(auto& mask : victoryMasks) {
        if((mask & player) == mask) {
            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.

Answer 2

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.