21 Flags Game Theory Puzzle: Dynamic generate unbeaten (hopefully) flag removal program with C# (Part 3)

For previous post, please have a read on

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

21 Flags Game Theory Puzzle: Multiple unbeaten flag removal program with C# Delegates (Part 2)

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

During the development, I discovered that I have to apply two different strategy, depends on the flags that 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

FlagsThatCanBeRemove is flag/s that can be remove per turn

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

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

Please take note that you may not necessary to win the game if you have the upper hand by start 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 rely on your opponent make at least 1 mistake if you do not start in upper hand position

WinningCondition is the how the game end, if game will end (player will lose if being left with) if only remain 1 flag, then the value for this property is 1, 0 for 0 flag and so on.

IsConsecutive is a property that 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 contains at least 2 number 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 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 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 are looks like this

Function GameStart will also initialize the FlagRemovalBrain class , as well as the constructor to analysis the game situation

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

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

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

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 start with 1, which also a losing state num, add it to the List.
3. Keep the increment, and will find out 2,3 and 4 are NOT losing state numbers, because whoever being left to these number of flags can remove [1,2,or 3] flag/s to let his/her opponent with 1 flag.
4. Once we reach 5, we will find it is a “losing state number”, since remove [1,2,or 3] flag/s are unable to left 1 flag to your opponent in next turn.
5. So 5 (and 1 previously) will be added to the List of “losing state number”.
6. And the for loop continue until reach 21 (the starting flags amount)

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

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

The c# decision to pull flag for consecutive removeable flags solution is pretty simple:

Computer only need one parameter, which is the current remaining number of flags, and remove 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 have 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 game will look like this

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

Non-Consecutive Removeable Flags solution

For non-consecutive removeable flags solution, things are little bit 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 the I need to get all possibility 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 path

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

And from all the possibilities path, 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 loser, so the winner of this game is whoever FINSIHED THE LAST NUMBER of the path.

Let assume now remained 12 flags, 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 ODD number of path, you will secured the victory by remove 2 (2,7,2), and your opponent remove 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 take the last flag win, 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 secured victory by choosing any ODD count of list of numbers, we still have to consider the last number of ODD count list does not exist in last number of EVEN count list.

From 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 not only need to choose the ODD count path, but also the last digit that only exist 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 failed to 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 snippet from PulledFlagDecisionNonConsecutive method that assign last number of ODD count and EVEN count List of number to different list, then compare both list using Linq Except method to get the last number that only exist in ODD count. (if any)

Above steps will continue until we get the victory.

Forced Stalemate

How will the program react if all the possibility path is even number? Which means it will lost regardless how it choose. Well, if that is the case , the program have two choices, hoping the opponent to make at least one mistake, or, try 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 choose 2, and it will lost the game after four turns by it and its opponent choose 2 alternately for another three turns.

If the computer realize 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 Draw. Draw is still better than losing the game.

Here is the code snippet of the ForceStaleMate method

And that’s all about solution 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 contains [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 what number it choose.

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

In this case, we will sum adjacent number 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 sum 2 and 4 to become 6, because 6 is NOT one of list of removeable numbers.

This is the code snippet of sum the two adjacent numbers and check if those sum results exist in the list of removeable flag.

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 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 has the upper hand by starting the game first/second as it has claimed. By right you should not, since my goal is to create an unbeaten flag removal program.