Introduction

Hex is played on a rhombus of hexagons. Two players take turns coloring a cell — one wants to build an unbroken chain of their color connecting the left and right sides, the other wants to connect top and bottom. The first to bridge their two sides wins.

That's the whole game. Yet from those two rules springs a small miracle: a Hex board can never end in a draw. Once every cell is filled, exactly one player has connected their sides — always. (This fact is equivalent to a deep result in topology, the Brouwer fixed-point theorem.)

And there is a second, stranger fact. On any board, the first player can force a win. We can prove this with certainty. What we cannot do — for boards bigger than a handful of cells — is tell you a single move that wins.

Play Hex

You are Blue, connecting the left and right edges. The bot is Red, connecting top and bottom. Tap an empty cell to place your stone; the bot replies. The instant either color links its two sides, that chain lights up.

<p class="hint">You are <b class="blue">Blue</b> — connect the <b>left and right</b> edges.
    The bot is <b class="red">Red</b> — it connects <b>top and bottom</b>. Click an empty
    hexagon to play; the bot replies. The moment a color links its two sides, the winning
    chain lights up. The board can never end in a draw.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Your move, Blue.</div>
<div class="btns">
  <button id="reset" type="button">New game</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.blue { color: #2563eb; }
.red { color: #dc2626; }
.board { position: relative; width: 320px; height: 250px; margin: .4rem auto; }
.hexwrap { position: absolute; width: 40px; height: 46px; }
.hex { width: 100%; height: 100%; cursor: pointer;
       clip-path: polygon(50% 0%, 100% 25%, 100% 75%, 50% 100%, 0% 75%, 0% 25%);
       background: #e8eef3; border: none; transition: background .12s; display: block; }
.hex.empty:hover { background: #d4dde6; }
.hex.blue { background: #2563eb; cursor: default; }
.hex.red  { background: #dc2626; cursor: default; }
.hex.win  { box-shadow: 0 0 0 3px #fbbf24; filter: brightness(1.15); }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; text-align: center; }
.status.blue { color: #2563eb; }
.status.red  { color: #dc2626; }
.btns { display: flex; gap: .5rem; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Hex: Blue links LEFT<->RIGHT, Red links TOP<->BOTTOM. On a full board exactly one side connects — a draw is impossible. Deciding the winner of a general position is PSPACE-complete (Reisch, 1981); the first-player win is proven nonconstructively by strategy stealing. Here we just play and detect the connection with a flood fill.
const N = 5;
// Hex neighbors on a rhombic board: the 6 adjacent cells.
const DIRS = [[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0]];
let board, current, over;

function reset(){
  board = Array.from({length:N}, () => Array(N).fill(0)); // 0 empty, 1 blue, 2 red
  current = 1; over = false;
  render(); setStatus('Your move, Blue.','blue');
}
function inB(r,c){ return r>=0 && r<N && c>=0 && c<N; }
function nbrs(r,c){ return DIRS.map(([dr,dc])=>[r+dr,c+dc]).filter(([a,b])=>inB(a,b)); }

// Flood fill: does `player` connect its two sides? Returns the winning cell set or null.
function winningSet(player){
  const seen = new Set(); const stack = [];
  // seed from the player's "first" side
  for(let i=0;i<N;i++){
    const [r,c] = player===1 ? [i,0] : [0,i]; // blue starts at left col, red at top row
    if(board[r][c]===player){ const k=r+','+c; if(!seen.has(k)){ seen.add(k); stack.push([r,c]); } }
  }
  while(stack.length){
    const [r,c] = stack.pop();
    for(const [a,b] of nbrs(r,c)){
      if(board[a][b]===player){ const k=a+','+b; if(!seen.has(k)){ seen.add(k); stack.push([a,b]); } }
    }
  }
  // did we reach the far side?
  const reached = [...seen].some(k=>{ const [r,c]=k.split(',').map(Number);
    return player===1 ? c===N-1 : r===N-1; });
  return reached ? seen : null;
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

function render(winSet){
  const b = document.getElementById('board'); b.innerHTML='';
  const dx=34, dy=38, sh=20; // horizontal step, vertical step, per-row shift
  for(let r=0;r<N;r++)for(let c=0;c<N;c++){
    const w=document.createElement('div'); w.className='hexwrap';
    w.style.left=(c*dx + r*sh)+'px'; w.style.top=(r*dy)+'px';
    const h=document.createElement('button'); h.type='button';
    const v=board[r][c]; const colorCls = v===1?'blue':v===2?'red':'empty';
    h.className='hex '+colorCls + (winSet && winSet.has(r+','+c)?' win':'');
    if(v===0 && !over) h.addEventListener('click',()=>play(r,c));
    w.appendChild(h); b.appendChild(w);
  }
}

function endIf(){
  const bw=winningSet(1); if(bw){ over=true; render(bw); setStatus('Blue connects left to right — Blue wins!','blue'); return true; }
  const rw=winningSet(2); if(rw){ over=true; render(rw); setStatus('Red connects top to bottom — Red wins.','red'); return true; }
  return false;
}

function play(r,c){
  if(over || board[r][c]!==0) return;
  board[r][c]=1; render(); if(endIf()) return;            // Blue moves
  botMove();                                              // Red replies
}

// Simple bot: take any immediately-winning cell, else the empty cell with the most Red neighbors (greedy toward connection), else a random empty cell.
function botMove(){
  const empties=[]; for(let r=0;r<N;r++)for(let c=0;c<N;c++) if(board[r][c]===0) empties.push([r,c]);
  if(!empties.length){ over=true; setStatus('Board full.',''); return; }
  let pick=null;
  for(const [r,c] of empties){ board[r][c]=2; if(winningSet(2)){ pick=[r,c]; board[r][c]=0; break; } board[r][c]=0; }
  if(!pick){
    let best=-1; for(const [r,c] of empties){ const score=nbrs(r,c).filter(([a,b])=>board[a][b]===2).length;
      if(score>best){ best=score; pick=[r,c]; } }
  }
  const [r,c]=pick; board[r][c]=2; render(); if(endIf()) return;
  setStatus('Your move, Blue.','blue');
}

document.getElementById('reset').addEventListener('click',reset);
reset();
Result
Console

Try to lose on purpose by leaving gaps — you will find the board simply refuses to stay unfinished without a winner. When the last cell is colored, someone has always connected. That no-draw guarantee is what makes the next fact possible: a clean argument that the first player wins, even though the board above is small enough to fill in by brute force but a real 11×11 board is not.

The Real Complexity

Here is the argument that the first player wins, due to John Nash (around 1949). It is called strategy stealing.

  • Suppose, for contradiction, the second player had a guaranteed winning strategy S.
  • The first player can then steal it: play any arbitrary first move, then simply follow S as if they were the second player. In Hex an extra stone of your own color never hurts you — it can only help.
  • That would make both players winners, which is impossible since Hex can never draw. So no winning strategy for the second player exists — meaning the first player must have one.

Read that again: the proof never names a move. It shows a winning strategy exists without producing it. This is a nonconstructive proof — it wins the argument, not the game.

And finding the actual moves is brutally hard. In 1981 Stefan Reisch proved that Hex is PSPACE-complete: deciding who wins a given Hex position is as hard as any problem solvable in polynomial memory, a class believed to dwarf P vs NP-style difficulty. So the gap is real and permanent: we know the first player wins, yet computing how, on a full-size board, is intractable.

Where It Matters

Hex is tiny, but the ideas around it are everywhere:

  • Existence without construction. Strategy stealing is a clean example of proving something exists without building it — the same move that powers many results across mathematics, from fixed-point theorems to the pigeonhole principle.
  • The frontier of game AI. Because optimal Hex is PSPACE-complete, programs can't just look it up; modern Hex bots lean on the same deep search and neural-network ideas that cracked Go.
  • Two-player games as a complexity yardstick. Generalized board games — Hex, Go, Checkers — are the canonical hard problems for PSPACE and beyond, the way SAT is the canonical NP problem.
  • A lesson in humility. Hex shows that knowing the answer exists and knowing the answer are genuinely different — a distinction at the heart of computational complexity.

Conclusion

Hex is the rare game that hands you a victory and withholds the instructions. A two-line argument proves the first player can always win, yet for any serious board no one can tell you the moves — and Reisch's theorem says no one ever will tell you cheaply, because the problem is PSPACE-complete.

So Hex is a perfect little parable for the limits of computation: the difference between "a solution exists" and "here is the solution" is not a technicality. Sometimes, as with this elegant grid of hexagons, that gap is the whole story — and it sits right next to P vs NP among the deepest questions about what we can and cannot compute.

Share this article

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

Comments

Loading comments...

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