Quoridor

Sometime last year, while I was staying with Andrew and his family, he and I dug out some of their old board games and we found one called Quoridor. Initially I was skeptical, but once he explained the rules I was hooked. The premise is so simple: each player starts on one side of the board and they try to get to the other. On your turn you may use 1 of your 10 walls to change the board or move your token. Barring some rather intuitive rules about how the tokens jump over each other if they get to be next to each other, there is only one more rule: you cannot add a wall such that either token cannot reach their goal.

What’s great about this game is that its a “perfect knowledge game” like Chess. What this means is that on your turn you don’t have any information about the board that your opponent doesn’t also have. Its a true battle of wits. I got super hooked on the idea of building an AI for the game. I had been reading about AlphaZero (Deep Mind’s Algorithm that can beat the best humans at several other perfect knowledge games) and I wanted to see if I could apply it to Quoridor.

The first thing I needed to do was implement all of the logic of the game as code. I did this in Rust because I’m really excited about the programming language, its very performant, and I got caught up in the hype. While I was visiting my sister in CT I wanted to show my mom what I was working on and the primitive TUI I had made to test the game myself just wasn’t making sense to her. I compiled my Rust code to WASM and implemented a Web UI.

The above game should be playable embedded straight into this blog post. I apologize that its pretty-much unplayable on mobile. You can move your token by clicking on the a square adjacent to it (the allowed squares should be highlighted in a lighter color). You can add a wall by clicking on the spaces between the squares. Walls are two squares long.

While I was working I got Daniel Amsel obsessed as well, much to Alissa’s chagrin. We spent many hours not getting Alpha Zero working with it and he created a re-implementation of the game in Python. Many CPU/GPU hours were burned trying to get the algorithm to train before we finally gave up. What you see above is using alpha-beta pruning (using a library called Rubot). In spite of these difficulties I think we both had a grand old time.

Until next time, Sheyne.