21 Flags Game Theory Puzzle - Dynamic Solution With C#

For conext, please read my previous posts:

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

I’m developing a program that can automatically generate a winning strategy based on different situations (e.g. different starting flags, winning condition, flags that allowed to remove per turn), compare to previous code, hard code some logic, and which only works for specific situations.

 

During the development, I discovered that I have to apply two different strategies  depending on the flags that  are allowed to be removed per turn. I called it: 

 

Consecutive Removeable Flags solution

• Non-Consecutive Removeable Flags solution
• I will explain it further in below.

I create a class named FlagRemovalBrain.cs to generate the winning strategy , and following are the properties of this class

public List<int> FlagsThatCanBeRemove { get; set; }
public List<int> LosingStateFlagsNum { get; set; }
public bool UpperHandIfStartFirst { get; set; }
public int WinningCondition { get; set; }
public bool IsConsecutive { get; set; }
public bool IsCommonMultiple { get; set; }

FlagsThatCanBeRemove is flag/s that can be removed per turn.

 

LosingStateFlagsNum is flag/s that will cause user to lose if  left to this amount of flag/s during his/her turn to make a move (refer to part 1 for detailed explanation).

 

UpperHandIfStartFirst is one of the important enhanced features for this version, which the system will have an insight before the game starts by analyzing all the parameters, and will know whether by choosing to start first or second if you will have the upper hand in order to win the game.

 

Please take note that you may not necessarily win the game if you have the upper hand by starting first/later, but at least you will NEVER lost the game if you have the upper hand and make no mistake in every coming turn. On the contrary, your only hope to win or at least draw is to rely on your opponent to make at least 1 mistake if you do not start in the upper hand position.

 

WinningCondition is the how the game ends. The game ends and the players will lose if being left with only 1 remaining flag, then the value for this property is 1, 0 for 0 flag and so on.

 

IsConsecutive is a property if the removable flags per turn are all in consecutive order. For example, if the removeable flags per turn are [1, 2, 3], then it is in consecutive order. But, if the removeable flags are [1, 2, 4,] then it is not.

 

IsCommonMultiple is a property to tell if the removable flags per turn contain at least 2 numbers and have common multiplier. For example, if the removable flags per turn are [1, 2, 4 ], first of all it is not consecutive, and it has at least two numbers that share a common multiplier (2 and 4 share the same multiplier of 2). This property is important in solving the Non-Consecutive Removeable Flags scenario, which I will explain later.

 

I begin with discussing the solution for Consecutive Removeable Flags scenario

 

Consecutive Removeable Flags Solution

 

Let's say we have 21 flags initially, and the removeable flags per turn is [1,2,3], and finally the winning condition is 1 flag and ONLY 1 flag remained to opponent. So in the implementation , the value of those parameters looks like this

static void Main(string[] args)
{
    int[] FLAGS_TO_REMOVED = new[] {1,2,3 };

    const int STARTING_FLAGS = 21;
    const int WINNING_CONDITION = 1;

    PrintRules(STARTING_FLAGS, WINNING_CONDITION, FLAGS_TO_REMOVED);
    bool startFirst = true;

    string playAgain;
    do
    {
        GameStart(STARTING_FLAGS, WINNING_CONDITION, FLAGS_TO_REMOVED, startFirst);
        WriteLine("Play Again? Y/N");
        playAgain = ReadLine();
    }
    while (playAgain.ToUpper() != "N" );

Constructor will assign the properties values of the class, e.g. assign value for winning condition, check if it is consecutive etc.

public FlagRemovalBrain(int _WinningCondition, int StartingFlags, List<int> _FlagsThatCanBeRemove)
{
    IsConsecutive = !_FlagsThatCanBeRemove.Select((i, j) => i - j).Distinct().Skip(1).Any();
    FlagsThatCanBeRemove = _FlagsThatCanBeRemove;
    WinningCondition = _WinningCondition;
    IsCommonMultiple = !IsConsecutive && IfRemoveableContainCommonMultiple(FlagsThatCanBeRemove);
    (LosingStateFlagsNum, UpperHandIfStartFirst) = UpperHandAnalysis(IsConsecutive, StartingFlags);

    Console.WriteLine("Upper hand if {0}", UpperHandIfStartFirst ? "Start First" : "Start Second");
}

Please note that the UpperHandAnalysis method, which serves to generate winning strategy and, from the strategy generated, we will know that if we have upper hand by starting the game first or second.

public (List<int>, bool) UpperHandAnalysis(bool IsConsecutive,int StartingFlags)
{
    if(IsConsecutive)
    {
        return WiningStrategyForConsecutive(WinningCondition, StartingFlags, FlagsThatCanBeRemove);
    }
    else
    {
        return WiningStrategyForNonConsecutive(WinningCondition, StartingFlags);
    }
}

The UpperHandAnalysis method will decide which winning strategy method is to be called based on the IsConsecutive property. In this case, WiningStrategyForConsecutive method will be called.

public (List<int>, bool) WiningStrategyForConsecutive(int WinningCondition, int StartingFlags, IEnumerable<int> FlagsThatCanBeRemove)
{

    List<int> LosingStateFlagsNum = new List<int>();

    for (int i = WinningCondition; i <= StartingFlags; i++)
    {
        bool isLosingFlagStage = true;
        foreach (int item in LosingStateFlagsNum)
        {
            int num = i - item;

            if (FlagsThatCanBeRemove.Contains(num))
            {
                isLosingFlagStage = false;
                break;
            }
        }

        if (isLosingFlagStage)
            LosingStateFlagsNum.Add(i);
    }

    bool upperHandIfStartFirst = LosingStateFlagsNum.Max() != StartingFlags;
    return (LosingStateFlagsNum, upperHandIfStartFirst);
}

The winning strategy for consecutive is pretty simple

1. Get the losing scenario ( 1 in this case), and using backward deduction, get the “Losing State Num” (player who being left with these number of flag/s is lose)
2. For loop starts with 1, which also a losing state num, add it to the List.
3. Keep the increment, and find out that 2,3 and 4 are NOT losing state numbers, because whoever is left with these number of flags can remove [1,2,or 3] flag/s to leave his/her opponent with 1 flag.
4. Once we reach 5, we will find it is a “losing state number”, since removing [1,2,or 3] flag/s are unable to leave 1 flag to your opponent in the next turn.
5. So 5 (and 1 previously) will be added to the List of “losing state numbers”.
6. And the for loop continues until reaching 21 (the starting flags amount).

Please read my previous post for better understanding of this algorithm.

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

The C# decision to pull flags for the consecutive removeable flags solution is pretty simple,

public int PulledFlagDecisionConsecutive(int remainingFlags)
{
    int pulledFlag = 0;
    var remainingLosingStateFlagsNum = LosingStateFlagsNum.Where(x => x < remainingFlags).ToList();

    foreach (int item in remainingLosingStateFlagsNum)
    {
        int num = remainingFlags - item;
        if (FlagsThatCanBeRemove.Contains(num))
        {
            pulledFlag = num;
            break;
        }
    }
    if (pulledFlag == 0)
    {
        Random random = new Random();
        int index = random.Next(FlagsThatCanBeRemove.Count);
        pulledFlag = FlagsThatCanBeRemove[index];
    }
    return pulledFlag;
}

Computer only neesd one parameter, which is the current remaining number of flags, and removing the flag/s accordingly to ensure it left the opponent with “losing state number of flag/s “.

 

For this case, the losing state of number of flags are: [1, 5, 9, 13, 17, 21] , so, if current remaining flags is 20, computer will remove 3 flags to make sure its opponent has 17 flags left for his/her turn, remove 1 flag to make it 13, if the remaining flags is 14 and so on.

 

The console of the game will look like this,

 

 

 

By the way, users can choose to start first or later by changing the value of startFirst Boolean variable in the main class.

 

 

Non-Consecutive Removeable Flags Solution

 

For non-consecutive removeable flags solution, things are little bit more complicated, and non-consecutive solution can also split to TWO kind of solutions, which are,

• Common Multiplier Scenario
• Non Common Multiplier Scenario

I start with Non Common Multiplier Scenario.

 

So, consider the following scenario,

• starting flag : 21 flags,
• winning condition is 1 flag and ONLY 1 flag remained to opponent
• removeable flags [2 , 7] (2 and 7 share no common multiplier)

Since 2 and 7 are not consecutive, so  I need to get all possibilities from game start (21 flags) till reach the end game (1 flag remained). There are 20 from start to end (21 minus 1), so I need to find all the permutation of sum between 2 and 7 to get 20.

 

I found a code snippet from https://jaytaylor.com that enable me to doing so.

 

So, there are 11 different permutations for 2 and 7 to get 20

 

 

I include a console project called CheckCombination in my solution for the checking.

 

In my FlagRemovalBrain class, there is a method to store all these possible paths.

List<List<int>> ListOfPaths = GenarateAllPaths(remainingFlags - WinningCondition);

Each permutation list means every possibility  -- both players can remove the flags in the game. For example, 7,7,2,2,2 means first player takes 2 flags, then the second player takes 2 flags, then alternately 2 flags, 7 flags and 7 flags before reach 1 flag and end the game.

 

And from all the possible paths, the computer will choose the path with ODD number of count as winning condition. The rational of choosing ODD number of count is because whoever left with the last flag (in this example) is the loser, so the winner of this game is whoever FINSIHED THE LAST NUMBER of the path.

 

Let's assume now 12 flags remain, and the only possible path is 2,7,2 , and this list of path is ODD in count, so if you start your path with an ODD number of paths, you will secure the victory by removing 2 (2,7,2), and your opponent removes 7 (2,7,2) and you remove the final 2 (2,7,2), your opponent will be left with 1 flag (in this example remained 1 flag lost the game) and you win.

 

 

So we can say ODD is the key to victory.

 

(or choose EVEN number if the person takes the last flag wins, ODD or EVEN just depends how you design your logic, there is no special law that state that ODD must be the solution)

 

BUT, it does not mean we will secure a victory by choosing any ODD count of list of numbers, we still have to consider that the last number of ODD count list does not exist in the last number of EVEN count list.

 

 

From the above example, there are 11 permutations , where ten of them are odd counts of list of numbers (5) and one is even count (10), and the ODD count contains 2 and 7 as their last number, and EVEN contains only 2.

 

In order to secure the victory, we don't only need to choose the ODD count path, but also the last digit that only exists in ODD count list but not in EVEN count. In this case, it is 7, so we should choose odd count path that end with 7, whether 2,2,2,7,7, or 7,2,2,2,7 etc.

 

The reason is if we choose the list that ends with 2 (we hope the game end in this path [2,2,7,7,2] or [7,7,2,2,2] ) and expect our opponent to choose 7 in second or fourth turn so we can end the game accordingly, but we might faileto secure the victory if our opponent choose the EVEN count path [2,2,2,2,2,2,2,2,2,2] and finally will cause us a defeat. But, if we choose 7, all those remaining possibly path will lead us to our victory.

 

Following are the code snippets from PulledFlagDecisionNonConsecutive method that assigns last number of ODD count and EVEN count list of numbers to a different list, then compare both lists using Linq Except method to get the last number that only exist in ODD count. (if any)

foreach (List<int> list in ListOfArrays)
{
    if (list.Count() % 2 != 0)//get odd Count of list of integer
    {
        if (!WinningSelection.Contains(list[list.Count - 1]))
            WinningSelection.Add(list[list.Count - 1]);
    }
    else
    {
        if (!LosingSelection.Contains(list[list.Count - 1]))
            LosingSelection.Add(list[list.Count - 1]);
    }

    if (WinningSelection.Count == FlagsThatCanBeRemove.Count && LosingSelection.Count == FlagsThatCanBeRemove.Count)
        break;
}
List<int> uniqueList = WinningSelection.Except(LosingSelection).ToList();//get unique last digit

The above steps will continue until we get the victory.

 

Forced Stalemate

 

How will the program react if all the possible path is an even number? That means it will lose regardless of how it choose. Well, if that is the case , the program has two choices, hoping the opponent  makes at least one mistake, or, trying to forced a stalemate if there is a way.

 

Consider the following scenario,

• starting flag : 9 flags,
• winning condition is 1 flag and ONLY 1 flag remained to opponent
• removeable flags [2 , 5, 7]

So the target number is 8 and there is only one possible permutation,

 

 

 

If the program chooses 2, it will lose the game after four turns by it and its opponent choose 2 alternately for another three turns.

 

If the computer realizes that it is in the losing state, the ForceStaleMate method will be called and the program will try to force a stalemate, by choosing any other number (if any) from removeable flags to break the ‘predicable outcome’. In this case, it will choose 5 or 7, so the game will end as a draw. A draw is still better than losing the game.

 

Here is the code snippet of the ForceStaleMate method

public int ForceStaleMate(List<int> LosingSelection )
{

    List<int> StaleMateList =  FlagsThatCanBeRemove.Except(LosingSelection).ToList();
    if (StaleMateList.Count > 0)
    {
        StaleMateList.Sort();
        return StaleMateList[StaleMateList.Count - 1];
    }
    else
    {  //will lose anyway no matter choose what
        //only hope the opponent make a mistake in their turn
        Random random = new Random();
        return FlagsThatCanBeRemove[random.Next(0, FlagsThatCanBeRemove.Count)];
    }
}

And that’s all about solutions for Non Common Multiplier Scenario. Now I will move to the final part of this article, the solution for Common Multiplier Scenario.

 

Common Multiplier Scenario

 

Consider the following scenario,

• starting flag : 9 flags,
• winning condition is 1 flag and ONLY 1 flag remained to opponent
• removeable flags [2 , 4] (2 and 4 share common multiplier which is 2)

so the target number is 8 (9 minus 1), and the all possible permutations are , like following,

 

 

The last number of ODD count and EVEN count list of number are the same , both contain [2,4] , if we use the above mentioned logic for non common multiplier solution, the program will think that this is the losing situation, regardless of what number it chooses.

 

But it is not, since the removeable flags have at least two numbers which  share the common multiplier, we need to do an adjustment by summing up adjacent two numbers if the sum result exists in the list of removeable numbers.

 

In this case, we will add the adjacent numbers 2 from first, second and fourth row to become 4, since 4 is one of list removeable numbers for this example[2,4].

 

However, we will NOT add 2 and 4 to become 6, because 6 is NOT one of list of removeable numbers.

 

This is the code snippet of adding the two adjacent numbers and checking if those sum results exist in the list of removeable flags.

public List<int> SumTwoAdjacent(List<int> arr, List<int> ListToRemoved, out List<int> afterAdjustment)
{

    bool gotAdjIdentical = false;
    List<int> NewArr = new List<int>();
    for (int i = 0; i < arr.Count; i++)
    {
        if (i < arr.Count - 1 && arr[i] == arr[i + 1] && ListToRemoved.Contains(arr[i] + arr[i + 1]))
        {
            gotAdjIdentical = true;
            NewArr.Add(arr[i] + arr[i + 1]);
            i += 1;
            continue;

        }
        NewArr.Add(arr[i]);
    }
    afterAdjustment = NewArr;
    if (gotAdjIdentical)
    {
        SumTwoAdjacent(NewArr, ListToRemoved, out afterAdjustment);
    }
    return afterAdjustment;
}

 

So after adjustment, there is only ONE ODD count of list, which is [2,4,2], so the program can secure a victory by removing 2 for this turn, and regardless  of whether 2 or 4 are removed by its opponent in next turn, the program can secure the victory in the final turn.

 

You can have my full source code via GitHub.

 

Please let me know if you able to beat the program after you let it have the upper hand by starting the game first/second as it has claimed. You should not, since my goal is to create an unbeaten flag removal program.