disc_wait.md

向聴数・不要牌・有効牌テーブル

概要

向聴数・不要牌・有効牌を同時に計算するツールで使われる数牌用のテーブル(index_dw_s.txt)を, 01-BFSにより高速に作成するためのプログラム. 字牌用のテーブルも同様にして作成できる.

ソースコード

C++20 で記述.

#include <deque>
#include <functional>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
constexpr int INF = 1 << 10;
using Vec = std::vector<int>;
using Hands = std::vector<Vec>;

struct Prop {
  int sht;  // 距離
  int disc; // 不要牌
  int wait; // 有効牌
};

using Dist = std::vector<Prop>;

// 手牌生成(全幅)
template <int N>
void generate(int n, int m, std::function<void(std::vector<int>&)> func)
{
  static Vec h(N);

  if (n == N) {
    func(h);
  }
  else {
    for (int i = std::max(0, m - 4 * (N - 1 - n)); i <= std::min(4, m); ++i) {
      h[n] = i;
      generate<N>(n + 1, m - i, func);
    }
  }
}

// 3N和了判定
bool iswh0(const int* h)
{
  int a = h[0], b = h[1];

  for (int i = 0; i < 7; ++i) {
    if (int r = a % 3; b >= r && h[i + 2] >= r) {
      a = b - r;
      b = h[i + 2] - r;
    }
    else return false;
  }
  return a % 3 == 0 && b % 3 == 0;
}

// 3N+2和了判定
bool iswh2(int* h)
{
  int s = 0;

  for (int i = 0; i < 9; ++i) {
    s += i * h[i];
  }

  for (int p = s * 2 % 3; p < 9; p += 3) {
    if (h[p] >= 2) {
      h[p] -= 2;

      if (iswh0(h)) {
        h[p] += 2;
        return true;
      }
      else h[p] += 2;
    }
  }
  return false;
}

int index(const std::vector<int>& h)
{
  return std::accumulate(h.begin(), h.end(), 0, [](int x, int y) { return 5 * x + y; });
}

// 01-BFS
Dist bfs(const Hands& hands)
{
  Dist dist(1953125 /* = 5^9 */, {INF, 0, 0});
  std::deque<Vec> deq;

  for (const auto& hand : hands) {
    dist[index(hand)] = {0, 0, 0};
    deq.push_back(hand);
  }

  while (deq.size()) {
    auto hand = deq.front();

    deq.pop_front();

    for (int i = 0; i < 9; ++i) {
      if (hand[i] < 4) {
        const auto& after = dist[index(hand)];

        ++hand[i];

        auto& before = dist[index(hand)];

        if (const auto comp = after.sht <=> before.sht; comp < 0) {
          before.sht = after.sht;
          before.disc = after.disc | (1 << i);
          before.wait = after.wait;
          deq.push_front(hand);
        }
        else if (comp == 0) {
          before.disc |= after.disc | (1 << i);
          before.wait |= after.wait;
        }

        --hand[i];
      }

      if (hand[i] > 0) {
        const auto& after = dist[index(hand)];

        --hand[i];

        auto& before = dist[index(hand)];

        if (const auto comp = after.sht + 1 <=> before.sht; comp < 0) {
          before.sht = after.sht + 1;
          before.disc = after.disc;
          before.wait = after.wait | (1 << i);
          deq.push_back(hand);
        }
        else if (comp == 0) {
          before.disc |= after.disc;
          before.wait |= after.wait | (1 << i);
        }

        ++hand[i];
      }
    }
  }

  return dist;
}

int main()
{
  std::vector<Dist> dists(10);
  std::ofstream fout("result.txt");

  for (int m = 0; m <= 4; ++m) {
    Hands hands0;
    Hands hands2;

    generate<9>(0, 3 * m, [&](std::vector<int>& h) {
      if (iswh0(h.data())) {
        hands0.push_back(h);
      }
    });

    generate<9>(0, 3 * m + 2, [&](std::vector<int>& h) {
      if (iswh2(h.data())) {
        hands2.push_back(h);
      }
    });

    dists[m] = bfs(hands0);
    dists[m + 5] = bfs(hands2);
  }

  for (int i = 0; i < 1953125 /* = 5^9 */; ++i) {
    for (int j = 0; j < 10; ++j) {
      const auto [sht, disc, wait] = dists[j][i];

      fout << (sht | (disc << 4) | (wait << 13)) << " ";
    }

    fout << "\n";
  }

  return 0;
}

結果

CPU: 2.3 GHz, RAM: 16 GB の環境で実行したところ, 約 20 秒でテーブルをファイル(result.txt)に出力した. result.txtとindex_dw_s.txtが同一のファイルであることを確かめた.

$ diff -s result.txt index_dw_s.txt
Files result.txt and index_dw_s.txt are identical

参考

• https://habara-k.hatenadiary.jp/entry/2021/06/09/181140