Introduction

Many families know Geography from long car rides. The first player names a place, say Lima. The next player must name a place that starts with the last letter of the previous one: Athens, then Seoul, then Lagos. No place may be named twice, and a player who cannot continue loses. (The same idea appears in Japan as shiritori, where the next word must begin with the last syllable of the previous one.)

Draw each place as a vertex and put an arrow from u to v whenever the last letter of u is the first letter of v. The game is now a token on a directed graph: players alternate moving the token along an arrow to a vertex that has never held it, and the player who has no legal move loses. This is generalized geography, and nothing in the definition requires the graph to come from words. Any directed graph is allowed.

There are two natural variants. In vertex geography a vertex may be visited at most once; in edge geography an edge may be used at most once. In both, one player wins with perfect play, so the question is purely algorithmic: given the graph and the starting vertex, who wins?

The answer is surprising. For small graphs you can search exhaustively, but in general no fast method is known, and the problem is PSPACE-complete: as hard as any problem that a computer can solve using a polynomial amount of memory. A word game for children sits at the same level as deciding the winner of generalized Hex positions and as evaluating quantified Boolean formulas (QBF and PSPACE).

Play Against the Computer

Pick a graph and move the token by clicking a highlighted vertex. The cities graph is built from real place names: there is an arrow from one city to another exactly when the last letter of the first equals the first letter of the second. The computer uses memoized minimax over (current vertex, set of visited vertices) and always plays a winning move when one exists, so, since you move first, you can beat it only from a start vertex that is winning for the first player, and only by playing perfectly yourself. Tick Show win/lose analysis to see, for each legal move, whether it leaves your opponent in a winning or losing position.

<p class="hint">Directed Geography: a token sits on the start vertex. You and the computer take turns moving it along an arrow to a vertex that has not been visited yet. Whoever cannot move loses. Click a highlighted vertex to move. Switch to an undirected graph to see the matching rule.</p>
<div class="row">
  <label>Graph: <select id="graph" aria-label="Geography game graph">
    <option value="cities">Cities (last letter to first letter)</option>
    <option value="gadget">Small directed gadget</option>
    <option value="random">Random directed graph</option>
    <option value="path6">Undirected path, 6 vertices</option>
    <option value="path7">Undirected path, 7 vertices</option>
    <option value="tri">Undirected: two triangles and a tail</option>
    <option value="urandom">Random undirected graph</option>
  </select></label>
  <label>Start: <select id="start" aria-label="Start:"></select></label>
  <label id="nwrap">Vertices: <input id="nin" type="number" min="5" max="12" value="9"></label>
</div>
<div class="row">
  <button id="newg" type="button">New random graph</button>
  <button id="restart" type="button" class="ghost">Restart game</button>
  <label class="chk"><input id="ana" type="checkbox"> Show win/lose analysis</label>
</div>
<svg id="board" viewBox="0 0 340 260" role="img" aria-label="Geography game graph"></svg>
<div class="status" id="status"></div>
<div class="info" id="info"></div>
<div class="info match" id="match"></div>
<div class="legend">Green check: a move after which the opponent loses. Red cross: a move after which the opponent wins. Blue edges: moves made so far.</div>
<div class="chartbox">
  <button id="runchart" type="button">Measure growth</button>
  <svg id="chart" viewBox="0 0 340 200" role="img" aria-label="Chart of positions reached against graph size"></svg>
  <div class="info" id="chartnote"></div>
</div>

:root { --bg:#ffffff; --fg:#1f2933; --muted:#52606d; --edge:#8a97a6; --pill:#eef2f6; --pillb:#c3ccd6; --visited:#cfd8e3; --accent:#1d4ed8; --good:#0a7d33; --bad:#c92f3c; --match:#d97706; --btn:#1d3557; }
@media (prefers-color-scheme: dark) { :root { --bg:#14181f; --fg:#e6ebf1; --muted:#a3b0bf; --edge:#6b7a8c; --pill:#232b36; --pillb:#3b4757; --visited:#3a4657; --accent:#6ea0ff; --good:#4cc77a; --bad:#ff7b87; --match:#f5a524; --btn:#6ea0ff; } }
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 2px; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .6rem; line-height: 1.45; }
.row { display: flex; gap: .5rem .8rem; flex-wrap: wrap; align-items: center; margin: .35rem 0; font-size: .85rem; }
select, input[type=number] { font: 14px system-ui, sans-serif; padding: .25rem; border: 1px solid var(--pillb); border-radius: 6px; background: var(--pill); color: var(--fg); }
input[type=number] { width: 4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid var(--btn); background: var(--btn); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--btn); }
button:disabled { opacity: .5; cursor: default; }
svg { width: 100%; height: auto; display: block; }
.pill rect { fill: var(--pill); stroke: var(--pillb); stroke-width: 1.2; }
.pill text { fill: var(--fg); font: 600 10px system-ui, sans-serif; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.pill.vis rect { fill: var(--visited); }
.pill.cur rect { fill: var(--accent); stroke: var(--accent); }
.pill.cur text { fill: var(--bg); }
.pill.legal rect { stroke: var(--good); stroke-width: 2.2; }
.pill.legal.canclick { cursor: pointer; }
.badge circle { stroke: none; }
.badge.g circle { fill: var(--good); }
.badge.b circle { fill: var(--bad); }
.badge text { fill: #fff; font: 700 9px system-ui, sans-serif; text-anchor: middle; dominant-baseline: central; }
.e { fill: none; stroke: var(--edge); stroke-width: 1.1; }
.e.used { stroke: var(--accent); stroke-width: 2.4; }
.e.m { stroke: var(--match); stroke-width: 3.2; opacity: .85; }
.arrow { fill: var(--edge); }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: var(--good); }
.status.bad { color: var(--bad); }
.info { font-size: .84rem; color: var(--muted); margin: .2rem 0; line-height: 1.4; }
.legend { font-size: .78rem; color: var(--muted); margin: .3rem 0 .8rem; line-height: 1.4; }
.chk { display: flex; gap: .3rem; align-items: center; }
.chartbox { border-top: 1px solid var(--pillb); padding-top: .6rem; }
.ax { stroke: var(--edge); stroke-width: 1; }
.gr { stroke: var(--pillb); stroke-width: .6; }
.lab { fill: var(--muted); font: 9px system-ui, sans-serif; }
.ser { fill: none; stroke: var(--accent); stroke-width: 2; }
.bnd { fill: none; stroke: var(--match); stroke-width: 1.6; stroke-dasharray: 4 3; }
.dot { fill: var(--accent); }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);

function rng(seed) {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6D2B79F5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const bit = (b) => 31 - Math.clz32(b);

function mk(names, edges, und) {
  const n = names.length;
  const adj = names.map(() => []);
  const add = (a, b) => { if (a !== b && !adj[a].includes(b)) adj[a].push(b); };
  for (const [a, b] of edges) { add(a, b); if (und) add(b, a); }
  const am = adj.map((l) => l.reduce((m, v) => m | (1 << v), 0));
  const list = [];
  for (let a = 0; a < n; a++) for (const b of adj[a]) if (!und || a < b) list.push([a, b]);
  return { n, names, adj, am, und, list };
}

const CITIES = ['Lima', 'Accra', 'Athens', 'Seoul', 'Lagos', 'Oslo', 'Osaka', 'Amman', 'Nairobi', 'Istanbul', 'Lisbon', 'Kyoto'];

function randomGraph(n, seed, und, deg) {
  const r = rng(seed);
  const names = [];
  for (let i = 0; i < n; i++) names.push(String.fromCharCode(65 + i));
  const p = Math.min(0.9, deg / (n - 1));
  const edges = [];
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
    if (i === j || (und && j < i)) continue;
    if (r() < p) edges.push([i, j]);
  }
  return mk(names, edges, und);
}

function build(kind, n, seed) {
  if (kind === 'cities') {
    const e = [];
    CITIES.forEach((a, i) => CITIES.forEach((b, j) => {
      if (i !== j && a[a.length - 1].toLowerCase() === b[0].toLowerCase()) e.push([i, j]);
    }));
    return mk(CITIES, e, false);
  }
  if (kind === 'gadget') {
    return mk(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'],
      [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 6], [5, 6], [6, 7], [2, 5], [5, 1], [7, 0]], false);
  }
  if (kind === 'path6') return mk(['A', 'B', 'C', 'D', 'E', 'F'], [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]], true);
  if (kind === 'path7') return mk(['A', 'B', 'C', 'D', 'E', 'F', 'G'], [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]], true);
  if (kind === 'tri') {
    return mk(['A', 'B', 'C', 'D', 'E', 'F', 'G'],
      [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3], [5, 6]], true);
  }
  if (kind === 'urandom') return randomGraph(Math.min(12, Math.max(5, n)), seed, true, 1.8);
  return randomGraph(Math.min(14, Math.max(5, n)), seed, false, 2.6);
}

function makeSolver(g, full) {
  const memo = new Map();
  let cnt = 0;
  function win(cur, mask) {
    const key = mask * 32 + cur;
    const m = memo.get(key);
    if (m !== undefined) return m;
    let r = false;
    let av = g.am[cur] & ~mask;
    while (av) {
      const b = av & -av;
      av ^= b;
      if (!win(bit(b), mask | b)) { r = true; if (!full) break; }
    }
    memo.set(key, r);
    cnt++;
    return r;
  }
  return { win, count: () => cnt };
}

function matcher(g) {
  const memo = new Map();
  function mm(av) {
    if (!av) return 0;
    const c = memo.get(av);
    if (c !== undefined) return c;
    const b = av & -av;
    const v = bit(b);
    const rest = av ^ b;
    let best = mm(rest);
    let nb = g.am[v] & rest;
    while (nb) {
      const ub = nb & -nb;
      nb ^= ub;
      const s = 1 + mm(rest ^ ub);
      if (s > best) best = s;
    }
    memo.set(av, best);
    return best;
  }
  function pairs(av) {
    const out = [];
    while (av) {
      const b = av & -av;
      const v = bit(b);
      const rest = av ^ b;
      const target = mm(av);
      if (mm(rest) === target) { av = rest; continue; }
      let nb = g.am[v] & rest;
      let done = false;
      while (nb) {
        const ub = nb & -nb;
        nb ^= ub;
        if (1 + mm(rest ^ ub) === target) { out.push([v, bit(ub)]); av = rest ^ ub; done = true; break; }
      }
      if (!done) break;
    }
    return out;
  }
  return { mm, pairs };
}

function analyzeUndirected(g, s) {
  const M = matcher(g);
  const full = (1 << g.n) - 1;
  const sb = 1 << s;
  const total = M.mm(full);
  const without = M.mm(full ^ sb);
  const every = without < total;
  let pairs;
  if (every) {
    pairs = [];
    let nb = g.am[s];
    while (nb) {
      const ub = nb & -nb;
      nb ^= ub;
      if (1 + M.mm(full ^ sb ^ ub) === total) { pairs = [[s, bit(ub)]].concat(M.pairs(full ^ sb ^ ub)); break; }
    }
  } else {
    pairs = M.pairs(full ^ sb);
  }
  return { total, without, every, pairs };
}

let g = null, solver = null, seedCounter = 7;
let cur = 0, mask = 0, turn = 'you', path = [], startV = 0, matchPairs = [], busy = false;

function layout() {
  const pos = [];
  const rx = g.n > 10 ? 112 : 105, ry = g.n > 10 ? 100 : 98;
  for (let i = 0; i < g.n; i++) {
    const a = -Math.PI / 2 + (2 * Math.PI * i) / g.n;
    pos.push([170 + rx * Math.cos(a), 130 + ry * Math.sin(a)]);
  }
  return pos;
}

function pw(i) { return Math.max(24, g.names[i].length * 6 + 12); }

function clip(pos, a, b) {
  const dx = pos[b][0] - pos[a][0], dy = pos[b][1] - pos[a][1];
  const hw = pw(a) / 2 + 1, hh = 11;
  const tx = dx === 0 ? Infinity : hw / Math.abs(dx);
  const ty = dy === 0 ? Infinity : hh / Math.abs(dy);
  const t = Math.min(tx, ty);
  return [pos[a][0] + dx * t, pos[a][1] + dy * t];
}

function render() {
  const pos = layout();
  const usedSet = new Set();
  for (let i = 1; i < path.length; i++) usedSet.add(path[i - 1] + '>' + path[i]);
  const matchSet = new Set(matchPairs.map(([a, b]) => Math.min(a, b) + '-' + Math.max(a, b)));
  let s = '<defs><marker id="ah" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="6" markerHeight="6" orient="auto"><path class="arrow" d="M0 0L10 5L0 10z"/></marker></defs>';
  for (const [a, b] of g.list) {
    const p = clip(pos, a, b), q = clip(pos, b, a);
    const used = usedSet.has(a + '>' + b) || (g.und && usedSet.has(b + '>' + a));
    const isM = g.und && matchSet.has(Math.min(a, b) + '-' + Math.max(a, b));
    const cls = 'e' + (used ? ' used' : '') + (isM ? ' m' : '');
    if (g.und) {
      s += `<line class="${cls}" x1="${p[0].toFixed(1)}" y1="${p[1].toFixed(1)}" x2="${q[0].toFixed(1)}" y2="${q[1].toFixed(1)}"/>`;
    } else {
      const dx = q[0] - p[0], dy = q[1] - p[1];
      const len = Math.hypot(dx, dy) || 1;
      const cx = (p[0] + q[0]) / 2 - (dy / len) * 12, cy = (p[1] + q[1]) / 2 + (dx / len) * 12;
      s += `<path class="${cls}" marker-end="url(#ah)" d="M${p[0].toFixed(1)} ${p[1].toFixed(1)}Q${cx.toFixed(1)} ${cy.toFixed(1)} ${q[0].toFixed(1)} ${q[1].toFixed(1)}"/>`;
    }
  }
  const ana = $('ana').checked;
  const canMove = turn === 'you';
  for (let i = 0; i < g.n; i++) {
    const vis = (mask >> i) & 1;
    const legal = canMove && (((g.am[cur] & ~mask) >> i) & 1);
    const cls = 'pill' + (vis ? ' vis' : '') + (i === cur ? ' cur' : '') + (legal ? ' legal canclick' : '');
    const w = pw(i);
    s += `<g class="${cls}" data-v="${i}" transform="translate(${pos[i][0].toFixed(1)} ${pos[i][1].toFixed(1)})"><rect x="${-w / 2}" y="-11" width="${w}" height="22" rx="11"/><text>${g.names[i]}</text></g>`;
    if (legal && ana) {
      const good = !solver.win(i, mask | (1 << i));
      s += `<g class="badge ${good ? 'g' : 'b'}" transform="translate(${(pos[i][0] + w / 2 - 2).toFixed(1)} ${(pos[i][1] - 12).toFixed(1)})"><circle r="7"/><text>${good ? '✓' : '✗'}</text></g>`;
    }
  }
  $('board').innerHTML = s;
}

function setStatus(t, cls) { const e = $('status'); e.textContent = t; e.className = 'status ' + (cls || ''); }

function afterMove() {
  const moves = g.am[cur] & ~mask;
  if (!moves) {
    const youWon = turn === 'cpu';
    turn = 'over';
    setStatus(i18nFmt(youWon ? "%who% has no unvisited neighbour: the computer is stuck after %p% moves. You win!" : "You are stuck at %who% after %p% moves. The computer wins.", { who: g.names[cur], p: path.length - 1 }), youWon ? 'ok' : 'bad');
  } else if (turn === 'cpu') {
    setStatus("The computer is thinking...", '');
  } else {
    setStatus(i18nFmt("Your move from %v%: click a highlighted vertex.", { v: g.names[cur] }), '');
  }
  render();
}

function play(v) {
  cur = v;
  mask |= 1 << v;
  path.push(v);
}

function cpuMove() {
  let av = g.am[cur] & ~mask;
  const opts = [];
  while (av) { const b = av & -av; av ^= b; opts.push(bit(b)); }
  let pick = opts.find((v) => !solver.win(v, mask | (1 << v)));
  if (pick === undefined) pick = opts[Math.floor(Math.random() * opts.length)];
  play(pick);
  turn = 'you';
  busy = false;
  afterMove();
}

function onClick(ev) {
  const el = ev.target.closest('[data-v]');
  if (!el || turn !== 'you' || busy) return;
  const v = Number(el.getAttribute('data-v'));
  if (!(((g.am[cur] & ~mask) >> v) & 1)) return;
  play(v);
  turn = 'cpu';
  if (!(g.am[cur] & ~mask)) { afterMove(); return; }
  busy = true;
  render();
  setStatus("The computer is thinking...", '');
  setTimeout(cpuMove, 450);
}

function refreshInfo() {
  solver = makeSolver(g);
  const first = solver.win(startV, 1 << startV);
  $('info').textContent = i18nFmt(first ? "Exact minimax from %s%: the player to move wins with perfect play (%n% positions evaluated)." : "Exact minimax from %s%: the player to move loses with perfect play (%n% positions evaluated).", { s: g.names[startV], n: solver.count() });
  const box = $('match');
  if (g.und) {
    const A = analyzeUndirected(g, startV);
    matchPairs = A.pairs;
    const agree = A.every === first;
    box.textContent = i18nFmt("Maximum matching: %t% edges; without %s%: %w% edges.", { t: A.total, w: A.without, s: g.names[startV] }) + ' ' +
      (A.every ? "Removing the start vertex shrinks the maximum matching, so it lies in every maximum matching: the first player wins by moving along a matching edge and then always answering along matching edges (orange)." : "Removing the start vertex does not shrink the maximum matching, so some maximum matching misses it (orange): the second player wins by always answering along matching edges.") + ' ' + (agree ? "Brute-force minimax agrees." : "Brute-force minimax disagrees.");
  } else {
    matchPairs = [];
    box.textContent = '';
  }
}

function restart() {
  cur = startV;
  mask = 1 << startV;
  path = [startV];
  turn = 'you';
  busy = false;
  refreshInfo();
  afterMove();
}

function fillStart() {
  const sel = $('start');
  sel.innerHTML = '';
  g.names.forEach((nm, i) => {
    const o = document.createElement('option');
    o.value = String(i);
    o.textContent = nm;
    sel.appendChild(o);
  });
  startV = 0;
  sel.value = '0';
}

function loadGraph(reseed) {
  const kind = $('graph').value;
  const isRand = kind === 'random' || kind === 'urandom';
  $('nwrap').style.display = isRand ? '' : 'none';
  $('nin').max = kind === 'urandom' ? '12' : '14';
  if (reseed) seedCounter += 1;
  g = build(kind, Number($('nin').value) || 9, seedCounter);
  fillStart();
  restart();
}

function runChart() {
  const btn = $('runchart');
  btn.disabled = true;
  const K = 6;
  const pts = [];
  let n = 4;
  function step() {
    if (n > 15) { drawChart(pts, K); btn.disabled = false; return; }
    let tot = 0;
    for (let k = 0; k < K; k++) {
      const gr = randomGraph(n, 1000 * n + k, false, 3);
      const sv = makeSolver(gr, true);
      sv.win(0, 1);
      tot += sv.count();
    }
    pts.push([n, Math.max(1, tot / K)]);
    drawChart(pts, K);
    n++;
    setTimeout(step, 20);
  }
  step();
}

function drawChart(pts, K) {
  const X0 = 36, X1 = 326, Y0 = 170, Y1 = 14;
  const xs = (n) => X0 + ((n - 4) / 11) * (X1 - X0);
  const ys = (v) => Y0 - (Math.log10(v) / 6) * (Y0 - Y1);
  const sup = ['⁰', '¹', '²', '³', '⁴', '⁵', '⁶'];
  let s = '';
  for (let e = 0; e <= 6; e++) {
    const y = ys(Math.pow(10, e)).toFixed(1);
    s += `<line class="gr" x1="${X0}" x2="${X1}" y1="${y}" y2="${y}"/>`;
    s += `<text class="lab" x="${X0 - 4}" y="${(Number(y) + 3).toFixed(1)}" text-anchor="end">10${sup[e]}</text>`;
  }
  for (let n = 4; n <= 15; n += 1) s += `<text class="lab" x="${xs(n).toFixed(1)}" y="${Y0 + 12}" text-anchor="middle">${n}</text>`;
  s += `<line class="ax" x1="${X0}" x2="${X1}" y1="${Y0}" y2="${Y0}"/><line class="ax" x1="${X0}" x2="${X0}" y1="${Y0}" y2="${Y1}"/>`;
  let bnd = '';
  for (let n = 4; n <= 15; n++) bnd += (n === 4 ? 'M' : 'L') + xs(n).toFixed(1) + ' ' + ys(n * Math.pow(2, n - 1)).toFixed(1);
  s += `<path class="bnd" d="${bnd}"/>`;
  let ser = '';
  pts.forEach(([n, v], i) => { ser += (i ? 'L' : 'M') + xs(n).toFixed(1) + ' ' + ys(v).toFixed(1); });
  if (pts.length) s += `<path class="ser" d="${ser}"/>`;
  pts.forEach(([n, v]) => { s += `<circle class="dot" r="2.6" cx="${xs(n).toFixed(1)}" cy="${ys(v).toFixed(1)}"/>`; });
  s += `<text class="lab" x="${(X0 + X1) / 2}" y="${Y0 + 25}" text-anchor="middle">vertices n</text>`;
  s += `<text class="lab" x="${X0 + 6}" y="${Y1 + 4}">positions reached</text>`;
  s += `<line class="ser" x1="${X0 + 14}" x2="${X0 + 30}" y1="${Y1 + 22}" y2="${Y1 + 22}"/><text class="lab" x="${X0 + 34}" y="${Y1 + 25}">measured (full memoized search)</text>`;
  s += `<line class="bnd" x1="${X0 + 14}" x2="${X0 + 30}" y1="${Y1 + 36}" y2="${Y1 + 36}"/><text class="lab" x="${X0 + 34}" y="${Y1 + 39}">upper bound n·2^(n−1)</text>`;
  $('chart').innerHTML = s;
  $('chartnote').textContent = i18nFmt("Average over %k% random directed graphs per size, out-degree about 3, start at vertex A, every move explored (no early cutoff). Logarithmic vertical axis.", { k: K });
}

$('board').addEventListener('click', onClick);
$('graph').addEventListener('change', () => loadGraph(false));
$('newg').addEventListener('click', () => loadGraph(true));
$('nin').addEventListener('change', () => loadGraph(false));
$('restart').addEventListener('click', restart);
$('ana').addEventListener('change', render);
$('start').addEventListener('change', () => { startV = Number($('start').value); restart(); });
$('runchart').addEventListener('click', runChart);
drawChart([], 6);
loadGraph(false);
Result
Console

Two things to try:

  • Measure growth. The chart runs the same search on random directed graphs of 4 to 15 vertices, exploring every move. The number of distinct positions reached grows roughly exponentially with the number of vertices, well under, but of the same exponential character as, the n⋅2n−1n\cdot 2^{n-1} ceiling on the number of possible (vertex, visited set) pairs.
  • Switch to an undirected graph. The panel below the board now computes a maximum matching and checks a simple rule: the first player wins exactly when the start vertex belongs to every maximum matching. The orange edges show the strategy. Brute-force minimax confirms the rule on every graph you generate.

The Real Complexity

Let the graph have nn vertices.

Upper bound: the problem is in PSPACE. Each move visits a new vertex, so a game lasts at most n−1n-1 moves. A depth-first search of the game tree needs only the current path, which takes O(n)O(n) vertices of stack, plus a visited set, so O(n)O(n) words of memory in total (or O(n2)O(n^2) bits). The search time is exponential in the worst case, O(n!)O(n!) moves in the naive tree, but the memory is polynomial. Memoizing on (vertex, visited set) as the demo does cuts the work to at most n⋅2n−1n\cdot 2^{n-1} positions, each examined in O(n)O(n) time, at the price of exponential memory, which is the classic time-space trade-off.

wins(v, V):                # V = visited vertices, v in V
    for each arrow v -> w with w not in V:
        if not wins(w, V + {w}):
            return true    # a move that leaves the opponent lost
    return false           # no move, or every move loses

Lower bound: PSPACE-hardness. Thomas J. Schaefer proved in 1978 (On the complexity of some two-person perfect-information games, Journal of Computer and System Sciences) that deciding the winner of generalized geography is PSPACE-complete. The reduction is from TQBF, the problem of deciding a fully quantified Boolean formula

∃x1 ∀x2 ∃x3⋯Qxn  φ(x1,…,xn),\exists x_1\,\forall x_2\,\exists x_3 \cdots Q x_n\;\varphi(x_1,\dots,x_n),

with φ\varphi in conjunctive normal form (this is the version in Sipser's textbook). The graph is built like this:

  • For every variable, a diamond: a top vertex, a left vertex (true), a right vertex (false) and a bottom vertex. Whoever moves from the top picks the side, and the rest of the diamond is forced. A diamond takes three moves, so the player who picks alternates from one diamond to the next. Arrange it so that the first player picks the existential variables and the second player the universal ones. The chain of choices is an assignment, and the visited vertices record it.
  • After the last diamond, the second player chooses a clause vertex, a claim that this clause is false. The first player then picks one literal vertex in that clause, a claim that the literal is true. The literal vertex has a single arrow, to the diamond vertex that makes it true.
  • If the literal is indeed true under the chosen assignment, that diamond vertex has already been visited, the second player cannot move, and the first player wins. If every literal of the clause is false, the first player is forced into an unvisited vertex and the play goes on in the second player's favour.

So the first player has a winning strategy exactly when ∃x1∀x2⋯φ\exists x_1\forall x_2\cdots\varphi is true. The graph has size linear in the formula, so the reduction is polynomial and generalized geography is PSPACE-complete. Because TQBF is PSPACE-complete (and, by Savitch's theorem, nondeterminism adds nothing at polynomial space), a fast algorithm for geography would put every polynomial-space problem, and in particular all of NP, in P.

Planar graphs. David Lichtenstein and Michael Sipser (GO is polynomial-space hard, Journal of the ACM, 1980) showed that the game stays PSPACE-complete on planar directed graphs. They used this to show that deciding the winner of Go positions on an n×nn\times n board is PSPACE-hard, the first such result for a board game that they were aware of.

Undirected graphs: easy for vertices, hard for edges. If every arrow comes with its reverse, the vertex version collapses to a polynomial problem. Fraenkel, Scheinerman and Ullman (Undirected edge geography, Theoretical Computer Science, 1993) gave a polynomial algorithm for undirected vertex geography built on matching theory:

The player to move from ss wins if and only if ss belongs to every maximum matching of the graph.

Equivalently, writing ν(G)\nu(G) for the size of a maximum matching, the first player wins iff ν(G−s)<ν(G)\nu(G-s)<\nu(G). The strategy is explicit. If ss is in every maximum matching MM, move along the MM-edge at ss and afterwards always answer along the MM-edge at the vertex the opponent just entered; the opponent can never strand you, because a vertex reached along a non-matching edge must itself be matched: otherwise swapping edges along the alternating path from ss would give a maximum matching that misses ss. If some maximum matching MM misses ss, the second player answers every move along MM. A maximum matching can be computed in polynomial time by Edmonds' blossom algorithm (see also maximum matching). The edge version on undirected graphs is again PSPACE-complete, according to the same paper.

Version Complexity
Directed vertex geography PSPACE-complete (Schaefer, 1978)
Directed, planar PSPACE-complete (Lichtenstein and Sipser, 1980)
Undirected vertex geography Polynomial, via maximum matching (1993)
Undirected edge geography PSPACE-complete (1993)

Where It Matters

Geography is less a game to play than a tool for proving other games hard. Its reduction from TQBF is clean and local, so it is easy to copy into a new setting.

  • Board games. Lichtenstein and Sipser chained TQBF to geography, to planar geography and finally to Go. Stefan Reisch (Hex ist PSPACE-vollständig, Acta Informatica, 1981) proved that deciding the winner of Hex positions is PSPACE-complete. Games whose length is not bounded by a polynomial can be even harder: generalized chess was shown EXPTIME-complete by Fraenkel and Lichtenstein (1981), and Go under Japanese ko rules by Robson (1983).
  • Puzzle and game design. Many puzzles with an adversary and an irreversible resource, such as visited cells or used tokens, reduce to or from geography.
  • Adversarial planning and verification. Alternating quantifiers, "for every choice of the environment there is a response of the system", are exactly what a geography play expresses. The same alternation shows up in game-based model checking and in interactive proofs, which characterize PSPACE.
  • A cautionary note on heuristics. Geography instances arising from real word lists are small and sparse, so exhaustive search works. The hardness is about worst-case graphs.

Conclusion

Generalized geography shows how a modest rule, "move the token to somewhere new", can hold the full strength of quantified logic. On directed graphs it is PSPACE-complete, so a general fast solver would collapse a large part of complexity theory. On undirected graphs the vertex version turns tractable because the game is secretly about matchings, a structure we can optimize in polynomial time.

The next time a long car ride produces a dead end at the letter x, remember that you have met both extremes: a worst case that encodes every alternating quantifier, and an easy case that a maximum matching settles in polynomial time. For the broader picture of why games sit at PSPACE, see QBF and PSPACE and P vs NP.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/generalized-geography/Content licensed under CC BY-NC 4.0.