与えられた手牌をブロック（和了形）に分解するアルゴリズムについて（C++ 実装）

背景

麻雀の上がり（和了）において点数計算が必要となるが，それに欠かせないのが与えられた手牌をブロック（和了形）に分解するアルゴリズムである．ある手牌が複数のブロックへの分解に対応する場合があり，その中から最も点数が高くなるブロックへの分解を採用する必要がある．このことから，手牌からブロックへの分解は一筋縄ではいかない．本稿では，与えられた手牌をブロックに分解するアルゴリズムについて，大まかに3種類の方針があることを示し，これら3種類の方針が全て等価であることの数学的に厳密な証明を与える．

本稿で取り扱う問題の数学的定義

順子全体の集合，すなわち数字が3つ連続した数牌の集合を $S$ とおく．

$$S = \lbrace (i, i + 1, i + 2) \ |\ 0 \leq i < 7 \vee 9 \leq i < 16 \vee 18 \leq i < 25\rbrace$$

刻子全体の集合，すなわち同じ種類の牌3つの組の集合を $K$ とおく．

$$K = \lbrace (i, i, i) \ |\ 0 \leq i < 34\rbrace$$

雀頭全体の集合，すなわち同じ種類の牌2つの組の集合を $Q$ とおく．

$$Q = \lbrace (i, i)\ |\ 0 \leq i < 34\rbrace$$

本稿において，ブロックとは順子・刻子・雀頭の総称であるとする．また，ブロック全体の集合を $B$ とおく．

$$B = S \cup K \cup Q$$

$n$ 面子 $h$ 雀頭分解，もしくはブロック分解とは，ブロックの多重集合であるとする．ただし， $0 \leq n \leq 4, 0 \leq h \leq 1$，すなわち，面子の数（言い換えれば順子の数と刻子の数の和）は最大で $4$，雀頭の数は最大で $1$ とする．ブロック分解全体の集合を $\mathbb{D}$ とおく．

$$\mathbb{D} = \left\lbrace m \in B \to \mathbb{N}\ \middle|\ \sum_{x \in S \cup K} m(x) \leq 4 \wedge \sum_{x \in Q} m(x) \leq 1\right\rbrace$$

ブロック分解 $D \in \mathbb{D}$ に対して，その多重度を $m_D$ と書くことにする．

各々が4つずつある34種類の牌を適当に選んで構成できる組み合わせ全体を手牌空間 $\mathbb{H}$ と呼ぶことにする．

$$\mathbb{H} = \lbrace 0, 1, 2, 3, 4\rbrace^{34}$$

一萬1つだけからなる手牌空間の要素を $\mathbf{e}_0$，二萬1つだけからなる手牌空間の要素を $\mathbf{e}_1$，などとするなど， $\mathbf{e}_i$ $(0 \leq i <34)$ を以下のように定義する．

$$\mathbf{e}_i = (\text{$i$ 番目の要素だけが $1$ でそれ以外が $0$ であるような $\mathbb{H}$ の要素})$$

$B$ から $\mathbb{H}$ への写像 $g_B: B \to \mathbb{H}$ を以下で定義する．

$$g_B((i, i + 1, i + 2)) = \mathbf{e}_i + \mathbf{e}_{i + 1} + \mathbf{e}_{i + 2}\quad\text{ for all }\ (i, i + 1, i + 2) \in S$$
$$g_B((i, i, i)) = 3\mathbf{e}_i\quad\text{ for all }\ (i, i, i) \in K$$
$$g_B((i, i)) = 2\mathbf{e}_i\quad\text{ for all }\ (i, i) \in Q$$

$\mathbb{D}$ から $\mathbb{H}$ への写像 $g_\mathbb{D}: \mathbb{D} \to \mathbb{H}$ を以下で定義する．

$$g_\mathbb{D}(D) = \sum_{b \in B} m_D(b) g_B(b)\quad\text{ for all }\ D \in \mathbb{D}$$

定義（ブロック分解集合）

$\mathbf{h} \in \mathbb{H}$ に対して，そのブロック分解集合 $\mathbb{D}_\mathbf{h}$ を $\mathbb{D}_{\mathbf{h}} = \lbrace D \in \mathbb{D} \mid g_\mathbb{D}(D) = \mathbf{h} \rbrace$ で定義する．

以下，本稿において解くべき問題を，与えられた手牌 $\mathbf{h} \in \mathbb{H}$ が $n$ 面子 $h$ 雀頭に分解できるものとした時に， $\mathbf{h}$ のブロック分解集合 $\mathbb{D}_{\mathbf{h}}$ を求めるものであるとする．

一色手牌のブロック分解

以下，本稿では一色手牌のブロック分解についてのみ議論する．というのも，一色手牌のブロック分解についてのみ議論すれば一般的な手牌のブロック分解についてはほぼ自明となるからである．

ブロック分解のデータ表現

ブロック分解には大まかに分けて2通りのデータ表現が考えられる．それぞれ得失があるが，本稿では以下のうちの前者を主たるデータ表現として採用し，一部，後者を補助的に援用する．

ブロック分解をデータとして表現する方法の1つはブロックの配列として表現する方法である．すなわち，以下のような Blocks 型として表現する方法である．

class Block
{
public:
  enum struct Type
    : std::uint_fast8_t
  {
    shunzi = 0u,
    kezi   = 1u,
    gangzi = 2u,
    quetou = 3u,
  }; // enum struct Type

  Block(Type type, std::uint_fast8_t tile);

  Block(Block const &) = default;

  Block(Block &&) = default;

  Block &operator=(Block const &) = default;

  Block &operator=(Block &&) = default;

  Type getType() const;

  bool isShunzi() const;

  bool isKezi() const;

  bool isGangzi() const;

  bool isQuetou() const;

  std::uint_fast8_t getTile() const;

  bool operator==(Block const &other) const;

  bool operator!=(Block const &other) const;

  bool operator<(Block const &other) const;

private:
  std::uint_fast8_t pack_;
}; // class Block

using Blocks = std::vector<Block>;

ブロック分解をデータとして表現するもう1つの方法は， std::array<std::array<std::uint_fast8_t, 3u>, 34u> のような型を用いるものである．ここで，この型の変数 blocks に対して， blocks[i][0u] は i 番目の種類の牌を先頭する順子の数， blocks[i][1u] は i 番目の種類の牌からなる刻子の数， blocks[i][2u] は i 番目の種類の牌からなる雀頭の数，を各々表すものとする．

実装1（重複型バックトラック）

1つ目の実装方針は極めて実直なバックトラックである．この実装方針の例としては，例えば『対戦型麻雀ゲームAIのアルゴリズムと実装』に掲出のもの（ただし実装言語は JavaScript）が挙げられる．

この方針の欠点として，ブロックの並びが異なるがブロック分解としては同値なものをバックトラック中で重複して列挙してしまうというものが挙げられ，この問題に対する対処をバックトラック後に施す必要がある．

void decompose0Impl(
  std::uint_fast8_t i,
  std::uint_fast8_t h,
  std::array<std::uint_fast8_t, 9u> &single_color_hand,
  Blocks &blocks,
  std::vector<Blocks> &result)
{
  assert((i <= 9u));
  assert((h <= 1u));

  if (i == 9u) {
    result.push_back(blocks);
    return;
  }

  if (single_color_hand[i] >= 3u) {
    single_color_hand[i] -= 3u;
    blocks.emplace_back(Block::Type::kezi, i);
    decompose0Impl(i, h, single_color_hand, blocks, result);
    blocks.pop_back();
    single_color_hand[i] += 3u;
  }

  if (single_color_hand[i] >= 2u && h == 0u) {
    single_color_hand[i] -= 2u;
    blocks.emplace_back(Block::Type::quetou, i);
    decompose0Impl(i, h + 1u, single_color_hand, blocks, result);
    blocks.pop_back();
    single_color_hand[i] += 2u;
  }

  if (i + 2u < 9u && single_color_hand[i] >= 1u && single_color_hand[i + 1u] >= 1u && single_color_hand[i + 2u] >= 1u) {
    --single_color_hand[i];
    --single_color_hand[i + 1u];
    --single_color_hand[i + 2u];
    blocks.emplace_back(Block::Type::shunzi, i);
    decompose0Impl(i, h, single_color_hand, blocks, result);
    blocks.pop_back();
    ++single_color_hand[i + 2u];
    ++single_color_hand[i + 1u];
    ++single_color_hand[i];
  }

  if (single_color_hand[i] == 0u) {
    decompose0Impl(i + 1u, h, single_color_hand, blocks, result);
  }
}

std::vector<Blocks> decompose0(std::array<std::uint_fast8_t, 9u> const &single_color_hand)
{
  std::array<std::uint_fast8_t, 9u> single_color_hand_(single_color_hand);
  Blocks blocks;
  std::vector<Blocks> result;
  decompose0Impl(0u, 0u, single_color_hand_, blocks, result);
  for (Blocks &blocks : result) {
    std::sort(blocks.begin(), blocks.end());
  }
  std::sort(result.begin(), result.end());
  result.erase(std::unique(result.begin(), result.end()), result.cend());
  return result;
}

実装2（非重複型バックトラック）

2つ目の実装方針もバックトラックであるが，1つ目の実装方針の欠点である「ブロックの並びが異なるがブロック分解としては同値なものを重複して列挙してしまう」という点をバックトラック内で事前に排除する工夫を導入している点が異なる．

この実装方針においては，例えば注目している牌の枚数が4枚ならば「4つの順子を一気に抜き出すこと」「2つの順子と1つの雀頭を一気に抜き出すこと」「1つの順子と1つの刻子を一気に抜き出すこと」の3通りを試みる．注目している牌の枚数が3枚ならば，同様に，「3つの順子を一気に抜き出すこと」「1つの順子と1つの雀頭を一気に抜き出すこと」「1つの刻子を抜き出すこと」の3通りを試みる．このような実装によって1つ目の実装方針におけるブロックの抜き出し方の順番の曖昧性を事前に解消しておくのである．

inline constexpr std::array<std::array<std::uint_fast8_t, 3u>, 10u> stable{{
  {{4u, 0u, 0u}}, // 注目している牌の枚数が4枚ならば4つの順子を抜き出せるか試す．
  {{2u, 0u, 1u}}, // 注目している牌の枚数が4枚ならば2つの順子と1つの雀頭を抜き出せるか試す．
  {{1u, 1u, 0u}}, // 注目している牌の枚数が4枚ならば1つの順子と1つの刻子を抜き出せるか試す．
  {{3u, 0u, 0u}}, // 注目している牌の枚数が3枚ならば3つの順子を抜き出せるか試す．
  {{1u, 0u, 1u}}, // 注目している牌の枚数が3枚ならば1つの順子と1つの雀頭を抜き出せるか試す．
  {{0u, 1u, 0u}}, // 注目している牌の枚数が3枚ならば1つの刻子を抜き出せるか試す．
  {{2u, 0u, 0u}}, // 注目している牌の枚数が2枚ならば2つの順子を抜き出せるか試す．
  {{0u, 0u, 1u}}, // 注目している牌の枚数が2枚ならば1つの雀頭を抜き出せるか試す．
  {{1u, 0u, 0u}}, // 注目している牌の枚数が1枚ならば1つの順子を抜き出せるか試す．
  {{0u, 0u, 0u}}, // 注目している牌の枚数が0枚ならば何も抜き出さない．
}};

void decompose1Impl(
  std::uint_fast8_t const i,
  std::uint_fast8_t const h,
  std::array<std::uint_fast8_t, 9u> &single_color_hand,
  Blocks &blocks,
  std::vector<Blocks> &result)
{
  assert((i <= 9u));
  assert((h <= 1u));

  if (i == 9u) {
    result.push_back(blocks);
    return;
  }

  std::uint_fast8_t const x = i + 1u < 9u ? single_color_hand[i + 1u] : 0u;
  std::uint_fast8_t const y = i + 2u < 9u ? single_color_hand[i + 2u] : 0u;
  for (std::uint_fast8_t s = 0u; s < stable.size(); ++s) {
    std::uint_fast8_t const hh = stable[s][2u];
    std::uint_fast8_t const n = stable[s][0u] + 3u * stable[s][1u] + 2u * stable[s][2u];
    std::uint_fast8_t const xy = stable[s][0u];
    if (h + hh > 1u) {
      continue;
    }
    if (n != single_color_hand[i]) {
      continue;
    }
    if (xy > x) {
      continue;
    }
    if (xy > y) {
      continue;
    }

    single_color_hand[i] -= n;
    if (i + 1u < 9u) {
      single_color_hand[i + 1u] -= xy;
    }
    if (i + 2u < 9u) {
      single_color_hand[i + 2u] -= xy;
    }
    for (std::uint_fast8_t j = 0u; j < xy; ++j) {
      blocks.emplace_back(Block::Type::shunzi, i);
    }
    if (stable[s][1u] == 1u) {
      blocks.emplace_back(Block::Type::kezi, i);
    }
    if (stable[s][2u] == 1u) {
      blocks.emplace_back(Block::Type::quetou, i);
    }
    decompose1Impl(i + 1u, h + hh, single_color_hand, blocks, result);
    if (stable[s][2u] == 1u) {
      blocks.pop_back();
    }
    if (stable[s][1u] == 1u) {
      blocks.pop_back();
    }
    for (std::uint_fast8_t j = 0u; j < xy; ++j) {
      blocks.pop_back();
    }
    if (i + 2u < 9u) {
      single_color_hand[i + 2u] += xy;
    }
    if (i + 1u < 9u) {
      single_color_hand[i + 1u] += xy;
    }
    single_color_hand[i] += n;
  }
}

std::vector<Blocks> decompose1(std::array<std::uint_fast8_t, 9u> const &single_color_hand)
{
  std::array<std::uint_fast8_t, 9u> single_color_hand_(single_color_hand);
  Blocks blocks;
  std::vector<Blocks> result;
  decompose1Impl(0u, 0u, single_color_hand_, blocks, result);
  return result;
}

実装3（雀頭位置列挙 + 三連刻変換）

3つ目の実装方針はバックトラックとは根本的に異なる．

まず，与えられた一色手牌の枚数が3を法として2と合同であるならば，この色の手牌の中には必ず雀頭が存在していなければならない．ただし，その位置には曖昧性がありうるため，可能な雀頭の位置を全て列挙して各々の位置に雀頭があると仮定した場合のブロック分解を試みる．なお，雀頭の位置は『和了(聴牌)になるための必要条件』の定理2によって3ヶ所にまで絞り込むことができる．

また，ブロック分解において，ある種類の牌が3枚以上あれば常に刻子として抜き出す．この抜き出し方は3枚以上ある牌が3つ連続していた場合に常に三連刻（3つの連続した刻子）として取り出してしまう．しかし，この牌の並びには一色三順（同一の順子3組）として取り出す曖昧性が存在する．この曖昧性を事後的に列挙するのがこの実装方針の核心部分である．

上記の「雀頭位置の曖昧性」と「三連刻・一色三順の曖昧性」だけを考慮するのがこの実装方針である．このままでは，他の種類の曖昧性がある不安を拭えないかもしれないと思われそうだが，実際にはこの2つの曖昧性の考慮だけで必要十分であるということが数学的に厳密に証明できる．つまりこの実装方針は正しいというのが本稿の結論である．

この実装方針の例としては，例えば『一色手の面子分解パターン列挙』に掲出のものが挙げられる．

bool decompose2Impl_(
  std::array<std::uint_fast8_t, 9u> &single_color_hand,
  std::uint_fast8_t quetou,
  std::array<std::array<std::uint_fast8_t, 3u>, 34u> &result)
{
  for (std::uint_fast8_t i = 0u; i < 9u; ++i) {
    if (single_color_hand[i] == 4u) {
      if (quetou == i) {
        if (i + 2u >= 9u || single_color_hand[i + 1u] < 2u || single_color_hand[i + 2u] < 2u) {
          return false;
        }
        single_color_hand[i] -= 4u;
        single_color_hand[i + 1u] -= 2u;
        single_color_hand[i + 2u] -= 2u;
        result[i][0u] += 2u;
        ++result[i][2u];
        continue;
      }

      if (i + 2u >= 9u || single_color_hand[i + 1u] == 0u || single_color_hand[i + 2u] == 0u) {
        return false;
      }
      single_color_hand[i] -= 4u;
      --single_color_hand[i + 1u];
      --single_color_hand[i + 2u];
      ++result[i][0u];
      ++result[i][1u];
      continue;
    }

    if (single_color_hand[i] == 3u) {
      if (quetou == i) {
        if (i + 2u >= 9u || single_color_hand[i + 1u] == 0u || single_color_hand[i + 2u] == 0u) {
          return false;
        }
        single_color_hand[i] -= 3u;
        --single_color_hand[i + 1u];
        --single_color_hand[i + 2u];
        ++result[i][0u];
        ++result[i][2u];
        continue;
      }

      single_color_hand[i] -= 3u;
      ++result[i][1u];
      continue;
    }

    if (single_color_hand[i] == 2u) {
      if (quetou == i) {
        single_color_hand[i] -= 2u;
        ++result[i][2u];
        continue;
      }

      if (i + 2u >= 9u || single_color_hand[i + 1u] < 2u || single_color_hand[i + 2u] < 2u) {
        return false;
      }
      single_color_hand[i] -= 2u;
      single_color_hand[i + 1u] -= 2u;
      single_color_hand[i + 2u] -= 2u;
      result[i][0u] += 2u;
      continue;
    }

    if (single_color_hand[i] == 1u) {
      if (i + 2u >= 9u || single_color_hand[i + 1u] == 0u || single_color_hand[i + 2u] == 0u) {
        return false;
      }
      --single_color_hand[i];
      --single_color_hand[i + 1u];
      --single_color_hand[i + 2u];
      ++result[i][0u];
      continue;
    }
  }

  return true;
}

bool decompose2Impl(
  std::array<std::uint_fast8_t, 9u> const &single_color_hand,
  std::uint_fast8_t const quetou,
  std::vector<Blocks> &result)
{
  std::array<std::uint_fast8_t, 9u> single_color_hand_(single_color_hand);
  std::array<std::array<std::uint_fast8_t, 3u>, 34u> result_{};
  bool success = decompose2Impl_(single_color_hand_, quetou, result_);

  for (std::uint_fast8_t i = 0u; i < 34u; ++i) {
    while (result_[i][0u] >= 1u) {
      for (Blocks &blocks : result) {
        blocks.emplace_back(Block::Type::shunzi, i);
      }
      --result_[i][0u];
    }
    if (result_[i][1u] == 1u) {
      if (i + 3u < 9u && result_[i + 1u][1u] == 1u && result_[i + 2u][1u] == 1u && result_[i + 3u][1u] == 1u) {
        std::size_t const original_result_size = result.size();
        result.reserve(3u * original_result_size);
        for (std::size_t j = 0u; j < original_result_size; ++j) {
          result.push_back(result[j]);
        }
        for (std::size_t j = 0u; j < original_result_size; ++j) {
          result.push_back(result[j]);
        }
        for (std::uint_fast8_t j = 0u; j < original_result_size; ++j) {
          result[j].emplace_back(Block::Type::kezi, i);
          result[j].emplace_back(Block::Type::kezi, i + 1u);
          result[j].emplace_back(Block::Type::kezi, i + 2u);
          result[j].emplace_back(Block::Type::kezi, i + 3u);
        }
        for (std::uint_fast8_t j = original_result_size; j < 2u * original_result_size; ++j) {
          result[j].emplace_back(Block::Type::kezi, i);
          result[j].emplace_back(Block::Type::shunzi, i + 1u);
          result[j].emplace_back(Block::Type::shunzi, i + 1u);
          result[j].emplace_back(Block::Type::shunzi, i + 1u);
        }
        for (std::uint_fast8_t j = 2u * original_result_size; j < result.size(); ++j) {
          result[j].emplace_back(Block::Type::shunzi, i);
          result[j].emplace_back(Block::Type::shunzi, i);
          result[j].emplace_back(Block::Type::shunzi, i);
          result[j].emplace_back(Block::Type::kezi, i + 3u);
        }
        --result_[i][1u];
        --result_[i + 1u][1u];
        --result_[i + 2u][1u];
        --result_[i + 3u][1u];
      }
      else if (i + 2u < 9u && result_[i + 1u][1u] == 1u && result_[i + 2u][1u] == 1u) {
        std::size_t const original_result_size = result.size();
        result.reserve(2u * original_result_size);
        for (Blocks &blocks : result) {
          result.push_back(blocks);
        }
        for (std::uint_fast8_t j = 0u; j < original_result_size; ++j) {
          result[j].emplace_back(Block::Type::kezi, i);
          result[j].emplace_back(Block::Type::kezi, i + 1u);
          result[j].emplace_back(Block::Type::kezi, i + 2u);
        }
        for (std::uint_fast8_t j = original_result_size; j < result.size(); ++j) {
          result[j].emplace_back(Block::Type::shunzi, i);
          result[j].emplace_back(Block::Type::shunzi, i);
          result[j].emplace_back(Block::Type::shunzi, i);
        }
        --result_[i][1u];
        --result_[i + 1u][1u];
        --result_[i + 2u][1u];
      }
      else {
        for (Blocks &blocks : result) {
          blocks.emplace_back(Block::Type::kezi, i);
        }
        --result_[i][1u];
      }
    }
    if (result_[i][2u] == 1u) {
      for (Blocks &blocks : result) {
        blocks.emplace_back(Block::Type::quetou, i);
      }
      --result_[i][2u];
    }
  }

  return success;
}

std::vector<Blocks> decompose2(std::array<std::uint_fast8_t, 9u> const &single_color_hand)
{
  std::vector<Blocks> result;
  {
    std::uint_fast8_t const n = std::accumulate(single_color_hand.cbegin(), single_color_hand.cend(), 0u);
    if (n % 3u == 0u) {
      result.emplace_back();
      bool success = decompose2Impl(single_color_hand, UINT_FAST8_MAX, result);
      assert((success));
    }
    else {
      std::uint_fast8_t const s = [&]() {
        std::uint_fast8_t s = 0u;
        for (std::uint_fast8_t i = 0u; i < 9u; ++i) {
          s += i * single_color_hand[i];
        }
        return s;
      }();
      for (std::uint_fast8_t quetou = (2u * s) % 3u; quetou < 9u; quetou += 3u) {
        std::vector<Blocks> result_;
        result_.emplace_back();
        if (decompose2Impl(single_color_hand, quetou, result_)) {
          result.insert(result.cend(), result_.cbegin(), result_.cend());
        }
      }
    }
  }
  return result;
}

等価性証明

定理（等価性）

上記3つのアルゴリズムは全て等価，すなわち同じ結果を返す．

証明

手牌空間 $\mathbb{H}$ は高々有限なので，対象となる手牌空間の全要素各々に対して上記3つのアルゴリズムが等価であることを示せば十分である．■