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.

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# - 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++;
    }
}