Skip navigation

Tag Archives: soccer game

Since I spent some time tweaking the AI in Freekick 3, I thought I should write down some of the implementation details for future reference.

The AI has quite a simple general structure. Apart from the special cases like restarts, goalkeeper AI etc. the main gameplay AI consists of three states: defensive AI, offensive AI and the AI when the agent is about to kick the ball. Whether a player is in the defensive or offensive state depends on the match situation (where the ball is, who has the ball) and the team tactics (agent’s position).

The defensive state is basically a decision “where should I stand to make the opponent’s offensive difficult”. There are a few options: try to take the ball from the opponent, try to block an opponent’s pass or shot or guard some area or opponent. The AI simply assigns scores to each action and picks the action with the highest score. (This, I suppose pretty standard AI technique, seems to be inspired by utility functions and is used throughout the Freekick 3 AI.)

The offensive state is even simpler than the defensive state: either the player tries to fetch the ball or tries to place himself in the best possible supporting position, which should be somewhere that can be passed to, far away from opposing players, and a good shot position. (The AI builds a kind of an influence map that is also affected by some soccer-specific things such as the offside rule.)

Probably the most important decision the AI has to make is what to do when the agent has the ball. Again, like with the defensive state, the AI has a few different possible actions, and it assigns scores to all of them and simply picks the action with the highest score.

The possible actions are Pass, Shoot, Long Pass, Clear, Tackle and Dribble. I’ll start with the Pass action.

When deciding the pass target, the AI loops through all of the friendly players and keeps track of the best option. For each player that’s not too far or too close, the AI considers either passing directly to the player or trying a through-pass. The base score for the pass is highest for players nearer the enemy goal, and then decreased for each opponent player that is seen as a possible interceptor.

The Shoot action score is basically a function of distance to the opponent’s goal and the distance from the opponent’s players (especially the goal keeper) to the possible shot trajectory.

The Long Pass action is actually a composite of Shoot and Pass – it checks for the Shoot and Pass action scores of the friendly players and chooses to make a long pass (or cross) to the player with the highest score. As with other actions, the score is multiplied by a team tactics coefficient, allowing the coach to influence the team’s playing style.

Clear and Tackle are basically emergency brakes that the AI can pull in a situation where the ball needs to be kicked away from the own goal or the opposing players.

With Dribble, the AI creates a few possible rays at regular angle intervals around the agent as possible dribble vectors and assigns scores to each of them. Similar to shooting, the score is higher near the opponent goal, but decreased by opponent presence.

So, in the end, the AI is composed by several rather simple techniques. It’s all heuristics without any algorithms providing optimal solutions (if any can even be used in soccer AI). It uses some simple seeking behaviors (arrive at a position, chase the ball). There’s one simple state machine, with state transitions decided mostly by the ball position. The top level AI is built around simple if-then-else-statements (I suppose you could call them decision trees). Lots of the decision making uses some sort of fuzzy logic, even though it’s not really structured like that (instead the code itself is fuzzy). Still, the AI manages to seem smart in most cases, it plays rather well and presents a challenge for the human player (for me, at least).

There are still quite a few standard AI techniques that I haven’t implemented which might make sense for Freekick 3. For example it might be interesting to experiment with adding some kind of learning ability to the AI, which should be possible using reinforcement learning, or adding a more complicated planning process with the use of a decision network. A useful first step would be to extract all the used generic concepts like decision trees and fuzzy logic to their own code pieces, which would enable experimenting with things like learning a decision tree.

My conclusion is that there are lots of different game AI techniques, many of which are quite simple, and the key to creating a fun AI is to find out which techniques to use for which problem and how to combine the techniques. The techniques are often intuitive but can be also described mathematically, so that when reading up on game AI, you may, depending on the material, get an impression that game AI is either very non-scientific or very mathematical (and therefore difficult), while I think it can be either, depending on how you look at it.

For the interested, the ~500 lines of Freekick 3 AI that make up the core can be found at GitHub.

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.

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.

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.