麻雀で天和に遭遇する確率をシミュレート＠C++

ランダムに牌を選択し、和了の形ができているかどうかチェックするプログラム。

10億回まわしてみた。

ソース

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const char* tile_names[] = {
		"m1","m2","m3","m4","m5","m6","m7","m8","m9",
		"p1","p2","p3","p4","p5","p6","p7","p8","p9",
		"s1","s2","s3","s4","s5","s6","s7","s8","s9",
		"wa","so","we","no","wt","gt","rt"};

unsigned long xor128(){
	static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
	unsigned long t;
	t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}


void new_hand(vector<int> &hand) {
	int l = 0;
	while(l < 14) {
		int new_til_num = ((unsigned int)xor128())%136;
		bool flag = true;
		for(int i=0;i<l;i++) {
			if(new_til_num == hand.at(i)) {
				flag = false;
			}
		}
		if(flag) {
			hand.at(l) = new_til_num;
			l++;
		}
	}
	for(int i=0;i<14;i++) {
		hand.at(i) = hand.at(i) % 34;
	}
	sort(hand.begin(),hand.end());
	return;
}
void print_hand(vector<int> &hand) {
	for(int i=0;i<14;i++) {
		cout << tile_names[hand.at(i)] << ", ";
	}
	cout << endl;
}

int orphans[] = {-1,0,8,9,17,18,26,27,28,29,30,31,32,33,-1};
bool is_thirteen_orphans(vector<int> &hand) {
	int bindex = 0;
	int eindex = 13;
	while(hand.at(bindex) == orphans[bindex+1]) {
		bindex++;
	}
	while(hand.at(eindex) == orphans[eindex]) {
		eindex--;
	}
	return bindex == eindex + 1;
}

bool is_seven_pairs(vector<int> &hand) {
	for(int i=0;i<7;i++) {
		if(hand.at(i*2) != hand.at(i*2+1)) {
			return false;
		}
	}
	return true;
}

bool stdhora_chk(vector<int> &hist, bool on_shu, bool on_head) {
	if(on_head) {
		bool result = false;
		for(unsigned int i=0;i<hist.size();i++) {
			if(hist.at(i)>=2) {
				hist.at(i)-=2;
				result = result || stdhora_chk(hist, on_shu, false);
				hist.at(i)+=2;
			}
		}
		return result;
	} else {
		vector<int> histcp = hist;
		for(unsigned int i=0;i<histcp.size();i++) {
			if(histcp.at(i)>=3) {
				histcp.at(i)-=3;
			}
			while(histcp.at(i)>0) {
				if(!on_shu)return false;
				if(i+2>=histcp.size())return false;
				histcp.at(i)--;
				histcp.at(i+1)--;
				histcp.at(i+2)--;
				if(histcp.at(i+1)<0)return false;
				if(histcp.at(i+2)<0)return false;
			}
		}
		return true;
	}
}

bool stdhora_check(vector<int> &hand, int offset, int length, int bas, int siz, bool on_shu, bool on_head) {
	vector<int> hist(siz);
	for(int i=offset;i<offset+length;i++) {
		hist.at(hand.at(i)-bas)++;
	}
	return stdhora_chk(hist, on_shu, on_head);
}

bool is_standard_hora(vector<int> &hand) {
	int b_m = 0;
	int m_p = lower_bound(hand.begin(), hand.end(), 9) - hand.begin();
	int p_s = lower_bound(hand.begin(), hand.end(), 18) - hand.begin();
	int s_t = lower_bound(hand.begin(), hand.end(), 27) - hand.begin();
	int t_e = hand.size();
	int mlen = m_p - b_m;
	int plen = p_s - m_p;
	int slen = s_t - p_s;
	int tlen = t_e - s_t;
	if(mlen%3==2 && plen%3==0 && slen%3==0 && tlen%3==0) {
		return
			stdhora_check(hand, b_m, mlen, 0, 9, true, true) &&
			stdhora_check(hand, m_p, plen, 9, 9, true, false) &&
			stdhora_check(hand, p_s, slen, 18, 9, true, false) &&
			stdhora_check(hand, s_t, tlen, 27, 7, false, false);
	} else if(mlen%3==0 && plen%3==2 && slen%3==0 && tlen%3==0) {
		return
			stdhora_check(hand, b_m, mlen, 0, 9, true, false) &&
			stdhora_check(hand, m_p, plen, 9, 9, true, true) &&
			stdhora_check(hand, p_s, slen, 18, 9, true, false) &&
			stdhora_check(hand, s_t, tlen, 27, 7, false, false);
	} else if(mlen%3==0 && plen%3==0 && slen%3==2 && tlen%3==0) {
		return
			stdhora_check(hand, b_m, mlen, 0, 9, true, false) &&
			stdhora_check(hand, m_p, plen, 9, 9, true, false) &&
			stdhora_check(hand, p_s, slen, 18, 9, true, true) &&
			stdhora_check(hand, s_t, tlen, 27, 7, false, false);
	} else if(mlen%3==0 && plen%3==0 && slen%3==0 && tlen%3==2) {
		return
			stdhora_check(hand, b_m, mlen, 0, 9, true, false) &&
			stdhora_check(hand, m_p, plen, 9, 9, true, false) &&
			stdhora_check(hand, p_s, slen, 18, 9, true, false) &&
			stdhora_check(hand, s_t, tlen, 27, 7, false, true);
	} else {
		return false;
	}
	return false;
}

int main(int argc, char *argv[], char *envp[])
{
	vector<int> hand(14);
	/*{
		//int hand_lit[] = {0,8,9,17,18,26,27,27,28,29,30,31,32,33};
		int hand_lit[] = {0,1,2,13,13,13,15,15,15,21,22,23,31,31};
		copy(&hand_lit[0],&hand_lit[14],hand.begin());
		print_hand(hand);
		cout << is_standard_hora(hand) << endl;
		return 0;
	}*/
	int output_period = 10000000;
	int calc_times = 100;
	int max_sample_size = output_period * calc_times;
	int count_thirteen_orphans = 0;
	int count_seven_pairs = 0;
	int count_standard_hora = 0;
	int count_all = 0;
	for(int i=0;i<max_sample_size;i++) {
		new_hand(hand);
		//print_hand(hand);
		if(is_thirteen_orphans(hand)) {
			count_thirteen_orphans++;
			count_all++;
		}
		if(is_seven_pairs(hand)) {
			count_seven_pairs++;
			count_all++;
			if(is_standard_hora(hand)) {
				count_standard_hora++;
			}
		} else {
			if(is_standard_hora(hand)) {
				count_standard_hora++;
				count_all++;
			}
		}
		int sample_size = i+1;
		if(sample_size % output_period == 0) {
			cout << "thirteen orphans: " << count_thirteen_orphans << "/" << sample_size << " = " << ((double)count_thirteen_orphans/sample_size) << endl;
			cout << "     seven pairs: " << count_seven_pairs << "/" << sample_size << " = " << ((double)count_seven_pairs/sample_size) << endl;
			cout << "   standard hora: " << count_standard_hora << "/" << sample_size << " = " << ((double)count_standard_hora/sample_size) << endl;
			cout << "             all: " << count_all << "/" << sample_size << " = " << ((double)count_all/sample_size) << endl;
		}
	}
	
	return 0;
}

結果

thirteen orphans: 0/10000000 = 0
     seven pairs: 8/10000000 = 8e-07
   standard hora: 27/10000000 = 2.7e-06
             all: 35/10000000 = 3.5e-06
thirteen orphans: 0/20000000 = 0
     seven pairs: 10/20000000 = 5e-07
   standard hora: 57/20000000 = 2.85e-06
             all: 67/20000000 = 3.35e-06
thirteen orphans: 0/30000000 = 0
     seven pairs: 11/30000000 = 3.66667e-07
   standard hora: 75/30000000 = 2.5e-06
             all: 86/30000000 = 2.86667e-06
(中略)
thirteen orphans: 0/980000000 = 0
     seven pairs: 367/980000000 = 3.7449e-07
   standard hora: 2532/980000000 = 2.58367e-06
             all: 2898/980000000 = 2.95714e-06
thirteen orphans: 0/990000000 = 0
     seven pairs: 373/990000000 = 3.76768e-07
   standard hora: 2556/990000000 = 2.58182e-06
             all: 2928/990000000 = 2.95758e-06
thirteen orphans: 0/1000000000 = 0
     seven pairs: 376/1000000000 = 3.76e-07
   standard hora: 2582/1000000000 = 2.582e-06
             all: 2957/1000000000 = 2.957e-06

既に計算されている結果によると、遭遇確率は約0.000003025なので、若干低く見積もってしまったようだ。

あと、国士無双天和の確率は約0.0000000003なので、10億回の計算ではぎりぎり出現しない程度である。

それと、この計算では、国士無双天和＋七対子天和＋一般の形の天和と、全体の天和回数に１だけずれがある。これは、七対子でかつ一般ともとれる形(大車輪のような)があると考えられる。

ソースの説明

136枚の牌からの選択は普通にランダムに行っている。ただし、疑似乱数として使ったのはxorshift法である。特に理由はない。

選んだ配牌はソートしてある。そのほうが便利だからである。

国士無双の判定は、前と後ろから単純に照合するだけでよい。

七対子の判定は、2個ずつ判定すればよい。

問題は、一般のあがりの形である。

まず、4種類のセクション(萬子、筒子、索子、字牌)にわけ、セクションの大きさを3で割った余りに応じて処理を分岐する。0なら頭のないセクション、2なら頭のあるセクション。

まず、それぞれ、牌リストから、ヒストグラムへ変換する。

そして、頭が存在するセクションは、頭を走査し、頭なしの検索関数を再帰呼び出しする。

頭が存在しないセクションは、下から走査し、３つ以上なら刻子、そうでなければ順子として取り除くことで確認する。途中で余りが出た時点でアウト。

最後にすべてのセクションの結果を論理積で結合すればいい。

ここまで書いてミスに気づいた

槓子を含む七対子を和了の形として認めてしまった！

まあ、いいか。書き直すのも面倒くさいし。

まとめ

TopCoderか何かの問題として出しても遜色ない面倒くささであった。