Monthly Archives: July 2011

Artificial Intelligence for Games, Second Edition

I’ve been thinking it’s time to cobble another IOS app up for sale, not just fiddle around with open source client apps (which is a lot of the IOS work I’ve been doing lately). So I found a board game idea that I liked, and thought I’d make a stab of doing it – maybe using some of the new IOS5 features for a multiplayer turn-based game.

As I got into the game, noodling on the design and how the interaction would work, I came to the realization that I really would like to have a reasonable single player game as well, and that I didn’t have a clue about how to do board-game AI to make a good game experience.

After looking around through a pile of game AI books, I came across “Artificial Intelligence for Games, Second Edition“. Heavy book, hardback – some $80 if you pick it up outside of Amazon’s discount mechanisms. It looked good after a glance-through and minimal reading, so I took it home to dig in depth. I’m really glad I did!

This book does an excellent job of describing the AI algorithms in pseudo good and good ole english, as opposed to many which seem to be littered with mostly un-parse-able fragments of C++. They reference a number of modern games, but rather than catalog “these used this type of AI, the others didn’t” (which I saw in a number of books), they took some time to explain the tradeoffs in choosing the AI mechanism in the game, even if they didn’t have the “why” of the game designer to pull from.

I liked it enough to put up a review on Amazon, and hey – I’m writing this too. If you’re looking for a good overview of AI algorithms and how they work, I recommend the book.

Inside the Nova service framework

In my previous spelunking article, I went over the basic pieces needed to get a nova service stood up. Well okay – I skipped logging – maybe another article later for that later…

Quick recap: The service framework in nova is set up to make it easy to write your own services that interact with any other nova services (such as nova-network, nova-scheduler, etc). The service framework includes all the pieces to communicate with these other services (using a module called rpc.py that abstracts away the communications), a database connection for looking up data from the nova persistence store, and leaves the rest to you.

The service module is expecting to be told a manager class to load, and the framework will use that to do what it needs. There are only two required methods to overwrite:

There are two kinds of services – I’m going to focus on the stand-alone (not WSGI) service that expects to communicate and respond entirely through the message queue system in Nova.

So how does this service critter work? Well, when it’s initialized, it gets a number of attributes assigned to it. This is typically done from a class method on service.py:

from nova.service import Service
my_service = Service.create()

The create() method has a number of parameters:

  • host – a string with the host this service is running on
  • binary – a string with the binary name of this program
  • topic – a string with a subset of the binary name, used to set up a message exchange in AMQP
  • manager – a string with the class name to be loaded to do the ‘work’
  • report_interval – an interval set from Flags, triggering a regular reporting loop
  • periodic_interval – an interval set from Flags, triggering a periodic loop to do repeating tasks

If you don’t provide any of them, all these values get populated with defaults and from configuration detail (the flags) in the service.serve() method. Once serve() gets everything configured up, it calls .start() on each service to kick it into gear.

start() is where things really get moving. This is where the service manager class gets loaded, registered with the nova database (if it isn’t already), and the RPC mechanisms get spun up with Eventlet greenthreads to accept messages to this service. The topic (which is the name of the binary, minus any “nova-” in front of it) is used as an exchange. Through this mechanism, any service can talk to any other service (or set of services). Here’s how that works:

rpc.py has two methods: call() and cast() that do all the heavy lifting. When you use these, they take a “context” (i.e. authorization for who’s doing the call), a topic (the name of the service you’re calling), and a message. call() sends this message and waits for a response. cast() sends the message entirely asynchronously, not expecting a response.

The message is a JSON structure – a dictionary, and it’s expected that the dictionary will have a key “method” and another key “args”. method is expected to be a string, and args is expected to be another dictionary. The rpc module does the work of using that method string to look up and invoke the method on your manager.

An example of this operating is right in the code. In the nova-network API, there’s an rpc.cast():

rpc.cast(context,
         self.db.queue_get_for(context, FLAGS.network_topic, host),
         {'method': 'associate_floating_ip',
          'args': {'floating_address': floating_ip['address'],
                   'fixed_address': fixed_ip['address']}})

Through the service framework and the RPC mechanisms, this is calling associate_floating_ip() on the network service manager class.

The other nifty thing about service is that it’s keeping and managing a number of greenthreads from Eventlet to do it’s work. The basic bits are all encapsulated in that rpc.py mechanism – when it sets up connections to the message queue service to receive communications, that starts a greenthread rolling to watch out for, pull, and process any messages inbound. The two periodic interval pieces are also spun up on their own greenthreads – looping every “interval” (specified by the flags –report_interval and –periodic_interval, set at 10 and 60 seconds by default respectively). These run continuously until the service is terminated.

Benchmarking Celery

Before you even go there, I’ll preface this with YMMV.

This little post is to document a benchmark that I did for an internal use case, in the hopes that it’ll be helpful for others. As a benchmark, I wasn’t attempting to fully characterize the performance of a specific system – I just wanted a pole against which to measure changes in the environment or underlying infrastructure. I was curious what the performance was of Celery, using RabbitMQ. The tests I ran were pretty much straight sample code of the project (a simple “add” task) and a client making multiple requests and combining the results with the veritable python “timeit“.

The code

All the code for this test (and more, I got excited…) is stashed up on Github: https://github.com/heckj/openstack-benchmarks/tree/CeleryBenchmark. Really, the parts you’re likely to be interested in is the worker class: tasks.py, the configuration: celeryconfig.py, and the actual benchmarking code: celery-benchmark.py.

And before you ask, no – the OpenStack project doesn’t currently use Celery – in fact they use Carrot right now. I’m just intending to add on more benchmarks and profile tools into this codebase around the OpenStack project in the future.

The config

The configuration was held constant – a stock Ubuntu 10.10 server with all the various dependencies installed. Since I’m sure someone will want to know about the versions:

  • rabbitmq-server 1.8.0-1ubuntu2
  • python2.6 2.6.6-5ubuntu1
  • python-amqplib 0.6.1-1
  • celery 2.2.7
  • kombu 1.1.6
  • anyjson 0.3.1

The host was a Shuttle PC, 8GB ram, Core 2 Duo processors. The host was never heavily burdened by the processing that took place (load < 1.0, no significant swaping). The benchmarking was done on the same host as RabbitMQ to remove any network latency effects.

The results

.

I was totally abusing MS Excel’s “stock graph” to show variability in the results (of which there wasn’t a hell of a lot). In the graph, the thin line represents the range (min to max) and the thicker box in the middle is standard deviation +/- the average result. The gist – the round trip time was pretty much straight up at 160ms per requests, and that sampled over 1,000,000 requests. The image above shows a portion of the sequence. The relevant code:

from benchmark.celerybench.tasks import add

result = add.apply_async(args=[4, 4]_
result.get()

(As I mentioned earlier, you can see the whole code on github).

I did more tests, but I need to keep some of those to myself, as they’re testing variations of configurations for my job.

Random side notes

I hadn’t done anything in depth with Celery before. I’d heard about it from friends, and in the community in general. The author pinged me a couple of times with help as well. Overall, I found the Celery setup to be incredibly easy to use and a very straightforward API (always nice). There were lots of options available, but everything was set with very usable defaults from the start. I’m totally looking forward to using Celery in some projects, as well as taking advantage of Kombu – a drop-in/compatibility layer for Carrot.

Update:

Ask mentioned some suggestions for optimizing in twitter – seemed a good place to put them. Try:

  • CELERYD_PREFETCH_MULTIPLIER=0
  • CELERY_DISABLE_RATE_LIMITS=True
  • and BROKER_TRANSPORT=”librabbitmq” to use the pylibrabbitmq C library