*All archives* |  *Admin*

<<08  2017/09  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  10>>
高速シャンテン計算プログラムのソースコード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
(非公開コメント受付中)

コメント

プロフィール

nisi5028

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

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

この人とブロともになる

QRコード
QRコード