Skip navigation

Tag Archives: open source

It’s been a while since the last post.

This post is to announce a new version of Freekick 3, the latest rewrite of my project of writing a soccer game. It doesn’t have fancy graphics (on the contrary, it’s very ugly), but it tries to provide a fun soccer game to play nevertheless.

This is actually the first announcement of Freekick 3. The previous announcement on the Freekick series was the announcement of Freekick 2. Here’s a short overview of the features.

– A few different game modes, including friendly games, knockouts, leagues, seasons and a mockup of a career mode.

– The team, league and player data is not included, but can be imported to Freekick 3 either from Sensible World of Soccer data files or, my favourite, from Wikipedia. By having a script to fetch all the data from Wikipedia it’s ensured that the data is relatively up-to-date and that there’s a fair amount of teams to play against.

– The AI is improved and may provide a nice challenge.

– You can either control the whole team in the match or choose to just control one player.

You can download Freekick 3 (source) from https://github.com/anttisalonen/freekick3. I’ll show a quick tour around Freekick 3.

This is the main menu (quite similar to Freekick 2).

This is the main menu (quite similar to Freekick 2).

After fetching the data from Wikipedia you have lots of teams to choose from.

After fetching the data from Wikipedia you have lots of teams to choose from.

You can tune the line up before the match.

You can tune the line up before the match.

During a match - about to cross.

During a match – about to cross.

Career mode currently includes a league season along with the national cup.

Career mode includes a league season along with the national cup.

Football league two mid-season table.

Football league two mid-season table.

Fighting for the ball mid-field.

Fighting for the ball mid-field.

Behold, Kingdoms 0.1.0 has been released. Kingdoms is a hobby project of mine I’ve been working on for the past couple of months. It’s a strategy game, where you lead a nation from stone age until the bittersweet end – in other words, a Civilization-like game. I’ve been wanting to write one for a long time, and I’m glad to see it’s doable.

It borrows features from all Civilization games I’ve played: graphics from Civ 1 (because I’m no artist), the configuration file type from Civ 2 (back when it was simple), strategic resources and culture from Civ 3 and (part of) the combat system from Civ 4. By the way, that’s also the reason why I wanted something else than FreeCiv: I find it’s too similar to Civ 2, which was never my favorite Civ game.

Here are some screenshots:

Babylonians vs. Aztecs

A map editor is included

You can get Kingdoms from its web page – there’s the source as well as the Windows binary. There are still quite a few features I wanted to implement but haven’t had the time yet, so if something bugs you, let me know.

About a month ago I announced my then-latest programming project, Star Rover 2. It’s a space flying game written in Haskell, and while programming that was fun and I learnt a lot from the project, it was time to find something else to do. So I started another soccer project, again in Haskell (like in September 2008), but with a bit more Haskell experience under my belt.

And now, after almost a month, it’s time for the first release. The new soccer game is called freekick2, and it’s an open source 2D arcade style soccer game.

If you have cabal, you can install it with a simple cabal update && cabal install freekick2. Here’s a screen  shot from a menu:

The freekick2 distribution includes only a few fantasy teams, but you can use the data files from a Sensible Soccer game for some additional realism.

One lesson I learnt when doing Star Rover 2 is that I should avoid over-engineering like plague, as that was probably one reason why I couldn’t get the first Freekick versions in a releaseable state.

Freekick2 now consists of about 3200 lines of Haskell code, around 1000 more than Star Rover 2, and it’s also a bit fancier, graphics-wise. With Star Rover 2 I used monad transformers to handle the main loop and state changes, which worked pretty well, and I’m using the same technique with freekick2. I still haven’t figured out the whole FRP thing, but game programming in Haskell seems to work out pretty well without.

Things I’ve learnt while programming freekick2:

* Texture mapping with OpenGL in Haskell. To load the textures you need to play around with pointers a bit, which are not really that usual in Haskell. But you can do it, and with the help of some great small libraries like pngload it’s relatively simple in the end. Adding dynamic recoloring of the textures after loading them (to support multiple kit colors) was fun as well.

* Parsing binary data in Haskell. Over a year ago, when I was writing Freekick in C++, I wanted to deserialize the SWOS data files (the format’s known; many thanks to the ones who figured the format out) and I thought parsing binary data sounds like a job for C or C++. The result from back then is about 850 lines long and took a few hours to write. Granted, it also generates some XML. Now I wrote a program to do the same task in Haskell; the result has 250 lines and was written in less than two hours. The Haskell version also includes code for writing SWOS data files – a feature I added just because it was so easy to do. Later, for the freekick-internal data structures, I let BinaryDerive derive the serialization/deserialization code for me. Needless to say, I won’t be doing binary data parsing in C anymore if I get to choose.

* Template Haskell. The state in freekick2 changes pretty often, and is managed in a State monad. I needed a lot of functions of type (FieldType -> FieldType) -> State -> State (like already with Star Rover 2), usually one for each field in a record, and so I let TH generate them all for me. Bulat’s tutorials (links to them can be found here) were a life saver.

* Implementing a GUI with colors, textures and dynamic content, with a tree-like hierarchy for screens.

* Use of the existential quantification language extension for heterogeneous collections. I’ve spent some time with object oriented design in the past, which sometimes leads to object-oriented designs in Haskell, so that something like existential types are needed. In this concrete case, I created the class Sprite, with both the player and the ball implementing it. The easiest way to draw all sprites sorted by depth is then to just put all sprites in one list and sort it. Without existential quantification, I would’ve had to write code to sort the players and then call the draw method of the ball somewhere between the draw methods of the players.

So, programming in Haskell is more fun than ever, and the productivity boost given by Haskell is starting to show more and more.

Here’s the announcement of my latest programming project. It’s called Star Rover 2, and it’s a space flying game. You can fly around in space, trade goods, fight against other ships and complete missions for different governments. It features different difficulty levels, a high score list and several ways for the player to play the game. It’s also the first game I wrote in Haskell that’s actually playable.

Flying between planets

The game itself is quite simple: you start on a planet, and you can buy some cargo if you want before launching into the space. In space, you can fly to other planets and see if you can sell your cargo for a better price. There are other ships in space as well, and you’ll get interrupted every once in a while when coming across one, with the possibility of attacking the other ship. If you win, you get their cargo, and the various governments may have their opinions about the attack as well.

(it looks better in motion :)

Combat in Star Rover 2

As the game progresses, you may earn a reputation among the governing bodies, which leads to new dangers and possibilities. The international relationships are complicated, and attacking a ship of one nationality may not only affect the nationality being attacked but their friends and enemies as well. By playing your cards right you can receive missions from governors, and by completing them you may boost your ranking further.

Captured cargo

The game is quite non-linear; it ends when your ship is destroyed often enough and you are too weak to continue, or when you choose to retire. At the end, your achievements are rated and you may make it to the high score list. Until then, you may choose your activities freely.

You can find Star Rover 2 at Hackage, so if you have cabal, you can install it by running cabal update && cabal install starrover2. You can also fetch the sources from github. As for dependencies, you’ll need SDL, OpenGL and FTGL.

In the beginning, Star Rover 2 was more or less a test of whether I can actually concentrate on one project enough to have a playable game in the end, and I’m glad it’s now reached a state where it can be released. Other than that, I was curious to see what programming such a game actually is like in Haskell, and I’m quite pleased with the results. I started working on Star Rover 2 on my spare time pretty much exactly a month ago, and now it amounts to about 2000 lines of Haskell code. I was a bit worried I couldn’t write a larger project in Haskell, but now I can see how well Haskell scales up to complex tasks. This was also my first project where monad transformers actually came in very handy.

Any feedback and bug reports are of course very welcome.

I wanted to start typing down some things as notes I’ve learnt during the development of Freekick until now before I forget all about them. The first article in the series is about one of the most important things that are different between Freekick and my previous hobby projects: modularization in software.

I first started to understand the importance and the benefits of modularity as I read the great book “The Art of Unix Programming” by Eric S. Raymond, a book I can recommend to every software developer, even those who’ve never used or programmed on Unix. Lacking modularity in my programs was the biggest reason why I had to abandon them sooner or later – I’ve ended up in such horrible situations where tweaking the AI creates a bug in the main menu, for example.

As mentioned in the book, managing complexity is one of the most crucial (and difficult) jobs when developing software. Basically, as long as you can simplify the tasks of the software into more and more smaller, simpler sub-tasks, and organize them so that you always know which parts of the software should be talking to each other and how the talking is done (interface design), you have no problem. If you lose the overview half-way to the project but go on writing code, you probably won’t get it finished.

From a developer’s point of view, some programming languages encourage designing the software top-down, always breaking problems into smaller pieces, and then implementing the software bottom-up. I take FORTH as an example, in which it is near to impossible to write even slightly complicated software without designing it thoroughly in a top-down fashion first. Most languages, such as Java or C, don’t really force you to manage complexity in any way, but merely provide you with the tools.

There are a lot of ways to bind all your software components so tightly together that there’s soon no way to take them apart anymore. One way is having a so called “god class“, a class usually aptly called something like “World” that ends up having most of the code in the project. Other popular ways include global variables, static variables or simply functions that are 1000 lines long, with multiple static variables that are conditionally used for different purposes in the beginning, middle and end of the function. Here are some small hints how such misfortunes can be avoided.

One thing to keep in mind is that each class, function and module should have exactly one well defined task to do. When I put it that way it sounds almost trivial, but it’s still sometimes forgotten. Another problem that I often see are confusing interfaces: when designing the interface, don’t have functions InitTaskX(), BeginTaskX() and StartTaskX(), where StartTaskX() internally calls InitTaskX() and BeginTaskX() in sequence. Instead rather decide on one option that the one using the interface will need (even when it’s “future you” – in a few weeks you’ve forgotten what you meant with all the weird functions anyway) and stick to it.

Another thing I wanted to use to increase modularity in Freekick was to split the whole application in multiple processes. There’s one process for doing all the non-soccer-match stuff – menus, league tables, transfers, etc. and other processes for the actual match. When the main menu process starts a match, it creates an XML file for the match server, then starts the server and passes this XML file to it, then starts the other match-related processes (client and AI). This allows me to be 100% sure that I can change anything in the menu part of the application and not break the actual match, as long as I don’t change the XML file which serves as the interface between the two.

The server itself handles the physics, rules and the match state, while the clients display the state received by the server and send user input to the server. As a nice bonus adding multiplayer capability is relatively easy, even though it was something I hadn’t originally planned. Another positive thing about it is that I can use different programming languages for different processes; I’m currently writing the menu part in Python and the actual match part in C++. There are also more sophisticated libraries for accomplishing a similar task, such as D-Bus, but I felt it would’ve been an overkill for this one.

As for the server and the clients, they communicate over a simple, clearly defined Freekick protocol that works over network sockets. This allows me to change the way the client displays the match, for example, without me being able to break the functionality in the server. In Freekick, the AI is a client as well, which allows me to reuse much of the client code while still having clear limits on what code belongs to the client that the player sees, what is only relevant for AI and what code is used by both of them.

Splitting the game into a server and a client is what FreeCiv did as well, by the way. That’s why there exist multiple clients for FreeCiv that do the same thing but look different. Freekick has two clients now as well, one that shows the match  in 3D and another where all the graphics are text based, using Curses. In the end they both same exactly the same soccer match with the same AI, logic, state and rules, only the way of displaying it and receiving input from the user different.

As for the internal structure of the server itself, I’ve also tried to keep things as independent from each other as possible. There’s the Physics class, which is a facade to the whole physics subsystem. Then there’s Rules, a class that is responsible for calculating the changes in the current rules status of the match. Physics can be subscribed to, implementing the visitor pattern, and is subscribed by Rules. Rules receives all updates from Physics (where the ball is at the moment, which player touched the ball, etc.) and updates the rules state correspondingly.

Rules can be subscribed as well, and both of these classes are subscribed by Dispatcher, a class that sends both kinds of updates, rules and physics, to the clients. How does Dispatcher know who the clients are? There is the class ServerManager, which accepts incoming connections and adds them to the list, which the Dispatcher has a pointer to. There are also classes ClientEventListener that receives the input from the clients and InputMonitor, which validates the data before passing it on to Physics.

Freekick is using Bullet for physics simulation. While Bullet is an excellent library, I can’t be sure Freekick will be using it forever (who knows what kind of open source physics libraries we have in five years). To make sure the physics engine can be exchanged in the future as easily as possible, I wrote an interface that should correspond my needs and no more – functions like addStaticObject(form, position) and simulate(timestep) – a wrapper. The interface is then implemented by the BulletPhysicsEngine class using the sometimes not-so-clear Bullet interface.

These are some ways to add modularity in software – of course, there are more and maybe better ways to do it, but these have made it rather easy for me to continue implementing Freekick, even as the code base has gotten bigger with time. For the interested, the Freekick code itself can be browsed here.

Time for a small update again. The last time I wrote I mostly reviewed the work done last year, wrote about the tools used and spent some time comparing Haskell with C++ as I had been busy rewriting the Freekick server in C++. So what’s been going on in the past month? Well, some of the points mentioned in “things to do next” part of the last post have been worked on, while others aren’t. Also, as I have now been using C++ for a few months there have been some signs of the need to wander off to another – hopefully better and shinier – programming language again, just like one would expect. This time I’m not thinking of Haskell though, but Python.

I’ll first let you know what’s new with Freekick core development. There’s been a lot of small improvements – I’ve added some server functionality such as allowing human players to play along or goal detection, but the most important update is that the OGRE client now has the ability to control a player and kick the ball around. This actually makes Freekick a soccer game that can be played. This doesn’t mean, however, that it would actually be fun to play the game – the relatively silly AI makes sure we’re not quite there yet. Another thing that makes the game less fun is that the clubs aren’t really there; the players have no differences in skills or personality, there are no kits or club names or tournaments.

The next thing for me to do is try and eliminate these two problems: first, the AI needs to be made better. At the moment it’s not really that bad – they pass the ball and try to score – but they only have a few actions which makes the match seem repetitive, and the goalkeepers are horrible. Second, the soccer match needs to have a menu around it, including creating and viewing tournaments, lineups, league tables – the whole deal. Actually I’ve already started work on that, which brings me to Python.

You see, working with C++ the whole time with Freekick core was not bad, but after you’ve seen something like Haskell in action, sooner or later you start to wonder if everything really needs to be so complicated. I’m talking about the sheer amount of time spent typing the code in, the loops, the iterators, the classes and headers and declarations, the curly brackets…

As Freekick was designed with modularity in mind and was split to multiple processes from the beginning on, the question of using Python for the game menu arose. After poking around with PyQt for a while the first drafts of the game menu were already finished. I had had my doubts about dynamic languages and duck typing before, but now, after having written a few small applications with Python I’m slowly starting to see the advantages such a dynamic high-level language can bring. I was amazed how fast you could actually write a simple-looking Python script that does the same thing as an application you could spend weeks writing in C++.

Encouraged by my Python adventures, I played around with the idea of solving the other problem – AI – with Python. Since I don’t really fancy writing all the Freekick client side logic in Python, I thought about using Boost.Python to export the C++ classes into Python. Doing the experiment was interesting, but the unfortunate truth is that exporting the classes still seems like too much work, even with the excellent library, especially with the page-long error messages and the fact that the STL containers would apparently also be have to exported manually. The other way would be embedding Python in C++, but I’d still have to export the data structures to Python and back, which makes me think it’s probably faster just to stick with C++ after all.

The GUI part is still far from ready – the only event that starts a match at the moment is a friendly match, and the GUI-match interface is non-existent at the moment – but the base is there and will be expanded when the time is ready. At the moment I think improving the soccer match itself is more important, since there is really no good reason to start a match if playing it isn’t fun, which brings me back to C++ and the AI. I’ve been reading the book “Programming Game AI by Example” by Mat Buckland again, which really is quite an inspiring work, but I think it will still take a while for me before the AI code is in a state where it both seems halfway smart and is easily extensible.

Luckily there are still a couple of mini projects for me to do in case writing AI gets boring. First of all there’s the GUI with all the tournament and schedule creation to do, but I think the time is also slowly getting ready for another Freekick client, this time with ncurses as the “graphics” library. I’ve been wanting to get my hands dirty with ncurses for a while now, and I’m all for minimalistic software, so hey, why not. Other fun things include creating a TV style soccer camera in OGRE and taking player skills into account on the server side. I’ll keep you posted.

New year, new tricks. In this post I’ll explain what Freekick has been doing for the last two months. The main events include rewriting Freekick in C++ so that it finally matches the Haskell version feature-wise, as well as gaining a bit of experience in using the associated tools and libraries. Before I get to that, let me first write down a brief summary of the last year, and of the blog thus far.

In April I wrote the first post announcing the beginning of the project, wondering which language and graphics library to use. The decision was in the end to go for C++ and Ogre. I was also preparing CEGUI as the GUI library. The build system was make, the version control system used was Subversion (if any).

In May I got to physics libraries and decided to look at ODE instead of Bullet. Soon after that I’d let the physics and graphics digest for a while and learn Haskell instead as a tool for AI programming.  Back then, there was no real code written for the project yet.

In June I had learnt the basics of Haskell and was using it to program some of the first things in Freekick.

In July the very basic design of Freekick was slowly getting clear. The plan was (and is) to split the game to different processes and use a server-client model. I went on programming the server and the AI in Haskell and played with the thought of writing the client in Python. I also started getting VCS conscious and mentioned darcs for the first time.

By August I had gotten as far as programming some multithreaded networking in Haskell, as well as doing some nice experiments and tests with neural networks. While the networking part was directly a part of Freekick at the time, I haven’t integrated the concept of neural networks with the project yet.

In September the very basic structure of Freekick, including the server, AI and a client, was finished in Haskell and the version 0.0.1 was released. The client was written using SDL, the primitive physics for the server was done without external libraries and the AI was a simple decision tree.

In October the negative sides of Haskell were starting to become clear, mainly being problems with the performance and problematic use of C++ libraries. The decision was to write a new client in C++ that uses Ogre for graphics. Implementing the data structures (classes) in C++ for the client also makes writing the server in C++ not such a big step.

In November the new client was finished. As it became clear that the performance problems had more to do with the Haskell server than with the client, the decision was to rewrite the server in C++.

In December I didn’t have the time to write about it, but I was busy rewriting the server in C++. This included updating the protocol between the server and the client as well as learning object oriented design.

And now, in January, it’s time for a post again. The C++ server is running, and the preliminary AI is finished too. As there were some updates to the Freekick protocol that broke the backwards compatibility; the old Haskell programs (server, SDL client, AI client) would have to be updated to match the new protocol in order to be able to work with the newer software (maybe I’ll get to it on some rainy day).

As there are some difficulties finding a public code hosting site for darcs repositories (and darcs seems to have some other problems too), I went for another RCS, namely git. I too am one of those who don’t want to go back to centralized SCM after seeing the other side, and git seems to fit my needs perfectly. The Freekick code can be found at GitHub by the way, at http://github.com/anttisalonen/freekick/tree/master. If you want to compile and run it though, there are some external dependencies (notably Bullet and Ogre) and the build script probably isn’t portable yet. If you run into problems, drop me a note.

As a side note, I also wondered which build tool to use for the C++ version of Freekick (for Haskell, Cabal is the excellent build tool, while C++ has a lot more options). The two strongest candidates were CMake and SCons, and in the end I went for the latter. The build tool for Freekick has the seemingly complicated task of compiling and managing a few libraries and applications, preferably comfortably configured in one configuration file. By now, my SCons build script (SConstruct) has become about 150 lines, but it does everything I want it to and how I want it to. The level of documentation for SCons is also excellent.

Now, a few words about implementing Freekick. First of all, even though C++ is more comfortable than I previously thought, it’s still far away from Haskell. My impression is that, thanks to the Boost libraries, you can use most of the nice things that Haskell has (e.g. tuples, lambdas), and everything will run slightly more efficiently than in Haskell, but there’s a lot more code to write and the code is a lot less elegant and a lot more verbose than in Haskell. I guess the better control of CPU cycles and bytes of RAM is worth it.

An interesting thing to note is that it took for both Haskell and C++ about three months to implement the basic functionality of Freekick. The comparison is unfair; I had just learnt Haskell when I started programming Freekick with it, while I’ve had previous (albeit now rather obsolete) experience with C++. Also, when I programmed Freekick the first time, the basic structure and design was only barely clear to me. With Haskell I had to program my own primitive physics engine, with C++ I used Bullet (which was about just as troublesome). The Haskell graphical client was easily done in SDL, while the Ogre client was a bit more work (though using Ogre is actually quite fast, easy and fun – signs of an excellent library). However, in the end the difference in development times wasn’t drastic, which shows to me that C++ really seems to do the job of evolving to a higher level language with time pretty well.

This was also the first time that I’ve actually done some object oriented design. It’s actually quite fun. The constant shuffling around with the header and cpp-files and the verbosity of it all is something I wouldn’t miss with Haskell, and the generic programming and code reuse that OOP offers is still light years away from the level you can find in a functional programming language. Still, C++ is on any account usable and I really need those cycles and bytes. Hopefully in a few years I can use a language that is as elegant as Haskell, while still maintaining the perceived efficiency of C++.

The next things to do with Freekick include relatively small improvements to the server (better compliance with the rules of the game), to the AI (it’s really quite primitive at the moment) as well as to the client (controlling a player and some small graphical enchancements). After that the next task is to go and implement the bigger plan, i.e. the game around the match – organizing the matches into cups and leagues.

It’s time for a small post again. I haven’t updated my blog for a while, but for a reason: there hasn’t really been anything interesting to write about lately. Don’t worry, I’ve been working on my project, but rather implementing it than designing it. The last time I wrote about AI and mentioned it’d be the next thing to implement for Freekick. Well, the basics of AI are there, as well as the basics of everything else (server + client + the organizatory part). I’ve spent the last month writing the AI, writing a client (i.e. a window to the soccer pitch) and making sure the thing doesn’t crash by itself. Sounds like a 0.0.1 release, doesn’t it? Yeah, we’re that far already.

To the disappointment of neural network fans I haven’t implemented them at all in Freekick AI, not yet. The basic structure of the AI is slowly coming together, and when I can concentrate on the details, I’ll try and make some use of neural networks. At the moment, however, the AI follows simple logic for decision making that will be refined later. Having a simplified AI at this stage is helpful because it lets me concentrate on figuring out the bigger picture of the AI functionality.

The current AI is roughly split into two parts, one that defines the possible actions and another that compares these actions with each other and chooses between them. Here, defining the possible actions also includes a set of helper functions such as for finding the best spots on the pitch for scoring or the chances of a successful pass to a teammate.

Splitting the AI code like this makes maintaining it easier than if it was one bloated, monolithic monster. Improving the code should also be simpler in the long run, because if the two parts only communicate via clearly defined interfaces, one part could be swapped or reworked without interfering with the other part. This way I can first make things run with simple logic and when the AI starts to seem too stupid replacing parts of it with, say, neural networks shouldn’t be a big problem. At the moment, though, the AI code is rather transparent (with 10 files and 400 lines of Haskell code), but when the code grows, it will be necessary to make this division even clearer.

I then went on to write an SDL client for Freekick. It’s actually a bit early to call it a client, since there is no single player (nor multi player) mode and the client doesn’t control a player but merely spectates the match, but for now it’s enough to see what the AI is doing. A simple single player mode with some awkward controls will be added later. The client is very ugly, though, and thereby reflects my artistic skills rather perfectly. Here’s a screen shot.

Soccer in all its beauty.

Soccer in all its beauty.

Here it probably starts to become clear for everyone why I wanted Freekick to be so modular. The client is just a client, its duties are merely receiving the match status from the server and displaying it as it sees fit, as well as taking input from the player. It can be exchanged or rewritten in another language without the need to touch the rest of the game logic. I’m also planning on writing an ncurses client for use in non-graphical environments (as if the SDL client wasn’t ugly enough).

As for the server (i.e. the code that handles the network, communication, enforces soccer rules and world physics), it’s running with no major problems. Minor problems include network code that has problems handling disconnecting clients and relatively inaccurate physics, but for now it’s adequate. Probably the biggest thing that differentiates Freekick from a real alpha version of a very ugly spectator only soccer game is (along with the fact that the match actually never ends) that there is actually no connection between the “organizatory part” (i.e. choosing two clubs that play a friendly game against each other, or starting a knockout tournament) and the actual, viewable match.

This all means there is still some more work to do before Freekick could be considered usable. But in the spirit of “Release early, release often” I’m giving you the code (written in Haskell as usual) already anyways. If you have darcs, the easiest way to the code is “darcs get http://code.haskell.org/freekick/”, but there are also tarballs of the code as well of a binary version (x86, Linux) at http://finder.homelinux.org/freekick/files/. With enough playing around one might be able to start the thing, but I’ll write here the way it’s supposed to work anyway. First you start the server (“physics”) with a matchdata file (“matchdata.md”) as parameter. Then you start both the client and the AI, which both connect to the server. AI interprets the information from the server and sends the desired player actions to it. The client displays the players in all its SDL glory. And voila, you’re witnessing a soccer AI experiment.

From the issues mentioned above, the ones I’ll be concentrating on in the near future will be the ability to actually play the game and control a player, finishing up the match flow (i.e. ending the match at some point), and tying the organizatory part together with the match part. After these steps, it’s probably time for some polish, like a main menu, configuration options and a prettier client. As for the 0.0.2 release, it’ll be available, soon. I’ll keep you posted.

In my last post I described the high-level architecture of my software, how the soccer match part is divided into a client that does the work on showing the graphics and receiving input, a server that actually has all the match info and the AI process that actually acts as a client but controls more players at once. I also said my next task would be to write a small working piece of code for each task to get me started. Well, I’m still there; the main physics part is done. As an exercise to working with the BSD sockets interface in another language than C I did the physics part in Haskell, which was fun. Fun, but not easy.

Basically the difficult part was that I wanted the server to establish connections with many clients, send them some information about the match during connection and then broadcast the match data to all clients simultaneously. For this, of course, you need concurrency and threads, though the fact that Haskell as a purely functional language already threads everything confused me a bit. The answer is Control.Concurrent.forkIO and, for the more complicated stuff (i.e. communication between threads) Control.Concurrent.STM. For tutorials on how to program servers with Haskell, a nice, light introduction can be found at http://metavar.blogspot.com/2007/03/simple-socket-programming.html while a bit more difficult but certainly as interesting article is at http://sequence.complete.org/node/258. For a client, check out http://www.haskell.org/haskellwiki/Roll_your_own_IRC_bot. But I digress. Actually I wanted to write about AI.

So, after finishing my physics server (actually it’s not completely finished, it has no soccer rules yet, but it’s a server with some physics understanding after all), I went on to do the AI part. Since it can get quite complicated, I thought about doing some exercises on AI first. Now, the way how to start designing and programming AI was not really clear for me. I have the book “Programming Game AI by Example” by Mat Buckland, (a very nice book by the way) which has installed the relatively simple scheme of state machines in my head. I was not all sure, however, if a state machine would really be enough for soccer players, so I went on to do some more research.

I then stumbled upon neural networks, a topic about which I had only briefly read in the past – they seemed interesting but I never had the patience to sit down and try to grasp the theory. I finally went through the basics about them on a few sites including Wikipedia, but noticed none of those sites really showed any practical examples. I finally came upon two web sites that really explained how to use neural networks in detail. The first one is actually in German and describes the use of neural networks in a Counter-Strike bot, see http://johannes.lampel.net/bll137.html. It was a very interesting read, but for grasping the details you’d need to dive in the source code. The second site can be found at http://www.ai-junkie.com/ann/evolved/nnt1.html; this one is a very very practical introduction to neural networks, it helped me a lot and it’s also by Mr. Buckland, who keeps surprising me how simple it can be for some to make difficult things seem simple. His tutorial trains the networks with genetic algorithms, for which he also wrote a great tutorial (http://www.ai-junkie.com/ga/intro/gat1.html). The code, like all code from Mat, seems to be written for a less standards compliant compiler such as Visual Studio 6.0 or similar, which means you have to tweak it a bit if you want it to compile on a compiler that follows a C++ standard, but it’s doable.

Encouraged by the theory and these practical tutorials, I went on translating Mat’s Minesweepers into Haskell. During this process I also realized why almost all of the tutorials and the theory of artificial neural networks didn’t show any practical examples; my neural network code itself is merely about 50 lines of active code and contains mostly just the mathematical formulas to the networks. The applicaton of neural networks, however, is nearing 200 lines of code (huge, isn’t it?) and basically describes the whole learning and using process of the brain, err, neural network.

What I learned was that how the neural networks work is basically just a few formulas that don’t really say much about the application; in the end the network is really just a black box that you don’t really know, but it just “magically” gives you the correct values. The difficult part when applying neural networks to a problem is designing the way they’re used and figuring out how to make them learn as well and fast as possible. (I haven’t figured out any of the other ways of getting networks to learn (like simulated annealing and whatnot), i.e. providing positive feedback to them than genetic algorithms, but for now it seems good enough.) I also realized how the whole process was based on randomness, and while I thought that was quite funky, I did have my moments of despair trying to figure out if the thing had actually learnt something or not. (If in doubt, wait.)

Well, in the end it worked, though the minesweepers weren’t rolling around the screen like in the Windows/C++ counterpart, but the path of a minesweeper is drawn into a SVG file instead, as in http://finder.homelinux.org/haskell/Mines-0.1/svg_sample/gen400.svg. In this picture, you can actually see a minesweeper (the line) going for the mines nearby (the dots). Oh, want to take a look at the code? That can be found at http://finder.homelinux.org/haskell/Mines-0.1/.

That being cleared out, the next thing to do would be to actually finally implement a simple soccer AI. And, well, if I actually did it like I originally planned, with the locations of all the players and the ball and the player skills and personality as input, action including the direction and power of the action (let it be running, kicking the ball etc.) as output, it would probably end up being a pretty big neural network. The time to train it would probably also be pretty long, I guess.

The solution I’m trying to come up with includes state machines, neural networks, decising trees and maybe an occasional Markov decision process. (I also need to finally get my hands on the book “Artificial Intelligence: A Modern Approach”, which I’ve managed to miss… until now.) The basic principle is the same one as discussed in my last post – breaking everything into smaller parts, with state machines or decision trees to assist with the splitting, while using neural networks for the smaller, more limited problems. Probably my next post will still be on AI, but when that’s done (or at least the skeleton of it), and the AI players are kicking the ball, the only bigger thing missing is a client that actually shows us the action…

It’s been quite a while (a month, actually) since my last post. That is not a sign of laziness, however, on the contrary; I’ve been busy playing around with Haskell and Python lately. In the last post I wrote about taking a break from Ogre to see what this thing called functional programming actually means. I think I’ve come closer to figuring that out in the past month.

Haskell really is quite an interesting language. (There’s a little tutorial showing some very nice aspects about Haskell here.) I started learning it by going through the tutorials available at haskell.org, and especially walking through Yet Another Haskell Tutorial, a mighty PDF book that explains all the major aspects of the language. I really had problems figuring out how to simulate state within Haskell, and the State monad didn’t really make it seem much easier. After going through the source code of some Haskell projects such as Frag (a 3D shooter) and LambdaHack (a roguelike), I finally started to slowly understand how a bigger project in Haskell could look like. So, to start from the bottom and work my way up, I made a blackjack and a video poker game. They’re text based but helped me figure out how to program some simple things in Haskell. (If you’re interested, you can find the sources + binaries here, MIT licensed.)

After finishing those two little cute things, I wanted to tackle the real prob– project, my soccer game wannabe. So I figured out how to read XML files in Haskell to serialize some data. As can be seen from my card games code above, I didn’t quite understand all of the monad concept (and still don’t), which turns out to be a pretty serious drawback when using Haskell to program in a bigger project. As Haskell is a purely functional programming language (one cannot emphasize that enough, I guess), doing something like file I/O without monads is impossible, and without advanced use of monads very tricky once things start to go wrong. The result is that if there is an error somewhere in the XML file to be parsed (my program doesn’t do any validation at the moment) or a bug in a function parsing the XML file, the bughunt may prove to be a very wiery task. So the next thing to do before I go on programming with Haskell is to learn more about monads. Luckily there are a lot of tutorials to the subject on Haskell.org. After that, the smartest thing for me to do would be a rewrite of my XML serializer.

My XML serializer could handle some data, but as I wrote the few XML files manually to test with I realized there is still a lot to design regarding the structure of my soccer game. And in order to see if my design would work, I needed some test scripts to create some XML files that should be able to work with each other. Since creating XML files by parsing text files and adding more or less random data to them is quite an I/O intensive thing to do and since I just wanted to quickly have some scripts that would do the job for me, I decided to do the job in Python instead.

Now, I wasn’t very experienced in Python (to be precise, I had programmed about 20 minutes in Python before this), but I still had somehow had the idea that programming in Python would be extremely fast and easy, especially for such not-very-large programs. After a few days of fooling around with Python and working with the excellent Python lxml library my scripts were finished and it seems I have proved myself correct. Even though my creations look quite terrible (if a Python fan saw my code he’d probably get his eyes hurt) and are written in a procedural fashion reminding me of my BASIC times (maybe Djikstra had a point after all) they do get the job done in the end and I think I can even understand the code.

There are some things I don’t like about Python (mainly the dynamic typing and the fact that is interpreted) and it surely doesn’t fit well for CPU intensive code, but for my XML creation scripts it’s perfect. Python also seems to be very easy to learn (just like Guido wanted it), and my scripts are a living (working) proof for that. I still keep learning Haskell (of course) since it seems even more elegant, faster and is purely functional, but the small Python excursion showed me I should keep clinging to the “right tool for the job” paradigm.

So, what now? Well, there’s the topic of monads to look at. After that I should do a rewrite of my XML serializer. (As boring as it may sound.) Then, well, I should be able to go on with my soccer game project, but with monads this time… We’ll see how it goes.