将棋 Shogi AI - Alpha-Beta Pruning

Interactive demonstration of minimax with alpha-beta pruning in Japanese Chess

🤖 AI Performance

Nodes Evaluated
0
Nodes Pruned
0
Pruning Rate
0%
Time (ms)
0

📊 Analysis

Position Value:
+0.00
Best AI Move:
None

⚡ Status

Move Count:
0
Game State:
Ready
Last Move:
None
Current Turn: Game not started
Click "New Game" to begin your Shogi adventure

☖ AI Captured Pieces (Gote)

No captures yet
9
8
7
6
5
4
3
2
1
a
b
c
d
e
f
g
h
i

☗ Player Captured Pieces (Sente)

No captures yet

📜 Move History

No moves recorded yet

📋 Game Events

Game not started

About This Demo

Alpha-Beta Pruning

An optimization for the minimax algorithm. It reduces the number of nodes evaluated by eliminating branches that won't influence the final decision.

Key Benefits:

  • Reduces computation time
  • Maintains optimal play
  • Enables deeper search

How It Works

The algorithm maintains two values: Alpha (best for maximizing player) and Beta (best for minimizing player). When Alpha ≥ Beta, the branch is pruned.

Process:

  • Explore game tree depth-first
  • Update Alpha/Beta values
  • Prune when Alpha ≥ Beta
  • Return best move

Complexity Analysis

Time Complexity:

Best: O(b^(d/2))
Worst: O(b^d)

Space Complexity:

O(b*d)

Alpha-Beta Pruning Pseudocode

Main Algorithm

function alphaBeta(node, depth, a, b, isMax):
    if depth == 0 or node.isTerminal:
      return evaluate(node)

    if isMax:
      v = -∞
      for child in node.children:
        v = max(v, alphaBeta(child, d-1, a, b, false))
        a = max(a, v)
        if b <= a: break // Prune
      return v
    else:
      v = +∞
      for child in node.children:
        v = min(v, alphaBeta(child, d-1, a, b, true))
        b = min(b, v)
        if b <= a: break // Prune
      return v

Initial Call

function findBestMove(pos, depth):
    bestMove = null
    bestVal = -∞, a = -∞, b = +∞

    for move in getLegalMoves(pos):
      newPos = makeMove(pos, move)
      val = alphaBeta(newPos, d-1, a, b, false)

      if val > bestVal:
        bestVal = val
        bestMove = move
      a = max(a, val)
    return bestMove

🏯 Shogi - Japanese Chess

Game Overview

A two-player strategy game where captured pieces can be returned to the board as your own, creating dynamic and complex gameplay.

Key Features:

  • 9×9 board, 40 pieces
  • Piece drops (re-entry)
  • Piece promotion

Basic Rules

Objective: Checkmate the opponent's King.

Captures: Captured pieces join your "hand" for dropping.

Promotion: Pieces can promote in the furthest 3 ranks.

How to Play