32
$\begingroup$

I devised a game recently. There is a string of numbers, and each player extends the string by appending a number to the end based on the current last number of the string. The string starts as the single number $1.$ If the last number of the string is $x,$ the player can append $2x+1,2x+5,$ or $\lfloor \frac{x}{3} \rfloor.$ The goal is to repeat a number already in the string.

Here's an example game: $1, 7, 2, 9, 19,$ 43$, 14, 33, 11,$ 3$, 1.$ The first player was trapped. The italicized number is the trapped player's mistake, the moves after that by the trapped player before the bolded number are forced moves (by forced moves I mean if the trapped player plays anything else, the other player wins on the next turn), and the bolded number is basically the player trapped resigning. In the general case, is it guaranteed that somebody wins with perfect play, or would two perfect players battle forever?

Edit: Trap #2: $1, 7, 2, 9, 19, 39, 13, 31, 10, 25, 55,$ 111$, 37, 79, 26,$ 8$, 2.$ This is also winning for the second player.

Trap #3: $1, 7, 2, 9, 19, 39, 13, 31, 10, 25, 55, 18, 37, 79, 26, 53, 107,$ 35$, 11,$ 3$,1.$ I'm pretty sure this trap using $33, 34,$ or $35$ can manifest itself in many situations. This is also winning for the second player.

I have been analyzing a different opening and found Trap #4: $1, 7, 15,$ 35, $11, 27, 9, 19, 6,$ 2, $9$.

Here's Trap #5 in yet ANOTHER opening: $1, 7, 19,$ 6, $2,$ 0, $0$.

$\endgroup$
17
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Paramanand Singh
    Dec 28, 2022 at 3:01
  • 1
    $\begingroup$ @CalvinLin $4$ and $29$ can be played, but the other player then has an immediate win: note that $9$ is already in the sequence and $2\cdot4+1=9$; $\lfloor \frac{29}{3} \rfloor=9$. $\endgroup$
    – nickgard
    Dec 31, 2022 at 20:44
  • 4
    $\begingroup$ Here's Java code that performs a tree search for a forced win (always trying $\left\lfloor\frac x3\right\rfloor$ first to limit the search as far as possible). It fills in the numbers surprisingly densely and doesn't find a win before running out of stack space. (The stack issue could be avoided by implenting it without recursion, but it shows that the search tree becomes infeasibly deep.) $\endgroup$
    – joriki
    Jan 4, 2023 at 12:11
  • 4
    $\begingroup$ Sounds so much like collatz conjecture! $\endgroup$
    – gsomani
    Jan 9, 2023 at 5:58
  • 3
    $\begingroup$ After thinking about this for a couple of hours, I'm pretty sure the game is finite, and a good enough programmer can determine who has the winning strategy. $\endgroup$ Mar 27, 2023 at 5:47

1 Answer 1

8
+200
$\begingroup$

This game is rather tricky because it has an infinite number of states and any one game can be infinitely long. It is possible to construct restricted versions of the problem to make the state space finite, but it is not trivial to use these constructions to provide rigorous insight into the infinite case. Strong insight into the infinite case using number theory may be hard to come by - there is suspicion that this problem is hard to solve for a similar reason to why the Collatz conjecture is hard to prove.

I offer the following in this answer:

  1. A description of what I believe to be the fastest algorithm we can hope for to solve a family of restricted versions of the problem, given a lack of other theoretical insight (from number theory etc.)
  2. A proof that, if there does exist a winning strategy for one of the players, the algorithm can in principle be used to solve the unbounded version of the problem in finite time.
  3. Performance-oriented code implementing the algorithm and achieving good depths.
  4. Provable bounds on the infinite version of the problem.
  5. A heuristic argument in favor of the answer to the unbounded problem being: the second player wins the game.

The restricted version of the problem

We will consider the variant of the problem where the maximum playable number in each round and the maximum depth of any one game is restricted. Call the problem $\mathrm{RepeatGame}(N, d)$, where $N$ is the maximum playable number and $d$ is the maximum depth.

In $\mathrm{RepeatGame}(N, d)$, a player is not allowed to append a number greater than $N$ (alternatively, we can say that doing so is an automatic loss). If a game progresses to $d$ rounds after the initial state without ending, we will say that Player 2 is the winner.

$\mathrm{RepeatGame}(N, \infty)$ is the game where a maximum depth is not imposed. $\mathrm{RepeatGame}(\infty, \infty)$ is the unbounded game of interest in the question.

I am assuming that infinitely stalling the game in $\mathrm{RepeatGame}(\infty, \infty)$ would be a draw, not a win for either player.

Solving $\mathrm{RepeatGame}(N, \infty)$

Without additional insight from number theory, we just have to solve the problem like any other zero-sum perfect information game such as chess. There exist many tricks to design very strong AI players for such games, but most of these tricks are irrelevant to a proof of optimality. Optimality in general can only be shown by reasoning through the full game tree.

A full search of the game tree can be done using alpha-beta pruning tree search. There are results showing that the time complexity attained by alpha-beta pruning is optimal if the branches are visited in a good order (see "Asymptotic properties of minimax trees and game-searching procedures"). There are many variants of alpha-beta pruning that attempt to achieve this optimal ordering, and these are used in practice for game tree analysis in programs such as chess engines.

This is the method used to study $\mathrm{RepeatGame}(N, \infty)$ here. Unbounded depth is achieved using iterative deepening.

$\mathrm{RepeatGame}(\infty, \infty)$ can't be solved directly with game tree search because many of the subtrees are infinitely big. It's technically possible that all the infinite branches get pruned during analysis, but there's no good way to guarantee this.

At any final state, we let the evaluation score of the winner for the game state be equal to the largest number given to player 1 (before their move) during the game, call this $\mathrm{maxP1}(s)$ where $s$ is the game state. The final game state is the one where player 2 produces the repeat number, and we don't consider this repeat number as being given to player 1.

If player 2 is the winner of $\mathrm{RepeatGame}(N, \infty)$, then the evaluation of the initial state will be the largest possible number that player 1 can receive, given optimal play by player 2 to minimize this number while still ensuring that player 2 eventually wins the game. We can define $\mathrm{maxP2}$ similarly.

In principle we don't need such a complex evaluation function to just solve $\mathrm{RepeatGame}(N, \infty)$. We can simply assign the evaluation score $1$ to the winner. But this formulation is useful for the remainder of the answer.

Solving $\mathrm{RepeatGame}(\infty, \infty)$ if a player wins

Firstly, if a player has a winning strategy then this player must be able to force a finite game length bounded by some maximum game length $d$. Otherwise, the game is a draw. It isn't possible for the losing player to force a finite but arbitrarily long game, because they only have at most three choices at each round.

WLOG, suppose player 2 is the winner. For any finite game, the $\mathrm{maxP1}$ function produces a finite value for the final game state. There are finitely many games of finite length. So there exists an optimally played game where player 2 bounds the value of the $\mathrm{maxP1}$ evaluation to be at most some integer $M$. No matter what moves player 1 chooses, the maximum value he receives will not exceed $M$. This also means player 2 will not receive a number above $2M + 5$. Player 2 would definitely respond with $\lfloor \frac {2M + 5} 3 \rfloor$, otherwise player 1 receives a number above $M$, or (if this is the last move) the number is too high to be a repetition of a number from earlier.

This would mean that player 2 can simply pretend the game is $\mathrm{RepeatGame}(2M + 5, \infty)$, and will never need to use numbers higher than $2M + 5$. Player 1 will never be given the opportunity to use numbers higher than $2M + 5$ because player 2 minimizes the numbers player 1 receives to be at most $M$. Player 2's optimal strategy for $\mathrm{RepeatGame}(2M + 5, \infty)$ using the $\mathrm{maxP1}$ evaluation function, will also be an optimal strategy for $\mathrm{RepeatGame}(\infty, \infty)$.

This argument establishes that there exists a finite version of $\mathrm{RepeatGame}$ which produces the optimal strategy for the unbounded game, assuming the unbounded game is not a draw. To find the strategy, try all $N$ and for each $\mathrm{RepeatGame}(N, \infty)$, check the evaluation of the root node $M$ to see if $N \geq 2M + 5$. Try both the player 1 wins and the player 2 wins assumptions.

Bounds on $\mathrm{RepeatGame}(\infty, \infty)$

I've written code to solve $\mathrm{RepeatGame}(N, \infty)$, and unfortunately the $N \geq 2M + 5$ condition doesn't occur for any tractable $N$. The runtime costs are exponential in $N$ and in $d$. The conclusion is either that $\mathrm{RepeatGame}(\infty, \infty)$ is a draw, or the required $N$ is too large to solve.

The experiments still produce rigorous bounds on $\mathrm{RepeatGame}(\infty, \infty)$. Firstly, it can be shown that the $\mathrm{maxP1}$ evaluation on the root node of $\mathrm{RepeatGame}(\infty, \infty)$ is greater than $200$. This is due to the results of $\mathrm{RepeatGame}(405, \infty)$. In this game, player 2 wins and is able to force $\mathrm{maxP1}$ to be at most $331$. If the root node evaluation of the unbounded game is under $200$, then $\mathrm{RepeatGame}(405, \infty)$ would have been able to find this optimal strategy and also produce an evaluation under $200$. Since the actual evaluation was higher, we know that the unbounded game must have an evaluation above $200$.

Secondly, it can be shown that if player 2 is the winner, any game where player 2 chooses optimal moves to minimize $\mathrm{maxP1}$ has depth at least 42. This is done by evaluating $\mathrm{RepeatGame}(2200, 42)$ with $\mathrm{maxP1}$. The game is deduced to be a win for player 2 that achieves an evaluation of $1015$, with the longest game being precisely $42$ moves long. Suppose player 2 were to play $\mathrm{RepeatGame}(\infty, \infty)$ by pretending it is $\mathrm{RepeatGame}(2200, 42)$. Until move 42, player 1 will not be able to receive a number above $1015$. Player 1 does not gain any additional move options in $\mathrm{RepeatGame}(\infty, \infty)$ because $2 * 1015 + 5 < 2200$, and obviously he also doesn't lose any move options. So the game must continue to at least move $42$, and only after move $42$ is it possible for player 1 to increase $\mathrm{maxP1}$ further.

By similar reasoning using $\mathrm{RepeatGame}(3100, 40)$ with $\mathrm{maxP2}$, if player 1 is the winner, any game where player 1 chooses optimal moves to minimize $\mathrm{maxP2}$ has depth at least 40.

Heuristic argument for a player 2 win

It is observed that for $N > 14$, player 2 always appears to win $\mathrm{RepeatGame}(N, \infty)$. My code was able to test up to $N = 405$.

Update: by prioritizing the win condition in the evaluation function, it can be shown that player 2 wins $RepeatGame(710, \infty)$ in under $40$ moves. This result can't be used to bound $M$ for an optimal game though, since the game tree was not fully searched. Playing the depth $38$ AI against itself on $RepeatGame(711, \infty)$ produces a $52$ move game containing $711$, so I suspect $RepeatGame(711, \infty)$ needs to be searched to at least depth $52$ in order to find the winner. Also it seems player 2 is favored to win on $RepeatGame(760, \infty)$ when the depth $38$ AI plays against itself, though nothing can be proven with this exercise.

That said, even if player 2 is proven to be the winner for all finite $N > 14$, it does not imply $\mathrm{RepeatGame}(\infty, \infty)$ is a player 2 win, because it could still be a draw if the $N \geq 2M + 5$ bound is never achieved.

(Changed, see edit) It is observed that using $\mathrm{RepeatGame}(30000, 36)$ to choose the best move at each round (i.e. searching at depth 36 like a chess engine), the player 2 AI wins against the player 1 AI and achieves $N \geq 2M + 5$ for the game (the actual $M$ of the game I sampled was $10735$). The same is consistently true for many different runs of $\mathrm{RepeatGame}(1000000, 25)$. It should be noted that the AI behaves nondeterministically due to ties in the evaluation, so each game is different yet player 2 is always observed to be the winner. The games usually last fewer than a few hundred moves.

That said, the player 1 strategy is not optimal and may be subject to horizon effects. It is possible that a stronger player 1 AI would win or at least draw even against an optimal player 2 AI.

A hand-wavey probabilistic argument can be made along a similar vein as the probabilistic arguments for why integers usually decay toward 1 in the Collatz conjecture. Due to the way the rules are constructed, the possible moves becomes more spaced apart as the numbers in the chain grow larger. The density of played numbers is expected to decrease along the number line. When the density of points is higher, there are more opportunities for a player to win or lose the game. Let's call the current number $n$. In a sense, receiving a larger $n$ in a round is safer, and receiving a smaller $n$ in a round is riskier.

Roughly speaking, at a position where player 2 is winning, player 2 (who chooses moves to minimize $\mathrm{maxP1}$) is inclined to keep the number $n$ small provided he controls the game enough to still ensure victory. In general, player 1 is not inclined to do anything since defeat is guaranteed at a position where player 2 is winning. Normally, AI programs aim to maximize the depth to defeat. But in the worst case scenario for player 2's evaluation function, player 1 is instead inclined to make the number big.

Since player 2 has the ability to divide the number by 3, yet player 1 can only roughly double the number, and player 2 controls the game since he is in a winning position, player 2 has the upper hand in making the number small if they play in a region when the density of already played numbers is small.

Suppose at any point in the game, there is some threshold $T$ where there's a significant probability that the game ends quickly if either player receives a number $n < T$, due to nearby numbers that are already played. We say the risk of a quick game over is low if $n > T$.

When $n < \frac 3 2 T$, player 2 can choose to avoid the $\lfloor \frac n 3 \rfloor$ move to avoid a risk of changing the game to a losing position by player 1 returning him a value under $T$.

Player 2 wants to arrange the game so that usually $n > \frac 3 2 T$ and $n < 9 T$. By doing so, player 2 is not easily trapped since the risk of ending the game is low in this region. On the other hand, player 2 can choose the $\lfloor \frac n 3 \rfloor$ move when $n$ is close to but still above $\frac 3 2 T$. This makes player 1 receive a number close to but still above $\frac 1 2 T$, which contains the risk of ending the game quickly. Since it was player 2's choice to land there, player 2 can take advantage of the risk if he sees that the result is advantageous to player 2, and can choose to instead give player 1 $n > 3 T$ if the result of decreasing the number is advantageous to player 1. As normally player 2 will give player 1 $n > 3 T$, player 1 must use either wait to receive an $n$ near $3 T$ and give player 2 an $n$ just above $T$, or act quickly after receiving $n$ near $\frac 1 2 T$ by progressing to $T$. In both cases player 1 may be able to give player 2 a value of $n$ near $\frac 2 3 T$. However, in both cases player 2 has a chance to put player 1 in risk first by giving him a value of $n$ near $\frac 1 2 T$.

Player 2 has a broad strategy that ensures player 1 can be put in significantly more risk than player 2 by having the initiative and by putting player 1 into lower values, and this adds over time as the game becomes longer. Of course, in reality the threshold is not sharp and the players can make complex plans in advance, so this cannot be more than a heuristic argument.

Based on the above, my educated guess is that the game is not a draw and the disadvantage to player 1 keeps compounding until player 2 eventually wins. However, the optimal game is probably too large to verify as being optimal using current methods, unless there is a more fundamental insight about the numbers used in the game.

Code for the tree search

https://github.com/JubilantJerry/RepeatGame

There are several constants next to the main function that can be changed to control $N$, $d$, whether to use $\mathrm{maxP1}$ or $\mathrm{maxP2}$, etc.

In this implementation the win condition is analogous to checkmate in chess, i.e. it is not possible to actually repeat a number, instead moves that lead to immediate loss are illegal, and checkmate occurs when all three of the opponent's moves are illegal.

Edit

In my experiment where I made two depth 36 computers play against each other, I realized that my evaluation function didn't incentivize the win condition enough. This doesn't affect the restricted $N$ and unlimited $d$ experiments, and it is actually the function we need to use in order to get rigorous bounds for the depth of the optimal game. However, it made the depth 36 player 1 AI much weaker at the game, and it is for this reason that player 2 keeps winning.

By prioritizing the win condition over the $\mathrm{maxP1}$, the games become much longer (usually a few thousand rounds) and using depth 36 to play a full game is not tractable anymore.

With depth 20, both player 1 and player 2 are able to win sometimes. The same is true if $\mathrm{maxP2}$ is used for the evaluation.

I still think that the game is not a draw, and that player 2 has the upper hand, both because of the finite $N$ results and the heuristic argument. But I do imagine that player 2's advantage is hard to maintain, meaning there are many small mistakes player 2 can make to allow player 1 to equalize the game or to take the lead.

Bonus

Here is a plot of $\log(n)$ vs. iteration during a typical game between depth 20 AI players:

Game between two AI players, depth 20, maxP1

Zoomed in:

Game between two AI players, zoomed, depth 20, maxP1

It appears like $n$ oscillates within a constant factor of some geometric center that increases linearly over time. I liken this central value to $T$ from my heuristic argument.

It seems that the player trying to maximize $\mathrm{maxP1}$ can't make $n$ grow too quickly, and therefore the iterations will usually stay within some factor of $T$. I believe this creates many opportunities for either player to end the game, and that's why I don't think the game is a draw.

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful! I went to depth 14 with my programs, but it was too slow beyond that. $\endgroup$
    – mathlander
    Apr 3, 2023 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .