Hex Game BitBoard with very fast algorithm to determine the winner

hex_bitboard.cpp

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <cassert>
#include <cinttypes>
#include <cstring>

/*
  BitBoard
 */
class BitBoard {
public:
  BitBoard(uint32_t size) : _size(size) {
    assert(size <= 32);
    _players[0].reset(new uint32_t[size]);
    _players[1].reset(new uint32_t[size]);
  }

  void reset() {
    std::fill_n(_players[0].get(), _size, 0);
    std::fill_n(_players[1].get(), _size, 0);
  }

  bool isToggled(uint32_t id) const noexcept {
    uint32_t row = id / _size;
    uint32_t col = id % _size;

    return (((_players[0].get()[row] >> col) & 1) | ((_players[1].get()[col] >> row) & 1));
  }

  void toggle(uint32_t id, uint32_t player) noexcept {
    uint32_t pos[2] = {id / _size, id % _size};
    uint32_t row = pos[0 ^ player];
    uint32_t col = pos[1 ^ player];

    _players[player].get()[row] |= 1 << col;
  }

  void toggle(uint32_t row, uint32_t col, uint32_t player) noexcept {
    toggle(row * _size + col, player);
  }

  bool isEndGame(uint32_t player) const noexcept {
    enum State {
      LinkDown,
      LinkUp,
      Capture
    };

    uint32_t board[_size];
    uint32_t shadow_board[_size];

    std::memcpy(board, _players[player].get(), _size * 4);
    std::fill_n(shadow_board, _size, 0);

    uint32_t shadow_row = board[0];
    uint32_t row = 0;

    shadow_board[0] = board[0];
    board[0] = 0;

    State state = LinkDown;
    uint32_t row_num = 1;

    uint32_t connections = 0;
    while (true) {
      switch (state) {
      case State::LinkDown: {
        row = board[row_num];
        connections = (row & shadow_row) | ((shadow_row & (row << 1)) >> 1);

        if (connections) {
          if (row_num == _size - 1)
            return true;

          state = State::Capture;
        } else {
          shadow_row = shadow_board[row_num];
          if (shadow_row) {
            row_num++;
          } else {
            return false;
          }
        }
        break;
      }
      case State::LinkUp: {
        row = board[row_num];
        connections = (row & shadow_row) | ((shadow_row & (row >> 1)) << 1);
        if (connections) {
          state = State::Capture;
        } else {
          shadow_row = shadow_board[row_num];
          row_num++;
          state = State::LinkDown;
        }
        break;
      }
      case State::Capture: {
        uint32_t capture = 0;

        for (uint32_t col_num = 0; col_num < _size;) {
          if (connections & (1 << col_num)) {
            uint32_t left_bits_count = __builtin_ctz(~(row >> col_num));
            uint32_t right_bits_count = __builtin_clz(~(row << (31 - col_num)));
            capture |= ((1 << (left_bits_count + right_bits_count - 1)) - 1) << (col_num - right_bits_count + 1);

            col_num += left_bits_count;
          } else {
            col_num++;
          }
        }
        board[row_num] ^= capture;
        shadow_board[row_num] |= capture;
        shadow_row = shadow_board[row_num];

        if (board[row_num-1]) {
          row_num--;
          state = State::LinkUp;
        } else {
          row_num++;
          state = State::LinkDown;
        }
        break;
      }
      }
    }
  }

private:
  std::unique_ptr<uint32_t> _players[2];
  uint32_t _size;
};


int main(int argc, char* argv[]) {
  BitBoard b = BitBoard(3);
  b.toggle(0, 1, 0);
  b.toggle(1, 0, 0);
  b.toggle(1, 0, 0);
  b.toggle(2, 0, 0);

  std::cout << b.isEndGame(0) << std::endl;

  return 0;
}