Game Engine - BeeHex

Game State Management

The game engine is built around three core classes that manage game state at different levels of complexity.

GameInstance Class

Location: src/app/hex/[gameId]/GameInstance.ts The GameInstance class represents an active game session with full player information.

class GameInstance {
  private game_id: GameId;
  private game_parameters: GameParameters | LocalGameParameters;
  private grid_array: Array<Array<number>>;
  private first_player_id: UserId;
  private second_player_id: UserId;
  private turn: number;
  private own_id: UserId;
}

Grid Representation

The game board is stored as a 2D array where:

0 = empty cell
1 = red player (connects left to right)
2 = blue player (connects top to bottom)

// Example 5x5 grid
[
  [0, 0, 1, 0, 0],
  [1, 0, 2, 0, 0],
  [0, 2, 1, 0, 0],
  [0, 0, 0, 2, 0],
  [0, 0, 0, 0, 1]
]

Key Methods

Move Validation
Turn Logic
State Updates

isValidMove(i: number, j: number): boolean {
  return this.grid_array[i][j] === 0;
}

Validates that a cell is empty before allowing a move.

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

isTurnOf(player_id: UserId): boolean {
  return player_id === this.getCurrentPlayer();
}

Odd turns = first player (red), even turns = second player (blue).

updateGameState(
  grid_array: Array<Array<number>>, 
  turn: number
) {
  console.log(`${grid_array.join("|")}`)
  this.grid_array = grid_array;
  this.turn = turn;
}

Updates the game state from server moves or AI calculations.

AI Engine Architecture

BeeHex implements a sophisticated minimax-based AI with parallel exploration using Web Workers.

Class Hierarchy

SimpleGameInstance

Location: src/app/hex/[gameId]/Algorithm.ts:7 Lightweight representation of a game state without evaluation.

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);
  }
}

Move Generation

getValidMoves(): Array<Coordinate> {
  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;
}

Immutable Move Application

The engine uses immutable state updates - each move creates a new game instance.

playMoveYX(y: number, x: number): SimpleGameInstance {
  if (this.isValidMove(y, x)) {
    let newGrid = this.grid.slice();
    let row = newGrid[y];
    newGrid[y] = array_cache.getFromOne(row, x, this.getCurrentPlayer());
    let newMoves = this.moves.slice();
    newMoves.push([y, x]);
    let newTurn = this.turn + 1;
    return new SimpleGameInstance(newGrid, newTurn, newMoves);
  } else {
    throw new Error("Invalid move");
  }
}

ScoredGameInstance

Location: src/app/hex/[gameId]/Algorithm.ts:95 Extends SimpleGameInstance with position evaluation and tree structure.

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

Score Propagation

Scores propagate up the tree using minimax logic:

updateScore() {
  if (this.nextInstances.size == 0) {
    console.warn("updateScore() called with no children")
  }
  
  let minMax;
  if (this.turn % 2 === 0) {
    // Blue player (minimize)
    minMax = (a, b) => a.getScore().isBiggerThan(b.getScore()) ? b : a
  } else {
    // Red player (maximize)
    minMax = (a, b) => a.getScore().isBiggerThan(b.getScore()) ? a : b
  }
  
  const nextInstances = this.nextInstances.values().toArray();
  const leadingInstance = nextInstances.reduce(minMax);
  let newScore = Score.fromRaw(leadingInstance.getScore().raw());
  
  if (newScore.isWinCountdown) {
    // Add 0.5 moves to countdown
    newScore.score += newScore.score > 0 ? 0.5 : -0.5;
  }
  
  this.grid = empty_array; // Clear grid to save memory
  this.completedBranch = leadingInstance.completedBranch;
  
  if (!currentScore.isEqualTo(newScore)) {
    this.score = newScore;
    this.leadingInstance = leadingInstance;
    this.updatePreviousInstances();
  }
}

Score Class

Location: src/app/hex/[gameId]/Algorithm.ts:783 Represents position evaluation with special handling for forced wins.

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

Score Semantics

Heuristic Scores
Win Countdown
Comparison Logic

When isWinCountdown = false, the score represents a heuristic evaluation:

Positive values: Red (player 1) is winning
Negative values: Blue (player 2) is winning
Magnitude: Distance from victory (lower = better for that player)

return new Score(player2Score[0] - player1Score[0], false);

When isWinCountdown = true, the score represents moves until forced win:

score = 0.5: Red wins immediately
score = -0.5: Blue wins immediately
score = 2.5: Red wins in 2.5 moves (2 complete turns)
score = -1.5: Blue wins in 1.5 moves (1 complete turn + 1 half turn)

if (player1Score[0] === 0) {
  return new Score(
    player1Score[1] + (instance.getTurn() % 2 === 0 ? 0.5 : 0), 
    true
  )
}

Custom comparison handles both heuristic and countdown scores:

isBiggerThan(other: Score): boolean {
  if (!this.isWinCountdown && !other.isWinCountdown) {
    return this.score > other.score;
  }
  if (this.isWinCountdown && !other.isWinCountdown) {
    return this.score > 0; // Positive win always better
  }
  if (!this.isWinCountdown && other.isWinCountdown) {
    return other.score < 0;
  }
  if (this.score * other.score < 0) {
    return this.score > other.score; // Different signs
  }
  // Same sign: closer to 0 is better
  return Math.abs(this.score) < Math.abs(other.score);
}

Position Evaluation Heuristic

Location: src/app/hex/[gameId]/Algorithm.ts:526 The basicHeuristic function evaluates positions using a sophisticated pathfinding algorithm.

Algorithm Overview

Calculate path costs

For each player, compute minimum cost to connect their edges using Dijkstra-style search.

Detect forced wins

If cost = 0, the player has already won. Return win countdown score.

Compute differential

Return player2_cost - player1_cost as heuristic evaluation.

Path Cost Calculation

function attributeScore(grid: number[][], player: number): [number, number] {
  let size = grid.length;
  let minCost = grid.length ** 2;
  let minBridges = grid.length ** 2;
  let hexagonsToCheck: Array<CheckableHexagon> = [];
  let checkedHexagons: Array<Coordinate> = [];
  
  // Initialize starting edge
  if (player === 1) { // Red: left edge
    for (let i = 0; i < grid.length; i++) {
      if (grid[i][0] === 1) {
        hexagonsToCheck.push([[i, 0], 0, 0]);
      } else if (grid[i][0] === 0) {
        // Empty cell costs 1, or 0 if bridge exists
        hexagonsToCheck.push([[i, 0], detectBridgeCost(i, 0), bridges]);
      }
    }
  }
  // ... (similar for player 2: top edge)
  
  // Dijkstra-style search
  while (hexagonsToCheck.length > 0) {
    hexagonsToCheck.sort((a, b) => b[1] - a[1]);
    let hexagon = hexagonsToCheck.pop()!;
    checkedHexagons.push(hexagon[0]);
    
    let surroundingHexagons = getSurroundingHexagons(size, hexagon[0][0], hexagon[0][1]);
    let freeHexagons = filterAntiHexagons(grid, surroundingHexagons, 3 - player);
    
    for (let surroundingHexagon of freeHexagons) {
      let cost = calculateMoveCost(hexagon, surroundingHexagon, grid, player);
      let bridges = isBridge ? hexagon[2] + 1 : hexagon[2];
      
      if (boundCheck === size - 1) { // Reached target edge
        if (cost < minCost) {
          minCost = cost;
          minBridges = bridges;
        }
      } else {
        hexagonsToCheck.push([surroundingHexagon, cost, bridges]);
      }
    }
  }
  
  return [minCost, minBridges];
}

Bridge Detection

A “bridge” is a connection pattern that allows jumping over opponent pieces without additional cost.

function getInnerBridgeHexagons(hex1: Coordinate, hex2: Coordinate): Array<Coordinate> {
  let diffY = hex2[0] - hex1[0];
  let diffX = hex2[1] - hex1[1];
  
  // Example: jump from (y,x) to (y+1,x+1) requires both (y,x+1) and (y+1,x) empty
  if (diffX === 1 && diffY === 1) {
    return [[y, x - 1], [y - 1, x]];
  }
  // ... (6 possible bridge patterns)
}

Explorer and Web Workers

Location: src/app/hex/[gameId]/Algorithm.ts:281 The Explorer class orchestrates parallel game tree search using Web Workers.

Explorer Architecture

class Explorer {
  private game: ScoredGameInstance;
  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 = new Worker(new URL("AlgorithmWorker.ts", import.meta.url));
    this.worker.addEventListener("message", this._workerCallback.bind(this));
    
    this.game = this.rateInstance(simpleGame);
    this.instances = new Map<GridHash, ScoredGameInstance>();
    this.instances.set(this.game.getGridHash(), this.game);
    
    this.mainInstances = this.populateMainInstances();
    this.sendNextInstanceToWorker();
  }
}

Exploration Strategy

Initialize root position

Create ScoredGameInstance from current board state and evaluate with heuristic.

Populate main instances

Generate all first-level moves as MainScoredGameInstance objects (special class that reports back to UI).

Explore second level

For each main instance, explore opponent replies to depth 2.

Send to worker

Identify best incomplete branch and send to Web Worker for deep exploration (2 more levels).

Process worker results

Receive explored game tree, reconstruct instance graph, propagate scores upward.

Update UI

Return top 10 moves with their scores and optimal continuations.

Repeat

Continue sending next best incomplete branch until tree is fully explored.

Worker Communication

Worker Code: src/app/hex/[gameId]/AlgorithmWorker.ts

// AlgorithmWorker.ts
self.addEventListener("message", (event) => {
  let packet = event.data as AlgorithmWorkerBoundGenericPacket;
  
  if (packet.type === AlgorithmWorkerBoundPacketType.EXPLORE_INSTANCE) {
    const game = ScoredGameInstance.fromRaw(packet.game);
    const resultMap = new Map<GridHash, RawScoredGameInstance>();
    const leaves: Array<GridHash> = [];
    
    // Explore 2 levels deep
    let nextInstances = explore(game);
    for (let nextInstance of nextInstances.values()) {
      resultMap.set(nextInstance.getGridHash(), nextInstance.raw());
      
      let furtherInstances = explore(nextInstance);
      for (let furtherInstance of furtherInstances.values()) {
        resultMap.set(furtherInstance.getGridHash(), furtherInstance.raw());
        leaves.push(furtherInstance.getGridHash());
      }
    }
    
    postMessage({
      type: AlgorithmExplorerBoundPacketType.RESULT,
      id: packet.id,
      result: { gameInstances: resultMap, leaves: leaves }
    });
  }
});

Performance Monitoring

// From Algorithm.ts:451
private _workerCallback(event: MessageEvent) {
  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, BeeHex can explore 10,000+ positions per second for 9x9 boards.

Recommended Move Format

interface RecommendedMove {
  coordinate: Coordinate;          // [y, x] of suggested move
  score: Score;                     // Evaluation of this move
  optimalRoute: Array<Coordinate>;  // Best continuation from this position
}

Example output from Explorer:

[
  {
    "coordinate": [4, 4],
    "score": { "score": -2, "isWinCountdown": false },
    "optimalRoute": [[4, 4], [3, 5], [5, 3], [4, 6]]
  },
  {
    "coordinate": [2, 3],
    "score": { "score": -1, "isWinCountdown": false },
    "optimalRoute": [[2, 3], [3, 2], [1, 4]]
  }
]

Next Steps

WebSocket Protocol

Learn about the multiplayer communication protocol and packet specifications

​Game State Management

​GameInstance Class

​Grid Representation

​Key Methods

​AI Engine Architecture

​Class Hierarchy

​SimpleGameInstance

​Move Generation

​Immutable Move Application

​ScoredGameInstance

​Score Propagation

​Score Class

​Score Semantics

​Position Evaluation Heuristic

​Algorithm Overview

​Path Cost Calculation

​Bridge Detection

​Explorer and Web Workers

​Explorer Architecture

​Exploration Strategy

​Worker Communication

​Performance Monitoring

​Recommended Move Format

​Next Steps

WebSocket Protocol

Game State Management

GameInstance Class

Grid Representation

Key Methods

AI Engine Architecture

Class Hierarchy

SimpleGameInstance

Move Generation

Immutable Move Application

ScoredGameInstance

Score Propagation

Score Class

Score Semantics

Position Evaluation Heuristic

Algorithm Overview

Path Cost Calculation

Bridge Detection

Explorer and Web Workers

Explorer Architecture

Exploration Strategy

Worker Communication

Performance Monitoring

Recommended Move Format

Next Steps