FC2ブログ

*All archives* |  *Admin*

<<06  2020/07  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  08>>
高速シャンテン計算プログラムのソースコード2
昨日の記事(高速シャンテン計算プログラムのソースコード)で、ソースを晒してみたところ、かなり有益な情報を頂きました。

前のコードは配列の操作とかをいろいろやっていた分、計算時間的に損をしているらしく、ビット列で操作する方が計算時間が早くなるみたいです。

その発想はAI計算部分で部分的に取り入れてはいましたが、シャンテン計算の関数はけっこう前に作ったものをそのまま利用していたので、ビット列(もしくは長整数型)で計算時間短縮のギミックをまだ搭載していませんでした。
というわけで、前のコードをなるべくビット列計算をメインになるよう改造してみました。
ソースコード2
hashtable2.txt

normalshantenfunc_game関数の代わりにnormalshantenfunc_game2関数を面子手シャンテン数計算に使用します。

normalshantenfunc_game2関数の中で、まずは再帰計算をしない限り(必要になるのは相当レアで複雑な牌姿に限定される)、Integer型配列はいらないので、その部分は全部取っ払いました。
次にハッシュ関数を乗算や累乗で計算していたのをビット演算子に変えたのが、tehaitolongtaiou関数です。
この関数は引数がInteger型配列と始点と終点のインデックスで戻り値がLong型整数です。
次のようにハッシュ値を計算します。
'例 引数{1,1,0,2}→(2進数で)10101100→(10進数で)172
'1と1の間にある0の個数が手牌の枚数…最上位に1を置いて、先頭は1枚なので01、2番目が1枚なので01、3番目が0枚なので1、最後尾が2枚なので00、の順で2進数を並べる
ポイントは異なる牌姿であれば必ず異なる戻り値を返す、つまり入力の牌姿と戻り値の長整数型が完全に1対1対応しているという点です。
0の個数がすべての牌の枚数(max14枚)で、1の個数が始点から終点までの牌の種類数(max37種)というわけで、maxで51ビット使うので、ぎりぎり長整数型(64ビット)でおさまる範囲です。
計算式で用いているのは+1の加算と左シフト演算のみなので、従前の乗算、累乗よりは高速で計算できると思われます。
コードの中身も前のnormalshantenfunc_game関数より2の方がやや読みやすくなったかもしれません。

また、ハッシュ関数の計算式が変わったので、ハッシュテーブルの中身を置き換えることも必要です。
それがソースコード2.txtの下のhashtable2.txtとhashyomikomi2関数です。
hashtable2.txtも前のhashtable.txtと同じところに保存しておいてください。

また、従前よりもハッシュ値の数値が大きくなってるので、検索時間の速度を考慮して、普通の配列ではなく、Dictionaryクラスを使用します。(hashmentusu3、hashkouho3)
キーがLong型のハッシュ値、値が対応するメンツ数(メンツ候補数)です。

修正点は以上なので、実践してみます。

このコードをビルドしてそのまま実行すると、
"2m4m5m8m8m9m9m5P6p8p3s4s5s東"というてきとうな牌姿に対して、1000万回シャンテンチェックを繰り返します。(1万回終了ごとにコンソールに終わった回数が表示される。)
従前のtotalshantenfunc_game関数だと私の環境で100万回に20秒、毎秒5万回というスピードでした。
これが改造したtotalshantenfunc_game2関数に変えると1000万回終えるのに30秒、毎秒30万回となりました。
およそ6倍くらいにスピードアップしたので、まぁ上出来でしょう。
爆打のプログラムはこれよりもっと早いらしいです。

まだ改善できる点はあるにはあるのですが(一部配列参照が残っているところとか)、
ビット演算は処理速度的にはいいのですが、プログラムの保守というか可読性みたいなのがちょっとネックです。String型とかInteger型配列の方が頭の中では考えやすいです。
いったん正しいロジックで組めればいいのですけど、私のおつむでは正しく組んだ上で、それ以上の手直しとかができる自信がありません。なんとなく考えやすいInteger型配列でなれ合ってしまうあたり、トップクラスのプログラマーにはなれない感じです。
まぁ、無料で公開するレベルの話なので、このレベルでお許しください。

計算の正確性についてはちょっと前にfloodgate for mahjongで対局した試合のリプレイでAIに再計算させて、1試合分動かしたところ従前の関数と違う数値が出たところはなかったので、おそらくだいじょうぶのはずです。

一応、ソースコードの中には従前で使用しているものも残しているのですが、以下のものは新関数では使わないので削除してもらって構いません。
Dim hashmentusu2(1562500) As Integer 'ハッシュテーブルメンツ数
Dim hashkouho2(1562500) As Integer 'ハッシュテーブルメンツ候補数
Sub hashyomikomi() 'hashtable読み込み
Function normalshantenfunc_game(ByVal tehaifuroigaiakanasi() As Integer, ByVal furosu As Integer) As Integer 'メンツ手のシャンテン数を返す。(ハッシュテーブル+パーツで区切って高速化)
Function totalshantenfunc_game(ByVal tehaiakanasi() As Integer, ByVal furosu As Integer) As Integer() '現在のシャンテン数を返す(0-最小、1-国士、2-チートイ、3-メンツ手)
スポンサーサイト



コメントの投稿

Secret
(非公開コメント受付中)

コメント

No title
つい先日、牌譜解析をしようと思い立ち、現在奮闘中の者です。
本記事も含め、nisi様のブログにはいつも大変お世話になっております。

> ポイントは異なる牌姿であれば必ず異なる戻り値を返す、つまり入力の牌姿と戻り値の長整数型が完全に1対1対応しているという点です。
> 0の個数がすべての牌の枚数(max14枚)で、1の個数が始点から終点までの牌の種類数(max37種)というわけで、maxで51ビット使うので、ぎりぎり長整数型(64ビット)でおさまる範囲です。

この点ですが、コードを見ると、萬子、筒子、索子(+字牌)のそれぞれでパーツ分けをし、ハッシュテーブルとの突合を行っているように見えます。
となると、0の個数が全ての牌の枚数(max14枚)で、1の個数が(例えば萬子なら)1mから9mまでの種類数(max9種)なので、maxで23ビット使う計算となり、32ビットの整数型でも収まると思うのですが、この理解でよろしかったでしょうか。

ちなみに、上記の理解でよければ、最大値は下記になるのかなと思っています。
牌姿:13577788889999m(14枚)
ハッシュ(2進):10110110110001000010000(23桁)
ハッシュ(10進):5,988,880
Re: No title

> この点ですが、コードを見ると、萬子、筒子、索子(+字牌)のそれぞれでパーツ分けをし、ハッシュテーブルとの突合を行っているように見えます。
> となると、0の個数が全ての牌の枚数(max14枚)で、1の個数が(例えば萬子なら)1mから9mまでの種類数(max9種)なので、maxで23ビット使う計算となり、32ビットの整数型でも収まると思うのですが、この理解でよろしかったでしょうか。
>

以前公開したシャンテン数計算プログラムを単体で使うにあたっては、
ご指摘の通り、色別に分解しているので、max23ビットで32ビット整数型でも足ります。

ただし、その先麻雀AIを作るにあたって、
すべての色を含んだ1つの手牌は1つの整数型で表せるようにしておくと、後々計算時間面で有利になると考えてそのような設計にしています。

具体的には、こちらの記事(http://epsilon69399.blog20.fc2.com/blog-entry-765.html)も参考にしていただきたいのですが、
ある手牌の局収支やアガリ率を再帰式で計算するにあたり、
途中計算用として、
ハッシュキーに手牌(+巡目等の補足情報)を表す64ビット整数型を、ハッシュの値に局収支やアガリ率を記録したDouble型配列とした、Dictionaryを用いており、計算済み牌姿の局収支やアガリ率を使う際、そのDictionaryに頻繁にアクセスします。
このとき、キーが単純な整数型の場合、クラスや構造体(例えば、マンズの32ビット整数、ピンズの32ビット整数、ソーズの32ビット整数、字牌の32ビット整数の4変数を含むクラス)と比較して、Dictionaryの検索速度が速いと考えられます。

この点が、シャンテン数計算においては、冗長な64ビット整数型を用いている理由です。


プロフィール

nisi5028

Author:nisi5028
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
FC2カウンター
フリーエリア
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード