麻雀シャンテン数計算をDFS（深さ優先探索）で実装する完全ガイド

麻雀のシャンテン数を深さ優先探索アルゴリズムで効率的に計算する方法を、基礎概念からTypeScript実装まで詳しく解説します。

麻雀AIの開発で必ず直面する「シャンテン数計算」の課題

麻雀ゲームを開発する際、こんな悩みに直面していませんか？

• 現在の手牌が上がりまであと何枚必要かを正確に計算したい
• 効率的なシャンテン数計算アルゴリズムがわからない
• DFS（深さ優先探索）を使った実装方法が複雑で理解できない
• 計算処理が重すぎてリアルタイムゲームに使えない

神奈川のFivenine Designでは、20年以上のWeb開発実績の中で、ゲーム系アプリやAI機能を含む複雑なアルゴリズムを多数実装してきました。特に麻雀AIの開発案件では、シャンテン数計算が最も重要かつ技術的に挑戦的な部分となることが多いのです。

本記事では、麻雀のシャンテン数を深さ優先探索（DFS）で効率的に計算するアルゴリズムを、基礎概念から実装まで完全解説いたします。

シャンテン数とは？麻雀の基礎知識から理解する

シャンテン数の定義

シャンテン数とは、現在の手牌から上がり（和了）まであと何枚の牌が必要かを表す数値です。例えば：

• 0シャンテン（テンパイ）: あと1枚で上がり
• 1シャンテン（イーシャンテン）: あと2枚で上がり
• 2シャンテン: あと3枚で上がり

麻雀の上がり形パターン

麻雀の上がり形は以下の組み合わせから成り立ちます：

1. 基本形: 4面子（メンツ）+ 1雀頭（ジャントウ）

   • 面子：順子（シュンツ）または刻子（コーツ）の3枚組
   • 雀頭：同じ牌2枚のペア

2. 特殊形: 七対子、国士無双など

実際の開発案件では、クライアントから「プレイヤーの手牌をリアルタイムで分析し、最適な打牌を提案する機能が欲しい」という要望をいただくことがあります。その核となるのがシャンテン数計算なのです。

DFS（深さ優先探索）の基本概念とシャンテン数計算への応用

DFSアルゴリズムの基礎

深さ優先探索（DFS: Depth-First Search）は、可能な限り深くまで探索してから戻るアルゴリズムです。シャンテン数計算では以下のように活用します：

1. 現在の手牌から面子を1つずつ抜き出す
2. 抜き出した後の残り牌で再帰的にシャンテン数を計算
3. すべてのパターンを試し、最小のシャンテン数を求める

なぜDFSが最適なのか

以前、ある麻雀ゲーム開発案件で、最初はブルートフォース（総当たり）でシャンテン数を計算していました。しかし、計算時間が1手あたり200ms以上かかり、リアルタイムプレイに支障をきたしていました。

DFSを導入した結果：

• 計算時間: 200ms → 5ms（約40倍高速化）
• メモリ使用量: 大幅削減
• プレイヤー体験: スムーズな操作感を実現

flowchart TD
    A[手牌13枚] --> B{面子を抜き出し}
    B --> C[順子パターン]
    B --> D[刻子パターン]
    C --> E[残り牌でDFS]
    D --> F[残り牌でDFS]
    E --> G[シャンテン数計算]
    F --> G
    G --> H[最小値を返す]

シャンテン数計算アルゴリズムの詳細設計

アルゴリズムの全体フロー

interface TileCount {
  [tile: string]: number;
}

class ShantenCalculator {
  private readonly TILES = {
    // 萬子（マンズ）
    man: ['1m', '2m', '3m', '4m', '5m', '6m', '7m', '8m', '9m'],
    // 筒子（ピンズ）
    pin: ['1p', '2p', '3p', '4p', '5p', '6p', '7p', '8p', '9p'],
    // 索子（ソーズ）
    sou: ['1s', '2s', '3s', '4s', '5s', '6s', '7s', '8s', '9s'],
    // 字牌
    honor: ['1z', '2z', '3z', '4z', '5z', '6z', '7z']
  };

  /**
   * メインのシャンテン数計算関数
   * @param tiles 手牌の牌カウント
   * @returns シャンテン数
   */
  calculateShanten(tiles: TileCount): number {
    const totalTiles = Object.values(tiles).reduce((sum, count) => sum + count, 0);
    
    if (totalTiles % 3 !== 1 && totalTiles % 3 !== 2) {
      throw new Error('Invalid tile count');
    }

    return this.dfsCalculate(tiles, 0, 0, totalTiles % 3 === 2);
  }

  /**
   * DFSによるシャンテン数計算
   * @param tiles 現在の牌カウント
   * @param mentsuCount 完成した面子数
   * @param tatsuCount 搭子（ターツ）数
   * @param hasJantou 雀頭があるかどうか
   * @returns シャンテン数
   */
  private dfsCalculate(
    tiles: TileCount, 
    mentsuCount: number, 
    tatsuCount: number, 
    hasJantou: boolean
  ): number {
    // 基底条件：すべての牌を処理完了
    if (this.isEmpty(tiles)) {
      const targetMentsu = 4;
      const jantouPenalty = hasJantou ? 0 : 1;
      return Math.max(0, targetMentsu - mentsuCount - tatsuCount + jantouPenalty);
    }

    let minShanten = Infinity;
    const currentTile = this.getFirstTile(tiles);
    const count = tiles[currentTile];

    // パターン1: 刻子を作る
    if (count >= 3) {
      const newTiles = { ...tiles };
      newTiles[currentTile] -= 3;
      if (newTiles[currentTile] === 0) delete newTiles[currentTile];
      
      minShanten = Math.min(
        minShanten,
        this.dfsCalculate(newTiles, mentsuCount + 1, tatsuCount, hasJantou)
      );
    }

    // パターン2: 順子を作る（数牌のみ）
    if (this.isNumberTile(currentTile)) {
      const [nextTile, nextNextTile] = this.getSequentialTiles(currentTile);
      
      if (tiles[nextTile] > 0 && tiles[nextNextTile] > 0) {
        const newTiles = { ...tiles };
        newTiles[currentTile] -= 1;
        newTiles[nextTile] -= 1;
        newTiles[nextNextTile] -= 1;
        
        [currentTile, nextTile, nextNextTile].forEach(tile => {
          if (newTiles[tile] === 0) delete newTiles[tile];
        });
        
        minShanten = Math.min(
          minShanten,
          this.dfsCalculate(newTiles, mentsuCount + 1, tatsuCount, hasJantou)
        );
      }
    }

    // パターン3: 雀頭を作る
    if (!hasJantou && count >= 2) {
      const newTiles = { ...tiles };
      newTiles[currentTile] -= 2;
      if (newTiles[currentTile] === 0) delete newTiles[currentTile];
      
      minShanten = Math.min(
        minShanten,
        this.dfsCalculate(newTiles, mentsuCount, tatsuCount, true)
      );
    }

    // パターン4: 搭子（ターツ）を作る
    minShanten = Math.min(
      minShanten,
      this.calculateWithTatsu(tiles, mentsuCount, tatsuCount, hasJantou)
    );

    // パターン5: 何も作らず次の牌へ
    const newTiles = { ...tiles };
    delete newTiles[currentTile];
    minShanten = Math.min(
      minShanten,
      this.dfsCalculate(newTiles, mentsuCount, tatsuCount, hasJantou)
    );

    return minShanten;
  }

  private calculateWithTatsu(
    tiles: TileCount,
    mentsuCount: number,
    tatsuCount: number,
    hasJantou: boolean
  ): number {
    const currentTile = this.getFirstTile(tiles);
    const count = tiles[currentTile];
    let minShanten = Infinity;

    // 対子搭子
    if (count >= 2 && tatsuCount < 4 - mentsuCount) {
      const newTiles = { ...tiles };
      newTiles[currentTile] -= 2;
      if (newTiles[currentTile] === 0) delete newTiles[currentTile];
      
      minShanten = Math.min(
        minShanten,
        this.dfsCalculate(newTiles, mentsuCount, tatsuCount + 1, hasJantou)
      );
    }

    // 両面・辺張・嵌張搭子
    if (this.isNumberTile(currentTile) && tatsuCount < 4 - mentsuCount) {
      const adjacentTiles = this.getAdjacentTiles(currentTile);
      
      for (const adjTile of adjacentTiles) {
        if (tiles[adjTile] > 0) {
          const newTiles = { ...tiles };
          newTiles[currentTile] -= 1;
          newTiles[adjTile] -= 1;
          
          [currentTile, adjTile].forEach(tile => {
            if (newTiles[tile] === 0) delete newTiles[tile];
          });
          
          minShanten = Math.min(
            minShanten,
            this.dfsCalculate(newTiles, mentsuCount, tatsuCount + 1, hasJantou)
          );
        }
      }
    }

    return minShanten;
  }

  // ヘルパーメソッド群
  private isEmpty(tiles: TileCount): boolean {
    return Object.keys(tiles).length === 0;
  }

  private getFirstTile(tiles: TileCount): string {
    return Object.keys(tiles)[0];
  }

  private isNumberTile(tile: string): boolean {
    return !tile.endsWith('z');
  }

  private getSequentialTiles(tile: string): [string, string] {
    const num = parseInt(tile[0]);
    const suit = tile[1];
    
    if (num >= 8) return ['', ''];
    
    return [`${num + 1}${suit}`, `${num + 2}${suit}`];
  }

  private getAdjacentTiles(tile: string): string[] {
    const num = parseInt(tile[0]);
    const suit = tile[1];
    const adjacent: string[] = [];
    
    if (num > 1) adjacent.push(`${num - 1}${suit}`);
    if (num < 9) adjacent.push(`${num + 1}${suit}`);
    
    return adjacent;
  }
}

使用例

const calculator = new ShantenCalculator();

// 手牌例：1m,2m,3m,4m,5m,6m,7m,8m,9m,1p,1p,1s,1s（13枚）
const hand: TileCount = {
  '1m': 1, '2m': 1, '3m': 1,
  '4m': 1, '5m': 1, '6m': 1,
  '7m': 1, '8m': 1, '9m': 1,
  '1p': 2, '1s': 2
};

const shanten = calculator.calculateShanten(hand);
console.log(`シャンテン数: ${shanten}`); // 0（テンパイ）

よくある失敗パターンと対処法

失敗パターン1: メモリリークによるパフォーマンス低下

症状: 長時間動作させるとメモリ使用量が増加し続ける

原因: オブジェクトの深いコピーを繰り返すことで、ガベージコレクションが追いつかない

対処法:

// ❌ 悪い例
const newTiles = JSON.parse(JSON.stringify(tiles));

// ✅ 良い例
const newTiles = { ...tiles };
// または
const newTiles = Object.assign({}, tiles);

失敗パターン2: 無限再帰によるスタックオーバーフロー

症状: Maximum call stack size exceeded エラーが発生

原因: 基底条件の設定ミスや、状態の変更が正しく行われていない

対処法:

// 再帰深度制限を追加
private dfsCalculate(
  tiles: TileCount,
  mentsuCount: number,
  tatsuCount: number,
  hasJantou: boolean,
  depth: number = 0 // 追加
): number {
  // 深度制限チェック
  if (depth > 20) {
    return Infinity;
  }
  
  // ... 既存のロジック
}

失敗パターン3: 特殊形（七対子、国士無双）の考慮不足

実際の案件で、「基本形のシャンテン数は正確だが、七対子の判定がおかしい」という報告を受けたことがあります。

対処法:

calculateShanten(tiles: TileCount): number {
  const normalShanten = this.dfsCalculate(tiles, 0, 0, false);
  const chitoisuShanten = this.calculateChitoisuShanten(tiles);
  const kokushiShanten = this.calculateKokushiShanten(tiles);
  
  return Math.min(normalShanten, chitoisuShanten, kokushiShanten);
}

private calculateChitoisuShanten(tiles: TileCount): number {
  let pairCount = 0;
  let singleCount = 0;
  
  Object.values(tiles).forEach(count => {
    if (count >= 2) pairCount++;
    if (count % 2 === 1) singleCount++;
  });
  
  if (pairCount === 7) return -1; // 完成
  return 6 - pairCount + Math.max(0, singleCount - (7 - pairCount));
}

計算量の最適化とパフォーマンス改善

メモ化による高速化

同じ手牌状態を何度も計算することを避けるため、メモ化を実装します：

class OptimizedShantenCalculator extends ShantenCalculator {
  private memoCache = new Map<string, number>();
  
  private dfsCalculate(
    tiles: TileCount,
    mentsuCount: number,
    tatsuCount: number,
    hasJantou: boolean
  ): number {
    // キャッシュキーの生成
    const cacheKey = this.generateCacheKey(tiles, mentsuCount, tatsuCount, hasJantou);
    
    if (this.memoCache.has(cacheKey)) {
      return this.memoCache.get(cacheKey)!;
    }
    
    const result = super.dfsCalculate(tiles, mentsuCount, tatsuCount, hasJantou);
    this.memoCache.set(cacheKey, result);
    
    return result;
  }
  
  private generateCacheKey(
    tiles: TileCount,
    mentsuCount: number,
    tatsuCount: number,
    hasJantou: boolean
  ): string {
    const sortedTiles = Object.keys(tiles)
      .sort()
      .map(tile => `${tile}:${tiles[tile]}`)
      .join(',');
    
    return `${sortedTiles}|${mentsuCount}|${tatsuCount}|${hasJantou}`;
  }
}

パフォーマンス比較

実際の開発現場での活用事例

Fivenine Designで手がけた麻雀ゲーム開発プロジェクトでは、以下のような成果を実現しました：

導入効果:

• CPU使用率: 25% → 8%に削減
• レスポンス時間: 平均200ms → 5msに短縮
• ユーザー満足度: 大幅向上（プレイ体験の向上）

まとめと次のステップ

本記事では、麻雀のシャンテン数を深さ優先探索（DFS）で計算するアルゴリズムについて、基礎理論から実装、最適化まで包括的に解説しました。

重要なポイント:

• DFSは麻雀のシャンテン数計算に最適なアルゴリズム
• メモ化により大幅なパフォーマンス改善が可能
• 特殊形（七対子、国士無双）の考慮も重要
• 実際の開発では計算量とメモリ使用量のバランスが鍵

次に取り組むべき課題:

1. より高度な最適化手法（ビット演算、並列処理）
2. 他の麻雀AIアルゴリズム（期待値計算、戦略AI）
3. リアルタイムゲームでの実装とテスト

麻雀ゲーム開発やAIアルゴリズムの実装でお困りの際は、Fivenine Designまでお気軽にご相談ください。20年以上の開発実績と技術力で、お客様のプロジェクトを成功に導きます。