Versi

Implementing the actual rules of Reversi took a surprising amount of time—which probably means I really over-engineered things. I also ran into a few hiccups and had to restructure things to make my life easier. For instance, I switched from unsigned integers to signed integers so that I wouldn’t have to do as many conversions when doing arithmetic. I also decided to use my 1D indices explicitly for many of my internal functions rather than calling get_piece, which converts 2D coordinate to a 1D index (so (2, 3) on a 4x4 board would become 11). Another noteworthy change was the decision to map the last bit of the bitmask to the first space on the board, as opposed to reading the bitmasks from left to right as I did previously. Reading the bitmasks from right to left makes more sense in hindsight since the 2^0th place now corresponds with the 0th index, the 2^1st place corresponds with the 1st index, etc.

One clunky detail I had to deal with using 1D indices instead of 2D coordinates was diagonals. Moving one square up and one to the right on an NxN array is generally the same as moving N-1 indices backwards on the flattened 1D array, unless you’re on the last space on a row, in which case you’d jump back to the start of the row rather than moving diagonally. This is definitely not the intended behavior. My fix doesn’t feel particularly elegant: I ended up converting the 1D coordinate into a 2D coordinate to make sure the row and column coordinates wouldn’t change by more than one before stepping the index. I may think of a nicer solution later, but it works for now. :)

Below is a quick demo Asciinema cast, where I’m playing on a 4x4 grid. (All sizes are supported up to 8x8, but a full 8x8 would have taken a while to record.)

I haven’t worked on Versi for a little while, but today I wrote some traits outlining what my game representation needs to be able to do in order for the search algorithm to find good moves. For those unfamiliar with Rust, traits are a bit like interfaces in Java- they define what a type needs to be able to do rather than how to do it. As I mentioned in the first devlog, I want the MCTS code to be very extensible, so rather than assuming the data types I’m working with apply strictly to Reversi, I can simply indicate what information I do need, regardless of the game. If I every want to apply my MCTS code to, say, chess, I can simply implement the methods required by the trait bounds and pass the game representation into the search algorithm, and it will just work. Here’s an example of one of the traits I’ve defined - SearchGame. SearchGame indicates that any state space searchable by my implementation must provide it with a set of possible actions, a way of mapping actions to new states, a way of detecting whether a state is terminal (end of the game), and a way of determining who won in that terminal state.

Yet another Rust command-line project! I’ve actually wanted to make a Reversi solver for a while now, and after doing a bit of research into Monte Carlo Tree Searches (MCTS), I think this project will be a valuable learning experience. I was originally going to do Minimax with alpha-beta pruning, which would have been nicely deterministic, but I also foresaw that being a pain. I’ve played around with Minimax for simpler games, and while it’s conceptually straightforward, I felt like taking a break from the headache of pruning and optimizing a full search through an enormous game tree. Furthermore, recursion with mutable parameters is especially brutal with Rust’s borrow checker, and I suppose there isn’t much learning experience to be gained from applying a familiar algorithm to another game. Or, perhaps, I am simply lazy and looking for novelty. At any rate, MCTS is the route we’re going. Besides adding a fancy new algorithm to my toolbelt, my goal for this project is make my Rust code a little more idiomatic and tidy. I’ve lumped all the logic into lib.rs in my previous Rust projects, but now I’ve finally taken two minutes to look up how to properly extract modules into different files. :) I’m also going to define some custom traits and make heavier use of generics; my hope is that my code is modular enough that one could copy the MCTS part of the crate and apply it to a different game without making any modifications. As usual, there isn’t much of an exciting development in this first log. So far I’ve created a BoardPiece enum and a Board struct. Since Board just contains a couple u64s (for bitmasks) and a usize tuple for keeping track of the board’s dimensions, I’ve decided to derive the Copy trait to save myself further borrow checker woe. So far, tests are passing, and I can index the bitmasks just like a normal 2D array using the get_piece method I wrote. Since there isn’t much output to see, I thought I’d show some of the example code in the awesome auto-generated docs Cargo generated for me: