Connect4 in Flash

Inspired by Giorgio Sardo who used my old Connect4 code to demonstrate moving a c# game to Silverlight for Mobile (when will you put that code online, Giorgio?) in a PDC 2008 session, I decided to use the same code as the basis of a project I had to do for a flash course last year.

This time, I didn't migrate all of the code, but rather made the flash talk to a back-end c# web service that calculated computer moves.

I know it's still a bit buggy - but some of you out there might enjoy it. While making it I found what could seem like a bug in ActionScript 3 - making it quite difficult to drag and drop nested objects....But I might share more about that later.

Try the original plain html here.

Try the new flash version here.

Code and written project will be available later.

Flash Rss Reader

Another little flash gadget I just made... An RSS reader. Yes, I know it's an original idea - but it seemed like a good, comprehensible, and to some degree useful thing.

For fun I made iPhone style navigation - in the sense that you need to drag right or left to move between items.
It lists the blog feed from labs.episerver.com.

The trickiest thing was to handle all the security around loading a URL in flash. Flash can only load data from the same domain as it is located on (or another domain that has a crossdomain.xml file in the root, allowing flash access). Anyway, the simple solution was to make a small rss proxy in c# (around 3 lines of code) and put it on my test-domain together with the flash app.

Solving Sudokus as CSP with Forward Checking

When you think about it, a Sudoku is a perfect example of a Constraint Satisfaction Problem, and so it made good sense that the final programming assignment in the IAIP course I'm taking was to solve a Sudoku as a CSP, using forward checking.

The basic idea is to define the problem as a set of variables (in this case 9*9=81 variables), where each has a finite domain of potential values (by default values 1-9 in this Sudoku example) and then there's a number of constraints connecting the variables. For the Sudoku these constraints ensure that the numbers 1-9 are distinct in every horizontal and vertical line, as well as in the same 3x3 square.

Once the problem is defined as a CSP there's several approaches to solving it. The assignment this time was to implement Forward Checking. The basic idea with forward checking is to make a backtracking depth-first search in the solution space, but every time a variable is assigned, the domains of all the affected variables (due to constraints) will be modified. If a domain becomes totally empty, we backtrack. It all sounds terribly complicated but it's really a straightforward approach, assigning the variables one at a time and whenever something is assigned revise the possible values for the rest of the affected variables.

As usual we were supplied with a nice codebase to extend to (in fact all we had to do was more or less to implement the Forward Checking part), but also as usual the entire codebase was in Java. This time it made the most sense to simply port it to C# and it didn't take much more than an hour to port the main solver class and even refactor a little.

The report can be seen here.
The project files can be found here.

Solving NQueens using Reduced Ordered Binary Decisision Diagrams

Here's one of the things I've been too busy to post:
At my AI course we've completed our last 2 assignments. The one that I'll post here is the N-Queens problem solver, that helps solving the n-queens problem using BDD's.
BDD's is a really clever technique that can help solve some satisfiability problems quite fast.

The N-Queens problem is a classic problem, described lots of places. The derives from the 8-queens problem, thats how to fit 8-queens onto an 8x8 chess board without any of them threatening the others (according to the rules of chess).
It can be solved in many ways, but BDD's is a quite efficient way of doing it.
The basic idea is to build a binary decision diagram, where every node corresponds to a variable in the problem, construct the diagram according to the rules (constraints) that apply to the specific problem and along the way reduce the diagram according to a couple of rules (and to avoid duplicate node-childnode patterns).
How we choose to assign the nodes can be found in our report (as always written with Thomas Gravgaard and Peter Thygesen). Also, a final web-version of our solution can be tried out here.

Awesome IKVM; Interact with JAVA from .NET

Yet again I've java in my studies at ITU. The current assignment Peter, Thomas and I are working on is to implement an assistant that helps a user solve the classic N-Queens problem using Reduced ordered Binary Decision Diagrams (RoBDDs or simply BDDs).
There's many(!) ways to solve that problem, but using BDDs does seem like a very intriguing approach. The only problem: it requires a BDD engine. We could of course write our own (and actually I'm currently working on that), but in the assignment we were given, there was actually a fully functioning BDD library ready for us to use. Only, it was in java... (NOTE: I don't have any problem with java and I'm not religious in any ways, but usually .NET is my weapon of choice).
"No problem, we'll just use J# to handle it like last time" was the initial reaction.
But, alas, the library was already a compiled jar, no source included. Naturally we could get all the source from sourceforge and port it to J#, but the time seemed right to try a new clever approach!
Luckily Peter found the right solution: Enter IKVM! IKVM is a great set of tools to interact between java and .NET and it works like a charm.
The two main tools is a command-line program that allows you to run compiled java files in .NET instead of java's virtual machine. The other tool that proved to be really useful to us, will allow you to take a JAR and transform it into a .NET DLL.
All I had to do was to call it command-line with the name of the JAR file and the name of the .NET output file, and run it - and in no time I had a working .NET dll that I could reference directly in my .NET projects.
In order for the referencing programs to work though, it's important to have two of the IKVM dlls' included in the "bin" folder or in the GAC (namely the "IKVM.GNU.ClassPath.dll" and "IKVM.Runtime.dll").
Great work, IKVM guys. Keep doing your magic!

And the programming assignement? Well, here is how far we've gotten so far. Keep in mind that it's work in progress. After the hand-in deadline I'll make a new post about how we did it.
I'm also considering trying out other of the known approaches to solve the same problem and comparing them. Drop a comment if you'd be interested in knowning what works best :-)

DPLL in C# - Satisfying problems in CNF

Time for another AI post! These last couple of weeks I've been working with two fellow C# guru's, Peter Thygesen and Thomas Gravgaard on an assignment in our AI class, on implementing a couple of specific parts of the DPLL algorithm, such as the methods for choosing split symbols, finding unit clauses and identifying pure symbols.
"What's DPLL good for?" I hear you cry...Well, it's simple really - or actually it isn't all that simple but I'll try to explain it anyway.Suppose you have a boolean statement in CNF (conjunctive normal form) and you want to test if it's satisfiable, that is - if a certain configuration exist, that will make it true - then you can run the DPLL algorithm to find out. The DPLL basically searches the solution space, but during the search uses the unit-clauses and pure symbols to prune the search space.In other words (and hopefully more understandable words) if you have a problem that you can formulate as a boolean problem (A and B or C implies D), then you can change that formulation into conjunctive normal form ((A or B or C) and (A or D or E) ... ) and when thats done you can determine if it's actually possible to assign values to the variables that will make this true.The way the algorithm works is basically to pick a symbol (=variable) and assign it true or false, and then for each options recursively call itself until all variables are assigned. In order to minimize the search space it uses a couple of simple rules to shortcut through this search, like finding out which clauses only contained one unassigned symbol. It's also very important in what order it assigns variables.
Another challenge in this assignment was that the code provided for the assignment that we should use as a basis for our work and for testing was all in java (typical university assignment). We're all C# people but too lazy to rewrite everything in C#, so luckily we got the java-code working in J# and were able to base our code on it anyway (and I wouldn't be surprised if our execution performance is higher that if we had used java).

Read our project here.

Back from Budapest

After spending a nice relaxing week in Budapest, seeing the sights and enjoying the spa's, I'm back in full force. One working day left, and then a loooong eastern which will be an excellent time to blog and code a bit more than what has been usual for the last couple of weeks.
I hope to get somewhere with the Poker Bot tournament, work on the DPLL group-assignment I'm in and perhaps also play around a bit with BDD's. For those who don't know what a BDD is, I'll post about it later. Until then, check out these really cool demo's at Configit Software, an ITU startup that uses BDD's in real life!

Connect 4: The code

Yesterday I handed in my code for the Connect4 game. Since the deadline has now passed I figured I might as well post it here, including the document I wrote to describe it. In case you want to play it again, do it here.

Download the code for this article here.

Introduction

In order to complete the assignment of making an implementation of a computer player for the game "Connect four", I started out by making an environment, a state model and a simple console based interface to test it.

The console based interface works by showing the current state as 7 columns with 6 rows in each. When it's the users turn, he/she should choose one of the 7 columns, by using the numbers 1-7. It is a very simple and basic UI because I wanted to my time on developing the search algorithm that will determine the computers moves.

To run the code, compile the project with a C# 2.0 compiler and run the executable. I've included solution and project files for VS2005 as well.

The console program also contains some experimental functionality that allows you to set up the computer to play against itself. This code was used when I was optimizing the weights of the evaluation algorithm, but is now commented out.

The Connect Four game has been "solved" by Victor Allis, and there is a "Perfect Play" path you can follow, that will force a win to the starting player. However I have chosen to disregard that playing strategy in this implementation since the goal was to learn about AI game-playing.

Class overview

Connect4: The main game class, that holds the current state and controls the flow of the game. In turn calls each of the two players, typically Computer and Human and executes their actions.

StateType: A state, containing the board, the number of moves made, and who is next in turn. It also contains methods to clone itself and perform a move, as well as evaluate if it is in a game-over state.

Computer: The class that holds all the logic related to the search algorithm. It is called like a player using the PlayerTurn(StateType state) method, and then begins to perform a modified MiniMax search with Alpha-Beta pruning to determine which action to choose. Its functionality is described below.

Human: The Human player. The PlayerTurn(StateType state) method is called by Connect4 every time it's the users turn. This then presents the state to the console and waits for input. When an action is retrieved it returns the action, a move is made and the turn changes.

Search Algorithm

The Search algorithm is a modified MiniMax algorithm with Alpha-Beta pruning. It is implemented in the "Computer" class, which controls the computer player.

Using double recursion is performs a depth-first search in the state-space until the cut-off method evaluates to true. At this point it uses the heuristic evaluation method to determine how close it (the computer player) is to winning. This value is passed up through the state tree, where each node either selects the maximum or the minimum of its values, depending on if it represents the computers turn or the players turn. The procedure is in fact quite similar to how a typical human player subconsciously would play the game: First enumerate the possible actions from the current state, then estimate the opponents move from any of the resulting states, and decide which would leave you in the most favorable state. However human (non-expert) players will typically only look 2-3 moves ahead, while the computer can search a much larger state-space.

In order to further improve the performance Alpha Beta pruning has been applied. This essentially is to remember the best (or worst) options for each node, so no time will be wasted exploring branches of the trees that's already identified as path that will not be played.

Heuristic Evaluation method

The Evaluation method is supposed to evaluate how good a given state is for the computer, e.g. how close is it to winning the game. After having experimented with several different models I found an approach that suited me the best in evaluation a state. In order to win the player must have 4 fields in a row, horizontally, vertically or diagonally. To find out how close both players was to this, I decided to examine all possible combinations of 4 fields that appear in a row in the 7*6 field board. First I would break it down to lines, horizontally, vertically and diagonally and evaluate each line. All lines I examine will of course need to be 4 fields or longer.

An example, a line with 7 fields would lead to the following possible winning combinations:

1 2 3 4 5 6 7 => 1234, 2345, 3456, 4567

For each of these combinations my evaluation method would examine the amount of them taken by each player. If none of the players or both of the players has selected fields in the same 4-field combination, the combination will be instantly discarded. Otherwise it will add to a state-score depending on the number of fields taken (how close it is to be a 4-in-a-row). Depending on the number, and if it's computer or player fields, a certain weight will be applied.

Determining the evaluation weights

Initially I started out with weights that was the square of the number of occupied fields in each block of four (e.g. 3-in-a-row would give a score of 9, 2 would be 4, 1=1) and if state resulted in 4 in a row it would get a big bonus / punishment of 10000/-10000.

However, it quickly became evident that I would at least need to raise the punishment if the player had 4 in a row, or take into account whose turn it was, to keep the computer player from focusing solely on its own block-building. After that optimization it became increasingly difficult to manually fine-tune the optimization of weights, since no matter how I adjusted them, I still couldn't beat the computer.

So I set up a game to allow two computer players to play against each other. The first player had the starting advantage, and the current weights. The second player would have almost the same weights, except one little difference at a time. If the second player would win in spite of the first player having the starter’s advantage, I would use the new weights as the current weights.

After having gone through this manual iteration 15-20 times, I decided that it was fairly optimized. If time had permitted I could imagine automating this process, perhaps using Simulated Annealing. However I felt that this was outside the scope of the current assignment.

Cut-off Method

Since the state space will typically be too large to explore in reasonable time, it's necessary to cut-off the search at a certain point.

First of all the cut-off method should be able to detect if we've actually reached a winning state, in which case it should always cut-off, alternatively it should determine if it is feasible to stop the search at the current level.

After experimentation I decided on a simple cut-off mechanism that cuts of the search after looking 6 moves ahead. 7 moves also seem possible within the allowed time-frame but I'm too impatient to wait more than 1-2 seconds for every move when playing.

An ideal approach would of course be a more intelligent cut-off mechanism that would keep searching until all available time was used, however time did not allow for such a solution at this time.

AI: Connect 4 Game

I have been kinda slow in posting these last couple of weeks. One of the reasons is of course that I've been busy coding (as always). This time however, it's actually real homework thats been keeping me busy.

In the AI course I'm taking at ITU we were assigned the task of making our own version of "Connect 4" - the well known board game where you drop coins into a board from the top and try to get four in a row, horizontally, vertically or diagonally - and preferably before your opponent.

I know that this game has already been "solved" and there exist a perfect solution for it. But nevertheless it's still interesting to make an algorithm that calculates the computers move.

In order to do this I've used a variant of the MiniMax algorithm, optimized with Alpha/Beta pruning. The basic idea is to search through a tree of possible actions and thereby thinking ahead to find the best possible action in order to go from an initial state to a goal state (win).
A state would typically consist of current game-board, and who's turn it is. From a state there's often 7 possible actions - each of the columns that it's possible to choose. If a column is full the number of possible actions decrease.
So, in theory, every time it's the computers time to move we would like to build a tree, starting at the initial (current) state and then branching out with the possible actions. Each of the possible actions will lead to a new node, that indicates the opponents move. The opponent again have a number of possible actions, and we assume that he will always pick the action that is best for him (= worst for us, the computer). This means that we can build a double-recursive method to traverse this tree, taking turns choosing the action with the maximum and minimum outcomes for us and thereby in the end evaluate which of the current actions available to us is the best (= where it's most likely we will win, even if the opponent does his best to screw it up).

If you haven't played around with algorithms like this before it might sound kinda complicated but it's really just applying the same method as most of us do in our heads when playing a game like this: "So, let me see.....if I select this column, then he will most likely select that column which means that I'm certain to win in the following move". However, where as humans often have difficulty thinking more than a couple of moves ahead, computers often have a better chance.

But there's one catch: Even with a game as simple as Connect 4, thinking several moves ahead scales terrible. Except for when the columns starts to fill up, there's 7 possible actions. For each of these actions the opponent can again choose 7 actions bringing us up to 7^2 (=49) states we need to consider. I've found that a typical game of Connect 4 often goes to at least 30 moves before a winner is found, meaning that we would have to examine something like 7^30 (=22539340290692258087863249) states. Of course Alpha-Beta pruning can help a lot on that, but in the end it'll still be too much to calculate in reasonable time.
Thats why it's a bit of a modified Minimax with AB pruning algorithm I use.
Instead of searching all states till it reaches a terminal state it will search until it reaches a certain cut-off depth. At that time it will apply some heuristic evaluation to the cut-off states to determine how close it is to winning in those states.
By experimentation I've so far found that to think 6-7 moves ahead makes the most sense performance wise. Perhaps even 8 will be a possibility if I optimize some more and allow the computer more time to think for each move.
The trick to achieving success even after "only" thinking 6 moves ahead is to have a good evaluation function that gives an accurate impression of how well the computer is doing compared to the player. I seem to have found one that works pretty well (so far only one of my friends have reported to have beat the computer once). The details of the evaluation function, along with code for the rest of my project you'll have to wait for until the project is officially handed in (there's going to be a computer vs computer contest in my class - not unlike the poker robot tournament I'm working on).

As for now, you can try out my game here! You always get to start first, you are red computer is blue. (And yes, I realize there are a couple of bugs still - no need to report them I'm working to fix them).

AI Efficient Programming

Today I started on a new course on ITU, entitled AI Artificial Programming. I've often before played a little around with various ML mechanisms, Neural Networks, m.m. but never studied AI in a structured mannor.. So far the course looks very promising.
I bought a couple of books for the course that both seem really good:

• Artificial Intelligence: A Modern Approach (2nd Edition), Russel & Norvig
  
• AI Application Programming, Jones

As soon as I find my feet in this course I'll post some of the silly AI thingies I'm destined to make :-)