An interactive demo

BFIDA*.

Ever since I was young, I remember a 37-hole peg solitaire board tucked away in the drawer of my grandma's couch table -- a small wooden board covered in cool glass marbles, with the one in the middle always missing. I'd jump marble over marble, watch the pile shrink, and try to leave just one in the center. To this day I have never managed it. Turns out the 37-hole European board, with a center-empty start, has no single-peg-in-the-center solution at all - a 3-colour parity argument proves it - so my younger self was chasing the impossible. This page is my second attempt.

Peg solitaire turns out to be a beloved playground for classical AI heuristic search. The algorithm that powers the demo below, Bidirectional Breadth-First Iterative Deepening A*, sits on a lineage that goes back to A* (1968), Korf's IDA* (1985), and Zhou and Hansen's breadth-first heuristic search (2006) - foundational symbolic-AI work from the era before deep learning ate the world. In 2012 Barker and Korf combined them into a bidirectional variant that solves a board in seconds where previous state-of-the-art took an hour.

Barker and Korf (2012), "Solving Peg Solitaire with Bidirectional BFIDA*" - AAAI 2012. The board layouts, pseudocode, and pruning ideas in the visualizer below all come from this paper.

Play it Watch the algorithm

Play it.

Click a marble to select it, then click an empty hole two cells away to jump. The jumped-over marble is removed. Try to leave just one.

Pegs remaining

started with 32

Moves

Watch the algorithm.

Step through a canonical optimal solution. The pseudocode panel lights up the lines of Bidirectional BFIDA* that drive each decision.

Visualization driven by a published optimal solution (Bergholt 1912, 31 jumps). Full BFIDA* on these boards won't run in a browser - this is the algorithm's shape, not its literal compute.

Speed1.00x

Step 1 / 64Jump — / 31

Considered jumps

Bidirectional BFIDA*

1procedure Bidirectional_BFIDA*(start, goal):
2  OPEN_F  ← { start }   ; g_F(start) ← 0
3  OPEN_B  ← { goal }    ; g_B(goal)  ← 0
4  bound_F ← h_F(start)  ; bound_B ← h_B(goal)
5  UB      ← ∞          ; bestPath ← null
6  repeat
7    dir ← SelectDirection(OPEN_F, OPEN_B)
8    if dir = FORWARD then
9      bound_F ← ExpandContour(F, B)
10    else
11      bound_B ← ExpandContour(B, F)
12  until UB ≤ max(bound_F, bound_B)
13  return bestPath
14 
15procedure ExpandContour(OPEN, OPPOSITE):
16  nextBound ← ∞ ;  NEW_OPEN ← ∅
17  for each node in OPEN do
18    f ← g(node) + h(node)
19    if f > bound then
20      nextBound ← min(nextBound, f) ;  continue
21    if PagodaFail(node) or PegTypeFail(node) then
22      continue
23    if node ∈ OPPOSITE then
24      pathCost ← g(node) + g_opp(node)
25      if pathCost < UB then
26        UB ← pathCost ; bestPath ← Reconstruct(node)
27      continue
28    for each child in Successors(node) do
29      g(child) ← g(node) + cost(node, child)
30      NEW_OPEN.add(child)
31  OPEN ← NEW_OPEN
32  return nextBound

Search state

Directionforward ->

Cutoff18

f = g + h18 = 0 + 18

Nodes expanded0

Frontier ->1

<- Frontier1