向聴数の計算2
向聴数の計算
前回の記事で向聴数の計算をある程度高速に行えるようになりましたが,手牌の距離計算のテーブルを構築するための計算量が問題でした.
距離テーブルをBFSで行う
BFSを二回に分けて距離テーブルを作成します.
有効な枚数の手牌の中での距離
有効な手牌の枚数は手牌が 0,2,3,5,6,8,9,11,12,14 のときであり,その中で距離を計算します.
例えば,11122233344466m は和了形であるため距離は0であり,11122233344478mは1向聴なので距離は2となります.つまり,和了形から1枚交換して得られる和了形以外の手牌の距離は2となり,聴牌形となります.同様に聴牌形から1枚交換して得られる和了形と聴牌形以外の手牌の距離は4となることが分かるので,BFSにより有効な手牌の枚数の中での距離を作成することができます.
全ての手牌と有効な手牌との距離
上記の有効な枚数の手牌 [tex; h] の距離を とします.
を
とします.
枚の手牌 から1枚追加または削除して得られる手牌と 枚の有効な手牌との距離は となります.追加または削除の操作によって増える距離は であり,BFSにより効率的に全ての手牌と有効な手牌との距離を求めることができます.
探索の注意点として が最小のものから探索を行う必要があることと,すでに探索した手牌を弾くことです.