DAG Minimax
(game/minimax.hpp)
- View this file on GitHub
- Last update: 2026-08-24 02:13:00+09:00
- Include:
#include "game/minimax.hpp"
Overview
Evaluates a finite scoring game represented by a directed acyclic graph. Each nonterminal state is controlled by either a maximizing or minimizing player. Terminal states carry values, and backward induction determines both the value and one optimal move for every state.
This representation supports transpositions directly: several states may lead to the same successor, which is evaluated only once.
Types
MinimaxResult<T> stores:
| Member | Description |
|---|---|
std::vector<T> value |
Minimax value of every state. |
std::vector<int> move |
Chosen zero-based successor, or -1 at a terminal state. |
Functions
All APIs are in namespace m1une::game. Values must be copyable and comparable
with <.
| Function signature | Description | Complexity |
|---|---|---|
template<class T>MinimaxResult<T> dag_minimax(const std::vector<std::vector<int>>& graph, const std::vector<T>& terminal_value, const std::vector<bool>& maximize)
|
Evaluates every state and recovers one optimal move. |
O(V + E) time, O(V) extra space |
All three arrays must have size V. terminal_value[v] is used only when
graph[v] is empty. At a nonterminal state, maximize[v] selects maximum or
minimum play. On equal values, the first optimal successor listed in graph[v]
is returned. Endpoints must lie in [0, V), and the graph must be acyclic;
these conditions are asserted in debug builds.
Example
#include "game/minimax.hpp"
#include <iostream>
#include <vector>
int main() {
std::vector<std::vector<int>> graph(5);
graph[0] = {1, 2};
graph[1] = {3, 4};
graph[2] = {3, 4};
std::vector<int> terminal_value = {0, 0, 0, -4, 7};
std::vector<bool> maximize = {true, false, false, false, false};
auto result = m1une::game::dag_minimax(
graph,
terminal_value,
maximize
);
std::cout << result.value[0] << '\n';
std::cout << result.move[0] << '\n';
}
Required by
Verified with
Code
#ifndef M1UNE_GAME_MINIMAX_HPP
#define M1UNE_GAME_MINIMAX_HPP 1
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
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
#endif // M1UNE_GAME_MINIMAX_HPP#line 1 "game/minimax.hpp"
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
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