Microsoft created the Facebook Game Waterloo in order to do some research on game theories.
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):
After that, for each pair of moves, I calculated the number of wins and finally get the better move.
The implementation of the Win extension method:
and the main body:
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.
So, the total number of moves is 4598126 !!!
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:
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.