Green Hackenbush
(game/green_hackenbush.hpp)

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

Overview

Computes the Grundy number of a finite Green Hackenbush forest. Every edge is available to both players. Cutting an edge removes that edge and every edge no longer connected to the ground.

The forest is represented by one vertex per edge. parent[v] = -1 means edge v touches the ground; otherwise edge v is attached immediately above edge parent[v]. This representation handles several grounded components without a separate virtual root.

The implementation applies the colon principle bottom-up: the nimber of an edge and everything above it is one plus the xor of its child branches. Grounded branches are combined with xor.

Functions

All functions are in namespace m1une::game.

Function signature	Description	Complexity
uint64_t green_hackenbush_grundy(const std::vector<int>& parent)	Returns the forest’s Grundy number.	O(N) time and space
bool green_hackenbush_first_player_wins(const std::vector<int>& parent)	Whether the first player wins under normal play.	O(N) time and space

The parent relation must form a rooted forest, and each parent must be -1 or a zero-based edge index. These conditions are asserted in debug builds.

Example

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

int main() {
    // A grounded edge with two edges attached above it.
    std::vector<int> parent = {-1, 0, 0};
    std::cout << m1une::game::green_hackenbush_grundy(parent) << '\n';  // 1
}

Required by

• Game Library (game/all.hpp)

Verified with

• verify/game/classic_games.test.cpp
• verify/game/game_algorithms.test.cpp

Code

#ifndef M1UNE_GAME_GREEN_HACKENBUSH_HPP
#define M1UNE_GAME_GREEN_HACKENBUSH_HPP 1

#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

#endif  // M1UNE_GAME_GREEN_HACKENBUSH_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

Back to top page