Inspiration

We heard Improbable's talk on their new probablistic programming language, Keanu, and thought it would be a lot of fun to try it out. We decided to focus on the game Battleships, since it is simple enough to program the graphics and logic in a hackathon, but has lots of hidden state to apply probabilistic programming on, and far too many configurations to simply brute-force.

What it does

First, the player can position their five ships on the board. The application then allows the player to step through running two different probabilistic AIs to play the game - one using Keanu, and one using more combinatorial heuristics. At each stage, the selected AI rates the probability of one of the player's ships being under each square of the board, based on a uniform prior and its observations of hits and misses so far in the game. The player can click a button to aim at the square rated as most likely and move on to the next turn.

How we built it

The AIs run on a Java backend, and communicate with the frontend via a REST API running on a Spring server. The frontend combines available online components with pure typescript code to create multiple game instances, keep track of valid/invalid states and visualise the probabilities in a dynamic heatmap.

Challenges we ran into

The Bayesian network for calculating which ships are in which squares is very large, and the resulting distribution is discontinuous and very high variance. Additionally many configurations of hits and misses are hard to fit -- very few arrangements of ships have non-zero probability. We also found that the sampler ran quite slowly for an interactive application.

Accomplishments that we're proud of

By making ship positions continuous and adding variance to observations, we allowed the Metropolis-Hastings optimiser to make much more headway than before, since this prevents regions of exactly zero probability.

Additionally we wrote a heuristic AI that uses a simple algorithm (considering each ship separately, and seeing where it fits on the board, weighting each configuration by motivated symmetry assumptions) and gives good results in a very short runtime, allowing interactive exploration.

What we learned

We learned how to use a probabilistic programming language, and a lot about the kinds of problems such languages are well suited for. We also gained experience writing an interactive frontend using modern web technologies.

What's next for BattleReeves

We would like to explore ways to make our Bayesian network more efficient, and perhaps use more advanced optimisers.

Share this project:

Updates