21 Flags Game Theory Puzzle: Create an unbeaten flag removal program with C# Part 1

There is one classic game theory puzzle named “21 Flags Game” (which the total flags and winning condition might vary from case to case), where two contestants are trying to move 1–3 flags from the 21 flags in turn, and whoever remove the last flag will be consider as loser.

Let list down the rule and try to think deductively to come out a winning strategy

1. Game start with 21 flags
2. Each player have to and can only remove 1 to 3 flags per turn
3. Each player remove the flag alternately by turn
4. Whoever remove the last flag will lost

So, in other word, each player have to make sure his/her opponent is being left with a last flag .

What is the best strategy to win this game?

Lets think few steps ahead to generate our winning strategy.

1. Game loser will be left 1 flag only, which in this case he/she have no choice but to remove the last flag, which make him/her lose the game
2. How to make sure the loser being left with only one step? We have to make sure in the previous turn, the winner is being left with 2 or 3 or 4 flags only.
3. If winner being left with 2 flag in the previous turn, he/she only need to remove 1 flag and end the turn, which lead the loser in condition 1. and lost the game. Same strategy if he/she being left 3 flags (remove 2) and 4 flags (remove 3).
4. So now we have our winning condition, which is whoever being left with 2 or 3 or 4 flags, he/she definitely will be the winner
5. Again, how the winner ensure that himself/herself being left with 2 or 3 or 4 flags in his/her turn? Then winner have to make sure that he/she end his/her turn with 5 flags on one more previous turn.
6. This is because if the loser being left with 5 flags, regardless how many flags he/she removed(1 to 3 flags only), it will inevitable put his/her opponent in winning condition of point 4. (5–1=4, 5–2=3, 5–3=2)
7. So, we have our another losing condition , which is whoever being left with 5 flags, , he/she definitely will be the loser.
8. And we can keep think forward and adding the total flags remaining in point 7, and we will eventually come out a losing condition, which is whoever being left: 21 or 17 or 13 or 9 or 5 or 1 flag during his/her turn, he/she definitely will be the loser.
9. From our list of ‘losing number’, we can write a simple C# console program to make sure we left our opponent with that total of flags during their turn, and secure the winning position

Here are the simple C# snippet of our winning strategy

The code is very straight forward, I just store our ‘losing number’ in a list of integer, and make sure my program return the total flag/s needed to be removed for every turn in order left the total ‘losing number’ of flags to my opponent each turn.

Here is the screenshot of the game when running (user start first):

Off course there is some trick in this game, which the user always has to start the first turn, so he/she will never able to beat my program even he/she know well about our 21 flags removal strategy.

Full source code can be download at Git Hub