Strategic Game-play and the Invariant Principle
Introduction
The invariant principle is a very powerful tool in our armory when we try to devise optimal strategies for playing certain classes of games. We are concerned primarily with 2-player games where the players alternate moves and the game always terminates with a win for one of the players (a finite game).
An invariant is a property of the game that does not change, irrespective of how the players play. Using the invariant principle, one can readily identify whether it is possible to reach a certain state of the game. This greatly reduces the set of possible end-states reachable from a starting point. The invariant principle also leads to certain vantage states, i.e., if a player is able to reach such a state, then by optimal play henceforth, he/she can always win. If this feels a lot now, don’t worry. An example will make things much easier to understand. Let us consider the following game.
Rules of the Game
Alice and Bob are two friends. One day they find a shiny old coin in their backyard. In order to decide who gets the coin, they play a game. Alice has just started learning Python and she knows how to generate random integers using numpy.random.randint. So, Alice gets her computer to output a positive integer n. Alice and Bob take turns alternately at playing. In each turn, they pick out a proper divisor of n (d < n) and subtract d from n. n is updated to n-d. If someone is unable to make a move, he/she loses. Since it was Alice’s idea to play the game, she is offered the choice to decide whether she would take first turn or second turn. If Alice always wants to win, what should she pick ?
Termination Point of the Game
Let’s break it down for Alice. The game terminates when n = 1 is reached. Why is that ? Because, for n = 1, there is no proper divisor d < n that can be subtracted from n. So, the key for Alice is to reduce n to 1 so that Bob cannot make a legit move and loses the game.
Ways to reach 1
Alice finds out that the easiest way to force Bob to make a move at n = 1 is for her to make a move at n = 2. Recall that 2 is a prime number and has only one proper divisor d = 1. So, after Alice has played her turn by operating on 2, Bob is left with n = 1 by default and doomed to lose.
Discovering the Invariant
Claim 1 : An odd integer has all odd divisors. So, if a player is asked to operate on an odd n, he/she will always end up changing the parity of n to even, irrespective of what move is made.
Claim 2 : Whoever gets to operate on an even n, has a winning strategy.
The first claim is straightforward, but the second one-maybe not so. Let’s understand in greater detail. If player A gets to operate on even n, he/she can always choose d = 1 in that turn. That makes n odd. Using claim 1, it is clear that irrespective of how player B plays, A will always get to operate on another even number in the next turn. Thus, A operates on a sequence of decreasing even numbers in consecutive turns. Hence, A will always get to operate on n = 2 after a finite number of rounds. Therefore, A has a winning strategy.
Alice’s winning strategy
Since Alice gets to choose whether to take the first or the second turn, she should make the choice in the following way:
- If the computer outputs an even n, Alice should take first turn.
- If the computer outputs an odd n, Alice should take second turn.
Concluding Remarks
This simple game clearly illustrates how to use the invariant principle to our advantage while we develop strategies. The key step is the identification of the invariant in any given problem. For further reading and access to more such problems, go to : https://brilliant.org/wiki/invariant-principle-definition/
If you like what you read and want to read more, please follow me on Medium. Cheers !
References
The problem described here has been inspired by the following article. It uses dynamic programming principles to find the winner, given any n. I take a more novel approach to solve the same. The article can be found at:
https://www.geeksforgeeks.org/optimal-strategy-for-the-divisor-game-using-dynamic-programming/