21 Flags Game Theory Puzzle With C# Delegate - Part Two

In this blog, you will learn how to solve the 21 Flags Puzzle with a C# delegate.

Introduction 

 

In my previous post, I created a flag removal C# program to play the classic 21 flags puzzle. Today, I want to create another flag removal program in C#, but with different rules and winning conditions.

 

The first game starts with 21 flags, whoever is left with the LAST flag is the loser, similar to my previous post. Following is the snippet of the code for this situation.

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

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

           return random.Next(1, 3);//AI randomly return a value if unable to left the losing flag to user

       }

The second game starts with 21 Flags, whoever is left with NO flag is the loser. Following is the snippet of the code for this situation:

static int NoFlagLoss(int remainingFlags)
       {
           List<int> LosingFlags = new List<int>() { 20, 16, 12, 8, 4, 0 };
           Random random = new Random();

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

           return random.Next(1, 3);//AI randomly return a value if unable to left the losing flag to user

       }

The third game starts with 21 Flags, whoever is left with 5 flags or less is the loser. Following is the snippet of the code for this situation:

static int NoFlagLoss(int remainingFlags)
        {
            List<int> LosingFlags = new List<int>() { 20, 16, 12, 8, 4, 0 };
            Random random = new Random();

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

            return random.Next(1, 3);//AI randomly return a value if unable to left the losing flag to user

        }

Regarding how I get the ‘Losing flags Numbers’ for different situation, please refer to my previous post:

• 21 Flags Game Theory Puzzle In C# - Part One

My program will start by allowing the user to choose which game that would like to challenge by providing the number, i.e. 1 for Game 1, 2 for Game 2, and 3 for Game 3.

 

The pseudocode will look like this:

 

 

Based on the user’s selection on which game she would like to play, I need to provide a corresponding flag removal method to fight against her, in the below do-while loop. So I realized that I need to pass the C# function as a reference to the below do-while loop, and the suitable solution is using the delegates function.

 

I just learned the feature of delegates in C# not long ago, so I think the best way to understand it is by using it in solving my problem.

 

To my understanding, delegates pass the function as a parameter, like what we did in passing an argument to a function, but this time the entire function is the parameter we pass.

 

One important rule of delegates is that all the methods being parameterized must share the same signature, which means they accept same parameter/s and have same return type.

 

All of my three functions share the same signature. They return Integer type data, and accept one parameter in Integer type, this means they can be parameterized.

 

First, I create a delegate that has the same signature with all my functions and named it as RemoveAIFlagDel.

delegate int RemoveAIFlagDel(int remainingflags);

Then, create an instance of this delegate:

RemoveAIFlagDel removeFlagAIdeleg = null;

Then, pass my function name to this delegate instance in the switch statement. Here, I will know which game the user wants to play, so I can use the correct function to beat her.

#region Select game region, assign delegate at here
              switch (game)//each game have different "game ended flag" amount
              {
                  case 1:
                      gameEndFlag = 1;
                      removeFlagAIdeleg = LastFlagLoss;//assign LastFlagLoss function to delegate
                      break;
                  case 2:
                      gameEndFlag = 0;
                      removeFlagAIdeleg = NoFlagLoss;//assign NoFlagLoss function to delegate
                      break;
                  case 3:
                      gameEndFlag = 5;
                      removeFlagAIdeleg = Last5FlagLoss;//assign Last5FlagLoss function to delegate
                      break;
                  default:
                      break;
              }
              #endregion

Delegate “removeFlagAIdeleg” will become my variable that store my function, and I will pass it to my another function named ProcessComputerDecision, which is another function that I created to process the current situation (remaining flags, how many flags the computer need to remove in order to beat the user, etc) of the game.

ProcessComputerDecision(remainingFlags, turn, removeFlagAIdeleg, ListOfResultTable);

Then we are done, we can now play the game.

 

Different from my previous post, this time I create a class named ResultTable to store the information all the turn, from this table we can see the decision that had been made from each player in every turn until the last turn, which looks like below.

 

 

 

 

The full source code can be download at my Git Hub repository.

 

Side Notes

1. If you understand the Game Theory Backward Induction well, the best you can do in this C# program is beat my Game 2, where whoever is left with 0 flags loses the game.
2. Since the winner is already being decided in the first step, whoever starts first matters in this kind of Flag Remover game, regardless of what is the winning condition or how many flags can be removed in each turn, or even how many flags start in the first place.
3. You only can win Game 2, because the winning condition for Game 2 starts first but another two games are start latter (In addition you do not remove the number of the wrong flag in each turn, otherwise my program will leave you no room to win), so what is the point in creating this program?
4. In my future post, I try to create a better challenge which lets the computer randomly generate the starting flags, the number of flags can be removed in each turn, the winning condition (i.e. how many flags left to the loser), and in order to make it more challenging, I will try to create a Flag Remover function that able to analysis and come out the best strategy dynamically based on those randomly generated parameters, of course including able to come out the conclusion whether start first or latter have the upper hand to win the flags remover game.
5. Humans can do Backward Induction in their brain by giving the condition like 21 flags, remove 1-3 and the last flag remaining lose the game. But how about like starting with 2,999,999 flags, remove prime number flags each turn, and whoever is left with the smallest prime number (which is 2) or a number cannot be reduced again to the losing number of flags is considered the loser.
6. I will include it in my next post if I am able to code it in C#!