置換表は煩雑です!
直前のエントリのはシンプルなネタだが、いざ実際に実装しようとするとカナーリ面倒なことに気がつく、
いや複雑な作り込みを要するという意味ではなくて、慎重に考えねば意図したものとは全然違った確率の計算になってしまう危険性が多きいすぐる、
ぶっちゃけ結論を言えば、ここでの正しい考え方はつぎのようなものだる。
- u_iやc_iの計算は、局面sが生成され、sに基づきハッシュ関数が計算され、置換表が参照された、というケース全てに渡り行う。よって、項番号iは、make moveされ、かつ、その結果として生成された局面sに基づき置換表の参照が行われたときインクリメントする。*1
- エントリの確保が起きた回数は、探索ルーチンから置換表を更新して抜ける際(βカットまたは全ての子ノードの探索を完了した時)に、更新直前の置換表の最新内容に基づき、エントリの新規確保にあたるか否か改めて判定の上で更新する。*2
手順としては次のような感じになる。
- Make moveカウンタmove_cntと、エントリの新規確保カウンタused_cntを設ける。
置換表クリアタイミングでいずれも0に初期化。
move_cntがu_i、c_iの項番号iにあたる。 - 探索ルーチンに入った直後、何もしない。
- 置換表を参照することなく抜ける場合(千日手、王手千日手、%KACHI宣言条件成立時)も何もしない。
- 探索ルーチンの通常の手順に従い置換表が参照される際、++move_cnt。
- 置換表エントリteが記憶する評価値上下限でcut-offする場合は、集計処理を行ってから抜ける。
(teが新規確保では有り得ないので、このときused_cntは変化しない。) - 上記以外で抜ける場合(βカットか全ての子ノードを探索完了時)も集計処理を行ってから抜ける。
ここで、集計処理とは、次の処理である。
エントリteが新規確保にあたるか否かを 最新の置換表内容に基づき改めて判定し、 判定結果に基づき、本クラスの目的のために必要なヒストグラムを更新後、 新規確保である場合のみ++used_cnt
詳細は下記の通り。
Happy Checking!
* (基本的想定) * 置換表のエントリ数をN、最新局面をs、sに対してハッシュ関数が返したハッシュ値をhとして、 * h%Nでsのエントリが特定されるとする。 * また、個々のエントリは、下記を記憶する。 * 1. 空か否かのフラグ * 2. 最後に書き込まれたときのh * 3. 局面の各種情報を集約したチェックコードchkc * 4. 評価値の上下限 * エントリteが特定されたとき、ヒットしたと見做す条件は、 * teが空でなく、かつteが記憶するhとchkcがsから計算された値と一致したとき * である。 * ハッシュ関数の出来の確認は、局面sの生起毎にエントリの新規確保が * 行われたか否かの観察に基づいて行う。(詳細の説明はここでは省略する。) * sの分布には仮定を置かない方式のため、sの重複は気にせず、 * make move 1回でsの生起が1回起きたとする。 * 故に、本クラスは、make move毎にインクリメントされるカウンタmove_cntと、 * 新規エントリ確保毎にインクリメントされるカウンタused_cntを有する。 * * (エントリ特定時の場合分け) * sの生起毎に特定されるエントリteは、次のどれかである。 * (1) 空 * (2) 空でなく、かつhが不一致 * (3) 空でなく、かつhが一致し、chkcは不一致 * (4) 空でなく、かつhが一致し、chkcも一致(ヒット!) * また、探索ルーチンの構造から、エントリ特定後に次の処理が行われる。 * A. (1)〜(3)成立時は、探索すべき子ノードがある場合に必ず * 「子ノードについて探索ルーチンが再帰呼び出しされ、戻ってきた後、」 * teが上書きされる。 * B. (4)成立時は、探索の評価窓と、teが記憶する評価値の上下限の関係次第で * teを上書きせずにcut-offし得る。Cut-offしなかった場合はAと同じ。 * * (本クラスの処理) * 1. 探索ルーチンに入ったときは何もしない。 * 2. 置換表を参照することなく抜ける場合(千日手、王手千日手、%KACHI宣言条件成立時)も何もしない。 * 3. 探索ルーチンの通常の手順に従い置換表が参照される際、++move_cnt。 * 4. 置換表エントリteが記憶する評価値上下限でcut-offする場合は、集計処理を行ってから抜ける。 * (teが新規確保では有り得ないので、このときused_cntは変化しない。) * 5. 上記以外で抜ける場合(βカットか全ての子ノードを探索完了時)も集計処理を行ってから抜ける。 * ここで、集計処理とは、次の処理である。 * エントリteが場合(1)〜(4)のどれにあたるかを * 最新の置換表内容に基づき改めて判定し、 * 判定結果に基づき、本クラスの目的のために必要なヒストグラムを更新後、 * (1)だった場合のみ++used_cnt * ステップ3で集計処理を行わないのは、処理A、Bの通り、 * 子ノードについての探索ルーチンの再帰呼び出しがte上書き前に行われるためである。。 * ステップ3でteが(1)と判定されたからといって++used_cntとすると、 * 子ノードの探索中にたまたま同じteが特定された場合も++used_cntが行われ、 * 使用エントリ数が実態より多くカウントされてしまう。
*1:Make moveされた、というだけでインクリメントすると探索ルーチン冒頭で行う千日手、王手千日手、%KACHI条件判定にかかって抜ける場合に誤カウントとなるから、置換表の参照が行われてからのインクリメントが必要。
*2:現局面sに基づき特定されたばかりの置換表エントリteは、子ノードについて再帰的に探索する過程でもたまたま再特定されるかもしれない。よって、te特定直後に新規エントリだからとカウンタを+1する論理にすると、子ノードでも重複インクリメントになってしまい実態より大目にカウントしてしまうから、teが新規エントリ確保なのか否かは子ノードの探索が全部終わってから判定する必要がある。