Building AI for Quoridor board game using graph representation in Prolog

Other Questions ai employee
1

I’m working on developing an AI system for Quoridor as part of my coursework. My approach involves modeling the game board as an undirected graph structure to make pathfinding calculations more efficient.

My current challenge

I want to convert the 9x9 Quoridor board into a graph where each square becomes a node connected to its neighbors. This would help me calculate the shortest routes for players to reach their goals. However, I’m struggling with implementing such a large graph structure in Prolog.

What I’ve tried

I know how to create basic graphs with a few connections like this:

connection(a,b).
connection(b,a).
connection(a,d).
connection(d,a).
connection(b,c).
connection(c,b).
connection(c,e).
connection(e,c).
connection(e,f).
connection(f,e).

But defining all 81 squares and their relationships manually seems overwhelming. I’m looking for a more elegant way to represent this board structure in Prolog so I can later implement a MiniMax algorithm for the AI decision making.

Any suggestions on how to handle such a complex graph representation efficiently?

2

you could also use position encoding like pos(Row,Col) and generate connections on the fly. something like valid_move(pos(R1,C1), pos(R2,C2)) - just check if positions are adjacent and no wall’s blocking. way cleaner than hardcoding everything, plus easier to debug when you add minimax later.

3

Been there with similar projects. Don’t hardcode all the connections - generate them programmatically instead.

For a 9x9 board, use coordinates like (X,Y) where X and Y are 1-9. Then create a rule for valid connections:

connected(X1,Y1, X2,Y2) :-
    adjacent(X1,Y1, X2,Y2),
    not(wall_between(X1,Y1, X2,Y2)).

adjacent(X1,Y1, X2,Y2) :-
    X2 is X1+1, Y2 = Y1, X2 =< 9.
adjacent(X1,Y1, X2,Y2) :-
    X2 is X1-1, Y2 = Y1, X2 >= 1.
adjacent(X1,Y1, X2,Y2) :-
    Y2 is Y1+1, X2 = X1, Y2 =< 9.
adjacent(X1,Y1, X2,Y2) :-
    Y2 is Y1-1, X2 = X1, Y2 >= 1.

The wall_between/4 predicate tracks placed walls. Start with it always failing (no walls), then add walls as they’re placed during gameplay.

This scales way better than static facts. I used something similar for pathfinding and it handled dynamic obstacles much cleaner than updating hundreds of connection facts.

For MiniMax later, you’ll want to cache shortest path calculations since they’re expensive. But get the basic representation working first.