秋口あたりから麻雀のプログラミングにハマっているフシがある。 すこし成果がまとまってきたので記事にしてみよう。
なんと言っても、
がきっかけだし、これがweb魚拓しか残っていないことに危機感を覚えた。シャンテン数計算と役計算は実装したい。あと有効牌判定。 そこから簡単なシミュレータ作って実験までできればいいなあと思うところ。
お役立ちリンク
他の有名な？プロジェクト
- オープン麻雀プロジェクト(仮称)
- mahjong-serverのクライアント実装例
- 爆打の中の人 ちゃんと研究に落とし込んでいる方。
- まうじゃん的空間 フリーでプレーヤーを自前実装できる「まうじゃん」の配布サイト。
- mahjong-cpp C++17(+ boost)で美しく書かれたライブラリ。テストも充実。
- 麻雀 - 何切る問題の期待値の計算方法について 期待値計算方法が載っている。
- あらの（一人）麻雀研究所 一人麻雀とそのシミュレーション方法が示されている。
アルゴリズム全般
- 気まぐれな戯れ言 バックナンバー１５ 役判定アルゴリズムの概要がつかめる。
- 麻雀 和了判定（役の判定） アルゴリズム バックトラック法とインデックスを用いた約判定アルゴリズムについて。
- 牌理/牌効率ツール 有効牌列挙の動作確認に。
数理的側面
乱数について
端的に言って沼。
ランダムシャッフル | Programming Place Plus ランダムシャッフルのやり方。Fisher-Yates法を使いましょう。
- 配列のシャッフルコードの間違った実装 実装を誤ると痛い目に合う。
一様乱数の作り方一つとっても落とし穴がある。。。
- いつからその方法で偏りのない乱数が得られると錯覚していた？ まず読みましょう。そして、偏らない乱数を出すためには、以下の実装で行く必要があるようです。
int uniform_int(int n) { int adjusted_max = (RAND_MAX + 1) - (RAND_MAX + 1) % n; int r; do { r = rand(); } while (r >= adjusted_max); return (int)(((double)r / adjusted_max) * n); }
乱数範囲をnの倍数で切り捨ててから、実数の一様乱数にキャストする。剰余は下位ビットの偏りに影響を受けるからNG。
- C言語/C++で範囲を指定した乱数を生成する
- C言語による乱数生成 注意点は、剰余による一様乱数は偏りが出るということか。例えばRAND_MAX=10でrand()%3して0,1,2の乱数を作ろうとすると、0は0,3,6,9、1は1,4,7,10、2は2,5,8だから偏る。解決法としては、[0,1]の浮動小数点乱数を作ってから整数化する方法が奥村先生のアルゴリズム本含め推奨されていた。→**よくない**
- 良い乱数・悪い乱数
- Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理 論文の紹介と検証：Marsaglia, G. 2003. Xorshift RNGs. XorShiftの分かりやすい解説。
- 乱数ライブラリを更新してみた XorShiftの初期値のとり方。
- xoshiro / xoroshiro 統計的により望ましい乱数列を出すアルゴリズム。
AI（プレーヤー）について
プレーヤーは間違いなくインターフェースとして実装すべきで、転用を考えて、他の有名なものと互換性のある形に実装しておきたい。
- 「まうじゃん」対戦相手プラグイン インターフェース仕様 C/C++版の解説。そうか、プレーヤーがゲーム側に問い合わせる状態取得インターフェースもいるな。
- まうじゃんのインターフェース仕様 Java版の解説
- [麻雀]コンピュータで鳳凰卓を目指すpart1[天鳳] 最初はシャンテン数を減らすことだけ考える。次はベタオリ、次は鳴き。取っ掛かりにはかなり良さそう。
- まうじゃんAI:
- 対戦相手プラグインの部屋 まうじゃんの対戦相手のプラグイン集。強いことで有名な「アカギ」がいる。
- まうじゃん対戦相手プラグイン「しぐま０」v1.00公開 アカギよりちょっと強い打ち手。
牌譜について
可能であれば牌譜出力にも対応できたほうが良い（AIがどんな挙動してるか見える）
- 電脳麻将の牌譜形式 jsonで独自だが可読性に優れていそう。
- mjscore.txtの書式について シンプルで可読性あるけど日本語ガッツリ入ってるのでパースに苦戦しそう