Position.hpp

/*
 * This file is part of Connect4 Game Solver <http://connect4.gamesolver.org>
 * Copyright (C) 2017-2019 Pascal Pons <contact@gamesolver.org>
 *
 * Connect4 Game Solver is free software: you can redistribute it and/or
 * modify it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Connect4 Game Solver is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Connect4 Game Solver. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef POSITION_HPP
#define POSITION_HPP
 
#include <cassert>
#include <cstdint>
#include <string>
 
namespace GameSolver {
namespace Connect4 {

 
class Position {
public:
  static constexpr int WIDTH = 7;  // width of the board
  static constexpr int HEIGHT = 6; // height of the board
 
#ifdef __GNUC__
  // Board size is 64bits or 128 bits depending on WIDTH and HEIGHT
  using position_t = typename std::conditional<WIDTH *(HEIGHT + 1) <= 64,
                                               uint64_t, __int128>::type;
#else
  // __int128 is a g++ non portable type. Use the following line limited to
  // 64bits board for C++ compatibility
  using position_t = uint64_t;
#endif
 
  static constexpr int MIN_SCORE = -(WIDTH * HEIGHT) / 2 + 3;
  static constexpr int MAX_SCORE = (WIDTH * HEIGHT + 1) / 2 - 3;
 
  static_assert(WIDTH < 10, "Board's width must be less than 10");
  static_assert(WIDTH * (HEIGHT + 1) <= sizeof(position_t) * 8,
                "Board does not fit into position_t bitmask");

  void play(position_t move) {
    current_position ^= mask;
    mask |= move;
    moves++;
  }
 
  /*
   * Plays a sequence of successive played columns, mainly used to initilize a
   * board.
   * @param seq: a sequence of digits corresponding to the 1-based index of the
   * column played.
   *
   * @return number of played moves. Processing will stop at first invalid move
   * that can be:
   *           - invalid character (non digit, or digit >= WIDTH)
   *           - playing a colum the is already full
   *           - playing a column that makes an alignment (we only solve non).
   *         Caller can check if the move sequence was valid by comparing the
   * number of processed moves to the length of the sequence.
   */
  unsigned int play(const std::string &seq) {
    for (unsigned int i = 0; i < seq.size(); i++) {
      int col = seq[i] - '1';
      if (col < 0 || col >= Position::WIDTH || !canPlay(col) ||
          isWinningMove(col))
        return i; // invalid move
      playCol(col);
    }
    return seq.size();
  }

  bool canWinNext() const { return winning_position() & possible(); }

  int nbMoves() const { return moves; }

  position_t key() const { return current_position + mask; }

  uint64_t key3() const {
    uint64_t key_forward = 0;
    for (int i = 0; i < Position::WIDTH; i++)
      partialKey3(key_forward, i); // compute key in increasing order of columns
 
    uint64_t key_reverse = 0;
    for (int i = Position::WIDTH; i--;)
      partialKey3(key_reverse, i); // compute key in decreasing order of columns
 
    return key_forward < key_reverse
               ? key_forward / 3
               : key_reverse / 3; // take the smallest key and divide per 3 as
                                  // the last base3 digit is always 0
  }

  position_t possibleNonLosingMoves() const {
    assert(!canWinNext());
    position_t possible_mask = possible();
    position_t opponent_win = opponent_winning_position();
    position_t forced_moves = possible_mask & opponent_win;
    if (forced_moves) {
      if (forced_moves &
          (forced_moves - 1)) // check if there is more than one forced move
        return 0; // the opponnent has two winning moves and you cannot stop him
      else
        possible_mask = forced_moves; // enforce to play the single forced move
    }
    return possible_mask &
           ~(opponent_win >> 1); // avoid to play below an opponent winning spot
  }

  int moveScore(position_t move) const {
    return popcount(compute_winning_position(current_position | move, mask));
  }

  Position() : current_position{0}, mask{0}, moves{0} {}

  bool canPlay(int col) const { return (mask & top_mask_col(col)) == 0; }

  void playCol(int col) {
    play((mask + bottom_mask_col(col)) & column_mask(col));
  }

  bool isWinningMove(int col) const {
    return winning_position() & possible() & column_mask(col);
  }
 
private:
  position_t current_position; // bitmap of the current_player stones
  position_t mask;             // bitmap of all the already palyed spots
  unsigned int moves; // number of moves played since the beinning of the game.

  void partialKey3(uint64_t &key, int col) const {
    for (position_t pos = UINT64_C(1) << (col * (Position::HEIGHT + 1));
         pos & mask; pos <<= 1) {
      key *= 3;
      if (pos & current_position)
        key += 1;
      else
        key += 2;
    }
    key *= 3;
  }

  position_t winning_position() const {
    return compute_winning_position(current_position, mask);
  }

  position_t opponent_winning_position() const {
    return compute_winning_position(current_position ^ mask, mask);
  }

  position_t possible() const { return (mask + bottom_mask) & board_mask; }

  static unsigned int popcount(position_t m) {
    unsigned int c = 0;
    for (c = 0; m; c++)
      m &= m - 1;
    return c;
  }

  static position_t compute_winning_position(position_t position,
                                             position_t mask) {
    // vertical;
    position_t r = (position << 1) & (position << 2) & (position << 3);
 
    // horizontal
    position_t p = (position << (HEIGHT + 1)) & (position << 2 * (HEIGHT + 1));
    r |= p & (position << 3 * (HEIGHT + 1));
    r |= p & (position >> (HEIGHT + 1));
    p = (position >> (HEIGHT + 1)) & (position >> 2 * (HEIGHT + 1));
    r |= p & (position << (HEIGHT + 1));
    r |= p & (position >> 3 * (HEIGHT + 1));
 
    // diagonal 1
    p = (position << HEIGHT) & (position << 2 * HEIGHT);
    r |= p & (position << 3 * HEIGHT);
    r |= p & (position >> HEIGHT);
    p = (position >> HEIGHT) & (position >> 2 * HEIGHT);
    r |= p & (position << HEIGHT);
    r |= p & (position >> 3 * HEIGHT);
 
    // diagonal 2
    p = (position << (HEIGHT + 2)) & (position << 2 * (HEIGHT + 2));
    r |= p & (position << 3 * (HEIGHT + 2));
    r |= p & (position >> (HEIGHT + 2));
    p = (position >> (HEIGHT + 2)) & (position >> 2 * (HEIGHT + 2));
    r |= p & (position << (HEIGHT + 2));
    r |= p & (position >> 3 * (HEIGHT + 2));
 
    return r & (board_mask ^ mask);
  }
 
  // Static bitmaps
  template <int width, int height> struct bottom {
    static constexpr position_t mask =
        bottom<width - 1, height>::mask | position_t(1)
                                              << (width - 1) * (height + 1);
  };
  template <int height> struct bottom<0, height> {
    static constexpr position_t mask = 0;
  };
 
  static constexpr position_t bottom_mask = bottom<WIDTH, HEIGHT>::mask;
  static constexpr position_t board_mask = bottom_mask * ((1LL << HEIGHT) - 1);
 
  // return a bitmask containg a single 1 corresponding to the top cel of a
  // given column
  static constexpr position_t top_mask_col(int col) {
    return UINT64_C(1) << ((HEIGHT - 1) + col * (HEIGHT + 1));
  }
 
  // return a bitmask containg a single 1 corresponding to the bottom cell of a
  // given column
  static constexpr position_t bottom_mask_col(int col) {
    return UINT64_C(1) << col * (HEIGHT + 1);
  }
 
public:
  // return a bitmask 1 on all the cells of a given column
  static constexpr position_t column_mask(int col) {
    return ((UINT64_C(1) << HEIGHT) - 1) << col * (HEIGHT + 1);
  }
};
 
} // namespace Connect4
} // namespace GameSolver
#endif