"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.)

  • 2
    $\begingroup$ According to p. 198 of Winning Ways v. 1, $1:(*:G+H)=1:H+*:G$ which together with the colon principle means that it suffices to understand forests of "two-layer" trees where the layer closer to the root is pure green and the layer further from the root is pure red-blue. $\endgroup$ – Gabriel C. Drummond-Cole Apr 13 '17 at 14:56
  • 1
    $\begingroup$ And then if you care mostly about outcome classes, atomic weight theory gives you a pretty good working knowledge of how to analyze forests where the green layer is nonempty in every tree (albeit that's not going to give you exact values). $\endgroup$ – Gabriel C. Drummond-Cole Apr 13 '17 at 15:03
  • 1
    $\begingroup$ (adding to my first comment) moreover the colon principle says that each of the connected components of the red-blue layers can be taken to be a string. $\endgroup$ – Gabriel C. Drummond-Cole Apr 13 '17 at 21:40
  • $\begingroup$ @GabrielC.Drummond-Cole Thank you for these comments: this clarifies the situation considerably (the presentation in Winning Ways was not exactly enlightening to me as it is written). $\endgroup$ – Gro-Tsen Apr 13 '17 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.