Chopsticks game with leftovers rule solver

chopsticks-leftovers.cpp

/**
 * Chopsticks game with leftovers rule solver.
 * @author Mygod
 */

// Here's a set of rules you can customize:

#define RULE_SPLITS
//#define RULE_SUICIDAL
//#define RULE_TRANSFER
#define RULE_MOD 5

// Ok that's it. Don't make further modifications unless you know what you're doing.

#include <algorithm>
#include <cassert>
#include <iostream>

using namespace std;

#ifdef RULE_SUICIDAL
  #define POSITION_FINAL POSITION_WINNING
#else
  #define POSITION_FINAL POSITION_LOSING
#endif

constexpr int getMaxMoves(int ax, int ay) {
#ifdef RULE_TRANSFER
  #undef RULE_SPLITS  // splits are included in transfer rules
  int a = ax + ay;
  if (a >= RULE_MOD) a = RULE_MOD + RULE_MOD - 2 - a;
  return (a >> 1) + 4;
#else
  return 4;
#endif
}

typedef uniform_int_distribution<mt19937::result_type> RandomRange;
mt19937 range;

enum Position {
  POSITION_UNKNOWN, POSITION_WINNING, POSITION_LOSING
} status[RULE_MOD][RULE_MOD][RULE_MOD][RULE_MOD];
int steps[RULE_MOD][RULE_MOD][RULE_MOD][RULE_MOD];

bool makeMove(int &ax, int &ay, int &bx, int &by, int move) {
  switch (move) {
    case 0:
#ifdef RULE_SPLITS
      if (ay || ax & 1) return true;
      ay = ax >>= 1;
      break;
#else
      return true;
#endif
#define TOUCH(a, b)               \
      if (!(a && b)) return true; \
      b = (b + a) % RULE_MOD;     \
      if (bx < by) swap(bx, by);  \
      break
    case 1: TOUCH(ax, bx);
    case 2: TOUCH(ax, by);
    case 3: TOUCH(ay, bx);
    case 4: TOUCH(ay, by);
#undef TOUCH
    default:
#ifdef RULE_TRANSFER
      if (move < 0) return true;
      int y = move - 5, a = ax + ay;
      if (a >= RULE_MOD) y += a - RULE_MOD + 1;
      if (y >= ay) ++y;
      if (y + y > a) return true;
      ax = a - (ay = y);
      break;
#else
      return true;
#endif
  }
  swap(ax, bx);
  swap(ay, by);
  return false;
}

inline void updateStatus(Position &flag, int ax, int ay, int bx, int by, int move, int &nowSteps) {
  if (makeMove(ax, ay, bx, by, move)) return;
  switch (status[ax][ay][bx][by]) {
    case POSITION_UNKNOWN:
      flag = static_cast<Position>(flag & ~POSITION_LOSING);
      break;
    case POSITION_WINNING:
      if (flag == POSITION_LOSING) nowSteps = max(nowSteps, steps[ax][ay][bx][by]);
      break;
    case POSITION_LOSING: // weakness found
      if (flag != POSITION_WINNING) {
        flag = POSITION_WINNING;
        nowSteps = steps[ax][ay][bx][by];
      } else nowSteps = min(nowSteps, steps[ax][ay][bx][by]);
      break;
    default: assert(false);
  }
}

inline bool isAcceptable(int ax, int ay, int bx, int by, int move, Position nowStatus, int nowSteps) {
  if (makeMove(ax, ay, bx, by, move)) return false;
  auto newStatus = status[ax][ay][bx][by];
  return newStatus == POSITION_LOSING && nowSteps == steps[ax][ay][bx][by] + 1 || !newStatus && !nowStatus;
}

inline bool userMovesFirst(int status) {
  switch (status) {
    case POSITION_WINNING: return false;
    case POSITION_LOSING:  return true;
    default:               return static_cast<bool>(RandomRange(0, 1)(range));  // whatever
  }
}

int main() {
  for (int i = 1; i < RULE_MOD; ++i) for (int j = 0; j <= i; ++j) status[0][0][i][j] = POSITION_FINAL;
  bool updated = true;
  while (updated) {
    updated = false;
    for (int ax = 1; ax < RULE_MOD; ++ax) for (int ay = 0; ay <= ax; ++ay)
      for (int bx = 1; bx < RULE_MOD; ++bx) for (int by = 0; by <= bx; ++by) if (!status[ax][ay][bx][by]) {
        auto flag = POSITION_LOSING;
        int nowSteps = -1;
        for (int move = 0, maxMoves = getMaxMoves(ax, ay); move <= maxMoves; ++move)
          updateStatus(flag, ax, ay, bx, by, move, nowSteps);
        if (flag) {
          status[ax][ay][bx][by] = flag;
          steps[ax][ay][bx][by] = nowSteps + 1;
          updated = true;
        }
      }
  }

  // Print solution and debug information to cerr
  cerr << "Positions to find:" << endl;
  for (int bx = 1; bx < RULE_MOD; ++bx) for (int by = 0; by <= bx; ++by)
    for (int ax = 1; ax < RULE_MOD; ++ax) for (int ay = 0; ay <= ax; ++ay)
      if (status[ax][ay][bx][by] == 2 && steps[ax][ay][bx][by] > 1)
        cerr << bx << by << ' ' << ax << ay << " (win within " << steps[ax][ay][bx][by] << " steps)" << endl;
  cerr << endl;

  cerr << "Positions to avoid except obvious ones:" << endl;
  for (int bx = 1; bx < RULE_MOD; ++bx) for (int by = 0; by <= bx; ++by)
    for (int ax = 1; ax < RULE_MOD; ++ax) for (int ay = 0; ay <= ax; ++ay)
      if (status[ax][ay][bx][by] == 1 && steps[ax][ay][bx][by] > 1)
        cerr << bx << by << ' ' << ax << ay << " (lose within " << steps[ax][ay][bx][by] << " steps)" << endl;
  cerr << endl;

  for (int ax = 1; ax < RULE_MOD; ++ax) for (int ay = 0; ay <= ax; ++ay) {
    for (int bx = 1; bx < RULE_MOD; ++bx) for (int by = 0; by <= bx; ++by) cerr << status[ax][ay][bx][by];
    cerr << endl;
  }

  // Kindly offer a game to the user
  range.seed(random_device()());
  int ax = 1, ay = 1, bx = 1, by = 1, move = -1, maxMoves;
  if (userMovesFirst(status[ax][ay][bx][by])) while (makeMove(ax, ay, bx, by, move)) {
    cout << ax << ay << ' ' << bx << by << ' ';
    cin >> move;
  }
  vector<int> moves(static_cast<size_t>(getMaxMoves(RULE_MOD - 1, 0)));
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wfor-loop-analysis"
  while (ax && bx) {
    auto nowStatus = status[ax][ay][bx][by];
    int nowSteps = steps[ax][ay][bx][by];
    assert(nowStatus != POSITION_LOSING); // there's no way I'm losing the game! no!
    for (move = 0, maxMoves = getMaxMoves(ax, ay), moves.clear(); move <= maxMoves; ++move)
      if (isAcceptable(ax, ay, bx, by, move, nowStatus, nowSteps)) moves.push_back(move);
    assert(!moves.empty());               // I have to have a move!
    // pick a random move in order to prevent getting into a loop
    cout << bx << by << ' ' << ax << ay << ' ' << (move = moves[RandomRange(0, moves.size() - 1)(range)]) << endl;
    makeMove(ax, ay, bx, by, move);
    if (!(ax && bx)) {
      cout << ax << ay << ' ' << bx << by << " YOU LOSE" << endl;
      return 0;
    }
    move = -1;
    while (makeMove(ax, ay, bx, by, move)) {
      cout << ax << ay << ' ' << bx << by << ' ';
      cin >> move;
    }
  }
#pragma clang diagnostic pop
  cout << bx << by << ' ' << ax << ay << " YOU LOSE" << endl; // you don't have a single chance :/
  return 0;
}