▲コンピュータ将棋スレッド132

▲コンピュータ将棋ス ..

184:名無し名人
18/02/04 18:11:20.78 23gFbzJ50.net
>>156訂正；
　誤： P = 3_C_1 * p * (1-p)^2 + 3_C_2 * p^2 * (1-p) + 3_C_3 * p^3
　正： P = 3_P_1 * p * (1-p)^2 + 3_P_2 * p^2 * (1-p) + 3_P_3 * p^3
　誤：（一致後の事後）確率は1/(ハッシュキーの総数)
　正：（一致後の事後）確率は1/(ハッシュキーの総数/(2^16 * (置換表のビン数)))
（∵エントリの特定に至った時点でハッシュキーの最上位16 bitと置換表のビンの数にあたる下位bitは一致がもともと確定
■ 具体的数値
ハッシュキー64 bit（で局面の識別に十分と仮定）、
最上位16 bitのみ等値比較、ビンの中の3エントリがどこも満杯とする。
置換表サイズ(ビン数)　　　p　　　　　　　P　　　　　　　r　　　　　衝突頻度(=1/(P*r))
--------------------------------------------------------------------------------
64 K　　　　　　　　　　　1.53e-5　　　　　　4.58e-5　　　1.00　　　2.18万回に1回
512 M 　　　　　　　　　　1.53e-5　　　　　　4.58e-5　　　1.00　　　2.18万回に1回
※ pとPは置換表サイズに拠らない。（ビンの中に3エントリかつエントリ特定にハッシュキーの16 bit等値比較、で確定
※ rは上で訂正した「（一致後の事後）確率」の逆数で、エントリ特定済条件での衝突確率。置換表サイズ依存だが64 K v.s. 512 Mでは差が出ない。
→2.18万回に1回衝突とか使い物にならない。>>133の置換表は満杯になるような使い方をしてはいけない
　置換表サイズに対する勝率は、「どのビンにも空きエントリがある」が満たされた時点で頭打ちになる（そこから先はいくら置換表を大きくしても勝率が伸びない）と予想

次ページ

続きを表示

1を表示