Probabilistic algorithm to determine the End Game in the game Hex. False negatives are possible, false positives are not.

hex_bit_board.cpp

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

/*
  Probabilistic algorithm to determine the End Game in the game Hex.

  False negatives are possible, false positives are not.
 */
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 {
    uint32_t* __restrict__ rows = _players[player].get();

    uint32_t row1 = rows[0];
    for (uint32_t row_n = 1; row_n < _size; ++row_n) {
      // find up-down connections
      uint32_t row2 = rows[row_n];
      uint32_t connections = (row1 & row2) | ((row1 & (row2 << 1)) >> 1);

      if (!connections)
        return false;

      uint32_t row2_result = 0;
      // find adjacent column bits connected with `connections`
      for (uint32_t col_n = 0; col_n < _size;) {
        if (connections & (1 << col_n)) {
          // find left bits
          uint32_t left_bits_count = __builtin_ctz(~(row2 >> col_n));

          // find right bits - 1
          uint32_t shift = 31 - col_n;
          uint32_t srow = row2 << shift;
          uint32_t right_bits_count = __builtin_clz(~srow);

          row2_result |= ((1 << (left_bits_count + right_bits_count - 1)) - 1) << (col_n - right_bits_count + 1);

          col_n += left_bits_count;
        } else {
          col_n += 1;
        }
      }
      row1 = row2_result;
    }
    return !!row1;
  }

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