Nim-like(?) game winning strategy?

Question

I have the following Nim-like game (at least, it seems Nim-like to me).

There are $2k$ tokens in a row, $k \in \mathbb{N}$.

Each token $a_i$ has a value $ v_i \in \mathbb{N}$

All this information is revealed to both players in advance.

In each turn, the acting player needs to take one token from on of the edges only! - i.e: take $a_i$ such that: $i$ is either the lowest remaining available index or the highest.

What would be a winning strategy for the first player? (computable in "reasonable")

Example game:

Tokens: $a_1=7;a_2=3;a_3=1000;a_4=10;a_5=7;a_6=1000 $

(Here $k=3$)

Turn 1 - Player 1 take $a_6$.

Turn 2 - Player 2 takes $a_1$

Turn 1 - Player 1 take $a_5$.

Turn 2 - Player 2 takes $a_4$

Turn 1 - Player 1 take $a_3$.

Turn 2 - Player 2 takes $a_2$

Player 1 wins with 2007 points. Player 2 loses with 20 points.

Answer 1

Joshua Erde's answer is better than he thought. Although the paper he cites proves the result for all trees with an even number of nodes, it contains a short remark (on the first page) about the case of a linear ordering. That remark provides the following answer to the present question in the case where draws are impossible. Assume, without loss of generality, that at least half of the total value is in odd-numbered positions. Then the first player gets all the odd-numbered positions (and therefore at least a draw, and therefore a win since I assumed draws are impossible) as follows. Take the element at position 1. That leaves even-numbered positions (2 and 2k) at both ends, and the second player must take one of them. The first player then takes the neighboring odd-numbered position. Once again, both ends are even-numbered positions and the second player must take one. Continuing in this way, the first player simply takes, at each move after the first, the token next to the one that the second player just took. It is clear that this strategy gives the first player all the odd-numbered tokens.

More generally, this strategy works unless the odd-numbered positions contain exactly half of the total value. In this case, the strategy only guarantees the first player a draw, and he cannot do better because a similar strategy for the second player also guarantees at least a draw.

EDIT: As Johan Wästlund pointed out, the last half-sentence, "and he cannot do better ...," is nonsense. Please ignore it.

Answer 2

If I understand your question right, then there is a winning strategy for the first player when the number of 'tokens' is even. More generally if you have a tree with weighted vertices (with integer values) and each player takes turns in removing a leaf then the first player wins if the number of vertices is even. A proof can be found in

http://www.math.unl.edu/~s-tseacre1/grab-the-gold-8.pdf

Unfortunately the proof isn't constructive.

Edit : Indeed Andreas points out the paper mentions the result for paths is simpler, was so happy to be able to answer an MO question I forgot to stop to think about it.

Answer 3

Well, if $\sum a_i$ is odd, then there cannot be a draw and so by Zermelo's theorem one of the players has a winning strategy. If the sum of the $a_i$'s is even then one player may be able to force a draw.

Edit: False statement removed, see answer by Joshua Erde.

You could naively work out the min-max tree to find the optimal strategy for each player in $O(2^k)$ worst-case time using a branch and bound algorithm, which would probably work much better than $O(2^k)$ as a heuristic.

Using dynamic programming it can be done in polynomial time.

Answer 4

I apologize for not being able to provide a reference, but I have heard Peter Winkler speak on precisely this problem, with essentially the same answer Andreas Blass gave here. One correction, though: If the two sums (of the odd- and even-numbered positions) are equal, the first player may still have a winning strategy, because at the beginning of each round he can reevaluate whether to go with evens or odds, as the example 2-1-2-4-2-1 shows.

As I recall, all bets are off if there's an odd number of tokens. That's in part because even with an even number of tokens, things get subtle if the goal is to find a strategy that maximizes the first player's total take.

Answer 5

Here's a simulation of the problem from Winkler's book:

http://www.cut-the-knot.org/Curriculum/Games/Coins.shtml

What if the tokens are arranged on a circle? The first move is arbitrary; after that the game proceeds as before.

Answer 6

It has already been pointed out that the first player can take either all tokens at odd positions or all tokens at even positions, thereby securing at least a draw. But the example 2-1-2-3 shows that such a strategy is not always optimal.

Since the game has only $O(k^2)$ positions (subsequences of consecutive tokens), an optimal strategy can be computed in polynomial time.

Answer 7

Some observations (correct ones, I hope): I will use $a_i$ to denote both a token and the value it has. Consider a position $a_1a_2\dots a_t$ We may assume that $a_1 \ge a_t$ and that not all the values are equal (because we already understand that case). For purposes of analysis, we may also scale so that the elements sum to 1 (remembering to rescale if we want the value for use elsewhere.) The value $v(a_1\dots a_t)$ is the winnings of the first player minus those of the second (under optimal play.)

• for $t=1$ the value is $a_1$ and for $t=2$ it is $a_1-a_2.$ In general it is the smaller of $a_1-v(a_2\dots a_t)$ and $a_t-v(a_1\dots a_{n-1}$)

• for $t=3$ it is $a_1 +\operatorname{min}(a_2,a_3)-\operatorname{max}(a_2,a_3)$

• For purposes of analysis that we may rescale so that the elements sum to $1.$ In the case that $t$ is even we may first subtract the same amount from each token to make the minimum $0.$

• The full course of the game (under optimal play) depends only on the order of the $2^t$ partial sums (not all of which are pertinent.)

• When the optimal strategy changes it is a tie game, with two optimal strategies.

• We have seen that when $t$ is even the first player can be sure to get at least half the value by a simple strategy.

• If one of the $a_i \gt 1/2$ then the winner is the first player when $t$ is even. It is the second player when $t$ is odd except for the case that $a_1 \gt 1/2.$ The value is easy to determine because one player has all the even index tokens and the other all the odd. If some $a_i=1/2$ then everything is the same except when $a_j=0$ for all tokens with $j-i$ even. Then there are two strategies.

• We assumed $a_1 \ge a_t,$ if also $a_1 \ge a_2$ then the first player has a winning strategy choosing $a_1.$

• An analysis by cases of $t=4$ is not hard, especially assuming that the smallest entry is $0$ and the rest sum to $1$

  • for $0x(1-x)0$ choose the $0$ by the smaller entry
  • for $xy(1-x-y)0$ choose $x$ unless $y=1/2$ in which case either choice leads to a tie.
  • for $x0(1-x-y)y$ choose $x$ unless also $y=1/2$ in which case either choice leads to a tie.
  • for $x(1-x-y)0y$ chose $y$ if $1-x-y \ge 1/2$

• I feel that the first player wins in the even case but do not have a justification for that.

I don't know how succinct $t=5$ and $t=6$ would be. A program with the rules for $t \le 4$ built in might lead to some easily proved observations.