Zoridor, a terminal Quoridor

tobyjaffey · November 24, 2024, 8:38am

A terminal version of the Quoridor board game, in Zig.

The machine player is good enough to beat a novice.
To watch it play itself forever (WarGames style):

zig build run -- -1 machine -2 machine -f

demo

tobyjaffey · November 27, 2024, 1:23am

I’ve now completely rewritten the backend of this to be based on a graph representation of the board. By modelling the board as a connected graph and having each fence/wall placement be a removal of graph edges, path finding and movement on the board is much more natural.

github.com

ringtailsoftware/zoridor/blob/main/src/graph.zig

const std = @import("std");

pub const BitGraph = struct {
    pub const NodeId = u8; // 0 <= n < 81
    pub const Coord = u4; // 0 <= n < 9
    pub const CoordPos = struct { x: Coord, y: Coord };
    pub const NodeIdRange = struct { // a range of continuous node ids inclusive of min and max
        min: NodeId,
        max: NodeId,
    };
    pub const MAXPATH = 9 * 9;
    const Self = @This();

    bitMatrix: [9 * 9]u128, // 81 lines, each using first 81 bits

    pub fn init() Self {
        return Self{
            .bitMatrix = std.mem.zeroes([9 * 9]u128),
        };
    }

This file has been truncated. show original

In Quoridor, pawns usually move 1 square per turn orthogonally. However, they can jump over another pawn to reach an empty square. Where there is a wall behind the opposing pawn this can even occur in an L shape. In the original version, this was a mess of special cases about detecting fences and working out where was legal to land.

Now, before making the move, the graph node occupied by the opposing pawn is removed. All connecting edges are re-routed to all neighbours of the removed node, creating a kind of wormhole for the pawn to jump through - while still respecting fences.

The graph is modelled as a 9^2 x 9^2 adjacency matrix with one bit per edge, meaning it’s fast to modify and cheap to clone.
In addition to all that, Dijkstra’s algorithm is now used for pathfinding via a std.PriorityQueue. It’s much faster.

For the first version - I just wanted to get something working:

A terminal UI
A legal move checker
A computer player which could pick legal moves which were at least better than random

The computer player is still basic. It assigns a score to each possible move based on how much nearer it brings the player to the goal vs how much harder it makes it for the opponent to reach the goal. It doesn’t yet look beyond the current turn, so can be beaten with a little strategy. The rules core is now possibly efficient enough to investigate better strategies.

The terminal UI has been reworked so that it looks like a traditional Quoridor board. It doesn’t quite fit in 80x24 but the old version is enabled with “–mini” on the command line.
It should now make sense if you’re familiar with the game, or watching a tutorial online.

tobyjaffey · November 29, 2024, 7:34pm

Now playable on the web Zoridor

I added a web front-end and am exposing the same zig core via WASM.