Over the past few months, I’ve been working on a game-playing AI for the board game Breakthrough. Breakthrough is interesting. The rules are very simple, but strategic play develops an almost fractal-like quality.
My AI is named Picket. It uses a Monte Carlo algorithm to intelligently figure out strategy without any domain knowledge programmed in. This means that, even though I had just learned about Breakthrough when I started programming the AI, Picket was able to play with developed strategy. Ultimately, Picket taught me much of what I know about Breakthrough strategy.
The capstone project of Harding’s computer science program puts students into teams and has them develop a computerized version of an (often obscure) abstract strategy game. A sub-competition of the project pits the student-created AIs against each other and against human testers. I created Picket to help the team of five human testers (including me) learn the game.
Currently, at its default strength of 100,000 iterations, Picket provides a strong challenge for all the human testers, with none of us able to beat it regularly. 10,000 iterations provides an easier challenge (and is much quicker), but is still a worthy opponent for us. I’d be curious to compare it to other Breakthrough players.
The capstone project testing took place in late April, but I still have plans for Picket. I’d like to:
- Write a series of posts explaining Picket’s algorithm, which has a few interesting features (some of which greatly improved strength).
- Translate Picket into Rust. Picket is currently written in C, and often Rust is compared with C. I’d like to gain more familiarity with Rust, especially since I’m planning other AI projects for more complicated games that might benefit from Rust’s additional safety and clarity.
- Develop a formal way of analyzing Picket’s playing strength, especially relative to other versions of Picket. During development, I used a small script to play two versions against each other (often the established best version versus a new modification). I’d like to do some experiments on how factors like the number of iterations affect Picket’s playing strength, and to do that I need a more robust system.
I’ll probably start with the last one first, as if I have a rating system I can compare the strength of C Picket with the Rust version.