Tic Tac Toe in Silverlight

When I first started looking Silverlight, I looked around for tutorials that focused on topics I find interesting. I have found that I typically learn better if I'm applying learning to topics for which I have a passion.

I love games and one of the simplest is Tic Tac Toe. I thought if I could find a tutorial on implementing Tic Tac Toe in Silverlight, it would not only teach the basics of Silverlight development but would also teach how to interact with graphics. Unfortunately I could not find such a tutorial.

I eventually waded my way through much less entertaining tutorials and got my programming feet wet with Silverlight. As a test of my learning I wrote a two player Tic Tac Toe game.

After finishing my first AI post on Rock/Paper/Scissors I started looking for my next AI project. Well I had that two player Silverlight game laying around, how about I write an AI opponent for it?

What could be easier?

Well a lot of things could be easier, like "Hello World", but once I get my teeth into a project I see it to the end. Well, first things first, how have others designed AI opponents for Tic Tac Toe? A quick google search proved that I was definitely not blazing an new trails here. I found tons of examples for just about every type of AI for Tic Tac Toe.

But this webpage gives a simple set of patterns for matching. Best of all, they could be implemented using Regular Expressions!

So, here is my Silverlight AI Tic Tac Toe game where the pattern matching AI is implemented using Regular Expressions.



And here is a zip file containing the entire Visual Studio 2008 Project.

Programmers must continue to stand on the shoulders of giants

Many of the greatest thinkers credit their accomplishments to those that came before them by stating the old saying that even a dwarf can see farther than a giant when the dwarf stands on the shoulder of the giant. Or, in other words, they came to their breakthroughs by understanding the research and works created by notable thinkers of the past.

How can that help modern programmers? Simple, when was the last time you read a computer book or magazine? It does not matter what the subject was, just the fact you read it added a little bit to your knowledge and experience. It is amazing what great little tidbits you can find to enhance your abilities.

For me, that two that come to mind the fastest are from Programming Pearls by Jon Bentley, first published in 1986 and Expert C Programming: Deep C Secrets by Peter Van Der Linden first published in 1994.

From Programming Pearls, I learned the lesson that a senior developer should never answer the question that he was asked, but instead answer the base need that spawned the question. In Programming Pearls, the programmer asked how to do a disk-based merge sort. Now, yes I know that coding things like that went out of style a looooong time ago, but the underlying process that the author used to help the programmer has stayed with me ever since. This is because the author did not show the programmer how to implement the disk-based merge sort, but instead learned what the base problem the sort was supposed to fix and with his greater programming and analyst experience came up with a much faster and more elegant solution. No, I’m not going to tell you want the solution was, go read the book!

From Expert C Programming: Deep C Secrets, I learned a very simple programming principle: look at a problem from both directions. Where from one direction, a problem may include complex tracking code, worked the other way, the problem may be quite simple to code.

What does that exactly mean? Let us look at an example:

Say you need to build a comma delimited list of numbers from some input. You could say “I need a comma after every number except the last”. This is the normal view and leads to either adding a comma after every entry and then removing the last one once you have exited the loop, or checking in every iteration if its time it is the last element so that you do not add the comma.

But if you look at it from the other end and say “I need a comma before every number except the first”. Once stated this way, the problem is simple. It’s much easier to code a beginning edge case than an ending edge case.

The point of this post was not just to share these two fun little facts, but to show that we, as senior level developers, and those that wish to become senior level developers need to continue reading and learning. As long as we do that, the giants that we stand on will keep getting taller.

The simplest AI in C#

Creating board games on the computer is easy, creating an opponent to play the game against is hard.

A lot of us programmers out there are also board game enthusiasts. We would like nothing better than to sit down in front of the computer and spend a few hours out maneuvering some truly diabolical AI opponents. Whether it’s crushing the Axis in Axis and Allies, dominating Europe in Diplomacy or simply enjoying a quick game of world conquest in Risk, we get to enjoy our favorite board games without the need to coordinate a date and time with up to five or six of your friends. Even when you can take on each other online, sometimes getting everyone together is harder than winning the games you wish to play.

Well with a good AI, all your games become playable by yourself and with a great AI, they become obsessive as you try to, at first barley hold your own and later to finally dominate these awesome challengers. Yet, how are these opponents created? Other than creating a completely random opponent, writing an AI to play a board game at a high level is one of the hardest things in programming you could do.

Which brings me to my point: I’m not going to show you how to create a diabolical AI opponent. I’m not even going to say if I even know how to. What I want to show you though, is how to take that first step in writing AI’s, by creating what could possibly be the simplest AI opponent ever … for the game of “Rock, paper and scissors”.

There are many types of AI opponents, but in “Rock, paper and scissors” the only type of opponent is one that tries to predict his opponent’s next move. So let’s create a predictive AI.

What is the one piece of data that a predictive AI needs to calculate a decision? His opponents’ prior moves. So, as play of “Rock, paper and scissors” continues, we will need to accumulate the human player’s prior moves. The easiest way to do that is to hold them in a string, each character (‘R’, ‘P’ or ‘S’) representing a move.

To keep it simple, my AI will look for three move patterns. It will take the last two moves off the end of the string and add each of the three possible moves, in turn, on the end and do a string search to find how many times the human opponent played the same three move pattern previously. The IA will assume that the pattern with the highest count will be the one the human plays and will choose the move to beat it. If there was a tie (Even if that it is a tie of zero count for all three possible patterns) a move is picked randomly among the tied choices. Just to through a bit of confusion in, 10% of the time, the AI’s move will be completely random.

Now, this AI is by no means unbeatable, but playing against it in a race for the first to win 100 games, it is a very tough opponent, just like AI opponents should be.

The complete code for a console application implementing the “Rock, paper and scissors” AI can be downloaded here.

C# Yields a better Fibonacci Sequence

In the title of this blog entry I've done a bit of punning. This quick blog entry is about an alternate usage of the Yield command and how, for example, it can help build a better FibonacciSequence() function.

With the addition of the Yield command, we can now create looping functions that return a value for each iteration. Ever need to walk through a sequence and perform some fuction for each element? Now it is as easy as pie!

private IEnumerable FibonacciSequence(int MaxIterations)
{
    decimal i = 0;
    decimal j = 1;

    while(true)
    {
        yield return j;
        MaxIterations--;

        if (MaxIterations==0) yield break;

        var temp = (ulong) j;
        j = temp+i;
        i = temp; 
    }
}

private IEnumerable FibonacciSequence()
{
    return FibonacciSequence(49);
}

C# - Counting the number of occurrences of a substring - Take two

In my last post, I stated that I knew of only one way to find a count of all the substrings within a string without looping through the string. Well, a co-worker pointed out to me the other day that I had shown a non-looping way to count all the substrings within a string when I gave a class on Regular Expressions.

That is true. A very simple Regular expression:

new Regex(mySubString).Matches(myString).Count

But, that simple line of code is not the reason for this post. I've found an even deeper issue, and it all comes down to how you define the problem (doesn't it always).

Lets say that my string is "BOBOBOB"

How many instances of the substring "BOB" is in "BOBOBOB"? 2 or 3?

My way in the previous post and the regular expression both agree, the number is 2.

But, say you are writing a game and you are using a string to store previous moves. Each move can have only two choices: a 0 or a 1. So after a number of moves, the storage string could look like this "0111110010100111110110111101".

Now, how many times did the player choose to play a 1 after playing a 1 the prior two moves, i.e. a "111"? If you did a substring search, you would get a 3. But if you count the number of times "111" appear including overlap, the number is much higher: 8.

So, an AI routine that was based on prior moves would need to find all combinations of "111" even if one set is partially contained within another.

So, here is my LOOP that counts the number of substrings within a string, even if the substring is partially contained within another substring.

for (var i = 0; i <= myString.Length - mySubString.Length; i++)
{
    if (myString.Substring(i, mySubString.Length) == mySubString)
    {
        count++;
    }
}