Partisan Game Outcomes
(game/partisan_game.hpp)
- View this file on GitHub
- Last update: 2026-08-24 02:13:00+09:00
- Include:
#include "game/partisan_game.hpp"
Overview
Classifies every position of a finite short partisan game. Left and Right may have different legal moves, and the player with no legal move loses. The union of both move graphs must be acyclic, so every play terminates.
Unlike an ordinary win/lose result, a partisan position belongs to one of four outcome classes because the identity of the starting player matters.
Types
PartisanOutcome has four values:
| Value | Meaning |
|---|---|
Left |
Left wins regardless of who starts. |
Right |
Right wins regardless of who starts. |
Next |
The next player wins. |
Previous |
The second player wins. |
Functions
All APIs are in namespace m1une::game.
| Function signature | Description | Complexity |
|---|---|---|
std::vector<PartisanOutcome> partisan_outcomes(const std::vector<std::vector<int>>& left_moves, const std::vector<std::vector<int>>& right_moves) |
Returns the outcome class of every state. |
O(V + E_left + E_right) time, O(V) extra space |
left_moves[v] and right_moves[v] list the states available to the respective
player from state v. Both arrays must have the same size, all endpoints must
be zero-based indices in [0, V), and their combined graph must be acyclic.
These conditions are asserted in debug builds.
Example
#include "game/partisan_game.hpp"
#include <iostream>
#include <vector>
int main() {
using m1une::game::PartisanOutcome;
std::vector<std::vector<int>> left(2), right(2);
left[0].push_back(1);
auto outcome = m1une::game::partisan_outcomes(left, right);
std::cout << (outcome[0] == PartisanOutcome::Left) << '\n';
std::cout << (outcome[1] == PartisanOutcome::Previous) << '\n';
}
Required by
Verified with
Code
#ifndef M1UNE_GAME_PARTISAN_GAME_HPP
#define M1UNE_GAME_PARTISAN_GAME_HPP 1
#include <cassert>
#include <queue>
#include <vector>
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
#endif // M1UNE_GAME_PARTISAN_GAME_HPP#line 1 "game/partisan_game.hpp"
#include <cassert>
#include <queue>
#include <vector>
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