How I Created my own AI Bot Game Using Lisp

I really enjoyed playing in an AI bot contest, so I decided to make my own game “Footsoldiers” using Lisp. I needed a match runner to manage the bots and enforce the rules. Here’s how I did that by controlling the Docker daemon using its HTTP API.

My game: Footsoldiers

Footsoldiers is a two-player, turn-based strategy game. I designed it so I could share it with my friends and then play against each other.

Players take part in the game by writing an AI for their bot to outfox the other player. Each player has a base, and each turn, the players get money to spend on soldiers. The bots tell the soldiers what moves to make. There are rocks which obstruct movement, so players have to give directions to soldiers to prevent them from getting stuck. The aim of Footsoldiers is to send your soldiers to attack the enemy base. If your soldiers destroy the enemy base successfully, you win.

Bots can build three types of soldiers to attack the enemy:

1. A tank: The tank, in the sense of a heavy soldier rather than an armoured vehicle, is slow but sturdy.
2. A scout: The scout is fast and balanced in attack and defence.
3. An assassin: The assassin does a lot of damage but is weak.

Participants implement their own strategies for their game-playing bot to use. To enable players to play against each other, I needed a match runner. The runner sends the current state to the bot programs and gets output from them about what moves they’ve decided to make. Then, the runner updates the state using their moves and lets the bots know about the new state. I decided to use Lisp to implement the game and the match runner, with Docker containers for process control. Here’s why and how I did that.

Using Lisp’s flexibility

I implemented Footsoldiers in Lisp because I love the language. Lisp’s greatest strength is its malleability. When you want a feature that it doesn’t have, you can add it.

Error handling

For example, I like monads because they provide a generic and expressive abstraction for concurrency, missing values, non-determinism and error handling, among other things. Unfortunately, Lisp doesn’t have monads, so I wrote a library called Salmon that adds them to Lisp.

The comparison below shows what it’s like to use monad comprehensions in Salmon (on the right) vs monad comprehensions in Haskell (on the left). This example generates pairwise sums of list elements using the list monad.

do                                        (mdo (a '(1 2 3))
  a <- [1, 2, 3]                                (b '(4 5 6))
  b <- [4, 5, 6]                                (yield (+ a b)))
  return (a + b)     
- [5, 6, 7, 6, 7, 8, 7, 8, 9]             ;; (5 6 7 6 7 8 7 8 9)

I leveraged monads to let me use monadic error handling while implementing Footsoldiers. Monadic error handling is an expressive way to use values for errors instead of using exceptions. I prefer to avoid exceptions because they cause jumps between distant parts of code, similar to how ‘goto’ statements work. Exceptions are side effects which violate the functional programming principle of referential transparency, making it harder to trace the execution of a program.

Managing multiple files

Another instance where I took advantage of Lisp’s flexibility was managing multiple file handles and safely closing them after use. By default, managing multiple file handles requires nesting:

(with-open-file (f "file1" :direction :output)
   (with-open-file (f "file2" :direction :output)
     (write-string "hello" f1) (write-string "there" f2)))

I wrote a macro called ‘with-files’ that made the compiler do the nesting for me so that my code didn’t require nesting. It looked like this instead:

(with-files ((f1 "file1" :direction :output) 
             (f2 "file2" :direction :output)) 
   (write-string "hello" f1) (write-string "there" f2)) 

Removing the nesting made my code shorter and easier to write.

Implementing the match runner

To implement the match runner, I had to plan how to structure the project. I decided to use three modules for the match runner:

• A low-level module called the runtime: It handles process management via the Docker daemon. It stops and starts processes, sends input and receives output, and manages connections to the Docker daemon.
• The game runner: Above the runtime module, there is high-level logic for discrete n-player games in the game runner module. This connects the bot programs to player roles in the game and runs the game until it finishes.
• The footsoldiers module: The footsoldiers module uses the current state and the outputs from players to generate the next state. This handles the game’s mechanics like moving soldiers and making them attack. It also validates moves that players make, decides when the game is over and determines who the winner is.

The runtime module

The runtime module has three important responsibilities:

Bot input and output (IO)

Bot input and output send the game state to bots and get the bot moves for the current turn.

Resource management

Resource management is required to prevent bots from exhausting the available RAM on the machine running the matches. Consuming too much RAM could interfere with the game runner and deprive a rival bot of enough RAM to compete effectively.

Process control

Process control is the main mechanism used to control the CPU available to bots. When a bot finishes its turn, it is put to sleep, so it can’t use CPU during the other bot’s turn.

Using Docker containers

I initially implemented the runtime using Lisp’s subprocess API and Unix signals. However, I found that this approach had weaknesses:

• It was difficult to enforce memory limits.
• If bots created subprocesses, then signals didn’t necessarily propagate to those subprocesses.
• This would allow a bot to break the rules by avoiding signals sent by the match runner.

That’s why, instead of using signals, I decided to use Docker containers.

Process control: The Docker daemon manages Docker containers. The containers can robustly control all processes inside them and set limits on resources available to those processes. Many developers use Docker, and most of us use it through the Docker command line client.

Docker also provides an HTTP API to control the daemon. The Docker HTTP API is available on a Unix socket at ‘/var/run/docker.sock’. Using Unix sockets is a lot like using TCP sockets, except that instead of sending packets over a network, Unix sockets allow communication between processes.

Bot input and output: Bot input and output are handled by establishing long-lived socket connections to a bot container at the ‘/containers/attach’ endpoint of the Docker daemon. This endpoint creates a bidirectional connection which allows the client to stream input, output and error channels from the container. The container must be created with ‘stdin open’ to send input to a container.

Because I wanted to separate the standard error and standard output streams, I needed to use the multiplexed attachment API. This scheme uses a socket protocol to send the output as a series of frames. Frame headers specify the type of output sent - stdout, stderr or stdin - and the size of the output, which can then be read into a buffer. The remaining endpoints I needed were ordinary HTTP endpoints at:

• ‘/containers/create’ for creating containers,
• ‘/containers/{id}/inspect’ for getting the status of a container,
• ‘/containers/{id}/start’ for starting a bot,
• ‘/containers/{id}/pause’ for pausing a bot and
• ‘/containers/{id}/unpause’ for resuming a bot when it is that player’s turn.

You can find more details about the Docker API in the documentation.

A Docker image is built from a Dockerfile that each competitor provides, and each bot is based on this. Before the game starts, the match runner creates named containers from the players’ docker images, using the ‘/containers/create’ endpoint, which is then run and managed using the Docker API. The match runner creates containers with a read-only root file system, which disallows processes in the container from writing to files. When creating each container, memory limits are controlled by specifying the memory and memory swap options in the host config. If a container process tries to allocate more memory than allowed, the OOM killer will terminate it. This prevents one player’s bot from using an unfair amount of memory. When creating a container, the typical JSON that I send to the Docker daemon looks like this.

{
  "Image": "bot-match/lisp-base",
  "OpenStdin": true,
  "Memory": <ram_in_bytes>,
  "MemorySwap": <swap_in_bytes>,
  "HostConfig": {
	"ReadonlyRootfs": true
  }
}

Time to initialise

Because different bot implementation languages have different startup overheads, bots are allocated time to initialise before the game starts. If it weren’t for this, some languages, like Java, would face an unfair penalty because the runtime can be slow to initialise. Once the bot has written “Ready” to its standard output stream, I know that I can provide it with its input and start its turn. Unless they crash, processes are only started once, so this initialisation only has to happen once. After all the bots are up and running, each bot’s turn is executed by unpausing it, sending it input and then waiting for its output using long-lived sockets connected to the bot’s docker container. A bot is paused at the end of its turn. At the end of the game, the containers are stopped and removed.

The game runner

The game runner module is at a higher level of abstraction than process management and interaction with Docker. The generic methods below define the interface for a game:

(defgeneric is-finished? (game))
(defgeneric game-result (game))
(defgeneric get-players-input-for-turn (game))
(defgeneric advance-turn (player-moves game disqualified-players))
(defgeneric input-parser (game))
(defgeneric turn-time-limit (game))

The module provides a high-level interface for running a turn-based n-player game. It uses the template method pattern to implement a method called tick, which advances the game one turn. Another method, n-player-game, runs a game until completion. This is what these template methods look like:

(defmethod tick (bots game logging-config)
  (let* ((player-input-for-turn (get-players-input-for-turn game))
     	(new-bots (make-hash-table :test 'equal))
     	(turn-results (mapcar (lambda (pin)
                             	(let ((bot (gethash (car pin) bots)))
                               	(if bot
                                   	(cons (car pin)
                                         	(bot-turn bot
                                                   	(cdr pin)
                                                   	(turn-time-limit game)
                                                   	(logging-config-turns           
                                                           logging-config)
                                                   	(input-parser game)))
                                   	(cons (car pin)
                                         	(make-bot-turn-result
                                          	:updated-bot bot
                                          	:output "")))))
                           	player-input-for-turn)))
	(mapc (lambda (res)
         	 (let ((updated-bot (bot-turn-result-updated-bot (cdr res))))
          	(when updated-bot
            	(setf (gethash (car res) new-bots) updated-bot))))
      	 turn-results)
	(maphash (lambda (p b) (when (not (gethash p new-bots)) 
                   (setf (gethash p new-bots) b))) bots)
	(let ((turn-result (advance-turn (mapcar (lambda (res) (cons 
                     (car res) 
                     (bot-turn-result-output (cdr res)))) turn-results)
                         game (find-disqualified-players new-bots))))
              (cons new-bots (game-turn-result-game turn-result)))))

(defmethod n-player-game (bots game logging-config)
  (unwind-protect
   	(loop for (cur-bots . gm) = (cons bots game) 
                   then (tick cur-bots gm logging-config)
      	 until (is-finished? gm)
      	 finally (return gm))
	(terminate-bots bots logging-config)))

This template is reusable. Suppose I want to implement another turn-based n-player game later. In that case, I can focus on game behaviour because the logic for running the game and interacting with Docker is encapsulated.

Footsoldiers module

The final module is Footsoldiers itself. Because interacting with Docker containers and managing an n-player game are separated from this module, it can be implemented as a function from the current game state to the next game state. It has no long-lasting state kept between turns. The main method for advancing the game is implemented like this:

(defmethod advance-turn (player-moves (game game) disqualified-players)
  (if (not (null disqualified-players))
  	(make-game-turn-result
   	:game (duplicate-game game :disqualified-players disqualified-players)
   	:move-log nil)
  	(bind ((parsed-moves (mapcar #'parse-move player-moves))
         	(valid-moves (rights parsed-moves))
         	(move-result (step-game valid-moves game)))
    	(make-game-turn-result :game (move-result-updated-game move-result)
                           	:move-log (mapcar #'format-parsed-move parsed-moves)))))

Runtime Configuration

After implementing the game logic in the Footsoldiers module, the final detail in the match runner is runtime configuration. It’s convenient to be able to change the cost of soldiers or damage done by soldiers without having to recompile the match runner or write code that needs additional testing.

To do this, I load configuration values for the game from a JSON file. The game map, seen in the image below, is configured in an ASCII text file. The Xs are rocks which soldiers must manoeuvre around. The number 1 is the first player’s base. The number 2 is the second player’s base. It’s easy to come up with interesting new maps in a text editor by positioning the bases differently and making patterns of rocks that affect what kind of strategy works best.

With the match runner in place and the logic of Footsoldiers implemented, I can run games. This is what it looks like to start the match runner using an example bot.

Below are two simplistic players that always build scouts and always send the scouts directly to the enemy’s base to attack. The scouts are represented by square brackets.

Writing this match runner has been a great way to explore the Docker API and to have fun with Lisp. It also provides a playground for me to experiment with inventing games for bots to play, something I can have fun with and invite friends to enjoy with me.

You can check out Footsoldiers on GitHub here.

If you enjoyed this article from Henry, check out his article: Lisp's Superpower: Saving Time Writing Code

Henry is a Scala engineer at GrapheneDB where he uses functional programming to manage graph databases in the cloud. He loves functional programming because it makes code robust and easy to reason about.