Star board game AI

I’ve implemented a computer player for a variant of the game of *Star, which can be played against here.

This player is written in Rust (source here) and compiled to javascript using Emscripten.

*Star

*Star is a board game related to Hex. These belong to the family of connection games, where the players alternate placing pieces, attempting to form some kind of connection while blocking their opponent from doing so. While most of these games have a connection goal which is accomplished with a single group of pieces, *Star is score-based and separate groups can all contribute to a player winning. It bears a vague resemblance to the ancient game of Go.

The original rules are described on the Wikipedia page. For this implementation, I have opted for a simpler plain hexagonal board without the special center point, done away with tiebreaking by who claims the most corners, and added one additional rule which gives 1 point as komi to the second player. The web interface has a full description of the variant rules (the rules are also rephrased somewhat).

Since a six-sided board has an even number of points on the boundary (so the sum of the players’ scores will be even), it’s necessary to break ties in some way. Since the first player will have an advantage by having the first move, a natural way of doing this is to add an odd number of points to the second player’s score. It seems like 1 point makes the game fairly balanced, but it’s possible that a swap rule would be needed as well.

The AI

The AI I wrote is very similar in design to this Poly-Y player, which was written with the constraint of using very little time per move. The basic approach is to use Monte-Carlo tree search with the all-moves-as-first heuristic.

Like with the top hex player MoHex, it uses random playouts except that when a bridge pattern is threatened, the player protects it (this greatly increases the strength of the player).

In theory compiling with emscripten should give performance comparable to native, since it compiles to asm.js. In reality it seems that there is an order of magnitude difference between the native code and emscripten. I’m not sure if it’s an issue with my code or the rust compiler, but rust support for emscripten is fairly new, so it’s possible this will improve with time.