反復深化に向かって
αβ探索(またはdf-pn探索)において枝のカットを効率よく行うには子ノードの列挙順序が重要だ。
特に反復深化させる場合、第k回目の反復において深度d毎にαβ幅極小だった子ノードを記憶しておいて、第k+1回の探索(最大深度を第k回より増す)で深度dに達したとき、(どうせ同じ親ノードに真っ先にたどりつくから)さっきの子ノードを最初に調べると効率がいい。この記憶と判断を0〜前回(第k回)の最大深度の各深度毎に行うとする。
αβ幅極小ノードが変動したときは？
最大深度を増した探索の結果、αβ幅極小だった子ノードが変動することがある。この場合は最新の極小ノードが最初、前の極小ノードがその次に探索されるようにするといい、、ような気がするが禿げしく違う気もする、、
実現方法
深度ごとに盤の空きセル*1のスキャンオーダーを記憶する(仮にスキャンオーダーマップと呼ぶ)。
記憶形式は、int(4 Byte)の1次元配列(要素数 = 総セル数 = 盤の縦サイズ×盤の横サイズ)。
配列要素の中身は次の通りとする。
- [i][j][prv][nxt] (4 Byte)
ここで、
- (i,j)
- 対応するセルの座標(行と列)
- prv
- 前要素のインデックス
- nxt
- 次要素のインデックス
最初にスキャンする要素をint* p_startで保持する。
要素同士は(prvとnxtによる)双方向リンクでつなぐ。(最後の要素と最初の要素もつないで全体を循環させる。)
で、αβ幅極小ノードを生じたら、それに対応するスキャンオーダー要素のリンクを繋ぎ変えてp_startが指すスキャンオーダー要素の直前に移動(挿入)後、p_startをその要素を指すように変更する実装とした。
どうなんだろ…？(←調べろよ
ふとｵﾓﾀ
反復深化中の極小ノードの入れ替わり頻度を水平線の手がかりとする手法はアリなのだろうか…、、
