<p>7th Guest AI spanking in progress</p>

7th Guest AI spanking in progress

7th Guest is a puzzle game released in 1993. At the time, the authors didn’t know what kind of puzzles should be in a good puzzle game, so we ended up with the “Infection” puzzle. You can find this puzzle in the game when you peer into a microscope in some mad scientist’s lab.

Now, this isn’t really a puzzle as much as its a battle of wits against an AI. It is a bit like checkers mixed with go. If you haven’t played it, I assure you, it is terribly unfun. Unless you want to spend weeks training to beat this puzzle (hint: you don’t) you may appreciate the AI I have written to do it for you.

Rules of the game

The “Infection” game rules are the same as another game known as Attax.
The rules are somewhat simple:

  • The board is a 7x7 grid, with pieces starting the corners of the grid.
  • On your turn any one of your pieces may spread one square any direction, including diagonals
    – or –
    Any one of your pieces can jump 2 squares in any direction, including diagonals, leaving behind a void
  • The oppenent’s pieces bordering your landing square swap colors to your color.
  • The goal is to get the majority of the squares to be your color when the game is over.

Problems with the game design

There are several problems with the game design.

  1. Determining the best move manually is extremely time consuming and errors are very unforgiving.
  2. Merely determining if you are winning is problematic because turns have such huge swings. Each player appears to be winning then losing big. It’s so bad that 7th Guest itself doesn’t know who is winning. Your character will often murmur to himself, “I’m going to have to start again”, when you are actually winning!
  3. Because of the huge swings between the turns, whoever moves last often wins with a huge swing. This means that at the end, the optimal strategy is to jump around a lot in an attempt to avoid moving last. This can somewhat randomize the outcome of games.

Implementing an AI

The actual implementation of the AI is a traditional minimax search tree (negamax), with alpha-beta pruning to speed it up. This particular AI was written in Java and compiled to javascript via libgdx, which uses GWT under the covers.

I believe the 7th Guest AI searches three plies deep, so reliably beating it requires four plies or better. This is simple and fast in native code, but…

Problem: Javascript is still slow

Don’t let the browser vendors fool you, javascript is still painfully slow compared to native implementations. The javascript code runs more than an order of magnitude slower than native code (I have a C++ implementation as well). At any rate, to make the AI run in javascript, I had to spend significant effort to optimize the speed of the search.

Remove all allocations at search time.

When learning algorithms in school, searching a tree involves visiting nodes. These nodes are invariably Objects that you allocate and have to be freed in the future, with garbage collection or otherwise. The main optimization to make here is that you do not need to allocate node objects on the heap. Imagine traversing a tree, generating and using objects purely on the stack. Unfortunately, this is not something that java and javascript let you do without a fight.

To get the stack performance without language support. I pre-allocate the “stack” and pass it down to recursive search calls where they use the appropriate objects at their depth. This means no nodes are allocated (or garbage collected) during the minimax search phase.

The impact of this is huge, it is by far the greatest speed savings. (It sped up the code by about 50%, measured in Chrome).

Reduce pointer chasing and object lookups.

In java/javascript there is no way clean way to compose objects that do not lead to multiple allocations and pointer chasing. For instance, in C/C++ you can have a struct that contains another struct. In java/javascript that internal struct must be a new object allocated on the heap. When you access that object, you end up chasing pointers in memory all over the place. Javascript also adds additional overhead in looking up those object pointers.

There are a few ways to work around the problem:

  1. Inline member variables into your object.
  2. Let your object inherit the other object (is-a relationship instead of has-a)
  3. Use arrays of primitives instead of objects.

I use all three of these methods to speed things up. My ‘node’ object “is a” board, and has inlined member variables for positions and moves. When enumerating child moves, the function writes positions to preallocated primitive arrays. The speed up was about 20%, measured in Chrome).

These solutions feel very cludgy and hacky. I thought about using emscripten but I couldn’t think of a way to make it work well with any UI frameworks.

Problem: Web UI frameworks suck

<p>libgdx, the best of the worst</p>

libgdx, the best of the worst

If you are a web programmer, you are likely well aware of pain induced by creating UIs that work across all web devices. One of my (mostly failed) goals was to get this UI to work properly on cell phones as well as desktop browsers. To make a long story short, I tried out several UI frameworks, ended up using libgdx, and I’m not impressed with it.

Let me be clear, libgdx is not horrible, with some polish it could be quite decent. Most features work as advertised. I only have a few complaints with gdx.

  1. No control over resizing or dynamic sized canvas viewports.
  2. I want to use threads (aka “web workers”), but there is no threading support of any kind in libgdx.
  3. As in every UI framework, input handling is broken and has to be done manually (at least they support that!)

The bigger problem is that javascript is an awful target platform. I prefer to use a strongly typed language for complex computation, which means code translation at some point. I briefly mentioned before that emscripten may be a decent solution, but the amount of work required for the UI elements may be a bit restrictive. Ideally, I’d like to write the performance critical stuff in C/C++ and the UI stuff in some fluffy quick language (perhaps something like QML). I’m pretty sure we’ll get there, but as far as I know, we can’t do that yet.

If you havn’t checked it out yet, heres a link to my AI. Sometimes it makes moves that look stupid, it might be a bug, I dunno, still wins.