AI Analysis Engine

BeeHex features a sophisticated AI analysis engine that evaluates board positions and recommends optimal moves using minimax search with custom heuristics. The engine runs entirely in the browser using Web Workers for parallel computation.

Overview

The AI engine provides real-time position analysis during game review, helping players understand optimal strategies and evaluate their move choices.

Minimax Search

Multi-threaded game tree exploration with alpha-beta pruning concepts

Position Scoring

Custom heuristic evaluating connection strength and bridge formations

Move Ranking

Top 4 moves displayed with evaluation scores and optimal continuations

Win Detection

Forced win sequences identified with exact move count

Core Architecture

Explorer Class

The Explorer class coordinates the analysis process:

src/app/hex/[gameId]/Algorithm.ts

export class Explorer {
  private game: ScoredGameInstance;
  private startTime: EpochTimeStamp;
  private exploredBoardCount: number = 0;
  private heuristic: Function;
  private updateCallback: Function;
  private mainInstances: Array<MainScoredGameInstance>;
  private worker: Worker;
  private instances: Map<GridHash, ScoredGameInstance>;
  private bestMoves: Array<MainScoredGameInstance>;

  constructor(grid: Array<Array<number>>, turn: number, heuristic: Function, updateCallback: Function) {
    let simpleGame = new SimpleGameInstance(grid, turn, []);
    this.worker.addEventListener("message", this._workerCallback.bind(this));
    this.heuristic = heuristic;
    this.updateCallback = updateCallback;
    this.startTime = Date.now();
    this.game = this.rateInstance(simpleGame);
    this.instances = new Map<GridHash, ScoredGameInstance>();
    this.mainInstances = this.populateMainInstances();
    this.sendNextInstanceToWorker();
  }
}

Game Instance Types

SimpleGameInstance
ScoredGameInstance
MainScoredGameInstance

Base class representing a board position:

src/app/hex/[gameId]/Algorithm.ts

export class SimpleGameInstance {
  public grid: number[][];
  public moves: Array<Coordinate>;
  public turn: number;
  protected gridHash: string;

  constructor(grid: Array<Array<number>>, turn: number, moves: Array<Coordinate> = []) {
    this.grid = grid;
    this.turn = turn;
    this.moves = moves;
    this.gridHash = hashGrid(grid);
  }

  getValidMoves() {
    const validMoves: Array<Coordinate> = [];
    for (let i = 0; i < this.grid.length; i++) {
      for (let j = 0; j < this.grid[i].length; j++) {
        if (this.isValidMove(i, j)) {
          validMoves.push([i, j]);
        }
      }
    }
    return validMoves;
  }

  getCurrentPlayer() {
    return this.turn % 2 === 0 ? 2 : 1;
  }
}

Extends SimpleGameInstance with evaluation data:

src/app/hex/[gameId]/Algorithm.ts

export class ScoredGameInstance extends SimpleGameInstance {
  public score: Score;
  public previousInstances: Array<ScoredGameInstance> = [];
  public nextInstances: Map<number, ScoredGameInstance>;
  public leadingInstance: ScoredGameInstance | null = null;
  public completedBranch: boolean;

  constructor(grid: Array<Array<number>>, turn: number, moves: Array<Coordinate>, score: Score) {
    super(grid, turn);
    this.score = score;
    this.moves = moves.slice();
    if (this.score.isWinCountdown && 
        (this.score.score == 0.5 || this.score.score == -0.5)) {
      this.nextInstances = empty_map;
      this.completedBranch = true;
    } else {
      this.nextInstances = new Map<number, ScoredGameInstance>();
      this.completedBranch = false;
    }
  }
}

Key features:

score: Current position evaluation
previousInstances: Parent positions in game tree
nextInstances: Child positions after each legal move
leadingInstance: Best continuation from this position
completedBranch: Whether subtree is fully explored

Special instance for root-level moves:

src/app/hex/[gameId]/Algorithm.ts

class MainScoredGameInstance extends ScoredGameInstance {
  private explorerCallback: Function;
  public playedMove: Coordinate;

  constructor(grid: Array<Array<number>>, turn: number, moves: Array<Coordinate>, 
              score: Score, playedMove: Coordinate, explorerCallback: Function) {
    super(grid, turn, moves, score);
    this.explorerCallback = explorerCallback;
    this.playedMove = playedMove;
  }

  updateScore() {
    // ... score update logic ...
    if (!currentScore.isEqualTo(newScore) || 
        this.leadingInstance != leadingInstance || 
        this.completedBranch == true) {
      this.score = newScore;
      this.leadingInstance = leadingInstance;
      this.explorerCallback(this); // Notify UI of updated evaluation
    }
  }
}

This type enables real-time UI updates as evaluations improve.

Position Evaluation

Score Type

The scoring system distinguishes between heuristic evaluations and forced wins:

src/app/hex/[gameId]/Algorithm.ts

export class Score {
  public score: number;
  public isWinCountdown: boolean; // true if forced win detected

  constructor(score: number, isWinCountdown: boolean) {
    this.score = score;
    this.isWinCountdown = isWinCountdown;
  }

  public isBiggerThan(other: Score): boolean {
    if (!this.isWinCountdown && !other.isWinCountdown) {
      return this.score > other.score; // Standard comparison
    }
    if (this.isWinCountdown && !other.isWinCountdown) {
      return this.score > 0; // Forced win beats heuristic
    }
    if (!this.isWinCountdown && other.isWinCountdown) {
      return other.score < 0;
    }
    if (this.score * other.score < 0) {
      return this.score > other.score; // Different winners
    }
    return Math.abs(this.score) < Math.abs(other.score); // Faster win is better
  }

  toString() {
    return this.isWinCountdown ? `#${Math.round(this.score)}` : `${this.score}`;
  }
}

When isWinCountdown is true, the score represents the number of moves until forced victory (positive for player 1, negative for player 2).

Basic Heuristic

The default evaluation function analyzes connection strength:

src/app/hex/[gameId]/Algorithm.ts

export function basicHeuristic(instance: SimpleGameInstance): Score {
  let grid = instance.getGrid();
  let player1Score = attributeScore(grid, 1);
  let player2Score = attributeScore(grid, 2);
  
  if (player1Score[0] === 0) {
    // Player 1 has won
    return new Score(player1Score[1] + (instance.getTurn() % 2 === 0 ? 0.5 : 0), true);
  }
  else if (player2Score[0] === 0) {
    // Player 2 has won
    return new Score(-player2Score[1] + (instance.getTurn() % 2 === 1 ? -0.5 : 0), true);
  }
  // Position evaluation based on connection strength
  return new Score(player2Score[0] - player1Score[0], false);
}

Connection Analysis

The attributeScore function performs pathfinding to evaluate connection strength:

src/app/hex/[gameId]/Algorithm.ts

export function attributeScore(grid: number[][], player: number): [number, number] {
  let size = grid.length;
  let minCost = grid.length ** 2;      // Minimum moves needed
  let minBridges = grid.length ** 2;    // Minimum bridges required
  let hexagonsToCheck: Array<CheckableHexagon> = [];
  let checkedHexagons: Array<Coordinate> = [];
  
  // Initialize starting edge
  if (player === 1) {
    for (let i = 0; i < grid.length; i++) {
      if (grid[i][0] === 1) {
        hexagonsToCheck.push([[i, 0], 0, 0]); // [coordinate, cost, bridges]
      } else if (grid[i][0] === 0) {
        // Check for bridge possibilities
        if (i > 0 && grid[i - 1][1] === 1 && grid[i - 1][0] === 0) {
          hexagonsToCheck.push([[i, 0], 0, 1]);
        } else if (i < grid.length - 1 && grid[i][1] === 1 && grid[i + 1][0] === 0) {
          hexagonsToCheck.push([[i, 0], 0, 1]);
        } else {
          hexagonsToCheck.push([[i, 0], 1, 0]);
        }
      }
    }
  }
  // ... similar logic for player 2 ...
  
  // Dijkstra-like search to find minimum cost path
  while (hexagonsToCheck.length > 0) {
    hexagonsToCheck.sort((a, b) => b[1] - a[1]);
    let hexagon = hexagonsToCheck.pop()!!;
    // ... pathfinding logic ...
  }
  
  return [minCost, minBridges];
}

Bridge Detection

The algorithm recognizes “bridges” - connection patterns that cannot be broken by the opponent:

function getInnerBridgeHexagons(hex1: Coordinate, hex2: Coordinate): Array<Coordinate> {
  let diffY = hex2[0] - hex1[0];
  let diffX = hex2[1] - hex1[1];
  let y = hex2[0];
  let x = hex2[1];
  
  if (diffX === 1 && diffY === 1) {
    return [[y, x - 1], [y - 1, x]];
  }
  // ... other bridge patterns ...
}

Bridges provide guaranteed connections without requiring additional moves.

Minimax Search

Tree Exploration

The engine uses minimax with iterative deepening:

src/app/hex/[gameId]/Algorithm.ts

getNextChildToExplore(): ScoredGameInstance {
  if (this.nextInstances.size == 0) {
    return this;
  }
  if (this.completedBranch) {
    return this;
  }
  
  const instancesLeft = this.nextInstances.values()
    .toArray()
    .filter(instance => instance.completedBranch == false);
  
  let minMax;
  if (this.turn % 2 === 0) {
    // Player 2 minimizes score
    minMax = (a: ScoredGameInstance, b: ScoredGameInstance) => 
      a.getScore().isBiggerThan(b.getScore()) ? b : a;
  } else {
    // Player 1 maximizes score
    minMax = (a: ScoredGameInstance, b: ScoredGameInstance) => 
      a.getScore().isBiggerThan(b.getScore()) ? a : b;
  }
  
  let nextInstance = instancesLeft.reduce(minMax);
  return nextInstance.getNextChildToExplore();
}

Score Propagation

When a leaf node is evaluated, scores propagate up the tree:

src/app/hex/[gameId]/Algorithm.ts

updateScore() {
  if (this.nextInstances.size == 0) {
    console.warn("ScoredGameInstance.updateScore() called on instance with no children");
  }
  
  let minMax;
  if (this.turn % 2 === 0) {
    minMax = (a: ScoredGameInstance, b: ScoredGameInstance) => 
      a.getScore().isBiggerThan(b.getScore()) ? b : a;
  } else {
    minMax = (a: ScoredGameInstance, b: ScoredGameInstance) => 
      a.getScore().isBiggerThan(b.getScore()) ? a : b;
  }
  
  const nextInstances = this.nextInstances.values().toArray();
  const leadingInstance = nextInstances.reduce(minMax);
  let leadingScore = leadingInstance.getScore();
  let newScore = Score.fromRaw(leadingScore.raw());
  
  if (newScore.isWinCountdown) {
    // Add 0.5 moves to the countdown (one more ply)
    newScore.score += newScore.score > 0 ? 0.5 : -0.5;
  }
  
  this.completedBranch = leadingInstance.completedBranch;
  for (let instance of nextInstances) {
    this.completedBranch = this.completedBranch && instance.completedBranch;
  }
  
  if (!currentScore.isEqualTo(newScore) || 
      this.leadingInstance != leadingInstance || 
      this.completedBranch == true) {
    this.score = newScore;
    this.leadingInstance = leadingInstance;
    this.updatePreviousInstances(); // Propagate upward
  }
}

Web Worker Integration

The engine uses Web Workers for parallel computation without blocking the UI:

src/app/hex/[gameId]/Algorithm.ts

private worker: Worker = new Worker(new URL("AlgorithmWorker.ts", import.meta.url));

this.worker.addEventListener("message", this._workerCallback.bind(this));

Worker Communication

Send Exploration Request

Main thread identifies next position to explore:

this.worker.postMessage({
  id: this.game.getGridHash(),
  type: AlgorithmWorkerBoundPacketType.EXPLORE_INSTANCE,
  game: bestInstance.raw()
} as AlgorithmWorkerBoundExplorePacket);

Worker Explores

Worker expands the game tree and evaluates leaf nodes.

Return Results

Worker sends back explored instances:

export interface AlgorithmExplorerBoundResultPacket {
  type: AlgorithmExplorerBoundPacketType.RESULT;
  id: string;
  result: ExploreResult;
}

export interface ExploreResult {
  gameInstances: Map<GridHash, RawScoredGameInstance>;
  leaves: Array<GridHash>;
}

Update UI

Main thread integrates results and updates move recommendations.

Performance Tracking

The explorer logs search performance:

src/app/hex/[gameId]/Algorithm.ts

const currentTime = Date.now();
this.exploredBoardCount += 1;
if (currentTime - this.startTime > 5000) {
  let boardsPerSecond = Math.round(
    (this.exploredBoardCount * 1000) / (currentTime - this.startTime)
  );
  console.log(`Explored ${this.exploredBoardCount} boards in ${currentTime - this.startTime} ms (${boardsPerSecond} boards/s)`);
  this.startTime = currentTime;
  this.exploredBoardCount = 0;
}

On modern hardware, the engine typically explores 5,000-15,000 positions per second.

Move Recommendations

The explorer maintains a ranked list of best moves:

src/app/hex/[gameId]/Algorithm.ts

mainInstanceCallback(mainInstance: MainScoredGameInstance) {
  if (!this.bestMoves.includes(mainInstance)) {
    this.bestMoves.push(mainInstance);
  }
  
  let minMaxFunction;
  if (this.game.turn % 2 === 0) {
    minMaxFunction = (a: MainScoredGameInstance, b: MainScoredGameInstance) => 
      a.getScore().isBiggerThan(b.getScore()) ? 1 : -1;
  } else {
    minMaxFunction = (a: MainScoredGameInstance, b: MainScoredGameInstance) => 
      a.getScore().isSmallerThan(b.getScore()) ? 1 : -1;
  }
  
  this.bestMoves.sort(minMaxFunction);
  
  if (this.bestMoves.length > 10) {
    this.bestMoves.pop();
  }
  
  const recommendedMoves = this.bestMoves.map(move => {
    return {
      coordinate: move.playedMove,
      score: move.getScore(),
      optimalRoute: move.getBestChildInstance().moves
    } as RecommendedMove;
  });
  
  this.updateCallback(recommendedMoves);
}

UI Integration

The game interface displays analysis results in real-time:

src/app/hex/[gameId]/page.tsx

function explorerCallback(moves: RecommendedMove[]) {
  for (let i = 0; i < moves.length; i++) {
    const move = moves[i];
    if (i === 0) {
      setMoveEvaluationScore1(move.score);
      setMoveEvaluationMoves1(move.optimalRoute.slice(0, 6));
    } else if (i === 1) {
      setMoveEvaluationScore2(move.score);
      setMoveEvaluationMoves2(move.optimalRoute.slice(0, 6));
    } else if (i === 2) {
      setMoveEvaluationScore3(move.score);
      setMoveEvaluationMoves3(move.optimalRoute.slice(0, 6));
    } else if (i === 3) {
      setMoveEvaluationScore4(move.score);
      setMoveEvaluationMoves4(move.optimalRoute.slice(0, 6));
    }
  }
  setRecommendedMoves(moves.map((move) => move.optimalRoute[0]));
}

Recommended moves are highlighted on the board:

src/app/hex/[gameId]/Grid.tsx

let highlightIndex = recommendedMoves.slice(0, 4).findIndex(
  (move) => move[0] === i && move[1] === j
);
if (highlightIndex !== -1) {
  const highlightClass = `var(--${hexSign}-preview-${highlightIndex + 1})`;
  newBackgroundColor = highlightClass;
}

The top 4 recommended moves are color-coded on the board, with the best move shown in the brightest shade.

Grid Hashing

The engine uses base-36 encoding for efficient position storage:

src/app/hex/[gameId]/Algorithm.ts

export function hashGrid(grid: Array<Array<number>>): GridHash {
  let hash = 0n;
  let ii = 1n;
  for (let i of grid) {
    for (let j of i) {
      hash += BigInt(j) * ii;
      ii *= 3n;
    }
  }
  let finalHash = hash.toString(36);
  return finalHash;
}

This allows the instances Map to detect transpositions and avoid re-evaluating identical positions.

Memory Optimization

The engine implements several memory-saving techniques:

src/app/hex/[gameId]/Algorithm.ts

if (newScore.isWinCountdown) {
  newScore.score += newScore.score > 0 ? 0.5 : -0.5;
}
this.grid = empty_array; // Clear grid data after children are created

Array Caching

The ArrayCache class reuses array allocations:

src/app/hex/[gameId]/ArrayCache.ts

export class ArrayCache {
  getFromOne(row: number[], x: number, value: number) {
    let newRow = row.slice();
    newRow[x] = value;
    return newRow;
  }
}

This reduces garbage collection pressure during deep searches.

Limitations and Future Improvements

The current implementation has some limitations:

Single Web Worker (multi-worker support is commented out)
No persistent transposition table
Limited depth on larger boards (9x9)
No opening book integration

Future enhancements could include:

Parallel worker pool for faster search
Monte Carlo Tree Search integration
Neural network evaluation
Endgame tablebase

Next Steps

Offline Mode

Learn about local gameplay implementation

Game Modes

Explore different ways to play

​Overview

Minimax Search

Position Scoring

Move Ranking

Win Detection

​Core Architecture

​Explorer Class

​Game Instance Types

​Position Evaluation

​Score Type

​Basic Heuristic

​Connection Analysis

​Minimax Search

​Tree Exploration

​Score Propagation

​Web Worker Integration

​Worker Communication

​Performance Tracking

​Move Recommendations

​UI Integration

​Grid Hashing

​Memory Optimization

​Limitations and Future Improvements

​Next Steps

Offline Mode

Game Modes

Overview

Core Architecture

Explorer Class

Game Instance Types

Position Evaluation

Score Type

Basic Heuristic

Connection Analysis

Minimax Search

Tree Exploration

Score Propagation

Web Worker Integration

Worker Communication

Performance Tracking

Move Recommendations

UI Integration

Grid Hashing

Memory Optimization

Limitations and Future Improvements

Next Steps