The Good News

You might have heard, Visual Studio 2010 is done, launched, and out the door! That’s right, after several short years F# version 1.0 is generally available! While it’s been alive and well in CTP form for many years, now you can go to the store and buy it. This doesn’t just mean that F# is easier to obtain. It marks a significant step in the language’s evolution; by shipping it in a officially supported release F# is a real product and is backed by Microsoft for at least the next decade.

I’m super excited about the release and look forward to F# taking off. It has already far surpassed my expectations in awesomeness, adoption, and excitement. If you are reading this blog then you are probably an F# enthusiast and none of this would have been possible without your support. So really, you should be just as proud as me.

The Sad News

However, for me at least, the excitement and buzz of the Visual Studio 2010 launch will be short lived. Earlier this month I’ve accepted a position at another software company and will be leaving Microsoft. My departure will no doubt raise the average IQ of both companies.

I first started working at Microsoft in 2002 as an intern, and since then I have shipped three versions of Visual Studio, filed a few patents, and even managed to have dinner at Bill Gate’s house. Working at Microsoft has been a fantastic experience and I have nothing but fond memories for my time spent here. However, having worked at Microsoft since before I graduated college I’m eager to try something new. So this Friday I’ll be packing up my belongings and exploring not-necessarily-greener-but-certainly-different pastures.

How will this impact the F# team? Well, without their weakest link I think the team will do just fine.

However, I will still be part of the F# community and you will definitely see a second edition of Programming F# when the time comes.  In fact, next Tuesday 4/20 I’ll be giving a talk: Writing a Java to x86 Compiler in F# at 11:00AM PST. If you have that time free watch it LIVE over LiveMeeting!

Anyways, you should definitely keep an eye on F# as this language will absolutely transform the way we write software on the .NET platform. You can reach me via my new blog http://achrissmith.blogspot.com/.

Artificial intelligence, programming, and StarCraft. It’s like peanut butter and jelly, only with Zerglets.

The day the contest was announced I worked feverishly on creating a StarCraft bot in F#. F# lends itself quite naturally to AI, asynchronous programming, and things which are awesome. However, I never blogged about this earlier on ethical grounds. Namely, that the API used to interact with Broodwar blatantly violates StarCraft’s EULA. Think about it, APIs to give programmatic access to computer games are dangerous. Encouraging bot development goes hand in hand with hacking, exploits, and ruining the game for everyone. While my own motives for modifying StarCraft are to write AI bots for my own use, I absolutely respect Blizzard’s wishes to prevent the reverse engineering of their software.

So, as a representative of Microsoft and one who respects license agreements, I kept my excitement quiet. That is, until the news came that Blizzard’s legal department gave the go ahead to the AIIDE. So, finally, let me introduce my StarCraft Bot in F#. (Which is really just a port of the Java Proxy Bot.)

Getting Setup

1. Buy and Install StarCraft

The first order of business is to install StarCraft and the BroodWar expansion. You can pick it up for $15 at Blizzard’s Online Store.

Be sure to install StarCraft into an easily accessible folder, like “E:\StarCraft”. Otherwise copying StarCraft bot files into the admin-only Program Files folder will be a huge pain.

2. Download and Install Chaos Launcher

Chaos Launcher is a tool which customizes how StarCraft loads and executes. Since the game originally came out in March, 1998 I won’t fault it for not rendering in a windowed-mode. However, for bot-development this is critical.

First, unzip the file into a folder, such as “E:\StarCraft\Chaos Launcher\”. Then, to test things out simply run ChaosLauncher.exe. Check W-Mode plugin and click Start. Now you can play StarCraft in a window!

3. Install the BWAPI

BWAPI is an open source API for interacting with StarCraft: BroodWar and is the API we will use to control our AI bot.

Download BWAPI_Beta_2.6.1.zip and unzip it into a folder, such as “E:\StarCraft\BWLAPI_Beta_2.6.1\”. Note however, that you still have more registration to do. From the steps listed in the README file:

1. Copy the contents of the ChaosLauncher folder to your Chaos Launcher folder (“E:\StarCraft\Chaos Launcher"\”)
2. Copy the contents of the StarCraft folder to your StarCraft folder (“E:\StarCraft\”)
3. Copy the contents of the Windows folder to your System folder (“C:\Windows\”)

Introducing StarCraftBot 9K

We now have all the pieces in place, but creating an AI-bot for a program not meant to be extended will be tricky. StarCraft Bot 9K has the following architecture, which follows the footsteps of the Java ProxyBot available on the AIIDE Website.

  
1. You use Chaos Launcher to launch StarCraft
2. When a StarCraft game starts, the BWAPI code executes on each game tick
3. On each tick the StarCraftConnector project (C++) broadcasts all public game data
4. The StarCraftBot9K Client (C#) will listen for those events
5. And finally StarCraftBot9K (F#) will do decision making

4. Download StarCraftBot9K

At the very bottom of this blog post is a .zip file with all the source code. Download that and unzip it into a folder, such as “E:\StarCraftBot9K\”.

5. Install the StarCraftConnector

One output of building the StarCraftBot9K soolution is StarCraftConnector.dll, which is the C++ library built on top of BWAPI that broadcasts game state to a socket. Later a C# application will listen to that data and send messages back to the StarCraft game.

To ‘install’ StarCraftConnector, copy it to “E:\StarCraft\bwapi-data\AI\”. This is the folder that you copied when installing BWAPI.

Next, edit “E:\StarCraft\bwapi-data\bwapi.ini” and set the ai_dll field to “bwapi-data\AI\StarCraftConnector.dll”.

6. Run StarCraftBot9K

Finally, you are ready to unleash StarCraftBot9K! Simply start run the application. It will begin listening to the socket until StarCraftConnector begins broadcasting.

7. Launch StarCraft

Next, run Chaos Launcher again, this time checking the “BWAPI Injector” module. Note that you must run it as an administrator.

You also need to check “BWAPI Injector” so that BWAPI get’s loaded with StarCraft.

When StarCraft starts everything will act as normal, BWAPI and the StarCraftConnector only come into play when starting a Custom Game.

8. Give StarCraftBot 9K Control

Once the game begins and you are connected you should see something like this. It is a mirroring of the internal StarCraft game state onto a simple WinForms app. There still is a lot of scaffolding to add, such as building up the object model to send proper commands to StarCraft.

When you check “Economy AI Module”, an F# asynchronous workflow will start up and monitor StarCraft trying to build up your basic economy. (Building SCVs, Drones, or Probes, and sending them to mine.)

/// AI module for managing your economy. Building drones, vespen geysers, etc.
let private getEconomyAI (mediator : GameMediator) =
    async {

        while true do

            let currentState = mediator.CurrentGameState

            // Build workers with all available cash
            if currentState.SupplyUsed < currentState.SupplyTotal &&
               currentState.Minerals >= 50 &&
               currentState.CanProduce.[ int (getWorkerType(g_GameMetadata.PlayerRace)) ] then
               
                // BUG: Builds a worker at the first command center we find, this might not be the best one.
                // Ideally we'd have some higher level notion of a 'base' with a 'status' such as 'active' or 'out of resources'.
                let cmdCenter = 
                    currentState.Units 
                    |> Seq.filter (fun unit -> unit.Player = g_GameMetadata.PlayerID)
                    |> Seq.tryFind (fun unit -> isCommandCenter (enum<UnitID> unit.TypeID))
                    
                if Option.isSome cmdCenter then
                    let cmdCenterID = cmdCenter |> Option.get |> (fun unit -> unit.ID)
                    let cmd = TrainUnit(cmdCenterID, int (getWorkerType(g_GameMetadata.PlayerRace)))
                    mediator.SendCommand(cmd)

            // Send idle workers to closest mineral patch
            for scunit in currentState.Units do
                // If you own the unit, it's a worker, and it's sitting there then
                // send it to the closest mineral patch.
                if scunit.Player = mediator.GameMetadata.PlayerID &&
                   isWorker scunit &&
                   scunit.OrderID = int (UnitOrder.PlayerGuard) then
                       
                    let orderID = scunit.OrderID

                    let scunitLoc = { X = scunit.XPos; Y = scunit.YPos }

                    let mineralPatches = 
                        currentState.Units
                        |> Seq.filter(fun unit -> unit.TypeID = int UnitID.MineralField)
                        |> Seq.map(fun minPatch -> let patchLoc = { X = minPatch.XPos; Y = minPatch.YPos }
                                                   scunitLoc.FlyingDistanceTo(patchLoc), minPatch)
                        |> Seq.sortBy(fun (dist, minPatch) -> dist)
                        
                    if mineralPatches <> Seq.empty then
                        let targetMinPatch = mineralPatches |> Seq.head |> snd
                        let cmd = RightClickUnit(scunit.ID, targetMinPatch.ID)
                        mediator.SendCommand(cmd)

            // Sleep and check again later. If this agent gets canceled it will be right here.
            do! Async.Sleep(100)
        }

The AI isn’t anything earth shattering yet. But F#’s asynchronous workflows, the reactive framework, and  first class events should make for a very powerful and elegant model on top of asynchronous operations happening in game.

Consider asking a unit such as a goliath to attack an enemy. Lots can happen! The goliath can kill the other unit, that unit can run away, the goliath can be killed, and so on. Even worse is that you won’t know the result of that action until several seconds later. F#’s asynchronous workflows provide a clean way to wrap those asynchronous actions.

let! result = tryEngage enemyUnit

match result with
| MarineWasKilled -> printfn "Sad."
| UnitWasKilled   -> printfn "Horray! Now go find a medic to heal"
| UnitRanAway     -> printfn "Should you chanse? Maybe..."

The tryEngage function could then simply be a union of several events (marine.OnKilled, unit.OnKilled, and new event when the unit is too far away). This concept may be difficult to grasp right now, I’ll try to post a follow up illustrating this concept later.

I’ve attached the source code. While it could stand to benefit from a lot of polishing it should be very straight forward. However, note that this post comes with not one but two disclaimers! Consider yourself blessed.

All code samples are provided "AS IS" without warranty of any kind, either express or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose. So in other words, if using the BWAPI somehow gets you banned from Battle.net or causes damage to your system, don’t expect any sympathy.

As you can tell there are a lot of moving parts here. I’m glad to provide technical support, but if you venture off the beaten path to don’t expect me to know why <random thing> isn’t working or how StarCraft is implemented.

StarCraftBot9K – 2010-03-18.zip

Even if Dr. McNamara’s code is better, I assure you I’ll have the last laugh. Muahhaha

Striking the balance

F# is a hybrid language and to truly harness its power for nefarious ends you need to embrace both function and object-oriented programming. Let’s review my trie implementation:

type TrieNode =
    | Node of IDictionary<char, TrieNode> * bool
    | Eow
    
    member this.IsLegalWord = 
        match this with
        | Node(_, true)
        | Eow -> true
        | _   -> false

/// seq<char list> -> TrieNode 
let rec generateTrieNode words =

    let hasEowNode = Seq.exists (fun word -> word = []) words

    if Seq.isEmpty words then
        Eow    
    else
        let nextWordFragments =
            words   
            |> Seq.filter (fun word -> word <> [])
            |> Seq.groupBy (fun word -> Seq.head word)
            |> Seq.map (fun (firstLetter, words) -> (firstLetter, words |> Seq.map List.tail))
            |> Seq.map(fun (firstLetter, rest) -> (firstLetter, generateTrieNode rest))
            |> Seq.fold
                (fun acc (letter, trieNode) ->
                    (Char.ToUpper(letter), trieNode) :: (Char.ToLower(letter), trieNode) :: acc
                )
                []

        Node(dict nextWordFragments, hasEowNode)

let searchStep (nodeInTrieTree : TrieNode) (tilesInChain : ITile list) =

    if nodeInTrieTree.IsLegalWord then
        foundWords.Add(getWordText tilesInChain)

    let currentTile = List.head tilesInChain

    match nodeInTrieTree with
    | Eow -> None
    | Node(possibleLetterSteps, _) 
        ->  let possibleSteps =
                currentTile.Neighbors
                |> Seq.filter 
                    (fun neighborTile -> 
                        not (List.exists 
                                (fun (prevTile : ITile) -> prevTile.Location = neighborTile.Location) 
                                tilesInChain
                            )
                    )
                |> Seq.filter (fun neighborTile -> possibleLetterSteps.ContainsKey(neighborTile.Letter))
                |> Seq.map 
                    (fun neighborTile ->
                        (   possibleLetterSteps.[neighborTile.Letter],
                            neighborTile :: tilesInChain   )
                    )
                    
            if not (Seq.isEmpty possibleSteps) then Some(possibleSteps)
            else                                    None

Not to toot my own horn here, but this is very functional and very elegant. With little use of mutation, data just flows from one point into the next. You don’t need an army of Singularity AI bots to tell you that the code looks sexy.

Now let’s look at Brian’s implementation and see how they differ. First, how Dr. McNamara represented his trie tree:

[<AllowNullLiteral>]
type TrieNode() =
    let nextChar = Array.create 26 null
    let mutable isEndOfWord = false
    member this.IsEndOfWord = isEndOfWord
    member this.Item with get(c:char) = nextChar.[int c - int 'A']
                     and private set(c:char) v = nextChar.[int c - int 'A'] <- v
    member this.Add(word) = 
        assert(word |> Seq.forall IsLetter)
        this.Add(word,0)
    member private this.Add(word:string,i) =
        if i = word.Length then
            isEndOfWord <- true
        else 
            match this.[word.[i]] with
            | null -> let newNode = new TrieNode()
                      newNode.Add(word,i+1)
                      this.[word.[i]] <- newNode
            | node -> node.Add(word,i+1)

The problem with my purely functional approach, is that when you are initializing a recursive discriminated union you have to have the entire tree laid out in memory before it gets initialized. Because once that root node has been set, you can’t update it. The second implementation however just kept an array of child nodes. This allows for quick indexing and makes it much easier to ‘fill out’ the tree. There isn’t any need to have some six-stage pipeline, Brian just created new nodes as necessary.

I was even more impressed by how Brian actually went about searching the Bookworm board for words. Each step I had to check that the word chain wasn’t ‘doubling back’ and using the same letter tile twice. Brian however gets around this by simply ‘zeroing out’ the tile once it is used and then restoring it later. I’ve added comments to point this out.

let rec Find(col, row, t:TrieNode) = seq {
    let c = board.[col,row]
    if c <> ' ' then
        board.[col,row] <- ' '  // REMOVE TILE, SINCE IT'S BEEN USED

        match t.[c] with
        | null -> ()
        | node -> 
            if node.IsEndOfWord then
                yield [c]
            for suf in Find(col-1, row-1, node) do yield c::suf
            for suf in Find(col-1, row+1, node) do yield c::suf        
            for suf in Find(col  , row-2, node) do yield c::suf        
            for suf in Find(col  , row+2, node) do yield c::suf        
            for suf in Find(col+1, row-1, node) do yield c::suf
            for suf in Find(col+1, row+1, node) do yield c::suf        
        board.[col,row] <- c    // RESTORE TILE, so other recursive calls can use.

    }

Inside Programming F# I wrote that at times imperative solutions can be much faster than functional. While some tech reviewers gave me crap for saying that, Brian’s implementation definitely strikes a good balance between functional and imperative. Kudos.

So, for Round 1 I’ll admit defeat. But I absolutely am not going to give up my (hard-earned) title of evil genius!

Destroying that MOFO where he stands

Fortunately I have a trick up my sleeve. To review, the following image is of a trie or prefix tree. (Stolen from wikipedia in an evil fashion.)

But consider the words “button” and “mutton”, or more appropriately, “super-mega-evilgenius” (me) and “barely-an-evilgenius” (Brian). In both cases the words share a common suffix, –utton or –evilgenius. When represented in a trie tree that would mean a huge waste of memory, because the node for ‘B’ would have child nodes for ‘u->t->t->o->n’ and the letter ‘M’ would have child nodes for ‘u->t->t->o->n’. When in actuality, they could both share the same suffix nodes. That is, both ‘B’ and ‘M’ can go to ‘u->t->t->o->n’. This sharing of suffixes is just like how prefix trees share prefixes, and both “Button” and “Buttons” share ‘b->u->t->t->o->n’.

This property is exactly what gives rise to the DAWG or directed-acyclic-word-graph. (Again, evilly stolen from Wikipedia.) In the image, the words “TOP”, “TOPS”, “TAP”, and “TAPS” are present. On the left is the trie tree and on the right the DAWG which reuses common suffixes.

The advantage of a DAWG is that it uses far less memory, since you are no longer duplicating shared suffixes. However, as one would expect, they are a bit more tricky to implement than a Trie.

Creating a DAWG in F#

The simplest way to create a DAWG is to simply create a trie-tree, and then unify common suffixes between tree nodes. (That is, if two nodes can add “-S” and form a complete word, we can have both child pointers point to the same TrieNode object.) To get started, let’s blatantly steal the wannabe-evil-genius-Dr.-McNarama’s trie implementation and add a few new properties.

type TrieNode() =
    let nextChar = Array.create 26 null
    let mutable isEndOfWord = false

    // ...

    member this.Children   = nextChar
    member this.IsLeafNode = Array.forall (fun child -> child = null) nextChar
    member this.NumChildren = 
        Array.fold
            (fun acc child -> if child <> null then acc + 1 else acc)
            0
            nextChar
    static member CompareNodes(lhs : TrieNode, rhs : TrieNode) =
        if lhs = null && rhs = null then 
            true
        elif (lhs = null && rhs <> null) || (lhs <> null && rhs = null) then
            false
        elif lhs.IsLeafNode && rhs.IsLeafNode then
            (lhs.IsEndOfWord = rhs.IsEndOfWord)
        elif lhs.IsEndOfWord <> rhs.IsEndOfWord then
            false
        else
            // For children, we can use a fast compare since we know that if they shared a common
            // suffix they would have been 'merged' already. (Going from the bottom of the tree up.)
            [| 0 .. 25 |] |> Array.forall(fun i -> (lhs.Children.[i] = rhs.Children.[i]))

Exposing the child node array will make it easy for us to rewire the tree later, and we will use the CompareNodes function to identify if two suffixes are identical. (More on that later.)

Rather than try to explain the algorithm outright, let’s just walk through the code. The first step is to associate each trie node with its height in the tree. Height being the number of letters away it is from a leaf EOW node. In order to do the DAWG conversion efficiently, we want to unify nodes going from the bottom of the tree up. So knowing where each node stands is an important first step. (Note that the nodeHeightDict dictionary is filled up as a side effect of calling walkTree, this is evil imperative programming at its worst!)

// Walk the tree and add associate each node with its height
let nodeHeightDict = new Dictionary<TrieNode, int>()

let rec walkTree (node : TrieNode) =
    if node.IsLeafNode then
        nodeHeightDict.Add(node, 0)
        0
    else
        let depth =
            node.Children
            |> Array.filter (fun child -> child <> null)
            |> Array.map walkTree
            |> Array.max
        nodeHeightDict.Add(node, depth + 1)
        depth + 1

let maxTreeHeight = walkTree trieRoot

Once we have associated each node with a height in the tree, then group nodes into buckets based on height. So all nodes with height 0 should be terminal EOW nodes. All nodes with height 1 should only have children which are EOW nodes, and so on.

// Next, fill a separate dictionary mapping each height to a set of nodes. This
// allows us to efficiently 'merge' suffixes going from bottom up.
let heightNodesDict = new Dictionary<int, HashSet<TrieNode>>()
for i = 0 to 16 do
    heightNodesDict.[i] <- new HashSet<_>()

Seq.iter 
    (fun node -> let height = nodeHeightDict.[node]
                 ignore(heightNodesDict.[height].Add(node)))
    nodeHeightDict.Keys

Now things start to get interesting. We need to store common tree suffixes for reuse. Rather than searching the suffix list at every node, we will index it by height of the tree and number of child nodes. (That way we can easily differentiate a suffix that leads to a word by adding “-ED” from a suffix that leads to a word by adding “-ING”.)

// Now add unique suffix nodes to our 'blessed' list, which
// should all be unique. We will then walk the tree bottom-up
// setting child nodes to the blessed/unique suffixes.
//
// We store our blessed suffix nodes in a (height * NumChildren) dictionary 
// for fast lookup if a suffix exists.
let suffixNodes = new Dictionary<int * int, HashSet<TrieNode>>()
for treeDepth = 0 to 16 do 
    for numChildren = 0 to 26 do
        suffixNodes.[(treeDepth, numChildren)] <- new HashSet<_>()

// All nodes at height zero are EOW nodes (EOWNode and IsLeafNode are true)
// So add exactly one EOW node to the blessed suffixNodes dictionary. All
// nodes at height 0 can be replaced with the one EOW node.
suffixNodes.[0, 0].Add(Seq.head heightNodesDict.[0]) |> ignore

Finally, we walk the nodes in the tree and rewire the child nodes with blessed suffixes. Again, we work from the bottom of the tree up for efficiency reasons. We don’t need to start at heightOfNode 0, since all of those nodes are identical (EOW) and will be replaced by suffixNodes.[0, 0] anyways.

We can compare child nodes using the TrieNode.CompareNodes methods. This checks if two child nodes contain essentially the same information.

for heightOfNode = 1 to 16 do   

    printfn "DAWGifying child nodes at height %2d. [%s]" heightOfNode (System.DateTime.Now.ToString("hh:mm:ss"))

 
    for node in heightNodesDict.[heightOfNode] do
    
        for childIdx = 0 to 25 do
            
            let childNode = node.Children.[childIdx]
            if childNode <> null then
            
                let validSuffixes = 
                    let childNodeHeight = nodeHeightDict.[childNode]
                    suffixNodes.[childNodeHeight, childNode.NumChildren]
                
                let foundValidSuffix = 
                    Seq.tryFind 
                        (fun validSuffix -> TrieNode.CompareNodes(childNode, validSuffix))
                        validSuffixes

                // If this suffix has never been encountered, then add it to our list.
                // Otherwise, reuse the blessed suffix.
                if Option.isNone foundValidSuffix then
                    validSuffixes.Add(childNode) |> ignore
                else
                    node.Children.[childIdx] <- Option.get foundValidSuffix

Of course, once we go through this procedure we still have the same TrieNode for the root of the tree. How can we validate that our DAWG has fewer nodes? We can validate this by simply walking the tree and adding the hash code of each node to a set. (Note we are relying on the default implementation of GetHashCode.)

let rec getUniqueNodes (node : TrieNode)  =
    
    let theSet = Set.singleton (node.GetHashCode())

    let children'sNodes =
        node.Children
        |> Array.filter (fun child -> child <> null)
        |> Array.map getUniqueNodes
        |> Array.fold
            (fun acc uniqueNodes -> Set.union acc uniqueNodes)
            Set.empty
        
    Set.union theSet children'sNodes

And, to drive the point home how much better our implementation is than that not-so-evil-genius Dr. McNamara we can use the following test function:

printfn "Building trie..."
let regularTrie = new TrieNode()
for w in words do
    regularTrie.Add(w)
printfn "Trie: %d nodes" <| (getUniqueNodes regularTrie).Count

printfn "Building trie for DAWG conversion..."
let dawg = new TrieNode()
for w in words do
    dawg.Add(w)
convertTrieToDawg dawg

printfn "DAWG : %d nodes" <| (getUniqueNodes dawg).Count
    
printfn "Testing..."
for w in words do
    assert IsWord(w, regularTrie)
    assert IsWord(w, dawg)

That’s it! I’ll admit that my implementation for converting a trie tree to a DAWG is a little slow, taking several minutes, but the results are worth it. The original trie tree required 393,960 nodes while the DAWG only needs 54,822. I’m not sure what I’ll do with all the memory savings. Perhaps use it to prepare for my next evil plan, which may or may not involve orbiting death lasers and the GPS coordinates of my enemy’s condo.

So good-genius Dr. McNamara, how do you like them apples?

Any evil genius knows that if you want to stay on top you need to exercise your mind. Most evil geniuses stay strong by lifting weights with their telekinetic abilities, however I prefer video games. PopCap.com’s Bookworm is one mental exercise I am particularly fond of.

Bookworm is simple. You have  7×7 hexagonal grid of letters and your goal is to create words by forming chains of adjacent tiles. Once you pick the word, the tiles are remove from the board and new ones drop down to fill the void.

The following screen shot shows a five letter word being selected. Obviously it is harder to find longer words, and thus they are worth more points.

Eventually you start getting Green, Gold, and Diamond tiles worth bonus points. However, if you make too many short words, typically those with only three-letters, you get flaming tiles. Each round a flaming tile exists on the screen it will burn through the tile below it. Once a flaming tile reaches the bottom of the screen it’s game over, man.

Mental exercise is important to keep any evil genius, well, a genius. However, a true evil genius would try to cheat. And that’s exactly what I intend to do in this blog post: write a program to find the longest word on a given Bookworm board.

Hexgrid Data Structure

In order to cheat at any game, first you need to write code to represent the game state. Which in the case of Bookworm is the hexagonal grid.  Creating our grid data structure isn’t going to be super interesting, but bear with me as it is required in order to do word searches later.

We’ll start by creating an interface to represent each tile on the board, which has a letter, set of neighbors, and position. Then we create a class for the actual letter grid.

/// Representing a tile on the board

[<AllowNullLiteral>]

type ITile =

    abstract Letter    : char

    abstract Neighbors : seq<ITile>

    abstract Location  : int * int

/// Data structure for a hex grid of letters

type LetterGrid(tileColumns : string[]) = 
    // Store the grid of letters in an array. Note that it is jagged. In

    // the flash version of Bookworm even columns have 8-tiles instead of 7.

    let mutable m_columns : char[][] = null
    // Cache of ITiles corresponding to tiles on the grid

    let mutable m_tileCache = Map.empty

Armed with these simple types, we can go about populating our LetterGrid class’ ITile cache. The following F# snippet shows using F# object expressions to create new instances of ITile. Note the recursive calls to getTile and then filtering out any tiles which are off the board. We can represent off-board tiles by simply having getTile return null. However, this requires some additional work.

By default any types defined in F# cannot be null, even interfaces like ITile. However, we can override this behavior by simply adding the [<AllowNullLiteral>] attribute.

/// Get an instance of an ITile from the given index. (Generating it if necessary.)

let rec getTile colIdx rowIdx =

    if not <| isValidLocation colIdx rowIdx then

        null

    else

        if Map.containsKey (colIdx, rowIdx) m_tileCache then

            m_tileCache.[(colIdx, rowIdx)]

        else

            let newTile =

                {

                    new ITile with

                        member this.Letter = getTileLetter colIdx rowIdx

                        member this.Neighbors =
                            let neighbors =
                                if (colIdx + 1) % 2 = 1 then

                                    // Odd column

                                    seq {

                                        yield getTile (colIdx – 1) (rowIdx + 0)  // NW

                                        yield getTile (colIdx + 0) (rowIdx – 1)  // N

                                        yield getTile (colIdx + 1) (rowIdx + 0)  // NE

                                        yield getTile (colIdx + 1) (rowIdx + 1)  // SE

                                        yield getTile (colIdx + 0) (rowIdx + 1)  // S

                                        yield getTile (colIdx – 1) (rowIdx + 1)  // SW
                                    }

                                else

                                    // Even column

                                    seq {

                                        yield getTile (colIdx – 1) (rowIdx – 1)  // NW

                                        yield getTile (colIdx + 0) (rowIdx – 1)  // N

                                        yield getTile (colIdx + 1) (rowIdx – 1)  // NE

                                        yield getTile (colIdx + 1) (rowIdx + 0)  // SE

                                        yield getTile (colIdx + 0) (rowIdx + 1)  // S

                                        yield getTile (colIdx – 1) (rowIdx + 0)  // SW

                                    }



                            // Filter out null (neighbors off the board)

                            neighbors |> Seq.filter ( (<>) null )
                        member this.Location = (colIdx, rowIdx)

                }
            m_tileCache <- Map.add (colIdx, rowIdx) newTile m_tileCache

            newTile

Crappy Word Detection

Great! Now that we have a way to represent the hex grid, all we need to do is start searching for words. First, we need a dictionary. Floating around on the internet(s) you can find a copy of the Scrabble Tournament Word List (TWL). The TWL contains all legal Scrabble words, however Bookworm only honors a subset of them. (For example, most curse words are not recognized.)

Once we have a word list, perhaps represented as a Set<string> we just need to start trying out all combinations of word chains and seeing if they are valid words, right? Wrong! That is a terrible idea and here is why:

Bookworm accepts words between 3 and 12-letters long. The board starts with 52 tiles, and each tile has six neighbors. Ignoring the fact that a tile cannot be used twice in the same word chain, we get:

which WolframAlpha tells me is 22,638,535,920, and that is just word chains! Once we are done permuting every single word chain we then have to look it up in our dictionary. Which would be O(log n), where n is the number of words. O(log n) is quite fast, but multiplied by 22 billion is still way too big.

What we need is a way to efficiently prune our search space. If you ever have a word prefixed with “AKVWOP”, and you know it isn’t a word, then it doesn’t make sense to continue looking in the vague hope of finding “AKVWOPS”, “AWKVWOPED”, “AWKVWOPING”, etc. 

The Trie Data Structure

Fortunately, there is a classic data structure for doing this called a trie. (Pronounced ‘try’, as in I was trie-ing to be clever when I titled this post.) It is also referred to as a prefix tree. The data structure can be explained quite well with the following picture: 

You start with the root node, and the edge to any of its children requires a letter. For example ‘t’. The child of the root node associated with ‘t’, has a child using the letter ‘o’ and another child associated with the letter ‘e’. Since there is no child associated with the letter ‘q’, you can infer that there is no leaf nodes prefix with the string “tq”.

If we constructed a trie for the entire contents of the dictionary, we would then have an efficient way to determine if a given substring prefixes any valid word. (By simply checking if such a node exists in the tree or not.)

The code for implementing this in F# is straightforward. Each trie node stores a dictionary potentially mapping a letter to a child node, or the it is at a terminal node. Meaning that the prefix is a valid word, and there are no further words with that prefix.

type TrieNode =

    // Letters go to other nodes, flag if it is a word node

    | Node of IDictionary<char, TrieNode> * bool

    // You are at the end of a legal word

    | Eow

    member this.IsLegalWord =

        match this with

        | Node(_, true)

        | Eow -> true

        | _   -> false

To generate our tree, we use the following function which takes a sequence of words, represented as F# lists of characters, and converts it into a TrieNode. I’ve added a glut of comments to help explain things. The only bit of black magic is the use of the dict function.

dict works by taking a seq<’k, ‘v> and produces an IDictionary<’k, ‘v>.

/// seq<char list> -> TrieNode

let rec generateTrieNode words =

    // Does this represent an EOW node for anything?

    let hasEowNode = Seq.exists (fun word -> word = []) words
    if Seq.isEmpty words then

        Eow

    else

        (* Now group all words by their first letter.

        [ “cat”; “cats”; “dogs” ]

        =>

        seq {

            (‘c’, seq { “at”; “ats” })

            (‘d’, seq { “ogs” })

        }

        *)

        let nextWordFragments =

            // [“”; “a”; “act”; “acts”; “actor”; … ]

            words

            // [“a”; “act”; “acts”; “actor”; … ]

            |> Seq.filter (fun word -> word <> [])

            // seq { (“a”, seq { “act”; “acts”; “actor”; … }); … }

            |> Seq.groupBy (fun word -> Seq.head word)

            // seq { (“a”, seq { “ct”; “cts”; “ctor”; … }); … }

            |> Seq.map (fun (firstLetter, words) -> (firstLetter, words |> Seq.map List.tail))

            // seq { (“a”, seq (“c”, seq { … } …  }

            |> Seq.map(fun (firstLetter, rest) -> (firstLetter, generateTrieNode rest))

            // seq { (“a”, seq …); (“A”, seq …) … }

            |> Seq.fold

                (fun acc (letter, trieNode) ->

                    (Char.ToUpper(letter), trieNode) :: (Char.ToLower(letter), trieNode) :: acc

                )

                []
        Node(dict nextWordFragments, hasEowNode)

let isWord word tree =

    let letters = word |> Seq.toList
    let rec isWord currentNode letters =

        match letters, currentNode with

        // When you are out of letters, check if you are on

        // an end-of-word node

        | [], Eow

        | [], Node(_, true)

            -> true
        // Otherwise, walk down the tree…

        | nextLetter :: rest, Node(childNodes, _)

            ->  let hasNode, childNode = childNodes.TryGetValue(nextLetter)

                if hasNode then

                    isWord childNode rest

                else

                    false
        | _ -> false
    isWord tree letters 

Searching

Searching through potential word chains can be parallelized trivially, but I’ll save that for a future blog post. For now we will use the following approach:

• Start with each tile on the board and put them into a stack of ‘search states’


• While the search stack is not empty do




• Pop the search stack


• Check that state to see if there are any legal words from that position (adjacent tiles leading to valid word prefixes)


• Push any legal, subsequent steps to our search stack

Here is the F# code. Note that each state is represented by TrieNode * ITile list. This represents the current word prefix node in the trie tree and the list of tiles forming the word chain. We then seed that search stack with word chains starting at every tile in the board.

let statesToExplore = new Stack<TrieNode * ITile list>()

// Start with searching all tiles

gameGrid.AllTiles

|> Seq.iter (fun tile ->

                let firstStepDownTrieTree =

                    match trieRoot with

                    | Node(nextSteps, _) -> nextSteps.[tile.Letter]

                    | _ -> failwith “Shouldn’t get here”

                statesToExplore.Push(firstStepDownTrieTree, [tile]))
// Now explore the entire search space

while statesToExplore.Count > 0 do

    let trieNode, prevLetters = statesToExplore.Pop()
    match searchStep trieNode prevLetters with

    | None -> ()

    | Some(nextSearchStates) ->

        // Add possible states to explore to our stack

        Seq.iter (statesToExplore.Push) nextSearchStates

All we need is a function to take some given search state – current node in the trie tree and tiles used so far – and then check all of the neighboring tiles if they can continue down the trie tree towards valid words.

/// Given a spot in the Trie tree, a game tile, and a list of previously used tiles used

/// to form a word, return Some(seq< all possible steps>). If no legal words are possible

/// from this state, return None.

let searchStep (nodeInTrieTree : TrieNode) (tilesInChain : ITile list) =

    // Are we at a legal word in the Trie tree?

    if nodeInTrieTree.IsLegalWord then

        foundWords.Add(getWordText tilesInChain)
    let currentTile = List.head tilesInChain
    match nodeInTrieTree with

    // Cannot make any valid words from this point, no purpose in stepping

    | Eow -> None

    // If you can form legal words beond where we are at in the tree, continue

    // searching.

    | Node(possibleLetterSteps, _)

        ->  let possibleSteps =

                currentTile.Neighbors

                // Filter out neighbors already used for the word chain

                |> Seq.filter

                    (fun neighborTile ->

                        not (List.exists

                                (fun (prevTile : ITile) -> prevTile.Location = neighborTile.Location)

                                tilesInChain

                            )

                    )

                // Filter out neighbors which couldn’t lead to avalid word

                |> Seq.filter

                    (fun neighborTile -> possibleLetterSteps.ContainsKey(neighborTile.Letter))

                // Now map them to the next ‘states’ to search

                |> Seq.map

                    (fun neighborTile ->

                        (   // Node in trie tree

                            possibleLetterSteps.[neighborTile.Letter],

                            // Tiles used in the word chain

                            neighborTile :: tilesInChain

                        )

                    )
            if not (Seq.isEmpty possibleSteps) then

                Some(possibleSteps)

            else

                None

And that’s it! We can use this efficient word search cheat to our heart’s content. Attached to this post is the source code.

I used BookwormBot9000 to spot this gem on my iPhone version of the game. But that begs the question what the hell is a madrilene?

Disclaimer

All code samples are provided “AS IS” without warranty of any kind, either express or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose. So in other words, if cheating at word games leads your brain to atrophy and turn to mush, don’t blame me or Microsoft.

BookWormBot9K v1.0.zip

Rather than doing the prototypical “Intro to F# Talk” I figured I go with something a bit more fun and relevant to the every day developer. Sure F# is neat and everything – but why bother to learn a new programming language unless you can use it to do something meaningful. Well, in addition excelling at both functional and object-oriented programming, F# is ideal for world domination.

——————————————————

To be honest, this may be the best talk abstract I’ll ever write.

Being an Evil Genius with F# and .NET

In today’s competitive global economy it’s increasingly difficult to find quality henchmen to aid you in taking over the Earth. Fortunately the .NET platform has plenty of technological gems which can help you

in your quest.

Speech recognition APIs to automate your demands for ransom. The Parallel Extensions to .NET for distributing control of your nanobots. Even image recognition to identify CIA spies and kill them on sight!

This code-focused talk will show you the libraries you can use to make your next high-powered plot for world domination a success. (F# knowledge is not required, though will help any aspiring evil genius grep the demos.)

Someone once told me that at the beginning of a talk you should introduce yourself. Well, I’m much like you – except that my ambition isn’t to build a house or write the great American novel. It’s to take over the world!

I’ve been very fortunate in my career as an evil genius and 2007 was a hallmark year. I had just leased a new volcano lair, had a growing army of minions, and even got a hold of real nuclear missile. The movies these days make it look like just anybody with three billion dollars can get a hold of one of these babies – not true! I had to get my minions to stage a raid on an ex-Soviet munitions dump and then kidnap a scientist to rebuild the flight systems. Hard work, the work was well worth it.

But the global economic disaster struck me just like everyone else. As embarrassing as it is to admit this, I couldn’t keep up the payments on my volcano and it got foreclosed on. Then my minions were all ambushed and killed by some CIA commandos. And worst of all I had to give up my nuclear missile.

Saddened, I trudged on.

Then it dawned on me. Maybe being an effective evil genius doesn’t mean volcano lairs or orbiting space lasers, perhaps you can still terrorize the Earth with software.

And that brings us to the meat of my CodeMash talk, being an evil genius with F# and .NET. The talk isn’t so much about F# as it is about being an evil genius. But we all know F# is the premier .NET language for aspiring villains, so along the way I’ll highlight some language constructs that are especially helpful when plotting to take over the world.

The first problem you’ll encounter is how to actually strike your foes? What if they are behind a wall, in a bunker, or inside of a tank?

As it turns out the terrorist training organization ‘Nerf’ had it right all along. Foam missiles are the ideal weapon.

• Ever hear of an evil genius getting caught while trying to sneak foam missiles onto an airplane? There’s a reason for that…
• Since they are sponges after all, why not soak them in poison to make them more lethal?

In order to get your hands on a foam-missile-WMD you could enslave a few engineers to build you one, but if you are more in a time crunch you can pick one up at Amazon for about $40.

Dream Cheeky USB Missile Launcher

However, this piece of specialized military hardware isn’t quite ideal for terror operations. The software it comes with is a little clunky and doesn’t offer the degree of precision required for world domination. What would any evil genius do in this case? Haxor, of course!

A great magician never reveals his tricks, however that rule didn’t stop Pedram Amini from detailing the process of reverse engineering how the USB Rocket Launcher works.

http://dvlabs.tippingpoint.com/blog/2009/02/12/python-interfacing-a-usb-missile-launcher

Once you know the protocol for communicating with the missile launcher, it’s just a matter of reading and writing to the underlying USB device. Which you can do using P/Invoke in .NET. The code provided is in C# and was written by level-9 ninja master Matt Ellis.

[DllImport("kernel32.dll", SetLastError = true)]
[return: MarshalAs(UnmanagedType.Bool)]
public static extern unsafe bool ReadFile(SafeFileHandle hHandle, byte* lpBuffer, uint nNumberOfBytesToRead, ref uint lpNumberOfBytesRead, IntPtr lpOverlapped);

[DllImport("kernel32.dll", SetLastError = true)]
[return: MarshalAs(UnmanagedType.Bool)]
public static extern unsafe bool WriteFile(SafeFileHandle hHandle, byte* lpBuffer, uint nNumberOfBytesToWrite, ref uint lpNumberOfBytesWritten, IntPtr lpOverlapped);

/// <summary>
/// That is, call directly into the drivers for the Rocket Launcher
/// </summary>
/// On a 64-bit OS: [DllImport(@"C:\Program Files (x86)\USb Missile Launcher\USBHID.dll")]
[DllImport(@"C:\Program Files\USb Missile Launcher\USBHID.dll")]
public static extern SafeFileHandle OpenHID(ushort VendorId, ushort ProductId, ushort ReveisionId);

Once you have a wrapper on top of the rocket launcher, then it’s just a matter of writing some code to interact with it. For RocketLauncherOfDoom v1.0 we’ll just have a console interface. Something like this:

let ckInfo = Console.ReadKey(true)
let t = 
    if (ckInfo.Modifiers = ConsoleModifiers.Shift) then 
        15
    else 
        5

let action =
    match ckInfo.Key with
    | ConsoleKey.UpArrow    -> MoveUp(t)
    | ConsoleKey.DownArrow  -> MoveDown(t)
    | ConsoleKey.LeftArrow  -> MoveLeft(t)
    | ConsoleKey.RightArrow -> MoveRight(t)
    
    | ConsoleKey.Spacebar -> Fire

    | ConsoleKey.Q  -> (loop <- false)
                       NoOp
  
    | _ -> NoOp

performAction rocketLauncher action |> ignore

However, we are far from done.

Once you have control over your USB rocket launcher, the problem is that you spend the rest of your time either making demands for ransom or listening to people beg for their lives. Both are kind of annoying and tedious. Fortunately we can automate this.

Build into Windows are the Microsoft Speech APIs (SAPI) which can do both speech recognition – transcribing feeble cries for help – and speech synthesis – giving your robo-army a verbal presence.

Getting setup is simple. First, you need a quality microphone. I’ve been very pleased with my purchase of:

Plantronics Audio 995 Wireless Stereo Headset

Next, you can dramatically improve your computer’s accuracy at recognizing your voice by training your computer. Simply open up Control Panel and click ‘Speech Recognition’ and then ‘Train your computer to better understand you’. Essentially you will dictate to your computer for 10 minutes but the results are worth it.

Once you dictate Windows into submission, it’s time for code! The System.Speech APIs come with .NET 3.0 and are quite straight forward. The following snippet prints all installed voices on your system and says “Hello, World!”

#r "System.Speech.dll"

open System
open System.Speech.Synthesis

// Say "Hello, World!"
let prompt = new PromptBuilder()
prompt.StartParagraph() 
prompt.AppendText("Hello", PromptEmphasis.Strong)
prompt.AppendText("World", PromptEmphasis.Reduced)
prompt.EndParagraph()

// List installed voices
let synthesizer = new SpeechSynthesizer()
let installedVoices = synthesizer.GetInstalledVoices()
for installedVoice in installedVoices do
    printfn 
        "Enabled:%b, Name:%s, Age:%A, Description:%s" 
        installedVoice.Enabled 
        installedVoice.VoiceInfo.Name 
        installedVoice.VoiceInfo.Age 
        installedVoice.VoiceInfo.Description

synthesizer.Speak(prompt)

Speech recognition is even easier. Once you instantiate the recognizer object, simply add an event handler to the ‘SpeechRecognized’ event. For more information about the inner workings of the System.Speech namespace, check out the documentation on MSDN.

#r "System.Speech.dll"

open System
open System.Speech.Recognition

let sp = new SpeechRecognitionEngine()
let defaultDictationGrammar = new DictationGrammar()

defaultDictationGrammar.Name <- "Default Dictation"
defaultDictationGrammar.Enabled <- true

sp.LoadGrammar(defaultDictationGrammar)
sp.SetInputToDefaultAudioDevice()

sp.RecognizeAsync(RecognizeMode.Multiple)

//sp.SpeechHypothesized.Add(fun args -> printfn "Hypothesized [%f] '%s'" args.Result.Confidence args.Result.Text)
sp.SpeechRecognized.Add(fun args -> printfn "Recognized [%f] '%s'" args.Result.Confidence args.Result.Text)

With a mastery of speech and sound, we can now upgrade our missile launcher software to be controlled via voice activation. The following snippet shows F#’s first-class events in action. Rather than interacting with the System.Speech APIs directly, the getRecognizer function returns an event object, to which you can add event handlers later. The result is a pretty clean implementation IMHO.

// Returns an event handler which fires when spoken text is
// recognized
let getWordRecognizer() =
    let sp = new SpeechRecognitionEngine()
    let defaultDictationGrammar = new DictationGrammar()

    defaultDictationGrammar.Name <- "Default Dictation"
    defaultDictationGrammar.Enabled <- true

    sp.LoadGrammar(defaultDictationGrammar)
    sp.SetInputToDefaultAudioDevice()

    sp.RecognizeAsync(RecognizeMode.Multiple)

    // Return an instance of an event which fires when words are recognized.
    // Callers can then subscribe to that event.
    sp.SpeechRecognized
    |> Event.map(fun args -> args.Result.Text.ToLower())

With the speech recognized event, all we need to do is write two event handlers. One to simply interact with the rocket and another to listen for when the user wants to exit the program.

let recognizerEvent = getWordRecognizer()

// Main handler - convert spoken text into RL commands
let handleWord spokenText =
    printfn "Recognized Word: %s" spokenText
    let action = 
        match spokenText with
        | "up"  // Has a hard time recognizing this 
        | "north" -> MoveUp(20)
        | "down"  -> MoveDown(20)
        | "left"  -> MoveLeft(20)
        | "right" -> MoveRight(20)

        | "fire"  -> Fire

        | _ -> NoOp
        
    performAction rocketLauncher action |> ignore

// Exit handler - specifically look for exit/quit
let terminateLoop = ref false
let terminateLoopHandler = function | "exit" 
                                    | "quit" -> terminateLoop := true
                                    | _      -> ()

// Hook up event handlers
recognizerEvent.Add(handleWord)
recognizerEvent.Add(terminateLoopHandler)

while terminateLoop.Value = false do
    System.Threading.Thread.Yield() |> ignore

()

Of course, the biggest challenge isn’t actually controlling your rocket launcher, but determining what to shoot.

Next we’ll try to add in some computer vision to identify faces. This is where things get serious, computer vision truly is the rocket science of software. Think about it, I give you an image, which is a matrix of pixels, which are a tuple of color intensities, which are just values, and you tell me if there is a ‘face’ somewhere in that sea of numbers? The sheer idea is ludicrous, but somehow people much smarter than me have figured out how to do it.

Currently the best computer vision library is Open CV, which continues to evolve with active research. If you are interested in learning more, check out:

Learning OpenCV, O’Reilly

However, OpenCV is written in C/C++ and we all know that true evil geniuses use .NET. While you could just write a million P/Invoke calls and use the OpenCV library as-is, fortunately the Egmu CV is a .NET wrapper on top of OpenCV.

For the purposes of this blog post I’ll avoid the specifics of how face detection works in OpenCV. In general, OpenCV uses a technique developed by Paul Viola and Michael Jones to quickly identify ‘features’ of an image. If a region shares many ‘features’ of a human face, then a face is detected. However, the Viola-Jones method can be used for detecting more than just faces. You can actually train the computer to identify any custom ‘features’ as long as you have an ample set of example images.

For more information check out the following resources:

http://www.cognotics.com/opencv/servo_2007_series/index.html

http://www.cognotics.com/opencv/servo_2007_series/part_2/sidebar.html

http://en.wikipedia.org/wiki/Viola-Jones_object_detection_framework

Now let’s get back to sewing evil!

To get setup detecting faces you’ll need to install OpenCV, EmguCV, and optionally get a webcam. For a cheap and viable option, try:

Microsoft LifeCam VX-1000

Using OpenCV to detect faces is very straightforward. The following code opens up a HaarCascade (or set of features to identify a specific thing in an image) and puts a square around the provided image file.

let detectFaces (filePath : string) =

    // Load the image file
    let img = new Image<Bgr, byte>(filePath)
    
    // Resize to something resonable
    let img = img.Resize(float 300 / float img.Width, CvEnum.INTER.CV_INTER_CUBIC)
    
    // Load the object detector
    let haarCascades = @"C:\OpenCV2.0\data\haarcascades\"
    let objectToDetect = new HaarCascade(haarCascades + "haarcascade_frontalface_default.xml")
    
    // Convert to grayscale
    let imgGray : Image<Bgr, byte> = img.Convert()
    
    let faces : MCvAvgComp[] = imgGray.DetectHaarCascade(objectToDetect).[0]
    for face in faces do
        img.Draw(face.rect, new Bgr(Color.White), 1)
        
    // Display the image
    let viewer = new ImageViewer()
    viewer.Image <- img
    viewer.Show() |> ignore

OpenCV comes with a slew of these HaarCascades for detecting faces from different angles. I’ wrote a simple WinForms application where you can open all the images in a directory and see what the HaarCascades identify.

The results are hit and miss, but overall I’m very impressed with the results.

While automating USB missile launchers and striking terror into the heart of men is fun, there are other worthwhile uses of these libraries. Using the System.Speech APIs you can write software to go hands free. For example, have a program dictate new F# questions on StackOverflow as they are posted. Or, training OpenCV to detect image features in real-time, such as defects in industrial manufacturing.

If you are interested in learning more about F#, you should consider buying my book. Have fun conquering!

Disclaimer #1

All code samples are provided "AS IS" without warranty of any kind, either express or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose. So in other words, if the attached source files cause you any grief, up to and including destroying your USB rocket launcher, you can’t blame me or Microsoft.

Disclaimer #2

Theme of evil genius-ery aside, consider the following. If you have above average programming skills, such as knowledge of reverse engineering debuggers or decompilers, then just like Spiderman you have amazing powers. Please consider the legal and ethical ramifications of your actions. Pedram Amini showing how to reverse engineer a USB rocket launcher is innocent enough. But you can apply the same techniques to cause real evil in the world. (For example spying on ordinary citizens.) 

The point is, like Uncle Ben said, “with great power comes great responsibility.” This applies to super heroes and evil geniuses alike.

RocketLauncher_v1.0.zip

We talked about all sorts of things, from me shamelessly promoting my book to Silverlight 4.0 to the new IntelliTrace feature of Visual Studio 2010. If you haven’t already heard about it, IntelliTrace is pretty kickass. Essentially it allows you to step backwards in time while debugging. Read this for more info.

Anyways, while we were talking about historical debugging I believe it was Keith who asked if IntelliTrace could detect if a program was in an infinite loop. Being the true Computer Science gangsta that I am, I took the opportunity to name drop BOTH the Halting Problem AND the Church-Turning Thesis. (Hell yeah!)

So this blog post is about explaining both of these somewhat pedantic but fundamentally important concepts.

The Problem

I give you a program and you tell me through any form of analysis if that program will terminate or not. That sounds simple enough, I mean it’s the year 2009 for crying out loud. We might not have flying cars but we do have automated stock trading and WiFi on airplanes.

Spoiler alert: it’s not possible. No matter how hard you try you cannot devise a general algorithm to determine if a program terminates or not. (Obviously you can determine if some programs terminate, but no single algorithm can determine if any program halts or not.)

However in order to prove this with rigor we need a more concrete notion of a program. (For example, are we talking about F# apps written on CLR 4.0 or a Perl script?) Fortunately, this guy already came up with a good theoretical notion of a algorithm and/or program. Enter the Turing machine.

In 1936 a British mathematician named Alan Turing proposed a theoretical model of computation called a Turing machine. (Note that I didn’t say computer because those things hadn’t been invented yet. The first electronic computer came along a decade later in 1946.) Generally speaking, a Turing machine is a finite state machine operating over an infinite tape of input. At each step the machine reads a character from the tape, and then based on its current state and the character read, transitions to a new state, advances the tape one position left or right, and possibly write a character back to the tape.  Eventually the Turing machine will wind up in a special state designated as either an accept state or reject state.

You use a Turing Machine to compute the answer to a Boolean problem (aka a decision problem). For example, given input “RACECAR”, answer whether or not it is a palindrome. The Turing Machine is obviously a far cry from the CLR, but in 1936 Turing machines were the bee’s knees.

Anyways, the specifics of how Turing machines work aren’t that important. Primarily they serve as a way describe the implementation of any algorithms in a mathematical context. We can use the Turning machine as the backdrop for proving whether or not any arbitrary program will terminate. This is known as the Halting Problem.

The Halting Problem

The halting problem is defined as: given a program (Turing machine) and its input (initial tape state), determine if the program will terminate (eventually land on an accept or reject state.)  In other words, if you have a program that takes another program as an input return true if that program halts, otherwise return false.

This seems pretty obvious when you see programs like:

open System

while true do
    Console.WriteLine("Not done yet...")

But what about any program? Turing proved that this is undecidable which means that it is impossible to construct an algorithm that will produce a correct answer every time. A sketch of the proof can be found here, but it goes something like this:

1. Suppose by way of contradiction that you have a function H(p, i) that for a program p and input i returns true if the program halts and false if the program goes into an infinite loop. (That is, H is a solution to the halting problem.) Note that H always terminates.

2. Now consider another function K(p) that is the somewhat of an inverse of H. K takes a Turing machine as input and calls H to check if K’s input halts or not. If K’s input halts, then K goes into an infinite loop. If K’s input does not halt then K returns true. (Note that we are taking K’s argument and converting into a valid input to H since a Turing machine can be encoded as the input into the same Turing machine.)

// H, determines if a program halts
let H (p : TuringMachine, i : TuringMachineInput) =
    if p.TerminatesWithInput(i) then
        true
    else
        false
    
// K, designed to screw with H
let K (p : TuringMachine) =
    // If the input program/input DOES NOT halt...
    if H(p, p.ToString()) = false then
        // return true
        true
    else
        // Otherwise, go into an infinite loop
        while true do 
            ()

Here’s where it gets crazy. What happens if we run program H with the program K and program input K?

match H(K, K.ToString()) with
| true  -> printfn "K with itself as input terminates"
| false -> printfn "K with itself as input does not terminate"

Case 1.) H returns true. Thus, K terminates. However, inside of K it calls H(K, K.ToString()) which if that returned true would have caused an infinite loop – meaning K doesn’t terminate. A contradiction.

Case 2.) H returns false. Thus, K does not terminate. By definition however, K only went into an infinite loop if H(K, K) returned true. (Meaning that by definition of H, K terminates.) Therefore, we arrive at another contradiction.

Since we have found a situation where function H cannot return either true or false, we can conclude that no such program H exists. You can read the original paper On computable numbers, with an application to the Entscheidungs problem here but the main takeaway is that “no Turing machine can determine if an arbitrary Turing machine will halt or not”.

While speaking in terms of Turing machines is great, but how does this relate to real programs? It’s highly unlikely that you are coding in Microsoft Visual Turing Machine .NET™. In order to apply our solution to the Halting Problem more broadly we need a way to compare different forms of computation. (In other words prove that Perl code is equivalent to Visual Basic .NET given enough if-statements and days spent in front of a debugger.)

Church-Turing Thesis

Back in the mid 30’s the Turing machine wasn’t the only game in town. Alonzo Church had also come up with a theoretical notion of computation known as the lambda calculus. (Which serves as the theoretical underpinning of functional programming languages, like F#.)

While Turing Machines were described in terms of states, transitions, and an infinite tape of values, the lambda calculus was really just a way of encoding mathematical functions.

Anyways, the Church-Turing Thesis postulated that Turing machines and the lambda calculus could compute the same things. In other words, any program you can write with a Turing machine could also be written with the lambda calculus. Any notion of computation which can convert any of its programs into a Turing machine is known as being Turing complete. While I can’t cite any proofs off hand, it’s generally assumed that modern languages like F# or <your favorite language here> are Turing complete. (No matter how simple the language, if it supports recursion, while loops, and integers then it’s probably Turing complete.)

While you can try to write some amazing library for detecting infinite loops, I can write the same code using a Turing machine. And, since it has been proving that no Turing machine can solve the Halting Problem, neither can your amazing library.

Summary

This blog post covers a lot of ground, but the bottom line is as follows:

• Turing machines are a theoretical notion of computation
• The Halting Problem asks if an arbitrary Turing machine will terminate or not
• The Halting Problem is undecideable
• The Church-Turing Thesis states that sufficiently advanced computational systems are all equivalent*
• Therefore, it is undecideable if an arbitrary program in your favorite language halts or not

*Most people think that Turing machines (and equivalent forms of computation) offer all the computational power possible. Meaning no matter how fancy the computational scheme, you can do the same thing with a Turing machine. However, it is possible that quantum computers offer more computational power than Turing machines and thus could possibly solve the Halting problem.

Hopefully this blog post was general enough to be approach able but detailed enough to keep the pedants at bay. If you are interested in theoretical Computer Science you should buy Programming F#. The book has absolutely nothing to do with any of this stuff, but if there were a program that could solve the Halting Problem I’m sure it would be written in F#

I’ve gotten a few requests recently for the source code of the examples in Programming F#. I’ve attached them as a series of F# Script files. In the ZIP file you’ll find a few gems such as:

• A ‘state’ computation expression


• Examples of F# Asynchronous Workflows and the Parallel Extensions to .NET


• References for writing OO code in F#, including advanced stuff like Delegates and Events


• Code for F# interop such as P/Invoke signatures

And as always, any code released on this blog it comes with the standard disclaimer:

All code samples are provided “AS IS” without warranty of any kind, either express or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose. So in other words, if the attached source files cause you any grief whatsoever you can’t blame me, O’Reilly Media, or Microsoft.

ProgrammingFSharpCode.zip

Overriding Equals and Not Equals

F# allows you to overload operators so you can better map mathematical concepts to your code. For example, consider this simple vector type. Notice how it overrides the Equals operator to compare just the vector’s magnitudes, not their actual values.

type Vector =
    | Vector of float * float * float

    member this.Length =
        // Extract values via ninja pattern match
        // hidden in a let binding
        let (Vector(x,y,z)) = this
        sqrt <| x * x + y * y + z * z

    static member (+) (lhs, rhs) =
        let (Vector(x1,y1,z1)) = lhs
        let (Vector(x2,y2,z2)) = rhs

        Vector(x1 + x2, y1 + y2, z1 + z2)
        
    // Equals
    static member (==) (lhs : Vector, rhs : Vector) =
        lhs.Length = rhs.Length

    // Not equals
    static member (!=) (lhs : Vector, rhs) =
        not (lhs == rhs)

When you run this code in FSI, it doesn’t work.

> // Bug?
let vec1 = Vector(10.0, 0.0, 0.0)
let vec2 = Vector(0.0, 0.0, 10.0);;

val vec1 : Vector = Vector (10.0,0.0,0.0)
val vec2 : Vector = Vector (0.0,0.0,10.0)

> vec1 = vec2;;
val it : bool = false
> vec1.Length = vec2.Length;;
val it : bool = true

The key here is to understanding a bit more about how operator overloading in F# and .NET works. When you override an operator such as (+) the compiler generates a method named op_Addition. So when a .NET compiler sees “x + y” it looks for a method with that name. Similarly it loops for op_Subtraction, op_BitwiseOr, etc.

Since F# allows you to define symbolic operators (functions with symbols for names) you can overload operators that aren’t valid in C# or VB.NET, for example (==>):

// Rotate the vector about the X axis
static member (==>) (vec : Vector, rads : float) =
    let (Vector(x,y,z)) = vec
    
    let x' = x * cos rads - y * sin rads
    let y' = x * sin rads + y * cos rads
    let z' = z

    Vector(x', y', z)

> let v = Vector(10.0, 0.0, 0.0);;

val v : Vector = Vector (10.0,0.0,0.0)

> v ==> System.Math.PI;;
val it : Vector = Vector (-10.0,0.0,0.0)

> v ==> (System.Math.PI / 2.0);;
val it : Vector = Vector (0.0,10.0,0.0)

While F# recognizes these symbolic operators, to call them from C# you need to use the ‘long name’ which in the previous example would be op_EqualsEqualsGreater.

To override the equals operator in C# requires that you define (==), which in turn generate a method called op_Equality. However, defining (==) in F# generates a method called op_EqualsEquals.

To properly overload the equals and not equals operators in F# you must use the F# operators for equality (=) and (<>).

// Equals
static member (=) (lhs, rhs) =
    lhs.Length = rhs.Length

// Not equals
static member (<>) (lhs : Vector, rhs) =
    not (lhs == rhs)

Improper use of Range Expressions

Consider the following two loops:

for i in [1 .. 10000000] do
    ...

for i in 1 .. 10000000 do
    ...

They may not look that different, but they have dramatically different performance profiles. You can find these differences detailed in the recently updated F# Language Specification. Both are examples of range expression, which is a way to create a sequence between to indexes. However, the subtlety here is that the first generates a full list, while the second is just the raw sequence.

So while one requires ten million memory allocations to generate the list, the second loop doesn’t. More importantly, the compiler can optimize the second loop into a standard for loop over a single integer. (And not need to do any memory allocation at all!)

open System

type Record = 
    {
        Outlook     : string
        Temperature : string
        Humidity    : string
        Wind        : string
        PlayTennis  : bool 
    }

    /// Given an attribute name return its value
    member this.GetAttributeValue(attrName) =
        match attrName with
        | "Outlook"     -> this.Outlook
        | "Temperature" -> this.Temperature
        | "Humidity"    -> this.Humidity
        | "Wind"        -> this.Wind
        | _ -> failwithf "Invalid attribute name '%s'" attrName

    /// Make the %o format specifier look all pretty like
    override this.ToString() =
        sprintf
            "{Outlook = %s, Temp = %s, Humidity = %s, Wind = %s, PlayTennis = %b}" 
            this.Outlook
            this.Temperature 
            this.Humidity
            this.Wind
            this.PlayTennis

type DecisionTreeNode =
    // Attribute name and value / child node list    
    | DecisionNode of string * (string * DecisionTreeNode) seq
    // Decision and corresponding evidence
    | Leaf         of bool * Record seq

// ----------------------------------------------------------------------------

/// Return the total true, total false, and total count for a set of Records
let countClassifications data = 
    Seq.fold 
        (fun (t,f,c) item -> 
            match item.PlayTennis with
            | true  -> (t + 1, f, c + 1)
            | false -> (t, f + 1, c + 1))
        (0, 0, 0)
        data

// ----------------------------------------------------------------------------

/// Return the theoretical number of bits required to classify the information.
/// If a 50/50 mix, returns 1, if 100% true or false returns 0.
let entropy data = 
    let (trueValues, falseValues, totalCount) = countClassifications data        

    let probTrue  = (float trueValues)  / (float totalCount)
    let probFalse = (float falseValues) / (float totalCount)

    // Log2(1.0) = infinity, short circuiting this part
    if trueValues = totalCount || falseValues = totalCount then
        0.0
    else
        -probTrue * Math.Log(probTrue, 2.0) + -probFalse * Math.Log(probFalse, 2.0)

/// Given a set of data, how many bits do you save if you know the provided attribute.
let informationGain (data : Record seq) attr =
    
    // Partition the data into new sets based on each unique value of the given attribute
    // e.g. [ where Outlook = rainy ], [ where Outlook = overcast], [ ... ]
    let divisionsByAttribute = 
        data 
        |> Seq.groupBy(fun item -> item.GetAttributeValue(attr))

    let totalEntropy = entropy data
    let entropyBasedOnSplit =
        divisionsByAttribute
        |> Seq.map(fun (attributeValue, rowsWithThatValue) -> 
                        let ent = entropy rowsWithThatValue
                        let percentageOfTotalRows = (float <| Seq.length rowsWithThatValue) / (float <| Seq.length data)
                        -1.0 * percentageOfTotalRows * ent)
        |> Seq.sum

    totalEntropy + entropyBasedOnSplit
    
// ----------------------------------------------------------------------------

/// Give a list of attributes left to branch on and training data,
/// construct a decision tree node.
let rec createTreeNode data attributesLeft =
    
    let (totalTrue, totalFalse, totalCount) = countClassifications data

    // If we have tested all attributes, then label this node with the 
    // most often occuring instance; likewise if everything has the same value.
    if List.length attributesLeft = 0 || totalTrue = 0 || totalFalse = 0 then
        let mostOftenOccuring = 
            if totalTrue > totalFalse then true
            else                           false
        Leaf(mostOftenOccuring, data)
    
    // Otherwise, create a proper decision tree node and branch accordingly
    else
        let attributeWithMostInformationGain =
            attributesLeft 
            |> List.map(fun attrName -> attrName, (informationGain data attrName))
            |> List.maxBy(fun (attrName, infoGain) -> infoGain)
            |> fst
        
        let remainingAttributes =
            attributesLeft |> List.filter ((<>) attributeWithMostInformationGain)

        // Partition that data base on the attribute's values
        let partitionedData = 
            Seq.groupBy
                (fun (r : Record) -> r.GetAttributeValue(attributeWithMostInformationGain))
                data

        // Create child nodes
        let childNodes =
            partitionedData
            |> Seq.map (fun (attrValue, subData) -> attrValue, (createTreeNode subData remainingAttributes))

        DecisionNode(attributeWithMostInformationGain, childNodes)

The entropy and informationGain functions were covered in my last post, so let’s walk through how the actual decision tree gets constructed. There’s a little work to calculating the optimal decision tree split, but with F# you can express it quite beautifully.

let attributeWithMostInformationGain =
    attributesLeft 
    |> List.map(fun attrName -> attrName, (informationGain data attrName))
    |> List.maxBy(fun (attrName, infoGain) -> infoGain)
    |> fst

First, it takes all the potential attributes left to split on…

attributesLeft 

… and then maps that attribute name to a new attribute name / information gain tuple …

|> List.map(fun attrName -> attrName, (informationGain data attrName))

… then from the newly generated list, pick out the tuple with the highest information gain …

|> List.maxBy(fun (attrName, infoGain) -> infoGain)

…finally returning the first element of that tuple, which is the attribute with the highest information gain.

|> fst

Once you can construct a decision tree in memory, how do get it out? The simplest way is to print it to the console.

The code is very straight forward. Note the use of ‘padding parameter’, so that recursive calls get indented more and more. This is a very helpful technique when printing tree-like data structures to the console.

/// Print the decision tree to the console
let rec printID3Result indent node =
    let padding = new System.String(' ', indent)

    match node with
    | Leaf(classification, data) ->
        printfn "\tClassification = %b" classification
        // data |> Seq.iter (fun item -> printfn "%s->%s" padding <| item.ToString())

    | DecisionNode(attribute, childNodes) ->
        printfn "" // Finish previous line
        printfn "%sBranching on attribute [%s]" padding attribute
        
        childNodes
        |> Seq.iter (fun (attrValue, childNode) ->
                        printf "%s->With value [%s]..." padding attrValue
                        printID3Result (indent + 4) childNode)

However, it’s almost the year 2010. So in lieu of flying cars perhaps we can at least do better than printing data to the console. Ideally, we want to generate some sexy image like this:

You could painstakingly construct the decision tree using Microsoft Visio but fortunately there are tools to do this for you. AT&T Research has produced a great tool called GraphViz. While the end result doesn’t quite have sizzle, it’s very easy enough to get going.

The following function dumps the decision tree into a format that GraphViz can plot. (Just copy the printed text into the tool and plot it using the default settings.)

/// Prints the tree in a format amenable to GraphViz
/// See http://www.graphviz.org/ for more format
let printInGraphVizFormat node =

    let rec printNode parentName name node = 
        match node with
        | DecisionNode(attribute, childNodes) ->

            // Print the decision node
            printfn "\"%s\" [ label = \"%s\" ];" (parentName + name) attribute

            // Print link from parent to this node (unless it's the root)
            if parentName <> "" then
                printfn "\"%s\" -> \"%s\" [ label = \"%s\" ];" parentName (parentName + name) name

            childNodes 
            |> Seq.iter(fun (attrValue, childNode) -> 
                    printNode (parentName + name) attrValue childNode)

        | Leaf(classification, _) ->
            let label =
                match classification with
                | true  -> "Yes"
                | false -> "No"
            
            // Print the decision node
            printfn "\"%s\" [ label = \"%s\" ];" (parentName + name) label

            // Print link from parent to this node
            printfn "\"%s\" -> \"%s\" [ label = \"%s\" ];" parentName (parentName + name) name

    printfn "digraph g {"
    printNode "" "root" node
    printfn "}"

So there you have it, ID3 in F#. With a little bit of mathematics and some clever output you can construct decision trees for all your machine learning needs. Think of the ID3 algorithm in the future the next time you want to mine customer transactions, analyze server logs, or program your killer robot to find Sarah Conner.

<TotallyShamelessPlug> If you would like to learn more about F#, check out Programming F# by O’Reilly. Available on Amazon and at other fine retailers. </TotallyShamelessPlug>

ID3.fsx