Tonight, just for fun, I wanted to create a piece of software that enumerate all the possible combinations and find the move with the highest probability of win (one Nash Equilibrium).
I created it using a simple C# console application.
First of all, I created a function that returns a list of all possible moves for each player (the funniest part):
The implementation of the Win extension method:
This is the output of the basic example:
Using total = 15 and n = 5 the result is:
The Waterloo game use total = 100 and n = 5. With these numbers the code is too slow to terminate but you can easily guess that the result will be (20, 20, 20, 20, 20).
If you are curious about the total number of possible moves in Waterloo I can tell you this with the following code. The code analyse a specific Waterloo move telling you what is the probability of win in addition to the total number of moves.
The output:
The move (20, 20, 20, 20, 20) is the "best move" in terms of probability. However, if you play against a human being it is probably easier to come up with a solution like (33, 33, 34, 0, 0) or (34, 34, 11, 11, 10). In both the cases, if you use the "best move" you lost.
Let's see the result using (33, 33, 34, 0, 0):
Let's see the result using (34, 34, 11, 11, 10):
Arrived at this point I feel a little bit lost. What is the best solution?
Probably there are more Nash Equilibrium's and the solution should be a probabilistic strategy instead of a simple move.
Let's see what will be the result of the research.
If you want to learn more about Game Theory, you can watch this introduction course taken from the Artificial Intelligence class:
https://www.ai-class.com/course/video/videolecture/164
You can find the full source code in my personal repository: Waterloo Game
UPDATE: Code from IanS
IanS proposed a recurvise implementation of the "combinations" algorithm. It it probably slower then mine (it is a recursive algorithm) but has the advantage of readability. This solution has the interesting property of not using any explicit assignments or increment operations.
Thank you Ian for your feedback.
Hi Andrea,
ReplyDeleteThis is an interesting game! I tried writing a recursive alternative to your Combinations method... (Hopefully this will display OK in comments)
using TroopDeployment = System.Collections.Generic.IEnumerable;
...
static IEnumerable EnumerateDeployments(int availableTroops, int numberOfBattlefields)
{
if (numberOfBattlefields == 1)
{
yield return AsEnumerable(availableTroops);
}
else if (numberOfBattlefields > 1)
{
foreach(int troopsInFirstField in RangeFromToInclusive(0, availableTroops))
{
foreach (TroopDeployment troopsInOtherFields in EnumerateDeployments(availableTroops - troopsInFirstField, numberOfBattlefields - 1))
{
yield return AsEnumerable(troopsInFirstField).Concat(troopsInOtherFields);
}
}
}
}
static IEnumerable AsEnumerable(T obj)
{
yield return obj;
}
static IEnumerable RangeFromToInclusive(int start, int end)
{
return Enumerable.Range(start, 1 + end - start);
}
Hi Ian.
DeleteThank you very much for your comment. I really appreciate this kind of feedback.
I think that your solution is pretty elegant.
Regards