DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

Quoridor Has One Rule That Turns Move Legality Into a Graph Search

#javascript #algorithms #gamedev #programming

Most board games check a move with a lookup. Quoridor cannot.

You may place a wall almost anywhere. The exception is the whole game: a wall is illegal if it leaves either player with no path at all to their goal row. You may block. You may never seal.

That single sentence means legality is not a table. It is a breadth-first search, run on the board as it would be after the wall goes down, once per player.

function isWallLegal(state, wall){
  if (conflicts(state, wall)) return false;      // crossing / overlapping
  const after = withWall(state, wall);           // remove the 2 edges
  return pathLength(after, TOP) !== null &&      // both players, or nothing
         pathLength(after, BOTTOM) !== null;
}
Enter fullscreen mode Exit fullscreen mode

Live, computed while you play: https://dev48.infy.uk/game/day64-quoridor.html

A wall is an edge deletion, not a picture

The cleanest way to hold the board is as an explicit adjacency structure over 81 cells. A wall spans two cells' worth of gap, so placing one deletes exactly two parallel edges:

function withWall(state, { r, c, orient }){
  const g = cloneGraph(state.graph);
  if (orient === 'H'){
    cut(g, cell(r, c),     cell(r + 1, c));
    cut(g, cell(r, c + 1), cell(r + 1, c + 1));
  } else {
    cut(g, cell(r, c),     cell(r, c + 1));
    cut(g, cell(r + 1, c), cell(r + 1, c + 1));
  }
  return { ...state, graph: g };
}
Enter fullscreen mode Exit fullscreen mode

Once the wall is an edge deletion, everything else in the rulebook is a query on the graph. Shortest path drives the display, the AI evaluation, and the legality test — the same function, three times, so they cannot disagree.

Two checks, because I do not trust one

The interesting part of a rule like this is not implementing it. It is proving you implemented it.

Check one — differential. The page enumerates all 128 candidate wall placements on the opening board and scores each with the BFS, then re-scores it with an independently written flood fill that shares no code with the first. 0 disagreements, and 0 of the 128 would seal (correct — you cannot seal on move one).

Check two — by construction. The invariant is not "no wall seals on the opening board", it is "no legal position ever has a sealed player". So the page plays 400 random legal games, and after every single ply asserts that both players still have a path:

400 games, 59,191 plies, 0 sealed positions, 101 games reached a goal row
Enter fullscreen mode Exit fullscreen mode

59,191 opportunities for the rule to be wrong. That number is worth more than the 128.

The jump rule is where implementations quietly differ

Pawns face to face: you jump straight over. Everyone gets that part.

The part people get wrong is the diagonal. The two diagonal moves are not an alternative you may choose — they unlock only when the straight jump is blocked, by a wall or by the edge of the board:

function jumpMoves(state, me, them){
  if (!adjacent(state, me, them)) return [];
  const behind = beyond(me, them);
  if (onBoard(behind) && connected(state, them, behind))
    return [behind];                       // straight jump available -> ONLY that
  return diagonals(state, me, them);       // otherwise, and only otherwise
}
Enter fullscreen mode Exit fullscreen mode

Offer both and you have written a different, easier game. The move generator on the page was checked over 1,232 generated moves against the legality test — 0 illegal.

The evaluation is the same BFS 

const evaluate = (s, side) => dist(s, other(side)) - dist(s, side);
Enter fullscreen mode Exit fullscreen mode

Symmetric board evaluates to exactly 0. Move closer and it rises. Flip the side and the sign flips. Three assertions, and they catch the classic sign bug immediately.

There is a strategic consequence hiding in that one-liner: walls are worth placing only when they cost the opponent more distance than they cost you. Run out of walls and the move list collapses to pawn moves — which the page shows directly, because the generator is the same code either way.

What I would keep

Rules that require reachability are rare and worth recognising when you meet one. When you do, the payoff is that the rule, the display and the AI can all be one function — and the way to trust it is not to read it but to run tens of thousands of plies through it and assert the invariant on every one.

Part of a from-scratch series — one page a day, all vanilla JS, one file, offline: https://dev48.infy.uk/gamefromzero.php

Top comments (0)