[Math] Hackenbush game strategy for stalk

game theory

There are some piles of numbers. Numbers are divided in 2 groups, A and B. Player x plays with group A and player y plays with group B. x makes the move first. On each step a player chooses a pile and chooses a number of his group and remove all numbers smaller and equal to the number (number of both group A and B) from that piles only.

The person who can't make the move which means he finds no number of his group, loses.

Is that a nim game? What should be the strategy? Who will win?

Best Answer

It's not a nim game, it's an Hackenbush game (Blue-Red version if $A\cap B=\emptyset$)

Replace each number by a line segment of color red for number from $A$, and blue for $B$. To each pile of number, build a pile of line segment, by decreasing order of number.

For example, if $A$ are even numbers, and $B$ are odd numbers, the pile $[3,4,7,8,10]$ will be replace by ground-red(for 10)-red(for 8)-blue(for 7)-red(4)-blue(3).

Hackenbush games are not nim games. To each finite position can be assigned a dyadic number whose sign will give the player who can win.

EDIT : strategy explained for player x : To each number (from $A$) in each pile, $x$ will assign a value that will be :

  1. $1$ if this the largest number of the pile
  2. $1$ if the next larger number was assigned 1 and is from the same set ($A$ or $B$)
  3. $2^{-n}$ where $n$ is the distance to the closest number with value $1$.

Example : in pile [10,8,7,4,3,1], 10 will have value 1 (by rule 1), 8 value 1 (by rule 2), and 4 value $\frac{1}{4}$ (by rule 3). For player y, 7 will be assigned value $\frac{1}{2}$ (rule 2 does not apply here because the next larger number 8 is not from the same set, so rule 3), 3 value $\frac{1}{8}$, and 1 value $\frac{1}{16}$.

The best strategy is to remove the number of lowest value. (This is not the quickest strategy !)

If you add all values for player x and subtract all values for player y, a positive sum means player x has a winning strategy, negative sum is for player y while a zero sum means second player.

Related Question