Tuesday 31 January 2012

Waterloo Game Analysis

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:

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:

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:
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.


2 comments:

  1. Hi Andrea,
    This 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);
    }

    ReplyDelete
    Replies
    1. Hi Ian.

      Thank you very much for your comment. I really appreciate this kind of feedback.

      I think that your solution is pretty elegant.

      Regards

      Delete

What you think about this post? I really appreciate your constructive feedback (positive and negative) and I am looking forward to start a discussion with you on this topic.