"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint union of trees), i.e., where we disallow loops. More precisely, it is the two-player perfect information game where we start with a forest (of rooted trees), all of whose edges are colored either red, or blue, or both ("both" being referred to as "green"); the two players, Left and Right, alternate in removing an edge from the forest, where Left can only remove blue (or green) edges, and Right can only remove red (or green) edges: when an edge is removed, the whole subtree that descends from it also disappears; the player who removes the last edge wins (i.e., the player who cannot play loses).

Formally, forest Hackenbush can be defined as the set of games obtained by the following operations:

the zero game $0$ is a Hackenbush forest,

if $G_1,\ldots,G_n$ are Hackenbush forests then (the disjunctive sum) $G_1 + \cdots + G_n$ is a Hackenbush forest,

if $G$ is a Hackenbush forest, then $*{:}G$ is a Hackenbush forest (connecting the forest from a green edge), where $*{:}G$ is defined as $\{0, *{:}(G^L) \; | \; 0, *{:}(G^R)\}$ (meaning that each player can either move in $G$ or delete the game altogether),

if $G$ is a Hackenbush forest, then $1{:}G$ resp. $(-1){:}G$ are Hackenbush forests (connecting the forest from a blue, resp. red edge), where $1{:}G$ is defined as $\{0, 1{:}(G^L) \; | \; 1{:}(G^R)\}$ (meaning that each player can either move in $G$ and Left can also delete the game altogether), and symmetrically for $(-1){:}G$ (alternatively, we can say that $-G$ is a Hackenbush forest when $G$ is and define $(-1){:}G$ as $-(1{:}(-G))$).

Solving green (=impartial) forest Hackenbush is very simple: the nim value of $G$ is computed by knowing that $0$ has nim value $0$, the nim value of a disjunctive sum is the nim sum of the nim values, and the nim value of $*{:}G$ is $1$ plus the nim value of $G$.

Solving red-blue forest Hackenbush is also fairly simple: the value of the game is always a number (a dyadic rational), and it is computed by knowing that $0$ has value $0$, the value of a disjunctive sum is the sum of the values, and the nim value of $1{:}G$ is computed from the nim value of $G$ in a fairly simple way (if I am not mistaken: if the value $v$ of $G$ is positive or zero, then it is $v+1$, and if $v$ is between $-n$ and $-n+1$ with $n>0$ integer, then it is $(v+n+1)/2^n$). Note that this is in contrast with *general* red-blue Hackenbush (without the "forest" requirement), which is apparently known to be NP-hard.

**Question:** What is the difficulty of three-color forest Hackenbush? Is there a simple way to manipulate and compare game values produced by the above rules? Or does the "forest" limitation add nothing in the three-color case?

(I'm not necessarily asking for a precise measurement of algorithmic complexity. An informal argument that "it's probably hard" will do, although I'm hoping for the opposite case.)

Winning Wayswas not exactly enlightening to me as it is written). $\endgroup$ – Gro-Tsen Apr 13 '17 at 22:49