Split game solver

splitgame.cpp

/**
 * Two-Player Split Game Solver
 *
 * This C++ program solves a two-player game played with two hands
 *
 * - Two players take turns, starting with two fingers out on each hand
 * - Each turn, a player can add the number of fingers on one of their hands to
 *   that of their opponent (addition wraps around after 5)
 * - If the numbers on a hand become 5, it resets to 0
 * - If one hand is empty and the other has an even number, it can be split
 *   equally into two hands
 * - A player loses when both hands are empty
 * - The objective is to determine the winnability status of each state
 *   (winning, losing, or unknown) and to find the best move to make from a
 *   given state.
 *
 * The program employs a dynamic programming approach to solve the game and
 * provides an interactive interface for users to input game states and receive
 * advice on the best move.
 *
 * @author Raziman T V
 * @date 2023-09-25
 */

#include <cassert>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>

// Enumeration representing the winnability status of a game state.
enum class Winnability { winning, losing, unknown };

// Define a State as a tuple of four integers.
using State = std::tuple<int, int, int, int>;

// Define StateVector as a vector of State tuples.
using StateVector = std::vector<State>;

// Define StateMap as a map that maps State tuples to their winnability status.
using StateMap = std::map<State, Winnability>;

/**
 * Generate all possible game states.
 *
 * This function generates a vector of all possible game states based on the
 * game's rules. The states are represented as tuples (p1_1, p1_2, p2_1, p2_2),
 * where p1_1, p1_2, p2_1, and p2_2 are integers representing the number of
 * fingers on hands of the players
 *
 * @return A vector containing all possible game states.
 */
StateVector get_all_states() {
  StateVector ret;
  for (int p1_1 = 0; p1_1 < 5; ++p1_1)
    for (int p1_2 = p1_1; p1_2 < 5; ++p1_2)
      for (int p2_1 = 0; p2_1 < 5; ++p2_1)
        for (int p2_2 = p2_1; p2_2 < 5; ++p2_2)
          if (p2_2) ret.push_back({p1_1, p1_2, p2_1, p2_2});
  return ret;
}

/**
 * Populate the cache with terminal states.
 *
 * This function populates the given cache (a map) with terminal states of the
 * game. A terminal state is a state in which player 1 (p1) has lost, which is
 * indicated by p1_2 being zero. When a terminal state is found, it is marked as
 * 'losing' in the cache.
 *
 * @param allStates A vector containing all possible game states.
 * @param cache     A map to store the winnability status of game states.
 */
void populate_terminal_states(const StateVector& allStates, StateMap& cache) {
  for (const State& state : allStates) {
    auto [p1_1, p1_2, p2_1, p2_2] = state;
    if (!p1_2) cache[state] = Winnability::losing;
  }
}

/**
 * Generate possible states resulting from splitting player 1's items.
 *
 * This function generates a vector of possible game states that can be reached
 * from the given state by splitting player 1's items if the following
 * conditions are met:
 *   - Player 1's first item count (p1_1) is zero.
 *   - Player 1's total item count (p1_2) is even.
 *
 * @param state The current game state as a tuple (p1_1, p1_2, p2_1, p2_2).
 * @return A vector of states, including the original state and split states (if
 * applicable).
 */
StateVector get_split_states(const State& state) {
  StateVector ret{state};
  auto [p1_1, p1_2, p2_1, p2_2] = state;
  if (p1_1 == 0 and p1_2 % 2 == 0)
    ret.push_back({p1_2 / 2, p1_2 / 2, p2_1, p2_2});
  return ret;
}

/**
 * Calculate the next game state based on item transfers.
 *
 * This function calculates the next game state based on the transfer of items
 * between player 1 (p1) and player 2 (p2) according to the game's rules.
 *
 * @param p1_1 The number of items held by player 1 in the first slot.
 * @param p1_2 The number of items held by player 1 in the second slot.
 * @param p2_1 The number of items held by player 2 in the first slot.
 * @param p2_2 The number of items held by player 2 in the second slot.
 * @return The next game state as a tuple (p1_1, p1_2, p2_1, p2_2).
 */
State get_next_state(int p1_1, int p1_2, int p2_1, int p2_2) {
  // Calculate the effective number of items after modulo 5.
  int n1_1 = p2_1 % 5, n1_2 = p2_2 % 5;

  // Ensure n1_1 is smaller than or equal to n1_2.
  if (n1_1 > n1_2) std::swap(n1_1, n1_2);

  // Create and return the next game state.
  return {n1_1, n1_2, p1_1, p1_2};
}

/**
 * Generate possible next game states from the given state.
 *
 * This function generates a vector of possible game states that can be reached
 * from the given state by considering various split states and item transfers
 * between players.
 *
 * @param state The current game state as a tuple (p1_1, p1_2, p2_1, p2_2).
 * @return A vector of possible next game states.
 */
StateVector get_next_states(const State& state) {
  StateVector ret;

  // Consider splitting if possible
  for (auto startState : get_split_states(state)) {
    auto [p1_1, p1_2, p2_1, p2_2] = startState;

    // Consider transfers from distinct nonzero hands
    std::vector<int> add{p1_2};
    if (p1_1 and p1_1 != p1_2) add.push_back(p1_1);

    // Consider all valid item transfers
    for (int x : add) {
      if (p2_1) ret.push_back(get_next_state(p1_1, p1_2, p2_1 + x, p2_2));
      ret.push_back(get_next_state(p1_1, p1_2, p2_1, p2_2 + x));
    }
  }

  return ret;
}

/**
 * Update the winnability status of game states in the cache.
 *
 * This function updates the winnability status of game states in the provided
 * cache map. It iterates through all possible game states and checks whether
 * they are already in the cache. If a state is not in the cache, it checks
 * whether all possible next states are losing for the current player. If they
 * are, the current state is marked as 'winning'; otherwise, it's marked as
 * 'losing'. The function continues to iterate until no more updates can be made
 * to the cache.
 *
 * @param allStates A vector containing all possible game states.
 * @param cache     A map to store the winnability status of game states.
 * @return True if the cache was updated, indicating that further updates may be
 * possible.
 */
bool update_winnability(const StateVector& allStates, StateMap& cache) {
  int size_before = cache.size();
  auto cache_copy = cache;

  // Iterate through all possible game states.
  for (const auto& state : allStates) {
    if (cache.count(state)) continue;
    bool all_winning{true};

    // Check all possible next states.
    for (auto next : get_next_states(state)) {
      if (cache_copy.count(next)) {
        if (cache_copy[next] == Winnability::losing) {
          // If the oppenent can be put to a losing state, player wins
          all_winning = false;
          cache[state] = Winnability::winning;
          break;
        } else if (cache_copy[next] == Winnability::unknown) {
          all_winning = false;
        }
      } else {
        all_winning = false;
      }
    }

    // Mark the state as 'losing' if all next states are 'winning' for the
    // opponent.
    if (all_winning) cache[state] = Winnability::losing;
  }

  // Return true if the cache was updated during this iteration.
  return cache.size() > size_before;
}

/**
 * Determine and display the best move from a given game state.
 *
 * This function calculates and displays the best move to make from the given
 * game state. It considers the next possible states and chooses the one that
 * leads to a 'losing' state for the opponent if possible. Otherwise it chooses
 * one that doesn't make the opponent win if possible, or any other state. It
 * then prints whether the move is 'winning', 'losing', or 'unknown' and the
 * resulting game state.
 *
 * @param state The current game state as a tuple (p1_1, p1_2, p2_1, p2_2).
 * @param cache A map storing the winnability status of game states.
 */
void show_best_move(const State& state, StateMap& cache) {
  State ret{0, 0, 0, 0};

  // Iterate through possible next states.
  for (auto next : get_next_states(state)) {
    // Initialise with the first state
    if (!std::get<3>(ret)) ret = next;

    if (cache.count(next) and cache[next] == Winnability::losing) {
      // Choose a move that leads to a 'losing' state for the opponent if
      // available.
      ret = next;
      break;
    } else if (cache.count(ret) and cache[ret] == Winnability::winning) {
      // If current choice will make opponent win, choose another move
      ret = next;
    }
  }

  // Display the result of the best move.
  if (cache.count(ret)) {
    if (cache[ret] == Winnability::losing) {
      std::cout << "Winning ";
    } else if (cache[ret] == Winnability::winning) {
      std::cout << "Losing ";
    } else {
      std::cout << "Unknown ";
    }
  } else {
    std::cout << "Unknown ";
  }

  // Print the resulting game state.
  auto [p1_1, p1_2, p2_1, p2_2] = ret;
  std::cout << "(" << p1_1 << "," << p1_2 << "),(" << p2_1 << "," << p2_2
            << ")\n";
}

/**
 * Main function for the two-player game solver.
 */
int main() {
  // Generate all possible game states.
  auto allStates = get_all_states();

  // Initialize the cache to store the winnability status of game states.
  StateMap cache;

  // Populate the cache with terminal states.
  populate_terminal_states(allStates, cache);

  // Continuously update the winnability status until no more updates can be
  // made.
  while (update_winnability(allStates, cache)) {
  }

  // Print the number of solved and unsolved game states.
  std::cout << "Solved: " << cache.size()
            << " , Unsolved: " << allStates.size() - cache.size() << "\n";

  // Enter an infinite loop to interactively provide and display game moves.
  while (1) {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;

    // Show the best move based on the provided game state.
    show_best_move({a, b, c, d}, cache);
  }

  return 0;
}