m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Game Library
(game/all.hpp)

Overview

game/all.hpp includes the game-theory library. Public APIs use the m1une::game namespace.

Included Headers

Header Contents
game/nim.hpp Ordinary and misere Nim outcomes and winning moves.
game/nim_product.hpp 64-bit nimber multiplication, powers, inverses, and quotients.
game/grundy.hpp Linear-time Sprague-Grundy numbers for finite DAG games.
game/retrograde_analysis.hpp Win/lose/draw classification and strategy recovery for finite directed games, including cycles.
game/partisan_game.hpp Four outcome classes for finite short partisan games.
game/minimax.hpp Backward-induction values and optimal moves for scoring games on DAGs.
game/subtraction_game.hpp Grundy tables and multi-heap outcomes for subtraction games.
game/green_hackenbush.hpp Linear-time Grundy numbers for Green Hackenbush forests.
game/silver_dollar_game.hpp Linear-time Grundy numbers for coin-sliding positions.

Depends on

Verified with

Code

#ifndef M1UNE_GAME_ALL_HPP
#define M1UNE_GAME_ALL_HPP 1

#include "green_hackenbush.hpp"
#include "grundy.hpp"
#include "minimax.hpp"
#include "nim.hpp"
#include "nim_product.hpp"
#include "partisan_game.hpp"
#include "retrograde_analysis.hpp"
#include "silver_dollar_game.hpp"
#include "subtraction_game.hpp"

#endif  // M1UNE_GAME_ALL_HPP
#line 1 "game/all.hpp"



#line 1 "game/green_hackenbush.hpp"



#include <cassert>
#include <cstdint>
#include <vector>

namespace m1une {
namespace game {

// Every vertex represents one green edge. parent[v] == -1 attaches that edge
// to the ground; otherwise it attaches it above the edge parent[v].
inline uint64_t green_hackenbush_grundy(const std::vector<int>& parent) {
    const int size = int(parent.size());
    std::vector<std::vector<int>> children(size);
    std::vector<int> roots;
    for (int edge = 0; edge < size; ++edge) {
        assert(-1 <= parent[edge] && parent[edge] < size);
        assert(parent[edge] != edge);
        if (parent[edge] == -1) {
            roots.push_back(edge);
        } else {
            children[parent[edge]].push_back(edge);
        }
    }

    std::vector<int> order = roots;
    order.reserve(size);
    for (int position = 0; position < int(order.size()); ++position) {
        const int edge = order[position];
        for (int child : children[edge]) order.push_back(child);
    }
    assert(int(order.size()) == size);

    std::vector<uint64_t> branch(size);
    for (int position = size - 1; position >= 0; --position) {
        const int edge = order[position];
        uint64_t children_grundy = 0;
        for (int child : children[edge]) children_grundy ^= branch[child];
        branch[edge] = children_grundy + 1;
    }

    uint64_t result = 0;
    for (int root : roots) result ^= branch[root];
    return result;
}

inline bool green_hackenbush_first_player_wins(
    const std::vector<int>& parent
) {
    return green_hackenbush_grundy(parent) != 0;
}

}  // namespace game
}  // namespace m1une


#line 1 "game/grundy.hpp"



#line 5 "game/grundy.hpp"
#include <queue>
#line 7 "game/grundy.hpp"

namespace m1une {
namespace game {

// graph[v] contains the states reachable from v in one move.
// The graph must be a DAG.
template <typename Graph>
std::vector<int> grundy_numbers(const Graph& graph) {
    const int size = int(graph.size());
    std::vector<int> indegree(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        for (int next : graph[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
    }

    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (indegree[vertex] == 0) queue.push(vertex);
    }
    std::vector<int> order;
    order.reserve(size);
    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        order.push_back(vertex);
        for (int next : graph[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
    }
    assert(int(order.size()) == size);

    std::vector<int> grundy(size);
    std::vector<int> seen(size + 1, -1);
    for (int position = size - 1; position >= 0; --position) {
        const int vertex = order[position];
        for (int next : graph[vertex]) {
            const int value = grundy[next];
            if (value <= size) seen[value] = vertex;
        }
        while (grundy[vertex] <= size && seen[grundy[vertex]] == vertex) {
            grundy[vertex]++;
        }
    }
    return grundy;
}

}  // namespace game
}  // namespace m1une


#line 1 "game/minimax.hpp"



#line 6 "game/minimax.hpp"
#include <utility>
#line 8 "game/minimax.hpp"

namespace m1une {
namespace game {

template <typename T>
struct MinimaxResult {
    std::vector<T> value;
    std::vector<int> move;
};

template <typename T>
MinimaxResult<T> dag_minimax(
    const std::vector<std::vector<int>>& graph,
    const std::vector<T>& terminal_value,
    const std::vector<bool>& maximize
) {
    const int size = int(graph.size());
    assert(int(terminal_value.size()) == size);
    assert(int(maximize.size()) == size);

    std::vector<int> indegree(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        for (int next : graph[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
    }

    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (indegree[vertex] == 0) queue.push(vertex);
    }
    std::vector<int> order;
    order.reserve(size);
    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        order.push_back(vertex);
        for (int next : graph[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
    }
    assert(int(order.size()) == size);

    std::vector<T> value = terminal_value;
    std::vector<int> move(size, -1);
    for (int position = size - 1; position >= 0; --position) {
        const int vertex = order[position];
        if (graph[vertex].empty()) {
            value[vertex] = terminal_value[vertex];
            continue;
        }

        move[vertex] = graph[vertex][0];
        value[vertex] = value[move[vertex]];
        for (int next : graph[vertex]) {
            const bool improves = maximize[vertex]
                                      ? value[vertex] < value[next]
                                      : value[next] < value[vertex];
            if (improves) {
                value[vertex] = value[next];
                move[vertex] = next;
            }
        }
    }
    return {std::move(value), std::move(move)};
}

}  // namespace game
}  // namespace m1une


#line 1 "game/nim.hpp"



#include <iterator>
#include <optional>
#include <type_traits>
#line 8 "game/nim.hpp"

namespace m1une {
namespace game {

template <typename T>
struct NimMove {
    int heap;
    T new_size;
};

template <typename Iterator>
auto nim_sum(Iterator first, Iterator last) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    T result{};
    while (first != last) {
        result ^= *first;
        ++first;
    }
    return result;
}

template <typename Range>
auto nim_sum(const Range& heaps) {
    using std::begin;
    using std::end;
    return nim_sum(begin(heaps), end(heaps));
}

template <typename Range>
bool nim_first_player_wins(const Range& heaps) {
    return nim_sum(heaps) != 0;
}

template <typename Range>
auto nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    const T sum = nim_sum(heaps);
    if (sum == 0) return std::optional<NimMove<T>>{};
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

template <typename Range>
bool misere_nim_first_player_wins(const Range& heaps) {
    using std::begin;
    using std::end;

    auto first = begin(heaps);
    const auto last = end(heaps);
    bool odd_nonzero_heaps = false;
    bool has_large_heap = false;
    using T = typename std::iterator_traits<decltype(first)>::value_type;
    T sum{};
    for (; first != last; ++first) {
        sum ^= *first;
        if (*first != 0) {
            odd_nonzero_heaps = !odd_nonzero_heaps;
        }
        if (*first > 1) has_large_heap = true;
    }
    return has_large_heap ? sum != 0 : !odd_nonzero_heaps;
}

template <typename Range>
auto misere_nim_winning_move(const Range& heaps) {
    using std::begin;
    using std::end;
    using T = std::decay_t<decltype(*begin(heaps))>;

    T sum{};
    int ones = 0;
    int large_heaps = 0;
    int only_large_heap = -1;
    int index = 0;
    for (
        auto iterator = begin(heaps);
        iterator != end(heaps);
        ++iterator, ++index
    ) {
        sum ^= *iterator;
        if (*iterator == 1) ones++;
        if (*iterator > 1) {
            large_heaps++;
            only_large_heap = index;
        }
    }

    if (large_heaps == 0) {
        if (ones == 0 || ones % 2 == 1) return std::optional<NimMove<T>>{};
        index = 0;
        for (
            auto iterator = begin(heaps);
            iterator != end(heaps);
            ++iterator, ++index
        ) {
            if (*iterator == 1) return std::optional(NimMove<T>{index, T(0)});
        }
    }
    if (large_heaps == 1) {
        const T new_size = ones % 2 == 0 ? T(1) : T(0);
        return std::optional(NimMove<T>{only_large_heap, new_size});
    }
    if (sum == 0) return std::optional<NimMove<T>>{};

    index = 0;
    for (auto iterator = begin(heaps); iterator != end(heaps); ++iterator, ++index) {
        const T new_size = *iterator ^ sum;
        if (new_size < *iterator) return std::optional(NimMove<T>{index, new_size});
    }
    return std::optional<NimMove<T>>{};
}

}  // namespace game
}  // namespace m1une


#line 1 "game/nim_product.hpp"



#include <array>
#line 7 "game/nim_product.hpp"
#include <limits>

namespace m1une {
namespace game {
namespace internal {

inline uint64_t nim_product_small(uint64_t x, uint64_t y) {
    if (x < 2 || y < 2) return x * y;

    int shift = 1;
    const uint64_t largest = x | y;
    while ((uint64_t(1) << (shift * 2)) <= largest) shift *= 2;
    const uint64_t mask = (uint64_t(1) << shift) - 1;
    const uint64_t x_high = x >> shift;
    const uint64_t x_low = x & mask;
    const uint64_t y_high = y >> shift;
    const uint64_t y_low = y & mask;

    const uint64_t high_product = nim_product_small(x_high, y_high);
    const uint64_t low_product = nim_product_small(x_low, y_low);
    const uint64_t mixed_product =
        nim_product_small(x_high ^ x_low, y_high ^ y_low);
    return ((mixed_product ^ low_product) << shift) ^ low_product
           ^ nim_product_small(high_product, uint64_t(1) << (shift - 1));
}

inline const std::array<uint8_t, 1 << 16>& nim_product_8_table() {
    static const auto table = [] {
        std::array<uint8_t, 1 << 16> result{};
        for (int x = 0; x < 256; ++x) {
            for (int y = 0; y < 256; ++y) {
                result[(x << 8) | y] = uint8_t(nim_product_small(x, y));
            }
        }
        return result;
    }();
    return table;
}

inline uint64_t nim_product_8(uint64_t x, uint64_t y) {
    return nim_product_8_table()[(x << 8) | y];
}

template <int Bits>
inline uint64_t nim_product_fixed(uint64_t x, uint64_t y) {
    if constexpr (Bits == 8) {
        return nim_product_8(x, y);
    } else {
        constexpr int shift = Bits / 2;
        constexpr uint64_t mask = (uint64_t(1) << shift) - 1;
        const uint64_t x_high = x >> shift;
        const uint64_t x_low = x & mask;
        const uint64_t y_high = y >> shift;
        const uint64_t y_low = y & mask;

        const uint64_t high_product =
            nim_product_fixed<shift>(x_high, y_high);
        const uint64_t low_product = nim_product_fixed<shift>(x_low, y_low);
        const uint64_t mixed_product = nim_product_fixed<shift>(
            x_high ^ x_low,
            y_high ^ y_low
        );
        return ((mixed_product ^ low_product) << shift) ^ low_product
               ^ nim_product_fixed<shift>(
                   high_product,
                   uint64_t(1) << (shift - 1)
               );
    }
}

}  // namespace internal

inline uint64_t nim_product(uint64_t x, uint64_t y) {
    return internal::nim_product_fixed<64>(x, y);
}

inline uint64_t nim_power(uint64_t base, uint64_t exponent) {
    uint64_t result = 1;
    while (exponent != 0) {
        if (exponent & 1) result = nim_product(result, base);
        base = nim_product(base, base);
        exponent >>= 1;
    }
    return result;
}

inline uint64_t nim_inverse(uint64_t value) {
    assert(value != 0);
    return nim_power(value, std::numeric_limits<uint64_t>::max() - 1);
}

inline uint64_t nim_quotient(uint64_t numerator, uint64_t denominator) {
    assert(denominator != 0);
    return nim_product(numerator, nim_inverse(denominator));
}

}  // namespace game
}  // namespace m1une


#line 1 "game/partisan_game.hpp"



#line 7 "game/partisan_game.hpp"

namespace m1une {
namespace game {

enum class PartisanOutcome { Left, Right, Next, Previous };

inline std::vector<PartisanOutcome> partisan_outcomes(
    const std::vector<std::vector<int>>& left_moves,
    const std::vector<std::vector<int>>& right_moves
) {
    const int size = int(left_moves.size());
    assert(int(right_moves.size()) == size);

    std::vector<int> indegree(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        for (int next : left_moves[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
        for (int next : right_moves[vertex]) {
            assert(0 <= next && next < size);
            indegree[next]++;
        }
    }

    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (indegree[vertex] == 0) queue.push(vertex);
    }
    std::vector<int> order;
    order.reserve(size);
    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        order.push_back(vertex);
        for (int next : left_moves[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
        for (int next : right_moves[vertex]) {
            if (--indegree[next] == 0) queue.push(next);
        }
    }
    assert(int(order.size()) == size);

    std::vector<bool> left_wins_moving(size);
    std::vector<bool> left_wins_waiting(size);
    std::vector<PartisanOutcome> outcome(size);
    for (int position = size - 1; position >= 0; --position) {
        const int vertex = order[position];
        for (int next : left_moves[vertex]) {
            if (left_wins_waiting[next]) left_wins_moving[vertex] = true;
        }
        left_wins_waiting[vertex] = true;
        for (int next : right_moves[vertex]) {
            if (!left_wins_moving[next]) left_wins_waiting[vertex] = false;
        }

        if (left_wins_moving[vertex] && left_wins_waiting[vertex]) {
            outcome[vertex] = PartisanOutcome::Left;
        } else if (!left_wins_moving[vertex] && !left_wins_waiting[vertex]) {
            outcome[vertex] = PartisanOutcome::Right;
        } else if (left_wins_moving[vertex]) {
            outcome[vertex] = PartisanOutcome::Next;
        } else {
            outcome[vertex] = PartisanOutcome::Previous;
        }
    }
    return outcome;
}

}  // namespace game
}  // namespace m1une


#line 1 "game/retrograde_analysis.hpp"



#line 8 "game/retrograde_analysis.hpp"

namespace m1une {
namespace game {

enum class GameOutcome { Win, Lose, Draw };

struct RetrogradeResult {
    std::vector<GameOutcome> outcome;
    std::vector<int> distance;
    std::vector<int> move;
};

// graph[v] contains the states reachable from v in one move.
inline RetrogradeResult retrograde_analysis(
    const std::vector<std::vector<int>>& graph
) {
    const int size = int(graph.size());
    std::vector<std::vector<int>> reverse_graph(size);
    std::vector<int> remaining(size);
    for (int vertex = 0; vertex < size; ++vertex) {
        remaining[vertex] = int(graph[vertex].size());
        for (int next : graph[vertex]) {
            assert(0 <= next && next < size);
            reverse_graph[next].push_back(vertex);
        }
    }

    std::vector<GameOutcome> outcome(size, GameOutcome::Draw);
    std::vector<int> distance(size, -1);
    std::vector<int> move(size, -1);
    std::vector<int> longest_win_successor(size);
    std::vector<int> longest_win_move(size, -1);
    std::vector<bool> decided(size);
    std::queue<int> queue;
    for (int vertex = 0; vertex < size; ++vertex) {
        if (remaining[vertex] == 0) {
            outcome[vertex] = GameOutcome::Lose;
            distance[vertex] = 0;
            decided[vertex] = true;
            queue.push(vertex);
        }
    }

    while (!queue.empty()) {
        const int vertex = queue.front();
        queue.pop();
        for (int previous : reverse_graph[vertex]) {
            if (decided[previous]) continue;
            if (outcome[vertex] == GameOutcome::Lose) {
                outcome[previous] = GameOutcome::Win;
                distance[previous] = distance[vertex] + 1;
                move[previous] = vertex;
                decided[previous] = true;
                queue.push(previous);
            } else {
                if (longest_win_move[previous] == -1
                    || longest_win_successor[previous] < distance[vertex]) {
                    longest_win_successor[previous] = distance[vertex];
                    longest_win_move[previous] = vertex;
                }
                if (--remaining[previous] == 0) {
                    outcome[previous] = GameOutcome::Lose;
                    distance[previous] = longest_win_successor[previous] + 1;
                    move[previous] = longest_win_move[previous];
                    decided[previous] = true;
                    queue.push(previous);
                }
            }
        }
    }
    for (int vertex = 0; vertex < size; ++vertex) {
        if (outcome[vertex] != GameOutcome::Draw) continue;
        for (int next : graph[vertex]) {
            if (outcome[next] == GameOutcome::Draw) {
                move[vertex] = next;
                break;
            }
        }
    }
    return {std::move(outcome), std::move(distance), std::move(move)};
}

}  // namespace game
}  // namespace m1une


#line 1 "game/silver_dollar_game.hpp"



#line 7 "game/silver_dollar_game.hpp"

namespace m1une {
namespace game {

template <typename T>
T silver_dollar_grundy(const std::vector<T>& coins) {
    for (int index = 0; index < int(coins.size()); ++index) {
        if constexpr (std::is_signed_v<T>) assert(coins[index] >= 0);
        if (index != 0) assert(coins[index - 1] < coins[index]);
    }

    T result{};
    int index = int(coins.size()) % 2;
    if (index == 1) result ^= coins[0];
    for (; index + 1 < int(coins.size()); index += 2) {
        result ^= coins[index + 1] - coins[index] - 1;
    }
    return result;
}

template <typename T>
bool silver_dollar_first_player_wins(const std::vector<T>& coins) {
    return silver_dollar_grundy(coins) != 0;
}

}  // namespace game
}  // namespace m1une


#line 1 "game/subtraction_game.hpp"



#include <algorithm>
#line 7 "game/subtraction_game.hpp"

namespace m1une {
namespace game {

inline std::vector<int> subtraction_game_grundy(
    int max_heap,
    const std::vector<int>& moves
) {
    assert(max_heap >= 0);
    for (int move : moves) assert(move > 0);

    std::vector<int> grundy(max_heap + 1);
    std::vector<int> seen(moves.size() + 1, -1);
    for (int heap = 1; heap <= max_heap; ++heap) {
        for (int move : moves) {
            if (move > heap) continue;
            const int value = grundy[heap - move];
            if (value < int(seen.size())) seen[value] = heap;
        }
        while (
            grundy[heap] < int(seen.size())
            && seen[grundy[heap]] == heap
        ) {
            grundy[heap]++;
        }
    }
    return grundy;
}

inline int subtraction_game_nim_sum(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    int max_heap = 0;
    for (int heap : heaps) {
        assert(heap >= 0);
        max_heap = std::max(max_heap, heap);
    }
    const std::vector<int> grundy = subtraction_game_grundy(max_heap, moves);
    int result = 0;
    for (int heap : heaps) result ^= grundy[heap];
    return result;
}

inline bool subtraction_game_first_player_wins(
    const std::vector<int>& heaps,
    const std::vector<int>& moves
) {
    return subtraction_game_nim_sum(heaps, moves) != 0;
}

}  // namespace game
}  // namespace m1une


#line 13 "game/all.hpp"
Back to top page