Taking Apart The NES Version of Tetris

January 28, 2014

I just came across this article which digs through the actual code of the original NES version of Tetris and then creates an AI to play it.


Dreaming Tetris

September 12, 2013

Fascinating. Dr. Robert Stickgold found that amnesiacs will dream about Tetris (aka The Tetris Effect) even though they do not remember playing the game.


Playing Tetris Forever

August 2, 2013

Somehow I had previously overlooked this excellent page on methods for playing Tetris forever.


Move Notation System For Tetris

December 23, 2012

Chess has had standard notations for a long time. Isn’t it time that Tetris had one as well?


Pioneer Spacecraft and Data Preservation

December 20, 2012

The newest IEEE Spectrum has a nice article on debugging a data anomaly with the Pioneer 10 and Pioneer 11 spacecraft. It is a short and interesting read – one of the key issues was the need to review many years of historical data retrieved from a variety of physical media formats.


WF3 Types Deprecated In .NET 4.5

December 16, 2012

As you are no doubt aware, .NET 4.5 shipped in October.

With the release of 4.5, our team has deprecated the original Workflow engine aka WF3 (System.Workflow, etc.). There is a detailed announcement from Jurgen on the team blog.

The types are marked deprecated but have not been removed. Using the types will result in build warnings, but the types may still be used. However, they will be removed in some future release.

I also want to point out that the types related to the WF Rule Engine are not marked as deprecated.

Full details of items marked obsolete in 4.5 can be found here.


Finding duplicate copies in msbuild logs

April 1, 2012

I have recently needed to track down some build races due to duplicate file copies. The build in question is MSBuild-based.

I found this tool provided by co-worker Buck Hodges to be very helpful.

I ran into one issue with the tool – it does not handle node names that contain colons, such as “152:3”. One cause of such node names is when the same project is built multiple times. So, I made some changes to the code to support these node names.

I also rewrote the output logic to group the violations according to the file being copied. This is very handy when you have more than 2 projects racing on the same file since the original tool would report a race for projects A & B and B & C, but not A & C.

Here is the updated source code with my modifications. Big thanks to Buck Hodges for the original!

using System;
using System.Collections.Generic;
using System.IO;
using System.Text.RegularExpressions;

/*
 * Original code taken from:
 * http://blogs.msdn.com/b/buckh/archive/2012/01/21/a-tool-to-find-duplicate-copies-in-a-build.aspx
 * 
 * Modified to support node names that contain colons and to group the output by race.
 *
 * This tool finds cases where more than one file is copied to the same target.  This will cause
 * build breaks when msbuild executes the copies in parallel because the copies are independent
 * (there are no dependencies).  This typically occurs in incremental builds because incremental
 * builds do a lot less work (not nearly as much to build), resulting in the copies being a much
 * higher percentage of the build activities and more likely to collide.  Gated checkin,
 * continuous integration, and developer/tester builds are almost always incremental, not clean.
 * These issues are still possible in regular clean builds, such as done nightly by the build lab.
 * 
 * These race conditions are difficult to debug manually.  Since msbuild records all of the copies
 * made via the copy task, we can use the log file to identify cases where the same destination
 * path is used in more than one copy.
 * 
 * Use the *.normal.* logs from a clean build with this tool.
 * 
 * The best thing to do is to ensure that each file copy to a particular destination is done by
 * one and only one project.  When that is the case, you are guaranteed not to have problems
 * with two copies colliding and breaking your build.
 * 
 * Here's example output from buildr.suitesrc.normal.log that shows a copy failure.  Here two
 * copies were executed in parallel and the second one failed, causing the build to fail.
 * 
    48>Project "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\dirs.proj" (48) is building "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\Azure\Microsoft.TeamFoundation.Data.Azure.csproj" (55) on node 8 (BuildLinked target(s)).

    55>_CopyOutOfDateSourceItemsToOutputDirectory:
         Copying file from "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\ReleaseManifest.xml" to "D:\a1\binaries.x86ret\bin\i386\ReleaseManifest.xml".


    48>Project "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\dirs.proj" (48) is building "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\SqlServer\Microsoft.TeamFoundation.Data.csproj" (53) on node 4 (BuildLinked target(s)).

    53>_CopyOutOfDateSourceItemsToOutputDirectory:
         Copying file from "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\ReleaseManifest.xml" to "D:\a1\binaries.x86ret\bin\i386\ReleaseManifest.xml".

    53>D:\a1\dd\tools\x86\managed\v4.5\Microsoft.Common.targets(3516,5): error MSB3021: Unable to copy file "D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\ReleaseManifest.xml" to "D:\a1\binaries.x86ret\bin\i386\ReleaseManifest.xml". Access to the path 'D:\a1\binaries.x86ret\bin\i386\ReleaseManifest.xml' is denied. [D:\a1\dd\alm\tfs_core\Admin\Servicing\Data\SqlServer\Microsoft.TeamFoundation.Data.csproj]
  
 * 
 * Note that there may be multiple copies in a sequence.
 * 
    291>_CopyOutOfDateSourceItemsToOutputDirectoryAlways:
         Copying file from "D:\a1\dd\suitesrc\TFS\common\deploytools\httpcfg.exe" to "D:\a1\binaries.x86ret\SuiteBin\i386\TFS\Tests\httpcfg.exe".
         Copying file from "D:\a1\dd\suitesrc\TFS\common\deploytools\makecert.exe" to "D:\a1\binaries.x86ret\SuiteBin\i386\TFS\Tests\makecert.exe".
         Copying file from "D:\a1\dd\suitesrc\TFS\common\deploytools\winhttpcertcfg.exe" to "D:\a1\binaries.x86ret\SuiteBin\i386\TFS\Tests\winhttpcertcfg.exe".
       CopyFilesToOutputDirectory:
         Copying file from "D:\int\641\194\suitesrc\tfshttpsconfig.csproj_80399372\objr\x86\TfsHttpsConfig.exe" to "D:\a1\binaries.x86ret\SuiteBin\i386\TFS\Tests\TfsHttpsConfig.exe".

 * Nodes are reused by msbuild.  The result is that a given node may process many projects, so it's not
 * possible to scan and pair up all of the nodes and project files at once.  In the code below, 
 * you will see that it always tracks the most recent node for that reason.
 * 
 */

namespace FindBadCopies
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length < 1)
            {
                Console.WriteLine("Usage: findbadcopies <logfile>\r\n");
                Console.WriteLine(
@"This tool scans a build log, such as buildr.suitesrc.normal.log, and produces a
list of file paths that are the targets of more than one copy and shows which
project files initiated each copy.  These redundant file copies are prone to
fail periodically in incremental builds, such as gated check ins and CI builds,
because copies are a higher percentage of the operations in the build, making
it more likely that two collide.");

                return;
            }

            ProcessFile(args[0]);
        }

        private static void ProcessFile(String fileName)
        {
            Dictionary<String, String> nodeTable = new Dictionary<String, String>(1000, StringComparer.InvariantCultureIgnoreCase);
            Dictionary<String, String> pathTable = new Dictionary<String, String>(1000, StringComparer.InvariantCultureIgnoreCase);
            Dictionary<String, HashSet<String>> duplicateTable = new Dictionary<String, HashSet<String>>(StringComparer.InvariantCultureIgnoreCase);
            String previousLine;

            string[] text = File.ReadAllLines(fileName);

            // Process all of the lines in the file, skipping the first line (we need the previous line,
            // and the first line in the file isn't important to this tool).
            string lastNode = String.Empty;
            for (int i = 1; i < text.Length; i++)
            {
                previousLine = text[i - 1];

                // Record most recent node.  The text that appears with it can be different
                // (see sample log data).
                string prevLinePattern = @"([0-9]+\:?[0-9]*)[>]";
                Match match = Regex.Match(previousLine, prevLinePattern, RegexOptions.IgnoreCase);
                if (match.Success)
                {
                    lastNode = match.Groups[1].Value;
                }

                // If the line is recording the start of a project, add it to the table.
                string pattern = @"([0-9]+\:?[0-9]*)[>]Project ""[^""]+"" \([0-9]+\:?[0-9]*\) is building ""([^""]+)"" \(([0-9]+\:?[0-9]*)\)";
                match = Regex.Match(text[i], pattern, RegexOptions.IgnoreCase);
                if (match.Success)
                {
                    string node = match.Groups[3].Value;
                    String projectPath = Path.GetFullPath(match.Groups[2].Value);

                    // Because nodes are reused, we are only keeping the project path for the most recent use
                    // of a given node.
                    nodeTable[node] = projectPath;

                    // If we matched a project line, it can't be a copy line.
                    continue;
                }

                // If the line is one that records a copy, see if there was an earlier copy made to
                // the same target path.  First, try the output of a copying task.
                string copyingPattern = @"Copying file from ""[^""]+"" to ""([^""]+)""";
                match = Regex.Match(text[i], copyingPattern, RegexOptions.IgnoreCase);
                if (match.Success)
                {
                    String targetPath = null;
                    try
                    {
                        targetPath = Path.GetFullPath(match.Groups[1].Value);
                    }
                    catch (Exception)
                    {
                        // There is a file in the test tree that uses non-English chars that causes
                        // GetFullPath() to throw (TODO: understand why), so we keep the raw text.
                        targetPath = match.Groups[1].Value;
                    }

                    // If we have already seen the target path, 
                    // then we have a duplicate copy path target to report.
                    String otherNode;
                    if (pathTable.TryGetValue(targetPath, out otherNode))
                    {
                        HashSet<String> otherNodes;
                        if (duplicateTable.TryGetValue(targetPath, out otherNodes))
                        {
                            otherNodes.Add(nodeTable[lastNode]);
                        }
                        else
                        {
                            HashSet<String> nodeList = new HashSe<String>();
                            nodeList.Add(nodeTable[otherNode]);
                            nodeList.Add(nodeTable[lastNode]);
                            duplicateTable[targetPath] = nodeList;                   
                        }
                    }
                    pathTable[targetPath] = lastNode;
                }
            }

            foreach(KeyValuePair<String, HashSet<String>> kvp in duplicateTable)
            {
                Console.ForegroundColor = ConsoleColor.Cyan;
                Console.WriteLine("Duplicate file: {0}", kvp.Key);
                Console.ResetColor();

                foreach(String project in kvp.Value)
                {
                    Console.WriteLine("      Project: {0}", project);
                }
                if (kvp.Value.Count == 1)
                {
                    Console.WriteLine("      (A single project listing means that this project performed multiple copies of the same item.)");
                }
                Console.WriteLine();
            }
        }
    }
}

Pac-Man, How Does It Work?

December 8, 2010

Speaking of game AI…two Pac-Man-related links are making the blog rounds these days – one of them is new.

The new one is Chad Birch’s “Understanding Pac-Man Ghost Behavior”. It is clear and well illustrated.

As Chad points out, he was inspired by and used Jamey Pittman’s “Pac-Man Dossier”. This is a nice resource.

It also seems that I haven’t previously blogged Don Hodges’ fix to a bug in the behavior of two of the ghosts. (The bug-fixing of classic videogames is a topic we will return to in the future.)

Of course, the ghosts need a Pac-Man to chase. I have previously linked to a Ms. Pac-Man computer player competition. Of specific interest is this paper on evolving rules to play Ms. Pac-Man (seems that I have not directly linked it before).

(Post title is of course a play on the “magnets…” meme.)


Detecting Poker Bots

December 7, 2010

The folks at the PokerStars online poker service actively police their games to make sure that bots are not being used to gain advantage.

Here’s a recent post from their Game Security staff demonstrating that they paid a visit to one player in order to witness the playing and playstyle in person.

It ends with the following wonderful quote:

We are pleased to report, however, that ‘rs03rs03’ is human.

(I also thought JWZ’s take on it was amusing. But you would need to have read Neuromancer to get it.)


WF Rules: Unleashing The Rule Engine Within .NET

October 18, 2010

I have written previously about WF Rules, the rule engine that ships in .NET. As I have described, this rule engine is bundled in .NET versions 3.0 and higher, and is included in the default installation of Windows Vista and Windows 7. (If you are using .NET 4.0, you need the Extended / Full install – the WF Rules assemblies are not in the Client install.)

Getting Access To WF Rules
The average rule author who is looking to try out WF Rules will ask where to start. At they point, they may become lost in the sea of WF documentation or find that they are told to use Visual Studio, which they may not even have installed. It is indeed the case, that WF Rules is typically used as part of Windows Workflow Foundation, and the rules are typically authored within Visual Studio. However, WF Rules can also be used without Visual Studio or Workflow Foundation if one is willing to read through the documentation, download some samples and write a bit code.

A Simple Example
Inspired by a co-worker, I have put together this quick example to lower the barrier to entry a bit. This is a very bare-bones example in order to highlight the rule-specific code that is needed to utilize WF Rules without Visual Studio or Workflow Foundation. So, the code will not feature command-line arguments, a mutable file name, factoring for re-use, etc. (If you are reading this, you most likely already know how to do those things in C#.) The emphasis here is upon demonstrating the scenario with the minimum amount of code. You should be able to paste these three code snippets into three files and have a working example.

The Target Type
In order to author rules, we require a target type to write the rules against. Let’s start with a simple data class:

using System;

class Person
{
  double age;
  public double Age { 
    get
    {
      return age;
    }
    set
    {
      age = value; 
    }
  }
}

For this example, I placed this code in a file named Person.cs. You may choose to place this type within the same file as the other code below. As I said, this example is geared for simplicity.

The RuleSetDialog
Now, let’s write some short code that will instantiate the RuleSetDialog and allow us to author a rule. This code needs to do three things:

  1. Open an existing or create a new .rules file – the WorkflowMarkupSerializer is used if we load an existing RuleSet
  2. Instantiate the RuleSetDialog, while supplying the target type
  3. Save the .rules file if the rules have been updated – using the WorkflowMarkupSerializer

Here is a minimal program to do this:

using System;
using System.IO;
using System.Windows.Forms;
using System.Workflow.Activities.Rules;
using System.Workflow.Activities.Rules.Design;
using System.Workflow.ComponentModel.Serialization;
using System.Workflow.Runtime;
using System.Xml;

class Program
{
  static string filename = "Test.rules";

  static void Main()
  {
    RuleSet ruleset = null;
	
    // Obtain or create ruleset
    if (File.Exists(filename))
    {
      // load file
      ruleset = Load(filename);
    }
    else
    {
      ruleset = new RuleSet();
    }

    RuleSetDialog dialog = new RuleSetDialog(typeof(Person), null, ruleset);
    DialogResult result = dialog.ShowDialog();

    if (result == DialogResult.OK)
    {
      // save the file
      Save(filename, dialog.RuleSet);
    }
  }

   static RuleSet Load(string filename)
  {
    XmlTextReader reader = new XmlTextReader(filename);
    WorkflowMarkupSerializer serializer = new WorkflowMarkupSerializer();
    object results = serializer.Deserialize(reader);
    RuleSet ruleset = (RuleSet)results;

    if (ruleset == null)
    {
       Console.WriteLine("The rules file " + filename + " does not appear to contain a valid ruleset.");		
    }
   return ruleset;
  }

  static void Save(string filename, RuleSet ruleset)
  {     
    XmlTextWriter writer = new XmlTextWriter(filename, null);
    WorkflowMarkupSerializer serializer = new WorkflowMarkupSerializer();
    serializer.Serialize(writer, ruleset);
    Console.WriteLine("Wrote rules file: " + filename);
  }
}

Authoring A Simple Rule
You will need to save each of these files before you can compile them – for example, I named them Person.cs and RuleEditor.cs.

Now we need to compile these files. You will typically find the C# compiler wherever your .NET installation is, for example:
C:\Windows\Microsoft.NET\Framework\v2.0.50727\csc.exe

Let me emphasize this – you don’t need Visual Studio for this example. If you have .NET on your machine, you should have the C# compiler already available.

If you saved the files as Person.cs and RuleEditor.cs and pass them to the compiler at the same time, you should end up with RuleEditor.exe – which we can then use to author a rule against a Person. Depending upon your environment settings, you may need to provide the following reference assemblies to the compiler at the same time: System.Workflow.Activities.dll, System.Workflow.ComponentModel.dll, and System.Workflow.Runtime.dll.

Now you should be able to execute RuleEditor.exe and author a rule such as this (click the picture to see full details):
Creating a simple rule in the rule editor dialog

Firing The Rules
Once we have our example rule authored, we need a simple program to load the ruleset and call the rule engine so we can fire the rules. (Note that the code here for loading the ruleset is the same as above.)

using System;
using System.IO;
using System.Workflow.Activities.Rules;
using System.Workflow.ComponentModel.Serialization;
using System.Workflow.Runtime;
using System.Xml;

class Program
{
  static string filename = "Test.rules";

  static void Main()
  {
    RuleSet ruleset = null;

    Person person = new Person();
    person.Age = 70;
		
    if (File.Exists(filename))
    {
      // load file
      ruleset = Load(filename);
    }
	
    if (ruleset != null)
    {
      RuleValidation validation = new RuleValidation(person.GetType(), null);
      RuleExecution engine = new RuleExecution(validation, person);
      ruleset.Execute(engine);
    }
  }

  static RuleSet Load(string filename)
  {
    XmlTextReader reader = new XmlTextReader(filename);
    WorkflowMarkupSerializer serializer = new WorkflowMarkupSerializer();
    object results = serializer.Deserialize(reader);
    RuleSet ruleset = (RuleSet)results;

    if (ruleset == null)
    {
      Console.WriteLine("The rules file " + filename + " does not appear to contain a valid ruleset.");		
    }
    return ruleset;
  }
}

This program should build much the same as the previous program. You will need to include the Person class again. In a real application, we would factor the business objects into a shared library.

Closing
I hope that this bit of code has demonstrated how readily WF Rules can be used by itself. I find it neat to see a rule engine included in a default OS installation.

Resources