Farkle AI Part 3: Is This Really Random?

It never even occurred to me that the generation of random numbers would become an issue within my Farkle core logic.  I knew that when you created a new System.Random object and used the default constructor, the current time would be the initial seed.  While this is perfectly fine for a mobile app (where only one game is played), this runs into problems for massive simulations.  Turns out (and it makes perfect sense) that when you create two System.Randoms within 15 ms of each other, they are both given the same seed.  Doh!  I was lucky because I knew from experience that if you need a Random object, you create it as a testable service and pass it to anything requiring a random number.  For me, that was my Farkle table’s die roller.  Thus, each game only had one random number generator.  However, each game created its own random.  So it turns out that during my simulations, for several games in a row, the dice were given the same seed!  This meant that the outcomes and scores of my games were exactly the same for a small game span.  In the output below, I printed out the first die rolled of each game.  The trend is disturbing.

NaiveRNGOutput

After some thought, I devised a solution.  I would just bite the bullet and make my Random Number Generator a singleton so that I would only have one throughout the entire simulation.  This didn’t work.  When I tried to run large simulations, the program would hang.  What was going on?  After some research, (Thank you StackOverflow) I discovered that Random.Next() is not thread safe and if threads placed successive calls too close together, Next() would just return 0.  Due to my recent parallelization, I now had each game running on a separate thread.  So, I had to devise a new solution.  SO to the rescue again!  An excellent answer in the thread http://stackoverflow.com/questions/3049467/is-c-sharp-random-number-generator-thread-safe provided me with the ability to create a thread safe random number generator.  The solution is to create a static Random object variable of the RandomNumberGenerator class.  This variable will persist throughout instances of the ThreadSafeRandomNumberGenerator.  Then, this Random’s .Next() method will determine the initial seeds of each local Random object (attribute ThreadStatic).

public class ThreadSafeRandomNumberGenerator : IRandomNumberGenerator
{
    private static readonly Random _global = new Random();
    [ThreadStatic] private static Random _local;

    public ThreadSafeRandomNumberGenerator()
    {
        if (_local == null)
        {
            int seed;
            lock (_global)
            {
                seed = _global.Next();
            }
           _local = new Random(seed);
        }
    }

    public void SetSeed(int seed)
    {
        _local = new Random(seed);
    }

    public int Calculate(int minimumValue, int maximumValue)
    {
        return _local.Next(minimumValue, maximumValue);
    }
}

Now, the first die rolled of each game is truly (you know what I mean) random.

ThreadSafeRNGOutput

I decided that for now I’d change the setup in my IoC Container so that the thread safe random number generator is used instead of my normal one.  For a finished app, I’ll probably switch back to the regular one, even though it really shouldn’t matter.

Farkle AI Part 2: Parallelization

My Farkle AI core logic is not fast.  I can’t say I really know how much of an impact modern OOP patterns (such as Inversion of Control) have on performance.  When I took a graduate class on parallel programming, I distinctly remember completing a project (a system of linear equations solver using the conjugate gradient method) using basic OOP principles.  The result was orders of magnitude slower than the instructor’s C-style solution.  While this taught me to always remain aware of performance issues within my code, there are many instances when performance doesn’t matter (or when I don’t care).  My Farkle AI is a case of the latter.

Despite this fact, I still didn’t want to wait all day when running AI simulations.  Therefore, I decided to investigate parallelizing my simulation runner.  Plus, this meant I got to use some skills I learned from the aforementioned class.  Writing parallel code in OpenCL or CUDA can get quite complicated.  This is where the power of .Net really shows.  My serial for loop was something like the following:

void SimulateAIGames(int numberOfGames)
{
    for (var n = 0; n < numberOfGames; n++)
    {
        var winner = PlayGame();

        if (winner == 0)
        {
            _player1Wins++;
        }
        else if (winner == 1)
        {
            _player2Wins++;
        }
    }
}

Parallelization in .Net literally took me 2 minutes.  (Who knows how long a comparable parallelization would take in OpenMP or OpenCL…)

SimulateAIGamesParallel(int numberOfGames)
{
    Parallel.For(0, numberOfGames, n => RunSimulation(n));
}

void RunSimulation(int n)
{
    var winner = PlayGame();

    if (winner == 0)
    {
        _player1Wins++;
    }
    else if (winner == 1)
    {
        _player2Wins++;
    }    
}

However, all was not well.  I immediately noticed that when I ran a simulation with a large number of games, the total number of wins did not equal the number of games played.  For a 100,00 game simulation, I was missing results for almost 1000 games!  After a quick think, I realized I was having access issues.  While I correctly created all my objects for a game within the PlayGame() method (thus making local variables for each thread), I failed to realize that _player1Wins and _player2Wins could have instances when multiple threads would need access.  Thus, I would occasionally lose the increment.

My solution was to allocate an int[] of length numberOfGames and assign the winner to each game index.  This would eliminate any conflicting memory requests.

void RunSimulation(int n)
{
    var winner = PlayGame();

    _winnerOfGames[n] = winner;   
}

The results of my parallelizations were comforting.  I saw the runtime of simulations decrease by roughly 40% (gotta love my dual-core laptop).  These results are consistent with Amdahl’s Law.  Now it only takes me an hour to run a 1 million game simulation between 2 AIs…

Farkle AI Part 1: Initial Investigations

Life as a second semester senior is quite enjoyable.  My workload is optimal: sparse but fascinating.  Thus, in my downtime I try to stay busy.

Last semester, my project of choice was a Chess PGN Viewer App.  It’s been an ongoing project since the summer of 2013 and helped launch my discovery and understanding of advanced programming concepts.  However, the next summer, I came to a realization.  Even though the app was close to publication, I had to rewrite it.  I had learned so much about proper Object-Oriented Design, such as SOLID and TDD, that I couldn’t continue writing an app when my core logic blatantly violated every principle in the book.

However principled the rewrite might be, it has been painfully slow.  Even though I know my old logic was correct (due to the simple unit tests I had written), I still wanted to test all of my logic using proper tests, e.g. using mocked objects.  The experience of reformulating the domain and writing unit tests has been extremely informative, albeit tedious.  Over the past semester, I’ve grown tired of spending hours to create the perfect mocked scenario for a single test.  Therefore, I decided I wanted to work on something a little less complex.

If told she could only play one game for the rest of her life, my mother would choose Farkle.  I mistakenly introduced it to her as a Christmas gift many years ago and it has since become our signature family game.  As a chess player, I can’t stand it.  As Farkle is a game of odds, you can employ the perfect strategy and still get destroyed.  However, what Farkle lacks in pure strategy, it makes up for in ease of modelling.

I’ve played enough Farkle to have a good sense for the best strategy possible.  Going off of my inclinations, I flow-charted a simple AI that can choose which dice to hold, given the necessary information, e.g. the rolled dice, current turn score.

flowchart
Naive Farkle AI Flow Chart

 

I did some research online to figure out if anyone had hashed out the optimal Farkle strategy.  On his blog, Matt Busche wrote an excellent analysis on Zilch (a variant of Farkle) where he calculated the expected value of a turn.   He subsequently posted a strategy generator for the game that computes an optimal strategy table, dependent on the scoring rules used.  Despite the fact that my family plays with an uncommon scoring scheme, I was able to use Matt’s generator to determine that the expected value of a normal Farkle turn was 542.

Once I implement the simple AI I devised, it will be interesting to see how it compares to the optimal strategy.  However, as Matt notes, his strategy just maximizes your score per turn, not number of wins in a series of games.

 

Sending an Email in a Unity Game for Windows Phone

Creating a game using Unity can be tricky.  Even though scripting in C# is allowed, Mono does not provide the complete experience that .Net does.  Thus, I frequently find that some tasks have to be outside the Unity game project.  One such task is sending an email.

Here’s a little bit of background.  A consumer of a game (Craps Alone) I helped produce for High Iron Software found a bug that completely crashed the game and prevented resumption without a complete re-installation.  While I was certain the bug was related to the serialization process used for saving game data, I could not reproduce the issue.  Therefore, I could only solve the symptom (the inability to relaunch the game), but not the root problem.  To help me figure out where exactly the error was occurring, I decided that when an exception occurs, the app should prompt the user to send an email to support with the details of the exception.  While this is easy enough on the Windows Phone side, Unity’s use of Mono does not make things straightforward.  I’ve found the solution to this and similar issues lies in creating an EventHandler and subscribing to it in the deployed Visual Studio solution.

Within my Unity project, I have a static class that acts as a mediator between my Unity scripts and the XAML/C# Windows Phone 8/8.1 framework.

public static class WindowsStatics
{
    public static event EventHandler OpenEmail;
 
    public static void FireOpenEmail(EmailContent content)
    {
        if (OpenEmail != null)
        {
            OpenEmail(content, null);
        }
    }
}

Originally, I planned on automatically copying the exception stacktrace to the user’s clipboard for pasting within the email.  However, I quickly realized the email recipient, subject, and body can be auto-populated.  When an exception is thrown, I create an EmailContent object, which possesses strings for “To”, “Subject” and “Body”.  Now, in MainPage.xaml.cs in the Windows Phone app project, I subscribe to the event.

// Constructor
public MainPage()
{
    WindowsStatics.OpenEmail += WindowsStatics_OpenEmail;
}

public void WindowsStatics_OpenEmail(object sender, EventArgs e)
{
    var content = (EmailContent)sender;
    var ect = new Microsoft.Phone.Tasks.EmailComposeTask 
              {
                  To = content.To,
                  Subject = content.Subject,
                  Body = content.Body 
              };
    ect.Show();
}

When Show() is called on an EmailComposeTask, the Mail app is launched and automatically populates the given fields.  All the user has to do is touch the send button.

Now, the creating an email within my Unity game is simple.  Constructing a string of an exception’s stacktrace is as easy as calling ToString().

void SendEmailForException(Exception e)
{
    var emailContent = new EmailContent
    {
        To = "support@highironsoftware.com",
        Subject = "Error Report: An exception was thrown during state restore",
        Body = e.ToString()
    };

    WindowsStatics.FireOpenEmail(emailContent);
}