Every time I visit my folks at their cabin we end up playing some rounds of scrabble. We allow the use of some aids, e.g., online tools that help find all words that that consist of a set of letters. Since we usually drive up to visit them (usually takes about 16 hours, usually split across 2 days), I’m always looking for some toy problem to work on in the car. On the last trip back, I figured I would write a scrabble word placement helper that find the maximum move given the set of letters. I didn’t finish this on the last visit, but had a skeleton of the solver (but my lookup was slow).

This past Christmas, I decided to revive that project, and ended up with a much more clean and efficient implementation. It’s obviously a pain to input the status of a game without a user-interface, so I whipped up a quick barebones UI (and server) that allowed playing from the game from the start.

With that, it’s easy to pit a few of these optimal players against each other. They have no actual strategy, though, beyond trying to maximize the score that you could get with the letters on hand.

More info and details along with the code here: https://github.com/nbirkbeck/scrablve

Here’s an example of two of the auto-players playing against each other:

While playing a video game (I believe Mafia 3, from previous Christmas, I believe), I had started to think about what a “fun” AI to play against would look like. I got excited about trying to spend some time learning a bit about this space, using a restricted/simpler game environment.

I decided that a simulation environment for a stripped down version of a 1st-person shooter game (mostly happening in 2D) would be sufficient. Agents can move around the environment and the objective is to shoot the opponent. The bullets look like little arrows and do a certain amount of damage (armor limits the damage).

Like Quake III (one of my all-time favorite games), there are some power-ups (health and armor). Controlling power-ups is necessary to be successful in this death-match game (first to hit a certain number of kills in a given time frame).

Simulation Libraries

The environment (world) and core actions of the agents are written in C++, where the agent gets observations from the world and returns a set of desired actions. Actions are carried out by the world, using proto-buffers for communication. This was mostly since I was designing this before thinking about how I would be interfacing with RL libraries.

In the end, I found that stable_baselines3 seemed like a reasonable RL python library, so I just had to adapt the python wrappers of the c++ core to expose what was necessary there.

So proto for data that needed to be serialized, bazel for build, gtest for testing (there aren’t many), stable baselines3 (for RL), and eventually Ogre and Blender cycles for rendering (see below).

Some example YouTube videos:

• Playing the game (1st person) against one of the agents: https://youtu.be/Dz061aS6qgM
• An example using the old (non-OGRE) rendering: https://youtu.be/h6Pw6QfVRgc

Code available: https://github.com/nbirkbeck/battle-ai

Agent Training using Reinforcement Learning

After a day or so of getting an environment ready, and then a bit more time integrating into an RL environment. I remember being slightly disappointed with the results. I think this was me being naive in terms of the amount of effort involved in tuning parameters / debugging models to get an agent to learn anything.

Finding power-ups

I had to dial things back to try to get an agent capable of even finding powerups. In that simpler environment, reward is proportional to the health or armor that the agent picks up, and actions are movement in one of 4 directions. Eventually, the agent did find a reasonable strategy to pick up items in a loop (but still missed finding one of the other health items that could have been more optimal). Likely, if I had better knowledge of the training algorithms / parameters / back-magic involved in tuning them, I could have found them.

Example: The agent starts out in the left of the video and does learn to pick up the health (middle left), and then go to the center (to get the armor). The agent then repeats this pattern.

There is also an example video here:: https://youtu.be/TCylBJaad6E

Higher-level actions

Seeing how long it took to get the agent to solve the simpler task of finding power-ups, and given I was interested in learning high-level strategies, I created the skeleton of a “plan-following” agent. This agent is parameterized in terms of behaviors (like go to a health or armor powerup, move towards the shortest path to a visible opponent, or move left, right, away from the opponent). The agent senses how far away from the items it is, as well as how far away from the opponent, it’s health/armor, etc.

I really wasn’t sure how to setup the parameters for the learning algorithms and just adapted them from other games (like the atari games). After several trials, I started adding more complexity in the rewards (e.g., reward for not standing still, for not hitting a wall, for getting health and powerups, as well as for killing the opponent, and negative reward for being killed). This just introduced more parameters that it wasn’t clear how to tune.

After some time of back-tracking my approach, just using a simple reward of “1” for killing the opponent seemed more desirable–given that really is all that matters in the end. After playing around with the training schedule and increasing the number of iterations, training loss was decreasing and the agent was doing better. Example: https://youtu.be/adXGj-8ppU0.  But the agent still seemed “dumb”, e.g., it was avoiding going to nearby powerups when health was low. And the agent wasn’t better than the hard-coded agent I wrote in a few hours to bootstrap the training process (and to test out the planning).

After several more attempts, each training for about 1.5 days (20 Million steps) with various parameters, things weren’t getting significantly better. Ultimately, the best I got was by penalizing all of the left, right, forward, back actions in favor or just going for powerups. The agent could at least hold its own against the opponent it had been learning against:

Example video: https://www.youtube.com/watch?v=MYxv-7oNm38

In the end, during the process, I realized that my initial motivation to work on this problem was about a “fun” agent to play against. Training an agent to be good at the task was likely to not be a fun opponent to play against. I guess I got out of the project what I had intended, but like any other of these projects there are many fun digressions along the way.

Interesting Digressions

Either when training agents (and waiting for things to happen) or just looking for other things to clean-up before finalizing the project, there are always some interesting findings along the way.

Pyclif vs other wrappers

In previous projects (years ago), I had used Swig (http://www.swig.org) for creating python wrappers of my c++ code. And since I was using QT for many UI’s at the time, I ended up switching my personal libraries to SIP. I look fondly back on writing custom implementations for accessors with SIP as it gave some visibility on the raw python C API. 

Another similar utility is CLIF (https://google.github.io/clif/), which I initially tried to use with this project. But for reasons that I can’t recall, I either couldn’t get it to work – or couldn’t get it working easily with Bazel (which was what I’d chosen to use for the build system). 

However, in the process I came across Pybind (https://pybind11.readthedocs.io/en/stable/) as an alternative. And I ended up loving it. It is trivial to create the mappings, the code is all c++ (instead of a domain specific language), and the custom implementations (say for accessors) can be concisely written with lambdas in c++.

For example, I have an image class that I have been using for more than a decade that primarily uses operator overloading for accessors. When simply trying to export a heatmap for the examples above, dealing with the image libraries (e.g., PIL) for floating point RGB turned out to be painful to figure out in minutes. Since I already needed python wrappers for the Agent and World, it was easy enough to export the image interfaces, which were already being used in this project. Adding custom code (using set instead of operator) was easily accomplished with the following wrapper:

  py::class_(m, "Image8")
    .def(py::init<int, int, int>())
    .def("width", &Image8::getWidth)
    .def("height", &Image8::getHeight)
    .def("set", [](Image8& image, int x, int y, int c, int v) {
       image(x, y, c) = v;
    })
    .def("resize", &Image8::resize)
    .def("save", &Image8::save);

Blender Cycles Render For Ambient Occlusion

I really wanted to automate a somewhat decent rendering from a simple box-based specification of the world. Simple materials with ambient-occlusion in Blender seemed good enough, but the steps required to do it (and make sure it was synchronized with all the geometry) was a bit of a pain. Likely possible to whip some scripts up in blender directly, but since Blender was using Cycles under the hood maybe it was just as easy to use Cycles directly to bake in some ambient occlusion directly from the level specification.

Where things went wrong:

1. I only ended up making one or two levels, so probably wouldn’t have been too much work to do this manually for those few cases
2. After hacking up a simple visualization, I really didn’t want to get too distracted with graphics (or animations) – so I ended up searching for a rendering engine to use. I just decided to use Ogre, mostly because it was available and I’d heard of it before.

So the sequence of steps for creating a level is something like:

1. Create the boxes in blender
2. Export the proto representation of the world and a concatenated mesh representation
3. Create the geometry and use cycles to do the ambient occlusion
4. Load the geometry into blender so that it can be exported (and converted) to an appropriate Ogre form

Obviously, that could be simplified, but whatever.

Resulting ambient occlusion map given below. With the example on the left being a handy trick I use all the time to rasterize barycentric coordinates of my triangles in the texture map.

Ogre for rendering

Some rough visualization was necessary, so I had just whipped up a quick visualization using some of the old libraries from my grad school days. But I still wanted it to look decent (hence the ambient occlusion digression), but when I was thinking about adding shadow, materials or animations, it seemed wasteful to do that without some other libraries.

I ended up using Ogre for this. Overall, this was a fairly painless transition, although I do remember the export and conversion of animations from blender to be a bit painful and required some time. Similarly for adding text.

Without ambient occlusion

Default interface (with ambient occlusion):

Ogre interface:

Checkout the videos instead:

• Ogre interface: https://youtu.be/MYxv-7oNm38
• Simple interface: https://youtu.be/h6Pw6QfVRgc

And with that, I think I’ve almost cleared my slate for this year’s christmas project (still TBD if at all…)

A long time ago (sometime as an undergrad) I wrote a NES emulator (http://www.neilbirkbeck.com/?p=1054)

For some time, I’ve wanted to take either the rendered frames, or some game state and try to make a more appealing rendering of emulated games. I did finally get a chance to spend some time on this over the previous Christmas break. However, despite my best intentions of producing something that looked photo-realistic, it simply wasn’t practical to do in 4-5 days. I figure it is interesting enough to post what I ended up with here anyway.

The source code and some more details here (https://github.com/nbirkbeck/ennes). Although, the actual implementation depends on a bunch of my internal libraries (nimage, nmath, levset, and a bunch of other code from my PhD). At one point, I was tempted to use ideas similar to (http://www.neilbirkbeck.com/?p=1852) to try and get nice silhouettes for the upsampled images.

Here’s an example rendered video:

What I ended up doing was extracting the game state from the emulator, grouping sprites (based on colors), upsampling the images, producing a silhouette, and using those to extrude 3D geometries. For the most part, there is a cache that maps an sprite group to a corresponding 3D model. More details in the README.md on github. And there are a few hacks specific to super mario1 (which was mostly what I was thinking about  when I started working on this).

Some examples of the puffed-up geometries:

The following image (right) illustrates the upsampling used. (Left is nearest, and middle is image magick’s default)

And some screenshots (mostly from smb1):

One other noteworthy thing was just how bad the code was from the old emulator. For example, in rendering from the pattern table, there would be something like the following. And then there would be multiple versions of that code for the various options available for flipping the pattern (horizontally and vertically)

cindex= ((temp>>7))| (0x2 & (temp2>>6));
if(cindex){
layer0[x]=uppercolor|cindex;
layer1[x]+=inc;
}
cindex= (0x1 &(temp>>6))| (0x2 & (temp2>>5));
if(cindex){
layer0[x+1]=uppercolor|cindex;
layer1[x+1]+=inc;
}
cindex= (0x1 &(temp>>5))| (0x2 & (temp2>>4));
if(cindex){
layer0[x+2]=uppercolor|cindex;
layer1[x+2]+=inc;
}
...
}


Contrast that to how simple a more comprehensive routine could be in the newer render_util.cc

Programming is a fun way to pass time.

A few years ago, I was playing lots of sokoban (or box pusher). Around the same time, I was also conducting a number of technical interviews, so was often thinking about self contained programming problems. Back as a grad student, in a single agent search class, we learned about searching with pattern databases–basically you solve an abstraction of the problem and use the solution length in that space to build up a heuristic (see this paper Additive Pattern Database Heuristics).

I’m sure there is plenty of research on the actual topic for sokoban, but I was interested in poking around the problem we were driving to Canada from California for a holiday.

The source code is up on github here:

https://github.com/nbirkbeck/soko-solve

And you can check out the demo (included in iframe below):

http://neilbirkbeck.com/soko-solve/

You can play the levels with ‘a’, ‘s’, ‘w’, ‘d’. Or you can click “solve” and “move” through the optimal path. The “Solve all” will benchmark a bunch of different methods. There is a much more detailed description of my analysis in these notes:

https://raw.githubusercontent.com/nbirkbeck/soko-solve/master/NOTES