21 Flags Game Theory Puzzle In C# - Part One

In this blog, you will learn how to create an unbeaten flag removal program with C#.

Introduction 

 

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

Let list down the rule and try to think deductively to come out with a winning strategy. In other words, each player has to make sure his/her opponent is being left with the last flag.

 

What is the best strategy to win this game?

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

Let's think a few steps ahead to generate our winning strategy.

1. The game loser will be left 1 flag only, which in this case he/she has 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 the winner is left with 2 flags in the previous turn, he/she only needs to remove 1 flag and end the turn, which leads the loser in condition 1. and lost the game. Same strategy if he/she is left 3 flags (remove 2) and 4 flags (remove 3).
4. So now we have our winning condition, which is whoever is left with 2 or 3 or 4 flags, he/she definitely will be the winner
5. Again, how the winner ensures that himself/herself being left with 2 or 3 or 4 flags in his/her turn? Then the winner has 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 inevitably put his/her opponent in winning condition of point 4. (5-1=4, 5-2=3, 5-3=2)
7. So, we have another losing condition, which is whoever is left with 5 flags, he/she definitely will be the loser.
8. And we can keep thinking 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 is the simple C# snippet of our winning strategy:

private static int AIPulledFlag(int remainingFlags)
       {

           List<int> WinningFlags = new List<int>() { 21, 17, 13, 9, 5, 1 };
           Random random = new Random();

           foreach (int i in WinningFlags)
               if (remainingFlags > i)
                   return remainingFlags - i <= 3 ? remainingFlags - i : random.Next(1, 3);



           return random.Next(1, 3);


       }

The code is very straight forward, I just store our ‘losing number’ in a list of integer, and make sure my program returns 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 running,

 

 

Of 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 knows well about our 21 flags removal strategy.

 

The full source code can be download at Git Hub