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.
- Determining the best move manually is extremely time consuming and errors are very unforgiving.
- 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!
- 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
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…
Remove all allocations at search time.
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.
There are a few ways to work around the problem:
- Inline member variables into your object.
- Let your object inherit the other object (is-a relationship instead of has-a)
- 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
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.
- No control over resizing or dynamic sized canvas viewports.
- I want to use threads (aka “web workers”), but there is no threading support of any kind in libgdx.
- As in every UI framework, input handling is broken and has to be done manually (at least they support that!)
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.