配牌時向聴数

shanten.md

配牌時向聴数(完全版)

概要

配牌時向聴数を求めるプログラムに01-BFSによる距離テーブルを作成する機能を追加し, 1つのファイルで完結するようにした完全版.

ソースコード

C++17で記述.

#include <algorithm>
#include <chrono>
#include <deque>
#include <functional>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>
#include <boost/container_hash/hash.hpp>
constexpr int INF = 1 << 10;
using Vec = std::vector<int>;
using Hands = std::vector<Vec>;
struct HashHand;
using Dist = std::unordered_map<Vec, int, HashHand>;
using Table = std::unordered_map<Vec, Vec, HashHand>;
struct Key;
struct HashKey;
using Keys = std::unordered_map<Key, int, HashKey>;

struct HashHand {
  std::size_t operator()(const Vec& hand) const
  {
    return boost::hash_range(hand.begin(), hand.end());
  }
};

struct Key {
  // 距離テーブルへのポインタ
  Vec* dist;
  // 手牌のパターン数
  long long dens;
  // 七対子を構成する牌の種類数
  int kind_sp;
  // 七対子を構成する対子の種類数
  int pair_sp;
  // 国士無双を構成する牌の種類数
  int kind_to;
  // 国士無双を構成する対子の種類数
  int pair_to;
};

struct HashKey {
  std::size_t operator()(const Key& key) const
  {
    using boost::hash_combine;
    using boost::hash_range;

    std::size_t seed = 0;

    hash_combine(seed, hash_range(key.dist->begin(), key.dist->end()));
    hash_combine(seed, key.kind_sp);
    hash_combine(seed, key.pair_sp);
    hash_combine(seed, key.kind_to);
    hash_combine(seed, key.kind_sp);

    return seed;
  }
};

bool operator==(const Key& lhs, const Key& rhs)
{
  return *lhs.dist == *rhs.dist &&
         lhs.dens == rhs.dens &&
         lhs.kind_sp == rhs.kind_sp &&
         lhs.pair_sp == rhs.pair_sp &&
         lhs.kind_to == rhs.kind_to &&
         lhs.pair_to == rhs.pair_to;
}

// 手牌生成(全幅)
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);
    }
  }
}

// 手牌生成(全幅)
template <bool IsHonor>
void generate(int n, int m, Table& table, Keys& keys)
{
  // 組み合わせ(4Cr)
  static const Vec c = {1, 4, 6, 4, 1};
  static constexpr int N = IsHonor ? 7 : 9;
  static Vec hand(N);
  static Vec dens(N + 1, 1);
  static Vec kind_sp(N + 1);
  static Vec pair_sp(N + 1);
  static Vec kind_to(N + 1);
  static Vec pair_to(N + 1);

  if (n == N) {
    const Key key{
        &table[hand],
        dens[N],
        kind_sp[N],
        pair_sp[N],
        kind_to[N],
        pair_to[N]};

    if (auto itr = keys.find(key); itr == keys.end()) {
      keys.emplace(key, 1);
    }
    else {
      ++itr->second;
    }
  }
  else {
    for (int i = std::max(0, m - 4 * (N - 1 - n)); i <= std::min(4, m); ++i) {
      hand[n] = i;
      dens[n + 1] = dens[n] * c[i];
      kind_sp[n + 1] = kind_sp[n] + (i > 0 ? 1 : 0);
      pair_sp[n + 1] = pair_sp[n] + (i >= 2 ? 1 : 0);
      kind_to[n + 1] = kind_to[n] + ((IsHonor || n == 0 || n == N - 1) && i > 0 ? 1 : 0);
      pair_to[n + 1] = pair_to[n] + ((IsHonor || n == 0 || n == N - 1) && i >= 2 ? 1 : 0);

      generate<IsHonor>(n + 1, m - i, table, keys);
    }
  }
}

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

// 01-BFS
Dist bfs(const Hands& hands)
{
  Dist dist;
  std::deque<Vec> deq;

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

  while (deq.size()) {
    const Vec hand = deq.front();

    deq.pop_front();

    const auto sum = std::accumulate(hand.begin(), hand.end(), 0);

    for (int i = 0; i < 9; ++i) {
      if (hand[i] < 4 && sum < 14) {
        auto before = INF;
        auto added = hand;

        ++added[i];

        if (const auto itr = dist.find(added); itr != dist.end()) {
          before = itr->second;
        }

        if (int after = dist[hand]; after < before) {
          dist[added] = after;
          deq.push_front(added);
        }
      }

      if (hand[i] > 0) {
        auto before = INF;
        auto removed = hand;

        --removed[i];

        if (const auto itr = dist.find(removed); itr != dist.end()) {
          before = itr->second;
        }

        if (int after = dist[hand] + 1; after < before) {
          dist[removed] = after;
          deq.push_back(removed);
        }
      }
    }
  }

  return dist;
}

void add1(Vec& lhs, const Vec& rhs, const int m)
{
  for (int j = m + 5; j >= 5; --j) {
    int sht = std::min(lhs[j] + rhs[0], lhs[0] + rhs[j]);

    for (int k = 5; k < j; ++k) {
      sht = std::min({sht, lhs[k] + rhs[j - k], lhs[j - k] + rhs[k]});
    }
    lhs[j] = sht;
  }
  for (int j = m; j >= 0; --j) {
    int sht = lhs[j] + rhs[0];

    for (int k = 0; k < j; ++k) {
      sht = std::min(sht, lhs[k] + rhs[j - k]);
    }
    lhs[j] = sht;
  }
}

void add2(Vec& lhs, const Vec& rhs, const int m)
{
  int j = m + 5;
  int sht = std::min(lhs[j] + rhs[0], lhs[0] + rhs[j]);

  for (int k = 5; k < j; ++k) {
    sht = std::min({sht, lhs[k] + rhs[j - k], lhs[j - k] + rhs[k]});
  }
  lhs[j] = sht;
}

inline int coef(const int i, const int j, const int k)
{
  if (i == j && j == k) {
    return 1;
  }
  else if (i == j || j == k || k == i) {
    return 3;
  }
  else {
    return 6;
  }
}

int main()
{
  constexpr int M = 14;
  const auto start = std::chrono::system_clock::now();

  std::vector<std::vector<Dist>> dists(2, std::vector<Dist>(10));

  for (int m = 0; m <= 4; ++m) {
    Hands hands10, hands12;
    Hands hands20, hands22;

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

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

    generate<7>(0, 3 * m, [&](std::vector<int>& h) {
      std::vector<int> cnt(5, 0);

      for (int i = 0; i < 7; ++i) {
        ++cnt[h[i]];
      }

      if (cnt[1] == 0 && cnt[2] == 0 && cnt[4] == 0) {
        hands20.push_back(h);
      }
    });

    generate<7>(0, 3 * m + 2, [&](std::vector<int>& h) {
      std::vector<int> cnt(5, 0);

      for (int i = 0; i < 7; ++i) {
        ++cnt[h[i]];
      }

      if (cnt[1] == 0 && cnt[2] == 1 && cnt[4] == 0) {
        hands22.push_back(h);
      }
    });

    dists[0][m] = bfs(hands10);
    dists[0][m + 5] = bfs(hands12);
    dists[1][m] = bfs(hands20);
    dists[1][m + 5] = bfs(hands22);
  }

  std::vector<Table> tables(2);

  for (int i = 0; i < 2; ++i) {
    for (const auto& [hand, dist] : dists[i][0]) {
      Vec sht(10);

      sht[0] = dist;

      for (int j = 1; j < 10; ++j) {
        sht[j] = dists[i][j][hand];
      }
      tables[i][hand] = sht;
    }
  }

  std::vector<Keys> keys1(M + 1);
  std::vector<Keys> keys2(M + 1);

  for (int m = 0; m <= M; ++m) {
    generate<false>(0, m, tables[0], keys1[m]);
    generate<true>(0, m, tables[1], keys2[m]);
  }

  std::valarray<long long> cnt(8);

  for (int i = 0; i <= M; ++i) {
    for (int j = i; j <= M - i; ++j) {
      for (int k = j; k <= M - i - j; ++k) {
        std::valarray<long long> tmp(8);

        for (const auto& [key0, value0] : keys1[i]) {
          for (const auto& [key1, value1] : keys1[j]) {
            for (const auto& [key2, value2] : keys1[k]) {
              for (const auto& [key3, value3] : keys2[M - i - j - k]) {
                Vec lhs = *key0.dist;
                add1(lhs, *key1.dist, M / 3);
                add1(lhs, *key2.dist, M / 3);
                add2(lhs, *key3.dist, M / 3);

                const auto dens = key0.dens * value0 * key1.dens * value1 * key2.dens * value2 * key3.dens * value3;
                const auto kind_sp = key0.kind_sp + key1.kind_sp + key2.kind_sp + key3.kind_sp;
                const auto pair_sp = key0.pair_sp + key1.pair_sp + key2.pair_sp + key3.pair_sp;
                const auto kind_to = key0.kind_to + key1.kind_to + key2.kind_to + key3.kind_to;
                const auto pair_to = key0.pair_to + key1.pair_to + key2.pair_to + key3.pair_to;

                const int num_lh = lhs[5 + M / 3];
                const int num_sp = 7 - pair_sp + (kind_sp < 7 ? 7 - kind_sp : 0);
                const int num_to = 14 - kind_to - (pair_to > 0 ? 1 : 0);
                const int num_all = std::min({num_lh, num_sp, num_to});

                tmp[num_all] += dens;
              }
            }
          }
        }

        cnt += tmp * coef(i, j, k);
      }
    }
  }

  const auto end = std::chrono::system_clock::now();
  const auto total = cnt.sum();
  double ev = 0.0;

  std::cout << "Shanten\tCount\tProp" << std::endl;

  for (int i = 0; i < 8; ++i) {
    ev += (i - 1) * cnt[i];
    std::cout << i - 1 << "\t" << cnt[i] << "\t" << static_cast<double>(cnt[i]) / total << std::endl;
  }

  std::cout << "Number of Tiles: " << M << std::endl;
  std::cout << "Total: " << total << std::endl;
  std::cout << "Time (msec.): " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << std::endl;
  std::cout << "Avg Shanten: " << ev / total << std::endl;

  return 0;
}

出力

Shanten Count   Prop
-1      12859078207674  3.02545e-06
0       2966241795738948        0.000697889
1       99154452630748356       0.0233288
2       828714358375292670      0.194978
3       1867404976243926528     0.439358
4       1211948980271480832     0.285144
5       233501763289743360      0.0549376
6       6601397483077632        0.00155316
Number of Tiles: 14
Total: 4250305029168216000
Time (msec.): 20908
Avg Shanten: 3.15594

参考

• https://habara-k.hatenadiary.jp/entry/2021/06/09/181140
• https://github.com/habara-k/flush-shanten