Game Retrograde Analysis
(game/retrograde_analysis.hpp)

• View this file on GitHub
• Last update: 2026-08-24 02:13:00+09:00
• Include: #include "game/retrograde_analysis.hpp"

Overview

Classifies every state of a finite directed normal-play game as winning, losing, or drawing. Unlike Grundy-number computation, the directed graph may contain cycles. An edge v -> u is a legal move, and a state with no legal move is losing.

A state is winning if it has a move to a losing state, and losing if every move goes to a winning state. States that cannot be resolved by these rules are draws. The result also records an optimal move and game length for resolved states: a winner finishes as soon as possible, while a loser delays defeat as long as possible. For a draw, the returned move preserves the draw.

Types

All types are in namespace m1une::game.

GameOutcome has the values Win, Lose, and Draw.

RetrogradeResult stores:

Member	Description
std::vector<GameOutcome> outcome	Classification of each state.
std::vector<int> distance	Moves until termination under optimal play, or -1 for a draw.
std::vector<int> move	Chosen successor, or -1 for a terminal state.

Functions

Function signature	Description	Complexity
RetrogradeResult retrograde_analysis(const std::vector<std::vector<int>>& graph)	Analyzes all states; graph[v] lists states reachable from v.	O(V + E) time and space

States and edges are zero-based. Every endpoint must be in [0, V), which is asserted in debug builds. Self-loops and parallel edges are allowed.

Example

#include "game/retrograde_analysis.hpp"
#include <iostream>
#include <vector>

int main() {
    using m1une::game::GameOutcome;

    std::vector<std::vector<int>> moves(4);
    moves[0] = {1};
    moves[1] = {0};
    moves[2] = {3};

    auto result = m1une::game::retrograde_analysis(moves);
    std::cout << (result.outcome[0] == GameOutcome::Draw) << '\n';
    std::cout << (result.outcome[2] == GameOutcome::Win) << '\n';
    std::cout << result.distance[2] << '\n';  // 1
    std::cout << result.move[2] << '\n';      // 3
}

Required by

• Game Library (game/all.hpp)

Verified with

• verify/game/game_algorithms.test.cpp

Code

#ifndef M1UNE_GAME_RETROGRADE_ANALYSIS_HPP
#define M1UNE_GAME_RETROGRADE_ANALYSIS_HPP 1

#include <cassert>
#include <queue>
#include <utility>
#include <vector>

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

#endif  // M1UNE_GAME_RETROGRADE_ANALYSIS_HPP

#line 1 "game/retrograde_analysis.hpp"



#include <cassert>
#include <queue>
#include <utility>
#include <vector>

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

Back to top page