"The object of naval warfare must always be directly or indirectly either to secure the command of the sea or to prevent the enemy from securing it. The paramount concern is the control of communications, and not, as in land warfare, the conquest of territory."
— Sir Julian Corbett, Some Principles of Maritime Strategy (1911)
Description
Gale is a game of inevitable collision where every connection forged physically severs an enemy lifeline.
After the computational exhaustion of Domineering, Gale offers a different kind of challenge—one that is topological rather than combinatorial. The board consists of two overlapping phantoms: one striving North to South, the other East to West, locked within a dual graph where every move is both a bridge and a barricade.
This duality harbors an elegant truth. We no longer need to calculate millions of hypothetical futures to secure a win. Beneath the crossing wires lies a perfect, polynomial-time pairing strategy—a dual spanning tree where every cut made by the enemy dictates the exact mathematical repair required to defeat them. In Gale, one does not search for victory; one weaves a snare and waits.
History
Gale originated in the late 1950s, a remarkably fertile period for combinatorial game theory. Mathematician David Gale—later renowned for his work in economics and game theory—was fascinated by the topological properties of connection games. Specifically, he was analyzing the mathematical mechanics of Hex (the subject of Chapter 10), which had been independently invented a decade earlier by Piet Hein and John Nash.
Hex, played on a grid of hexagons, has a geometry that inherently prevents a game from ending in a draw. Gale wanted to know if this “no-draw” certainty could be translated to a standard orthogonal grid. By offsetting two standard rectangular grids—one for a vertical player and one for the horizontal player—he created a dual-graph structure where every move directly intersects exactly one potential move by the opponent. He successfully designed a game mathematically guaranteed to produce a winner—no draws, no ambiguities.
Elegant, intuitive, and highly marketable, in 1960, the Hassenfeld Brothers company (which we know today as Hasbro) released Gale commercially under the name Bridg-It. The physical board featured plastic bridges that players snapped over intersecting ravines, allowing children and families to engage in deep topological warfare without necessarily realizing they were manipulating planar graphs.
Gale was able to prove that the first player possessed a guaranteed winning strategy. He did this using a brilliant, albeit frustrating, mathematical technique known as a strategy-stealing argument. By assuming the second player has a winning strategy, Gale showed that the first player could simply play a random move, “steal” the second player’s strategy, and force a win. The proof was absolute, but it had a catch: it was an existence proof. It proved a winning strategy existed, but gave absolutely no instruction on how to compute it.
The puzzle of how to win was ultimately solved by mathematician Oliver Gross, a researcher at the RAND Corporation. Gross looked past the physical board and saw the game as a pair of interconnected graphs. He discovered that by partitioning the unplayed edges into two overlapping spanning trees, the first player could instantly pair every enemy attack with a corresponding defensive repair.
Gross’s explicit pairing strategy was a breakthrough. It demonstrated that Gale was completely solvable in polynomial time, unlike the computationally intractable Hex. Around the exact same time, Claude Shannon, the father of information theory, was formulating a generalized mathematical framework for all such network-connection games—a framework we now call the Shannon Switching Game, which we will explore in the following chapter.
Rules and Gameplay
Gale is a two-player connection game played on two interlaced grids. The players are traditionally Blue (seeking vertical connection) and Red (seeking horizontal connection). Each are restricted to drawing segments exclusively between dots of their own color.
The Board. The board consists of two offset, rectangular grids of dots. Typically, Blue’s dots form an
Legal Moves. A move consists of drawing a straight horizontal or vertical edge between two adjacent dots of the player’s color. Once a segment is drawn, it becomes a permanent fixture of the board. Since the grids overlap, a drawn segment physically blocks the opponent from drawing the corresponding intersecting segment of their color. Line segments may never cross.
Turn Order and Passing. Players alternate moves. Blue traditionally moves first. Passing is prohibited; a player must draw exactly one legal segment on their turn.
Termination and Victory. The game is finite as there are a strictly bounded number of empty spaces between dots. Play continues until one player successfully forms a continuous, unbroken path of segments connecting their two designated sides of the board (North-to-South for Blue, East-to-West for Red). The first player to complete their path wins immediately. Due to the board’s interlaced structure, a draw is impossible; one player’s victorious connection is the equivalent of their opponent’s complete blockade.
Mathematics of Gale
The Interlaced Graph Model
To analyze Gale mathematically, we must first abstract the physical board and view it as a pair of interlaced graphs. This abstraction is the key to understanding Gale’s solvability in polynomial time.
Definition (The Blue Graph).
Let
Blue’s goal is to connect the top row
Definition (The Red Graph).
Let
Red’s goal is to connect the left column
The key observation is that
Property (The Intersection Property).
For every potential edge
This duality is the heart of Gale. When Blue draws an edge
Remark.
The intersection property is what distinguishes Gale from Hex. In Hex, moves do not block opponent moves (not in the sense of Gale, anyway); they merely occupy cells. In Gale, every move carries a dual consequence.
Connection Games and the No-Draw Theorem
The rules state a simple condition for victory: that the first to connect their two designated sides wins. But what does “connect” mean in the sense of the interlaced graphs we have just defined? And why is a draw a mathematical impossibility?
Definition (Connection).
In the graph
Definition (Edge Cut).
Let
Because the graphs are interlaced, these goals are mutually exclusive in the strongest possible sense.
Theorem (No-Draw Theorem for Gale).
In any completely filled board of Gale (i.e., where for every edge
- Blue has formed a North-South connection, or
- Red has formed an East-West connection.
Proof.
The proof relies on the topological properties of planar dual graphs. Consider a completely filled board and suppose, for the sake of contradiction, that Blue has not formed a North-South connection.
Let
By the Intersection Property, every potential Blue edge that crosses this frontier could not have been drawn by Blue, and therefore its dual edge must have been drawn by Red. Since the frontier completely separates the top of the Blue graph from the bottom, this sequence of intersecting Red dual edges forms an unbroken path connecting the left side of the Red graph to the right.
This is exactly an East-West Red connection and, if Blue has not won on a completely filled board, Red must have won. Furthermore, because a North-South path and an East-West path must cross each other, and no crossing is possible without an edge and its dual being drawn simultaneously, the two conditions are mutually exclusive. Exactly one player must have won.
Strategy-Stealing: The First Player’s Advantage
The No-Draw Theorem guarantees that when Gale is played to completion it must produce a winner. However, it says nothing about which player will win, or when. David Gale himself showed that the first player always has a winning advantage. The argument is a classic example of a standard strategy-stealing argument.
Theorem (Gale’s Strategy-Stealing Theorem).
The first player (Blue) has a winning strategy in Gale. That is, there exists a strategy for Blue such that, no matter how Red plays, Blue will always be the first to complete a North-South connection.
Proof.
We proceed by contradiction, utilizing the fact that Gale is a finite, symmetric, monotonic game of perfect information without chance. By the No-Draw Theorem, Gale cannot end in a draw; therefore, exactly one player must possess a winning strategy.
Assume, for the sake of contradiction, that the second player (Red) possesses a winning strategy, which we will call
We construct a scenario where Blue “steals” strategy
Blue begins by placing a first edge,
If the edge
Crucially, Gale is a monotonic game. I.e., once an edge is placed, it cannot be moved, removed, or captured. Therefore, having an extra edge on the board (whether it is
By following this protocol, Blue is effectively executing the winning strategy
Therefore, the assumption that the second player has a winning strategy is false. Since one player must have a winning strategy, it must be the first player (Blue).
This proof tells us with absolute certainty that Blue can force a win. It does not tell us how.
The Pairing Strategy (Gross’s Construction)
The puzzle of how to win was solved by Oliver Gross, who discovered that the first player’s winning strategy can be encoded entirely in the structure of two edge-disjoint spanning trees.
A spanning tree of a graph
Gross’s key insight was that the potential edges of the Gale board can be partitioned into two edge-disjoint spanning trees—one for Blue and one for Red. We will need the following terminology.
Let
Let
We will also need the following lemma.
Lemma (Spanning Tree Duality).
Let
is a spanning tree of
Proof.
We show that
First, suppose for contradiction that
Second, suppose for contradiction that
Since
We will now need the following terminology. Let
We now give the statement of Gross’s Theorem.
Theorem (Gross’s Theorem for Gale).
Let
is a spanning tree of and contains the artificial edge , is a spanning tree of , and - Every potential edge
is paired with exactly one potential edge in . Specifically, each non-tree edge of (an edge in ) crosses exactly one tree edge of .
Furthermore, this partition yields an explicit pairing strategy that guarantees a win for the first player (Blue).
Proof.
While the raw grids
Under this augmentation, the planar dual of
By Lemma 4.1, we may select an arbitrary spanning tree
This partition defines a bijective pairing between the edges Blue needs to maintain
When Red blocks this non-tree edge, it is equivalent to Red deleting an edge from a cycle in
Blue’s winning strategy, therefore, is to immediately draw that specific restoring edge. Since Blue plays first, Blue begins by claiming the physical location corresponding to the artificial edge
For every subsequent move, Red claims an edge, which cuts
Once the two spanning trees
Let
This pairing has a crucial property: for any edge
By Lemma 4.1, the dual spanning tree
Gross realized that this partition allows for a dynamic pairing strategy. Whenever Red plays an edge, that physical location corresponds either to an edge Blue needs for
Theorem (Gross’s Explicit Winning Strategy).
Blue can force a win by playing according to the following strategy:
- Blue computes the augmented graph
and selects an arbitrary spanning tree that includes the artificial winning edge . The remaining physical locations define Red’s dual spanning tree, . - Blue’s initial move is to claim the artificial edge
. (Since cannot be physically drawn, Blue achieves this by drawing any available edge in the fundamental cut of ). - Thereafter, whenever Red draws an edge
, Red claims a physical intersection. - Case A: If
blocks a Blue edge , Red has cut Blue’s spanning tree into two components. This cut defines a fundamental cycle in Red’s tree . Blue responds by claiming the Blue dual of any other Red edge in that cycle, effectively repairing . - Case B: If
, Red is building their own tree. This move forms a fundamental cycle in . Blue responds by claiming any available Blue edge in that cycle, which simultaneously advances and blocks Red’s path.
- Case A: If
Under this strategy, Blue maintains the connectivity of
Proof.
Since
Whenever Red claims an edge, they either sever a branch of
Because Blue always plays the paired response within these fundamental cycles/cuts, Blue guarantees that
Remark.
Gross’s construction is remarkable, not only because it gives an explicit winning strategy, but because it is polynomial-time. The spanning trees can be computed in
Example of Gameplay: Applying Gross’s Strategy
To see Gross’s pairing strategy in action, consider a standard game of Gale played on a grid of
By claiming an edge, a player simultaneously builds their own path and blocks the intersecting potential edge of their opponent.
According to Gross’s constructive proof, Blue can guarantee a win by selecting an initial starting edge and then mapping the remaining potential edges into pairs using the dual spanning trees
Figure 3 illustrates this tactical exchange in the center of the board.
Blue opens with a strong central move (Move 1). Red attempts to block Blue’s Northward progress by claiming a horizontal edge (Move 2), which effectively destroys Blue’s potential vertical edge directly above. Instead of recalculating a global path, Blue relies on the pre-computed dual spanning tree and claims the paired edge (Move 3), seamlessly routing around Red’s blockade.
Calculus of Double Threats
In the theory of connection games, as explored in [WW82], a single linear path is mathematically insufficient for victory. Since the game is alternating, and due to Property 4.1, every move can act as a barrier, and any singular, unbranching threat can be trivially severed by the opponent. Victory, therefore, relies on the construction of a double threats (commonly known as forks).
Let
Theoretically, a double threat implies that the player’s subgraph has branched, creating two paths to the target boundary that are independent at their terminal steps. Since the opponent can only claim a single edge per turn, they can block
Viewed thusly, Theorem 4.3 is effectively a global, pre-computed web of double threats. By partitioning the board into mutually dual spanning trees, Gross guarantees that whenever Red plays an edge that creates a cut in Blue’s tree, that cut contains at least two critical edges: the dual edge that Red just claimed, and its paired Blue response.
Gross’s bijection, then, ensures that across every possible fundamental cut on the board, Blue is mathematically guaranteed to possess a localized double threat. If Red takes one path across the cut, the pairing ensures Blue always has a guaranteed second path to restore connectivity.
Gale in Command Line (with Lisp for game engines)
Foundational Algorithms: Dijkstra and Minimax
While Gross’s explicit spanning-tree construction provides a beautiful, polynomial-time mathematical proof for the first player’s winning advantage, implementing a dynamic engine that can play optimally as either player—and evaluate mid-game states dynamically—requires a heuristics approach. To achieve this we bridge the topological goals with two foundational search algorithms: Minimax (introduced in Chapter 4) and Dijkstra’s Algorithm.
A weighted graph is a graph
Dijkstra’s algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It maintains a set of unvisited nodes and iteratively selects the node with the smallest tentative distance, relaxing the distances to its neighbors until the shortest path to the target is found.
Now let
In adversarial pathfinding, maintaining a lower network volume quantifies board control. It indicates that a player requires fewer total edge placements to access the broader graph, therefore maintaining a higher density of branching paths and potential double threats.
In the context of Gale, we modify the traditional algorithm to evaluate the “cost” of a connection path based on the current board state. Rather than physical distance, the cost represents the number of unplayed edges a player must claim to complete a path:
- Cost 0: Edges already claimed by the evaluating player
- Cost 1: Unplayed, available edges
- Cost
: Edges blocked by the opponent’s dual edges
function shortest_path_distance(player, board_state)
dist = hash_table()
queue = empty_list()
target_reached = infinity
// Initialize starting boundary with cost 0
for each node in player.start_boundary
dist[node] = 0
queue.push(node)
while queue is not empty
curr = extract_min(queue, dist)
if curr in player.target_boundary
target_reached = min(target_reached, dist[curr])
for each edge connected to curr
neighbor = edge.other_node(curr)
if edge in player.owned_edges
cost = 0
else if edge.dual in opponent.owned_edges
cost = infinity
else
cost = 1
if cost < infinity
if dist[curr] + cost < dist[neighbor]
dist[neighbor] = dist[curr] + cost
queue.push(neighbor)
// Calculate network volume to combat horizon effect
network_volume = 0
for each node in dist
network_volume += dist[node]
return target_reached, network_volume
Remark (Network Volume and the Horizon Effect).
Returning only the shortest path distance (target_reached) exposes the AI to the horizon effect. Since the opponent can often maintain their shortest path distance by building multiple independent branches (forks), a simplistic evaluator sees all defensive moves as equally futile. By also calculating the network volume—the sum of the shortest distances to all reachable nodes—the algorithm mathematically quantifies board control. This allows the AI to break ties intelligently, and to actively suffocate the opponent’s branching paths.
Minimax Integration
As established in earlier chapters, the Minimax algorithm navigates the game tree to determine optimal adversarial moves. In our Gale implementation, a full-depth search is computationally prohibitive due to the high branching factor of a grid graph. Instead, we utilize a bounded Depth-2 Minimax search combined with our Dijkstra heuristic.
The heuristic evaluation function assigns scores based on the Dijkstra output:
- Infinite positive/negative scores for guaranteed wins/losses.
- Heavy prioritization of increasing the opponent’s shortest path (cutting off their primary connection).
- Network volume minimization to suppress the opponent’s ability to form the double threats.
Architectural Overview
Our Gale implementation (as several previous implementations) operates as an optimized, standalone Common Lisp engine, utilizing the terminal for I/O while generating dynamic vector graphics for state visualization.
- Common Lisp (SBCL): The core engine handles all computational logic, including:
- Graph generation and dual-edge coordinate mapping.
- Dijkstra shortest-path evaluations and network volume calculations.
- 2-ply Minimax decision trees for the Hard AI tier.
- Atomic rendering of the board state directly to SVG format.
- Bash/System Shell: Acts as the launcher and visual coordinator, passing board dimensions, player start toggles, and difficulty tiers as POSIX arguments to the Lisp script, while external image viewers (such as
eog) handle live-updating the SVG output.
This architecture leverages Common Lisp’s exceptional execution speed for deeply nested graph traversals, easily evaluating thousands of Dijkstra simulations per turn in a fraction of a second, without the need for external C-bindings.
#!/bin/bash
cd "$(dirname "$0")" || exit 1
# ANSI Color Codes
BLUE='\033[1;34m'
RED='\033[1;31m'
GREEN='\033[1;32m'
YELLOW='\033[1;33m'
CYAN='\033[1;36m'
NC='\033[0m' # No Color
# Initial State
BOARD_SIZE=4 # Represents a 4x5 Blue grid / 5x4 Red grid
BOARD_LABEL="4x5"
DIFFICULTY="Hard"
STRATEGY="Gross's Pairing"
PLAYER_TURN="First" # options: First, Second, Random
# clear screen function
clear_screen() {
printf "\033c"
}
# print the header
print_header() {
echo -e "${CYAN}=========================================${NC}"
echo -e "${CYAN} G A L E ${NC}"
echo -e "${CYAN}=========================================${NC}"
echo -e "Board Size: ${YELLOW}${BOARD_LABEL}${NC} | Difficulty: ${YELLOW}${DIFFICULTY}${NC} (${STRATEGY})"
echo -e "Human Plays: ${YELLOW}${PLAYER_TURN}${NC}"
echo -e "${CYAN}-----------------------------------------${NC}"
}
# launch game
start_game() {
clear_screen
echo -e "${GREEN}Initializing Lisp Engine...${NC}"
echo -e "Starting ${BOARD_LABEL} board using ${STRATEGY}."
echo -e "Watch the eog window for the board state!\n"
# touch SVG file so eog can open immediately
rm -f current_gale_board.svg
touch current_gale_board.svg
# launch eog in background. (eog auto-reloads when file changes)
eog current_gale_board.svg > eog_error.log 2>&1 &
EOG_PID=$!
# translate ACTUAL_TURN string into numeric human player ID
# 1 = Blue (First/North-South), 2 = Red (Second/East-West)
HUMAN_PLAYER=1
if [ "$ACTUAL_TURN" == "Second" ]; then
HUMAN_PLAYER=2
fi
# translate DIFFICULTY string to numeric ID
DIFF_NUM=3
if [ "$DIFFICULTY" == "Easy" ]; then DIFF_NUM=1; fi
if [ "$DIFFICULTY" == "Medium" ]; then DIFF_NUM=2; fi
# Blue (Player 1) ALWAYS makes first move
START_PLAYER=1
# pass control to Lisp engine
echo -e "${YELLOW}Enter your moves by specifying two adjacent nodes (e.g., B2 B3).${NC}"
echo -e "${YELLOW}Press Ctrl+D if you wish to exit early.${NC}\n"
# pass ALL 4 arguments to Lisp engine
sbcl --script gale-engine.lisp $BOARD_SIZE $START_PLAYER $DIFF_NUM $HUMAN_PLAYER 2> engine_error.log
echo -e "\n${GREEN}Game Over!${NC}"
# Pause and wait for user to hit Enter BEFORE killing eog
read -p "Press Enter to return to the main menu..."
# Now that user pressed Enter, kill eog viewer
kill $EOG_PID 2>/dev/null
}
# main menu loop
while true; do
clear_screen
print_header
echo "1) Start Game"
echo "2) Set Board Size"
echo "3) Set Difficulty"
echo "4) Set Player Turn"
echo "5) Exit"
echo -e "${CYAN}-----------------------------------------${NC}"
read -p "Select an option [1-5]: " choice
case $choice in
1)
# handle random coin flip right before start
ACTUAL_TURN=$PLAYER_TURN
if [ "$ACTUAL_TURN" == "Random" ]; then
if [ $((RANDOM % 2)) -eq 0 ]; then
ACTUAL_TURN="First"
else
ACTUAL_TURN="Second"
fi
echo -e "${GREEN}Random selection: You are going ${ACTUAL_TURN}!${NC}"
sleep 2
fi
# pass $ACTUAL_TURN to start_game function/Lisp engine here
start_game
;;
2)
echo -e "\n${YELLOW}Select Board Size:${NC}"
echo "1) 4x5 (Standard - From Chapter Example)"
echo "2) 5x6 (Advanced)"
echo "3) 7x8 (Tournament)"
read -p "Choice [1-3]: " size_choice
case $size_choice in
1) BOARD_SIZE=4; BOARD_LABEL="4x5" ;;
2) BOARD_SIZE=5; BOARD_LABEL="5x6" ;;
3) BOARD_SIZE=7; BOARD_LABEL="7x8" ;;
esac
;;
3)
echo -e "\n${YELLOW}Select Difficulty:${NC}"
echo "1) Easy (Random Moves)"
echo "2) Medium (Greedy Connection)"
echo "3) Hard (Gross's Pairing Strategy)"
read -p "Choice [1-3]: " diff_choice
case $diff_choice in
1) DIFFICULTY="Easy"; STRATEGY="Random" ;;
2) DIFFICULTY="Medium"; STRATEGY="Greedy" ;;
3) DIFFICULTY="Hard"; STRATEGY="Gross's Pairing" ;;
esac
;;
4)
echo -e "\n${YELLOW}Select Who Goes First:${NC}"
echo "1) Human goes First (Blue / North-South)"
echo "2) Human goes Second (Red / East-West)"
echo "3) Randomize"
read -p "Choice [1-3]: " turn_choice
case $turn_choice in
1) PLAYER_TURN="First" ;;
2) PLAYER_TURN="Second" ;;
3) PLAYER_TURN="Random" ;;
esac
;;
5)
echo -e "${GREEN}Exiting. Goodbye!${NC}"
exit 0
;;
*)
echo -e "${RED}Invalid option.${NC}"
sleep 1
;;
esac
done
AI Engine (Common Lisp)
The Lisp component handles game flow, state managemant, the building of boards, and the strategic AI using Minimax and Dijkstra algorithms.
;;; gale-engine.lisp
;;; run with: sbcl --script gale-engine.lisp [SIZE] [START] [DIFF] [HUMAN]
(setf *random-state* (make-random-state t)) ; Seed RNG for AI
(defparameter *cell-size* 70)
(defparameter *offset-x* 80)
(defparameter *offset-y* 80)
(defparameter *board-size* 4)
(defparameter *current-player* 1)
(defparameter *difficulty-level* 3) ; 1=Easy, 2=Med, 3=Hard (Defaulted to Hard)
(defparameter *human-player* 1) ; 1 = Blue, 2 = Red
;; edges stored as lists of two coordinate pairs: '((c1 r1) (c2 r2))
(defparameter *blue-edges* nil)
(defparameter *red-edges* nil)
;;; --- Helper Formatting ---
(defun node-to-str (node)
"Converts internal coords (0 0) to 'A1'"
(format nil "~A~A" (code-char (+ (char-code #\A) (first node))) (1+ (second node))))
(defun format-edge-str (edge)
"Converts '((0 0) (0 1)) to 'A1 A2'"
(format nil "~A ~A" (node-to-str (first edge)) (node-to-str (second edge))))
;;; --- Coordinate Geometry ---
(defun blue-node-xy (c r)
"Returns (values X Y) for Blue node. c: 0 to N-1, r: 0 to N"
(values (+ *offset-x* (* c *cell-size*))
(+ *offset-y* (* r *cell-size*))))
(defun red-node-xy (c r)
"Returns (values X Y) for Red node. Interlaced by a half cell. c: 0 to N, r: 0 to N-1"
(values (+ *offset-x* (* (- c 0.5) *cell-size*))
(+ *offset-y* (* (+ r 0.5) *cell-size*))))
;;; --- SVG Rendering ---
(defun draw-svg-board (filename &optional game-over-msg)
"Builds interlaced board SVG and atomically writes it"
(let* ((width (+ (* *offset-x* 2) (* *board-size* *cell-size*)))
(height (+ (* *offset-y* 2) (* *board-size* *cell-size*)))
(temp-filename (concatenate 'string filename ".tmp"))
(svg-data
(with-output-to-string (stream)
(format stream "<svg xmlns='http://www.w3.org/2000/svg' width='~A' height='~A'>~%" width height)
(format stream "<style>text { font-family: monospace; font-size: 18px; text-anchor: middle; dominant-baseline: middle; font-weight: bold; }</style>~%")
(format stream "<rect width='100%' height='100%' fill='#f4f4f9'/>~%")
;; 1. Draw edges
(dolist (edge *blue-edges*)
(multiple-value-bind (x1 y1) (blue-node-xy (first (first edge)) (second (first edge)))
(multiple-value-bind (x2 y2) (blue-node-xy (first (second edge)) (second (second edge)))
(format stream "<line x1='~A' y1='~A' x2='~A' y2='~A' stroke='#4a4add' stroke-width='8' stroke-linecap='round'/>~%" x1 y1 x2 y2))))
(dolist (edge *red-edges*)
(multiple-value-bind (x1 y1) (red-node-xy (first (first edge)) (second (first edge)))
(multiple-value-bind (x2 y2) (red-node-xy (first (second edge)) (second (second edge)))
(format stream "<line x1='~A' y1='~A' x2='~A' y2='~A' stroke='#dd4a4a' stroke-width='8' stroke-linecap='round'/>~%" x1 y1 x2 y2))))
;; 2. Draw blue nodes
(dotimes (c *board-size*)
(dotimes (r (1+ *board-size*))
(multiple-value-bind (x y) (blue-node-xy c r)
(format stream "<circle cx='~A' cy='~A' r='7' fill='#1e1e8c'/>~%" x y))))
;; 3. Draw red nodes
(dotimes (c (1+ *board-size*))
(dotimes (r *board-size*)
(multiple-value-bind (x y) (red-node-xy c r)
(format stream "<circle cx='~A' cy='~A' r='7' fill='#8c1e1e'/>~%" x y))))
;; 4. Draw labels (for human only)
(if (= *human-player* 1)
(progn
;; Blue labels (uppercase top, numbers left)
(dotimes (c *board-size*)
(multiple-value-bind (x y) (blue-node-xy c 0)
(format stream "<text x='~A' y='~A' fill='#1e1e8c'>~A</text>~%" x (- y 30) (code-char (+ (char-code #\A) c)))))
(dotimes (r (1+ *board-size*))
(multiple-value-bind (x y) (blue-node-xy 0 r)
(format stream "<text x='~A' y='~A' fill='#1e1e8c'>~A</text>~%" (- x 55) y (1+ r)))))
(progn
;; Red labels (Uppercase bottom, numbers right)
(dotimes (c (1+ *board-size*))
(multiple-value-bind (x y) (red-node-xy c (1- *board-size*))
(format stream "<text x='~A' y='~A' fill='#8c1e1e'>~A</text>~%" x (+ y 65) (code-char (+ (char-code #\A) c)))))
(dotimes (r *board-size*)
(multiple-value-bind (x y) (red-node-xy *board-size* r)
(format stream "<text x='~A' y='~A' fill='#8c1e1e'>~A</text>~%" (+ x 30) y (1+ r))))))
(when game-over-msg
(let ((box-w 300) (box-h 60))
(format stream "<rect x='~A' y='~A' width='~A' height='~A' fill='black' opacity='0.85' rx='8'/>~%"
(- (/ width 2) (/ box-w 2)) (- (/ height 2) (/ box-h 2)) box-w box-h)
(format stream "<text x='~A' y='~A' font-size='22' fill='white'>~A</text>~%"
(/ width 2) (+ (/ height 2) 2) game-over-msg)))
(format stream "</svg>~%"))))
(with-open-file (out temp-filename :direction :output :if-exists :supersede :if-does-not-exist :create)
(write-string svg-data out))
(rename-file temp-filename filename)))
;;; --- Game Logic & Validation ---
(defun sort-edge (n1 n2)
"Ensures edges are always read left-to-right or top-to-bottom"
(if (or (< (first n1) (first n2))
(and (= (first n1) (first n2)) (< (second n1) (second n2))))
(list n1 n2)
(list n2 n1)))
(defun parse-node (str)
"Converts 'A1' into (0 0). Returns NIL if input is malformed."
(let ((clean (string-trim " " (string-upcase str))))
(when (>= (length clean) 2)
(let* ((col (- (char-code (char clean 0)) (char-code #\A)))
(row-num (parse-integer (subseq clean 1) :junk-allowed t)))
(when row-num
(list col (1- row-num)))))))
(defun all-possible-edges (player)
"Generates every possible valid board edge for given player"
(let ((edges nil))
(if (= player 1)
(progn
(dotimes (c (1- *board-size*)) (dotimes (r (1+ *board-size*))
(push (list (list c r) (list (1+ c) r)) edges))) ; blue horiz
(dotimes (c *board-size*) (dotimes (r *board-size*)
(push (list (list c r) (list c (1+ r))) edges)))) ; blue vert
(progn
(dotimes (c *board-size*) (dotimes (r *board-size*)
(push (list (list c r) (list (1+ c) r)) edges))) ; red horiz
(dotimes (c (1+ *board-size*)) (dotimes (r (1- *board-size*))
(push (list (list c r) (list c (1+ r))) edges))))) ; red vert
edges))
(defun crossing-edge (edge player)
"Returns exact opponent edge that would block this edge"
(let* ((n1 (first edge)) (n2 (second edge))
(c1 (first n1)) (r1 (second n1))
(c2 (first n2)) (r2 (second n2)))
(if (= player 1)
(if (= r1 r2) (list (list c2 (1- r1)) (list c2 r1)) ; blue horiz crossed by red vert
(list (list c1 r1) (list (1+ c1) r1))) ; blue vert crossed by red horiz
(if (= r1 r2) (list (list c1 r1) (list c1 (1+ r1))) ; red horiz crossed by blue vert
(list (list (1- c1) r2) (list c1 r2)))))) ; red vert crossed by blue horiz
(defun edge-equal (e1 e2)
(and (equal (first e1) (first e2)) (equal (second e1) (second e2))))
(defun contains-edge (edge-list edge)
(member edge edge-list :test #'edge-equal))
(defun legal-move-p (edge player)
"Validates boundaries, previous plays, and planar crossings"
(let ((all (all-possible-edges player)))
(when (contains-edge all edge)
(unless (contains-edge (if (= player 1) *blue-edges* *red-edges*) edge)
(let ((cross (crossing-edge edge player)))
(if (= player 1)
(not (contains-edge *red-edges* cross))
(not (contains-edge *blue-edges* cross))))))))
;;; --- Win Detection (BFS Pathfinding) ---
(defun check-win (player)
"Traverses connected edges via BFS to detect full bank-to-bank connection"
(let ((edges (if (= player 1) *blue-edges* *red-edges*))
(visited nil)
(queue nil))
;; Gather starting nodes at top (blue) or left (red) boundary
(dolist (edge edges)
(dolist (node edge)
(let ((c (first node)) (r (second node)))
(if (= player 1)
(when (= r 0) (pushnew node queue :test #'equal))
(when (= c 0) (pushnew node queue :test #'equal))))))
;; BFS traversal
(loop while queue do
(let ((curr (pop queue)))
(unless (member curr visited :test #'equal)
(push curr visited)
;; Check if reached bottom (blue) or right (red) boundary
(if (= player 1)
(when (= (second curr) *board-size*) (return-from check-win t))
(when (= (first curr) *board-size*) (return-from check-win t)))
;; Add adjacent connected nodes
(dolist (edge edges)
(cond
((equal curr (first edge)) (push (second edge) queue))
((equal curr (second edge)) (push (first edge) queue)))))))
nil))
;;; --- AI Algorithms ---
(defun shortest-path-distance (player)
"Calculate minimum unplayed edges needed to complete a winning path (Dijkstra)"
(let ((queue nil)
(dist (make-hash-table :test #'equal))
(target-reached 999)
(all-edges (all-possible-edges player)))
;; Initialize start boundaries (Cost 0)
(if (= player 1)
(dotimes (c *board-size*)
(setf (gethash (list c 0) dist) 0)
(push (list c 0) queue))
(dotimes (r *board-size*)
(setf (gethash (list 0 r) dist) 0)
(push (list 0 r) queue)))
(loop while queue do
;; Pop node with minimum distance
(let ((curr nil) (min-d 9999))
(dolist (node queue)
(when (< (gethash node dist) min-d)
(setf min-d (gethash node dist))
(setf curr node)))
(setf queue (remove curr queue :test #'equal :count 1))
(let ((d (gethash curr dist)))
;; Check if reached target boundary
(if (= player 1)
(when (= (second curr) *board-size*) (setf target-reached (min target-reached d)))
(when (= (first curr) *board-size*) (setf target-reached (min target-reached d))))
(dolist (edge all-edges)
(let ((n1 (first edge)) (n2 (second edge)))
(when (or (equal curr n1) (equal curr n2))
(let* ((neighbor (if (equal curr n1) n2 n1))
(cross (crossing-edge edge player))
(blocked (if (= player 1)
(contains-edge *red-edges* cross)
(contains-edge *blue-edges* cross)))
(owned (if (= player 1)
(contains-edge *blue-edges* edge)
(contains-edge *red-edges* edge)))
;; 0 if owned, 999 if blocked, 1 if open
(cost (cond (owned 0) (blocked 999) (t 1)))
(new-d (+ d cost)))
(when (< cost 999)
(let ((old-d (gethash neighbor dist)))
(when (or (null old-d) (< new-d old-d))
(setf (gethash neighbor dist) new-d)
(unless (member neighbor queue :test #'equal)
(push neighbor queue))))))))))))
;; Calculate total network volume
(let ((total-dist 0)
(total-nodes (* *board-size* (1+ *board-size*))))
(maphash (lambda (k v)
(declare (ignore k))
(when (< v 999) (incf total-dist v)))
dist)
;; Massive penalty for allowing nodes to be walled off
(let ((unreachable (- total-nodes (hash-table-count dist))))
(incf total-dist (* unreachable 100)))
(values target-reached total-dist))))
(defun get-legal-moves (player)
(let ((moves nil) (all (all-possible-edges player)))
(dolist (edge all)
(when (legal-move-p edge player) (push edge moves)))
moves))
(defun opponent-winning-move (player)
(let* ((opp (if (= player 1) 2 1))
(moves (get-legal-moves opp)))
(dolist (m moves nil)
(if (= opp 1) (push m *blue-edges*) (push m *red-edges*))
(let ((win (check-win opp)))
(if (= opp 1) (pop *blue-edges*) (pop *red-edges*))
(when win (return m))))))
(defun ai-easy-move (player)
(let* ((moves (get-legal-moves player))
(my-edges (if (= player 1) *blue-edges* *red-edges*))
(opp (if (= player 1) 2 1))
(opp-win (opponent-winning-move player))
(greedy-moves nil))
(when moves
;; Block immediate win
(when opp-win
(let ((block (crossing-edge opp-win opp)))
(when (and block (legal-move-p block player))
(return-from ai-easy-move block))))
;; Greedy
(dolist (m moves)
(let ((n1 (first m)) (n2 (second m)))
(when (loop for e in my-edges
thereis (or (equal n1 (first e)) (equal n1 (second e))
(equal n2 (first e)) (equal n2 (second e))))
(push m greedy-moves))))
(if greedy-moves
(nth (random (length greedy-moves)) greedy-moves)
(nth (random (length moves)) moves)))))
(defun ai-medium-move (player)
"Greedy connection with blocking and directional progress"
(let* ((moves (get-legal-moves player))
(my-edges (if (= player 1) *blue-edges* *red-edges*))
(opp (if (= player 1) 2 1))
(opp-win (opponent-winning-move player))
(best-moves nil) ; moves that both connect AND make progress
(greedy-moves nil) ; moves that connect but no special progress
(fresh-moves nil)) ; moves that don't connect to anything yet
(unless moves
(return-from ai-medium-move nil))
;; 1. Block opponent's immediate win
(when opp-win
(let ((block (crossing-edge opp-win opp)))
(when (and block (legal-move-p block player))
(return-from ai-medium-move block))))
;; 2. Find frontier - how close to our goal
(let ((max-progress 0))
;; Determine furthest progress toward the goal side
(dolist (edge my-edges)
(dolist (node edge)
(let ((progress (if (= player 1)
(second node) ; Blue: row number = north-south progress
(first node)))) ; Red: column number = east-west progress
(when (> progress max-progress)
(setf max-progress progress)))))
;; 3. Categorize moves
(dolist (m moves)
(let* ((n1 (first m))
(n2 (second m))
(connects (loop for e in my-edges
thereis (or (equal n1 (first e)) (equal n1 (second e))
(equal n2 (first e)) (equal n2 (second e)))))
;; How far this move reaches toward goal?
(progress1 (if (= player 1) (second n1) (first n1)))
(progress2 (if (= player 1) (second n2) (first n2)))
(move-progress (max progress1 progress2)))
(cond
;; BEST: connects AND extends frontier
((and connects (> move-progress max-progress))
(push (cons move-progress m) best-moves))
;; GOOD: connects to existing edges (maintains connectivity)
(connects
(push m greedy-moves))
;; OK: fresh start (maybe near the starting side)
(t
(push m fresh-moves))))))
;; 4. Pick best available move
(cond
;; Prefer moves that extend frontier, pick the one that goes furthest
(best-moves
(setf best-moves (sort best-moves #'> :key #'car))
(cdr (first best-moves)))
;; Otherwise connect to existing edges
(greedy-moves
(nth (random (length greedy-moves)) greedy-moves))
;; If no connections exist yet, start near the beginning side
(fresh-moves
(let ((starter-moves nil))
(dolist (m fresh-moves)
(let* ((n1 (first m))
(n2 (second m))
(min-progress (if (= player 1)
(min (second n1) (second n2))
(min (first n1) (first n2)))))
;; Blue: prefer low row numbers (top), Red: prefer low col numbers (left)
(when (= min-progress 0)
(push m starter-moves))))
(if starter-moves
(nth (random (length starter-moves)) starter-moves)
(nth (random (length fresh-moves)) fresh-moves)))))))
(defun evaluate-board (player opp)
"Calculate heuristic score. Prioritize shortest path, use network volume to break ties"
(multiple-value-bind (my-target my-total) (shortest-path-distance player)
(multiple-value-bind (opp-target opp-total) (shortest-path-distance opp)
(cond ((= my-target 0) 10000000) ; We won
((= opp-target 0) -10000000) ; They won
(t
;; Prioritize choking opponent path (500k) over advancing ours (250k).
;; Network totals act as tie-breakers to avoid horizon effect.
(+ (* opp-target 500000)
(- (* my-target 250000))
opp-total
(- my-total)))))))
(defun ai-hard-move (player)
"Minimax Depth 2: maximizes AI score while minimizing human best response score"
(let ((best-move nil)
(best-score -99999999)
(moves (get-legal-moves player))
(opp (if (= player 1) 2 1)))
(dolist (m moves)
;; 1. Simulate AI move
(if (= player 1) (push m *blue-edges*) (push m *red-edges*))
;; Did this move instantly win the game?
(multiple-value-bind (my-t my-tot) (shortest-path-distance player)
(declare (ignore my-tot))
(if (= my-t 0)
(progn
(if (= player 1) (pop *blue-edges*) (pop *red-edges*))
(return-from ai-hard-move m))
;; 2. Simulate all human responses
(let ((min-score 99999999)
(opp-moves (get-legal-moves opp)))
(if (null opp-moves)
(setf min-score (evaluate-board player opp))
(dolist (om opp-moves)
(if (= opp 1) (push om *blue-edges*) (push om *red-edges*))
(let ((score (evaluate-board player opp)))
(when (< score min-score)
(setf min-score score)))
(if (= opp 1) (pop *blue-edges*) (pop *red-edges*))))
;; 3. Keep move that leaves human with worst best-response
(when (> min-score best-score)
(setf best-score min-score)
(setf best-move m)))))
;; Backtrack AI's move
(if (= player 1) (pop *blue-edges*) (pop *red-edges*)))
(or best-move (ai-medium-move player))))
;;; --- Game Loop (REPL) ---
(defun apply-move (edge player)
"Apply edge, check for victory, switch turn"
(setf *last-move* edge)
(if (= player 1)
(push edge *blue-edges*)
(push edge *red-edges*))
(if (check-win player)
(let ((msg (if (= player 1) "Blue Wins!" "Red Wins!")))
(draw-svg-board "current_gale_board.svg" msg)
(format t "~%========================================~%")
(format t " GAME OVER! ~A ~%" msg)
(format t "========================================~%")
t) ; signals game over
(progn
(draw-svg-board "current_gale_board.svg")
(setf *current-player* (if (= player 1) 2 1))
nil)))
(defun game-loop ()
(loop
(if (= *current-player* *human-player*)
;; human turn
(progn
(format t "~%Your turn! Enter move (e.g., A1 A2) > ")
(force-output)
(let ((input (read-line *standard-input* nil :eof)))
(when (eq input :eof) (return))
(let* ((trimmed (string-trim " " input))
(space-pos (position #\Space trimmed)))
(if space-pos
(let* ((n1 (parse-node (subseq trimmed 0 space-pos)))
(n2 (parse-node (subseq trimmed (1+ space-pos)))))
;; Ensure both nodes parsed successfully before proceeding
(if (and n1 n2)
(let ((edge (sort-edge n1 n2)))
(if (legal-move-p edge *current-player*)
(when (apply-move edge *current-player*)
(return)) ; end game loop on win
(format t "Illegal move! It may be blocked, out of bounds, or not adjacent.~%")))
(format t "Invalid coordinate format! Please use LetterNumber (e.g., A1 A2).~%")))
(format t "Error: Type two coordinates separated by a space.~%")))))
;; AI turn
(progn
(format t "~%AI is thinking...~%")
(sleep 0.75)
(let ((move (case *difficulty-level*
(1 (ai-easy-move *current-player*))
(3 (ai-hard-move *current-player*))
(otherwise (ai-medium-move *current-player*)))))
(if move
(progn
(format t "AI plays: ~A~%" (format-edge-str move))
(when (apply-move move *current-player*)
(return)))
(progn
(format t "AI has no valid moves! Board is full.~%")
(return))))))))
;;; --- Main Execution ---
(let ((args (cdr sb-ext:*posix-argv*)))
(when (>= (length args) 4)
(setf *board-size* (parse-integer (first args)))
(setf *current-player* (parse-integer (second args)))
(setf *difficulty-level* (parse-integer (third args)))
(setf *human-player* (parse-integer (fourth args)))))
(draw-svg-board "current_gale_board.svg")
(game-loop)
References:
- Berlekamp, E. R., Conway, J. H., and Guy, R. K. (1982). Winning Ways for your Mathematical Plays, volumes 1 and 2. Academic Press, London.
- Gardner, M. (1958). Mathematical Games: Four mathematical diversions involving concepts of topology. Scientific American, 199(4):124–129.
- Lehman, A. (1964). A Solution of the Shannon Switching Game. Journal of the Society for Industrial and Applied Mathematics, 12(4):687–725.