A Quoridor implementation in Rust, including different AIs

Overview

Quoridor in Rust

Quoridor is a zero-sum strategic board game with complete information. It was initially designed by Marko Marchesi based on Blockade by Philip Slater.

Gameplay

Example board for a 4-player game

Quoridor is played on a 9x9 board, either as a 2-player game (red and blue) or as a 4-player game. The goal of each player is to get to the other side of the board. So the red player would have to reach the very bottom row of the board and the blue player would have to reach the very top row, respectively. During their turn players can either move or place a wall. They can move to any adjacent tile that is not blocked by wall but can't move diagonally. There is also rules that allow players to jump over another player (see the Wikipedia entry for the full set of rules). In a 2-player game both players get 10 walls each (in a 4-player game everyone gets 5). A wall is two tiles wide and can be placed between tiles - they prevent players from moving as walls can't be jumped. Walls can't be placed on top of each other (on an actual board this is physically impossible) and one may not place a wall such that a player can't reach their goal.

Implementation and idea

The main idea of this project was to implement a simple board and allow users to not only play the game but implement and try different AIs.

The entry point of the game is the run function: it takes two "players" (structs that implement the AI trait). It then runs the game until it's over. When simulating the game, it does not check whether a move is valid or not - gentlemen's agreement - since it seemed unnecessary to check if a move is legal since the AI most likely already made sure of that (the provided helper functions like get_valid_walls obviously only return valid wall placements).

The board is a plain Vec<Node>. A node represents the "state" of a tile:

struct Node {
    right: bool,
    down: bool,
}

right and down specify whether a player could move right/down from this tile. Having left and up is redundant, as two adjacent tiles would be holding "duplicate" information (right on tile A "==" left on tile B and same for up/down).

There is a few simple tests to make sure everything is implemented properly (and doesn't break when I fix the pathfinding). In the examples folder there is an example simulation to let two AIs play against each other, you can compile and run it as followed:

cargo run --example test

Additionally, since just knowing which AIs is a little boring, we can watch them play against each other by enabling the print_game feature:

cargo run --example test --features print_game

Current AIs

Most of the currently implemented AIs are very primitive and straight forward.

  • MoveOnly: takes the shortest path to its goal every turn
  • Random: random
  • RandomMoving: similar to Random but doesn't place walls, it only moves randomly They were mostly implemented to test how "random" "randomness" can be and to test the simulation and helper functions. WallFirstMax and WallFirstMinmax are little more sophisticated, but not perfect. WallFirstMax iterates over all legal wall positions and picks the one that extends the enemy path the most (if there is multiple, it picks one at random). WallFirstMinmax turned out worse than I expected, the idea was to maximize the enemy path while keeping my own path as short as possible but this turned out to be a very weak algorithm.

To-Do

Currently, the path finding is flawed: It doesn't really take jumping-over-a-player into consideration.

Based on a few other implementations of Quoridor and a few research papers, there is still a few more AIs I'd like to try and implement, as well as an actual "player" player (so you can play against the AIs yourself, instead of just watching them play). I'd also like to include better test cases and have more examples ready to run.

Check out other implementations of Quoridor:

These papers helped me grasp the sheer complexity of Quoridor and helped me better understand the game as well as implement certain things.

You might also like...
A first-time implementation of Conway's Game of Life in Rust: Adventure and Commentary

A Commentary on Life This project documents the process and final result of my first-ever attempt at implementing Conway's Game of Life. I'll be using

Rust implementation of behavior trees.
Rust implementation of behavior trees.

Bonsai 盆栽 Rust implementation of Behavior Trees Contents Quick intro to Behavior Trees Concepts Examples Development Guide Kanban Board Honorable Ment

Terminal UI implementation and types for the Dark Forest game

dark-forest.rs Terminal UI implementation and types for the Dark Forest game Development We use the standard Rust toolchain cargo check

A simple implementation of Conway's Game of Life using Fully homomorphic Encryption

Game of life using Fully homomorphic encryption A simple implementation of Conway's Game of Life built using Zama's concrete-boolean library. Build Ju

An implementation of the Game of Life

Lifeee – An implementation of the Game of Life I realized this application to keep learning Rust, discover the front-end library Yew, and because I’m

A wordle implementation that I made for a competition of wordle solvers

Wordle tester A wordle implementation that I made for a competition of wordle solvers. Runs tests using a list of words and outputs the total turns ta

The study of a simple path tracer implementation (image raytracing in shorts)
The study of a simple path tracer implementation (image raytracing in shorts)

The study of a simple path tracer implementation (generate a raytraced image, in shorts).

RusTTS is an unofficial Coqui TTS implementation.

RusTTS RusTTS is an unofficial Coqui TTS implementation. Currently, only the YourTTS for [ TTS & VC ] has been implemented. So, feel free to contribut

bevy-hikari is an implementation of voxel cone tracing global illumination with anisotropic mip-mapping in Bevy
bevy-hikari is an implementation of voxel cone tracing global illumination with anisotropic mip-mapping in Bevy

Bevy Voxel Cone Tracing bevy-hikari is an implementation of voxel cone tracing global illumination with anisotropic mip-mapping in Bevy. Bevy Version

Owner
canta slaus
i like vimbs \ discord: canta#5556
canta slaus
Cross-platform (including wasm) persistent key value store plugin for rust games/apps

bevy_pkv bevy_pkv is a cross-platform persistent key value store for rust apps. Use it for storing things like settings, save games etc. Currently, it

Johan Klokkhammer Helsing 17 Aug 30, 2022
Bevy plugin to simulate and preview different types of Color Blindness.

Bevy Color Blindness Simulation Bevy plugin to simulate and preview different types of Color Blindness. This lets you ensure that your game is accessi

annie 25 Sep 23, 2022
A no-frills Tetris implementation written in Rust with the Piston game engine, and Rodio for music.

rustris A no-frills Tetris implementation written in Rust with the Piston game engine, and Rodio for music. (C) 2020 Ben Cantrick. This code is distri

Ben Cantrick 17 Aug 18, 2022
An (unofficial) open source Rust implementation of the Discord Game SDK.

⚔️ discord-sdk An (unofficial) open source Rust implementation of the Discord Game SDK. Why not use this? This project is not official and is using a

Embark 70 Sep 20, 2022
Rust implementation of Another World (aka Out of this world) game engine

RustyWorld Rust implementation of Another World (aka Out of this world) game engine. I wanted a fun project to challenge myself while learning Rust, a

Francesco Degrassi 3 Jul 1, 2021
Implementation of the great book Ray Tracing in One Weekend in Rust.

Ray Tracing in One Weekend (Rust) Implementation of the great book Ray Tracing in One Weekend in Rust. Fun easy way to pick up and learn Rust (was rou

Stanley Su 6 Dec 29, 2021
A Rust implementation of the legendary solitaire game

Freecell Yet another implementation of the legendary total information solitaire. Play patience like it's 1991, complete with sights and sounds. Build

null 15 Aug 25, 2022
Game of life implementation written in Rust.

Game of life Game of life implementation written in Rust. Part of my journey in learning Rust. Pattern files The patterns are based on the example pat

Hashem Hashem 2 Jan 3, 2022
A simple, very minimal Minecraft server implementation in Rust.

A simple, very minimal Minecraft server implementation in Rust. For a simple Minecraft server that isn't supposed to do much (for example, a limbo ser

Chris 7 Aug 17, 2022
Rust implementation of the Nomic Bitcoin sidechain

Nomic Bitcoin Bridge testnet v0.3.0 (codename "gucci") Guccinet In this testnet, we've added two core featues: staking and Bitcoin integration. Full s

Nomic 63 Sep 5, 2022