« 鳳凰卓の牌譜URL | トップページ | いまさら »

2009/06/18

棒テン即リーアルゴリズムと向聴数計算方法

手牌を探索するとき、受け入れ牌、捨て牌候補のリストアップをする必要があるけれど、そのために、まずは向聴数をベースにリストアップするのがひとつの現実解となる。

13枚状態の手牌と14枚状態の手牌の向聴数が調査できるアルゴリズムが作れれば、14枚状態から向聴数を落とさずに13枚状態にできる牌をリストアップすることも簡単にできる。
そして、打牌をして13枚状態になった手牌で、個別に牌を追加して14状態にしたとき向聴数が向上する牌の種類と枚数をカウントし、最も多くなるような、打牌を選択すれば、棒テン即リーのアルゴリズムは出来る。
 東風荘でR1400以下程度のあまり真剣に麻雀に取り組んでない人相手なら、単純にこれだけのアルゴリズムでもそこそこ相手になる麻雀プログラムになる。

向聴数を調査するアルゴリズムには、おおむね2通りのやり方がある。ひとつは手牌をバックトラック法で、面子、塔子、対子、孤立牌に分割する全パターンをリストアップし、そこから、面子数、塔子数、対子数から向聴数を計算する方法。

もうひとつは、あらさんのホームページに載ってるような1スーツ分のハッシュテーブルを持つ方法。
1スーツ分(例えば、萬子)の考えうる全てのパターンと、
手牌を面子数×10+(塔子+対子)の数が最大となる面子の数と(塔子+対子)の数と、
、面子数×2+(塔子+対子)が最大となる、面子の数と(塔子+対子)の数を
構造体メンバとしてもつハッシュテーブルを作ってそこから向聴数を計算する。

 単純に向聴数をカウントするだけだと、ハッシュ方式の方が50倍近く早い。
あらさんの一人麻雀練習機はこちらを採用している模様。

 ただ、ハッシュ方式だと、死に塔子の判定がしにくい。死に塔子とは、例えば1-3のカンチャン塔子を持ってるとき、他者に2を槓されて面子に変化しなくなってしまった塔子のこと。このときは実質向聴数が+1になるけれど、ハッシュ方式だとこういった死に塔子をバックトラックで探索していかないと見つけられない。
それに、アルゴリズムによっては打牌せず、ツモだけして、多牌状態にしてから評価したりする場合もあり、そういった方式に応用しにくいし、事前に無駄だと分かる打牌を前方枝刈りするのも難しい。
 また、単純に速度面から言っても、向聴数の計算は速いものの受け入れ牌のカウントや、打牌候補の選定は手牌分割方式より遅いという欠点もある。(これはそれ専用のテーブルを作れば解決できるが)

 鳴きなし、相手なしの一人麻雀だとハッシュ方式でなんら問題ないんだけれど、点数状況による和了点の制限や鳴き、他家の捨て牌等がからむ4人麻雀ではたとえ50倍遅くても手牌分割方式のメリットは捨てがたい。

なので、私は今まで手牌を面子塔子対子孤立と分割状態にした状態のままコンテナに入れておく手牌クラスをつくり、、探索中は、分割状態を持ちまわって手牌のツモ&打牌が出来るようにしている。
そのことで、速度的に遅い手牌分割を最初の1回だけしかやらずに済ましている。

 今回Ver0.9用に作り直すにあたり、両方の方式を実装してみたけれど、トータル的に、手牌分割方式のほうが便利そう。
 ただ、Ver0.9用につくっている最中に発見したんだけど、Ver0.8では同じ手牌を何度も評価する無駄な処理があり、結構時間がかかってしまっている。私がVer0.8で採用しているアルゴリズムはあらさんのものより遅いのだが、どうもここの無駄な処理が原因だったようだ。てっきりハッシュ方式の向聴数チェックをしていないためだと思い込んでいた。

 ちなみに、麻雀ゲーム作ってるときはパターンが多くてテストが大変なんで、確実に動くが遅いバージョンと高速化バージョンの2パターン(以上)を実装してアウトプットが同じになるか比較して検証している。
そのため、オブジェクト指向型の言語で個々のパーツの入れ替えが簡単に効くように作ったほうが何かと便利だと思う。

|

« 鳳凰卓の牌譜URL | トップページ | いまさら »

コメント

ちょうど今、向聴数をカウントするプログラムを作ろうと思っていたところで、実装方式について考えているところでした。
探索方式とハッシュ方式についてや、アルゴリズムの検証法など、とても参考になりました。

投稿: idaten! | 2009/06/19 07:43

今まで結構隠してるノウハウがあったけど。今後は情報を出すようにしたいと思ってます。

投稿: kmo2 | 2009/06/19 23:44

いつも楽しく遊ばせていただいております。

この度、Ver.0.8.20の牌譜を見直しておりましたら、アルゴリズムに疑問を感じたので、コメントさせて下さい。

オーラス、荘家、2着目と3100点差のトップ目、2着目からリーチがかかったという状況で、同順、ピンフのみをテンパイしたら追っかけるという判断をしておりました。

オーラスで、トップ目が出あがりのきくテンパイをしたら、リーチ棒で逆転されるリスクも増えますし、リーチしないほうが有利かと思いますが、27000持ちのオカのみでウマなしなら、リーチした方がスコア的に見ると有利なのでしょうか?

投稿: 魑魅魍魎 | 2009/06/27 18:34

情報ありがとうございます。>魑魅魍魎さん

>同順、ピンフのみをテンパイしたら追っかけるという判断をしておりました。

トップ目が平和のみの手で追っかけ立直したということですか。

たしか、オーラスで安目の出和了でトップやらダマにするよう、ベタにプログラムしていたと思いますので、何か問題の箇所があるのかもしれません。もう一度見直します。

現状のまったり麻雀は点数状況判断がヘタレなので、いろいろ修正するつもりです。
(ちょっと時間がかかってしまうかも知れませんが……)

投稿: kmo2 | 2009/06/27 20:08

見直しましたが、オーラスに安めを出和了で上がったときにトップの場合は立直しないようになっていました。

投稿: kmo2 | 2009/06/27 21:18

大変失礼を致しました。

返事を頂いて、再度見直しましたところ、結果的に最終局でしたので、オーラスと勘違いしておりましたが、実は、下家がハコ割れで終了しただけでした。

過去の対局を、牌譜の再生ソフトを使って見ていただけなので、ラス目の点数状況を見落としておりました。

貴重なお時間を、申し訳ありませんでした。


最後になりましたが、いつも素晴らしいソフトを提供していただき、ありがとうございます。
特に、コンピュータの「危険度」判断を見られるのは、とても参考になります。感覚的には生牌の役牌はとても危なく感じるのですが、無スジの数牌に比べると遙かに安全であることを再認識させられます。

押し引きに関しては、流局寸前でも「押し」と表示されることがあるので、「聴牌料を考えるとここは『押し』なのかぁ」などと考えながらも、「やっぱリーチ怖い」と逆らってしまうこともありますが、ブレない一貫した判断は、人間の助言よりも遙かに参考にしやすいです。
あまりの楽しさに、最近はネット対局も含め、めっきり対人戦が減ってしまいました。

これからも、利用させて頂きます。

投稿: 魑魅魍魎 | 2009/06/29 13:38

オーラス、立直の件連絡ありがとうございます。

>最後になりましたが、いつも素晴らしいソフトを提供していただき、ありがとうございます
気に入っていただければ、こちらもうれしいです。

コンピュータの評価値は、ベタオリはそこそこいい線いってるとは思いますが、超一流の人から見たらまだどこかおかしい部分もあると思いますので、あくまで参考程度に活用してください。

投稿: kmo2 | 2009/06/30 22:21

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/61182/45381045

この記事へのトラックバック一覧です: 棒テン即リーアルゴリズムと向聴数計算方法:

« 鳳凰卓の牌譜URL | トップページ | いまさら »