"I'm sorry Dave, I can't allow you to do that". That chilling statement made by the machine HAL in 2001 A Space Odyssey is just one of the many examples of how humans have been fascinated by the idea of artificial intelligence. I myself am very interested in the subject and hope to go back to graduate school for a degree in the field. In the meantime I'm writing small applications like these to demonstrate what AI can do.

This is an ASP.NET application that will play a perfect game of Tic-Tac-Toe using the AI algorithm called minimax. First a little about the game Tic-tac-toe. It is a deterministic game, meaning that all actions have a direct and knowable consequence to the game state. It is what theorists like to call a "Zero Sum" game - where the compluter has complete, or perfect information about the game state, the game space, and the environment. 

As with the majority of things in AI, what the sitation boils down to is search. Here's the components we need to have in order to complete our search of the tic-tac-toe game space:

• An initial state. For us this is an empty board
• A successor function. A method which gives us the resulting states that are accessible by making a particular action against the state we pass in.
• A terminal test. A method that determines if we are in a terminal state - i.e., whether the game is over or not. In our case it would be Player 1, Player 2, or draw (cat's game).
• A utility function that gives a numeric value for terminal states.

Since tic-tac-toe is a turn-based, two player game, it lends itself to using the minimax algorithm to determine the best move for a given state. The minimax algorithm is a little bit confusing.  Here's a really simple rundown:

In a normal search situation, you use a initial state and determine a sequence of moves to get you to your desired goal state. However, in turn based games, there is not just one player MAX, but the opponent player MIN that we must worry about. MIN's moves can impact the game states that are available to us and indeed can render our desired goal state (where we, MAX win) unreachable. That of course is not satisfactory. What can we do? The MAX player, the first to make a move, must pick a move that has the highest value returned by the utility function.

However, assuming MIN plays optimally, MIN will also try to choose the best move that he can, thus minimizing MAX's outcome. Thus, MAX should make the move that minimizes the value of MIN's utility function. In other words, the computer MAX, should make the move which leaves its opponent capable of doing the least damage.

Hopefully that sheds some light on how the algorith works. For an in-depth discussion  of the details of how minimax works, see this article at the AI Depot. (Note that our algorithm makes use of Alpha-Beta pruning to reduce our search tree).

-------------

Now that we have talked about how our AI logic works, lets look at the architecture of our application. Even though this is a small application, I made use of the N-Tier approach to web programming. Since our example is simple, we will only have 2 layers: our presentation layer, and our business logic. In laymans terms, this is just the layer that displays our information and the layer that contains our logic, respectively. The reason I did this is because it helps us modularize our code for easy re-use and modification, and makes the code much cleaner to read.

I created an ASP.NET User Control to display our tic-tac-toe board, then placed it in an ASP.NET page that configures and displays it. The User Control in turn uses a custom Board object that I created that represents the tic-tac-toe board as an object. I have methods implemented in a separate class that performs the Artificial Intelligence operations on the Board object. 

Board.cs

This is the class that serves as a wrapper class around a simple integer array. The positions in the array map to positions on the board; e.g. the first three spaces on the first row map to the first 3 positions in the integer array. We also implement the ICloneable and IEnumerable interfaces. ICloneable so that we can make an exact duplicate of a board and manipulate it and not touch the original. The IEnuerable interface is optional, but it lets us use a foreach statement to traverse the board, which is handy. The class also includes helper methods like IsFull, that can tell us some information about a given board.

MinimaxAlgorithm.cs

This is where the magic happens. This is the C# implementation of the minimax algorithm with alpha-beta pruning. The class implements an IGameAlgorithm interface which is an interface I created that has on simple method in it named Solve. It take a Board object as an argument and returns the optimal move. I did this so that when calling the algorithm, we can call the interface and not the class itself. That way, if we want to swap out the algorithm for a different one (say with a Q-Learning Reinforcement Algorithm), it will be quite easy. Here's the meat of the code:

As you can see the code is not very complex or long. It's just very recursive, which can be confusing in its own right.

BoardManager.cs

This class encapsulates the different actions that we want to perform on the Board. If we want to make a move on the board, or compute the next best minimax move, this class handles that through a bunch of static functions. It helps to have all of this code localized into one place. 

As I mentioned, all the methods that we need to interact with a Board are handled in this class. This is our true "business logic" component of the system. It functions more like a facade design pattern than anything else.

Continue on to the next page to get the rest and the source code...