Skip navigation

Category Archives: ai

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.

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…