About general strategies for game-problems: Adding 31 from numbers on a regular calculator

Question

I am new to game related problems so, in particular, I'm starting with symmetry game problems. In this case, I was trying to solve the following problem:

Two players, A and B, use a special calculator with number buttons without the zero and provided only with the "+" button as operation. Player A starts by pressing one number button, then pressing "+" and passing the calculator to B. Then B must choose a number that is either in the same column or the same row as the number picked by A in their previous turn (B cannot choose the same number A picked in their last turn). Then B presses "+", wich makes the calculator show the current sum of all the numbers chosen so far. In the next turn, A does the same thing. The first player that obtains a sum equal or larger than 31 by pressing the "+" button loses the game. Which one of the two players has a winning strategy?

I was thinking that maybe A would want to start with the greatest possible number, but in that case B would want to do the same. This however, doesn't seem to lead to anything interesting. As I stated before, I'm very new to this kind of problems and have no idea how to approach them. I have seen many examples but all of the solutions seem very specific to the problems. Do general strategies to approach this kind of problems exist? For example, could number theory be useful to solve this problem?

I would like to see some general hints not only for this problem but for general problems related to game strategies.

Answer 1

Here, we can capture the relevant state information using $(S, M)$ where $S$ represents the current Sum displayed on the calculator and $M$ represents the number button pressed / Move to get that sum.

Note for e.g. that $(30, x)$ for any allowable $x \in \{1, 2, 3, \dots 9\}$ represents a winning state for the player who just achieved that state (i.e. the next player has no option but to lose).

Assuming both players are trying to win and are aware of their best strategy, let us define a function $W(S, M)$ which takes the following values - $0$ if there are no winning moves for the next player (i.e. it is a winning state for the previous player). Similarly $W(S, M)=x >0$ would indicate the next player can press the number $x$ to get to a winning state. Of course the choices of $x$ are limited by the moves permitted on the calculator keypad, and there may be more than one move which may take the next player to a winning state, so for the sake of uniqueness we pick the maximum allowable such move to be $x$.

Now given $W(30, 1)=0$ represents a winning state for the previous player, we can think of which last moves could have led to that state, and from which previous states could we have such moves. Clearly the last move was $1$, so the last sum was $29$, and the possible states which allow a move of $1$ are hence $(29, 2), (29, 3), (29, 4), (29, 7)$. We can hence set $W$ value of all these states to $1$, which is the best move at this state for any next player for reaching a winning position.

We can follow this process for all the winning states $(30, 2), (30, 3), \dots$ thereby identifying values of the $W$ function. Further then we can progress to states of form $(29, x)$ and so on step by step. Clearly given the constraints on the moves and possible sums, this is perhaps better done with a program. Here is one written in python:

---

allowable_moves = {
    1: {2, 3, 4, 7},
    2: {1, 3, 5, 8},
    3: {1, 2, 6, 9},
    4: {1, 5, 6, 7},
    5: {2, 4, 6, 8},
    6: {3, 4, 5, 9},
    7: {1, 4, 8, 9},
    8: {2, 5, 7, 9},
    9: {3, 6, 7, 8},
    }
"""
allowable_moves is a dictionary of allowable next moves, if the last number 
key pressed is given.  Note the same dictionary also captures the "reverse" 
moves, i.e. given a move, what could have been allowable preceding moves.
"""

win = {(i, j+1) : 0 for i in range(31) for j in range(9)}
"""
Each state is represented by:
    c_sum   current sum on the calc display, from 0 to 30
    move    last number key pressed, from 1 to 9  
The entries of the "win" dict represent:
    0           a winning position for the last player
    x           what number the next player should press to win, 1 to 9
"""

for c_sum in range(30, -1, -1):
    for move in range(1, 10, 1):
        if win[(c_sum,move)] == 0:
            last_set = allowable_moves[move]
            # last_set is the possible moves before the one just played
            
            for last_move in last_set:
                if c_sum >= move and win[(c_sum - move, last_move)] == 0:
                    
                    win[(c_sum-move, last_move)] = move
                    # records that this is a possible winning move
                    
    print(str(c_sum).zfill(2), " : ", 
          [win[(c_sum,i)] for i in range(1, 10, 1)])

---

The output is a table of $W$ values:

        Moves --->
Sum |   1, 2, 3, 4, 5, 6, 7, 8, 9
----------------------------------
30  |  [0, 0, 0, 0, 0, 0, 0, 0, 0]
29  |  [0, 1, 1, 1, 0, 0, 1, 0, 0]
28  |  [2, 1, 2, 1, 2, 0, 1, 2, 0]
27  |  [3, 3, 0, 0, 0, 3, 0, 0, 3]
26  |  [4, 0, 0, 0, 4, 4, 4, 0, 0]
25  |  [0, 5, 0, 5, 0, 5, 0, 5, 0]
24  |  [3, 5, 6, 6, 6, 5, 1, 5, 6]
23  |  [7, 3, 6, 7, 6, 4, 4, 7, 7]
22  |  [4, 8, 6, 6, 8, 5, 8, 5, 8]
21  |  [0, 8, 9, 0, 8, 9, 9, 9, 8]
20  |  [7, 5, 9, 7, 0, 9, 9, 9, 7]
19  |  [0, 8, 9, 0, 8, 9, 9, 9, 8]
18  |  [7, 8, 1, 7, 8, 0, 8, 7, 8]
17  |  [4, 0, 9, 0, 4, 9, 9, 9, 0]
16  |  [0, 0, 9, 0, 0, 9, 9, 9, 0]
15  |  [4, 5, 2, 5, 4, 5, 4, 5, 0]
14  |  [2, 0, 2, 0, 2, 0, 0, 2, 0]
13  |  [4, 0, 0, 0, 4, 4, 4, 0, 0]
12  |  [4, 0, 6, 6, 6, 4, 4, 2, 6]
11  |  [2, 5, 2, 5, 2, 5, 0, 5, 0]
10  |  [4, 3, 2, 0, 4, 4, 4, 2, 3]
09  |  [4, 0, 0, 0, 4, 4, 4, 0, 0]
08  |  [0, 0, 9, 6, 6, 9, 9, 9, 6]
07  |  [7, 1, 9, 7, 2, 9, 9, 9, 7]
06  |  [4, 3, 9, 0, 4, 9, 9, 9, 3]
05  |  [4, 8, 9, 0, 8, 9, 9, 9, 8]
04  |  [7, 0, 9, 7, 0, 9, 9, 9, 7]
03  |  [0, 0, 0, 0, 0, 0, 0, 0, 0]
02  |  [4, 1, 9, 1, 4, 9, 9, 9, 0]
01  |  [4, 8, 2, 0, 8, 4, 8, 2, 8]
00  |  [3, 3, 9, 0, 0, 9, 9, 9, 3]

from which it is evident that the first player can get to $(3, 3)$ or $(9, 9)$ in the first move, both of which have a $W$ value of $0$, so the next player has no winning moves. Whatever is played then, the first player can jump to another state with $W$ value $0$ because of the way we constructed the table, which gives the winning strategy.

P.S. The last row in the table does not mean much as there is no previous move when sum shown is $0$ at the start - except that it shows the only winning moves are $3$ or $9$.