たくさん読めば強くなる伝説外伝
コメント欄ではなんか歯切れの悪いまとめになってしまったのでここで再度取り上げてみるテスト
評価関数のサイドローブレベル
あるプレイヤーにとっての神の手筋はゲーム木(AND/OR木)のORノードで1本以上の枝、ANDノードでは全ての枝をそれぞれ包含して葉に達している。
逆に適当なノードから葉に達する全ての経路を列挙すると(サイクル手順は1周以上回らず展開する)、それは探索開始ノードにおける神の一手を含む経路と、そうでない経路の2種類に分かれる。前者の集合をS1、後者の集合をS2としよう。
(、、、なんかスゲー当たり前すぎる設定ですがorz)
ある評価関数Hでαβ探索したときORノードにおける神の一手を逃さないためには、次式の成立が必要十分である
- max{ pのα値 | p∈S1 } ＞ max{ p'のα値 | p∈S2 } かつ
min{ pのβ値 | p∈S1 } ≦ min{ p'のβ値 | p∈S2 }
ここで、pのα値とは、p以外の枝を無視したときのα値を指すとする。β値も同様。
特に、以下の2つの値がどこまでいっても正であれば、神の一手を外さないという意味で申し分ない。
- max{ pのα値 | p∈S1 } - max{ p'のα値 | p∈S2 }
- (-min{ pのβ値 | p∈S1 }) - (-min{ p'のβ値 | p∈S2 })
次手を分類する動作をフィルタになぞらえて差の左側をメインローブ頂点の座標、右側をサイドローブ頂点の座標とみなそう。メインローブ頂上を0 dBとするサイドローブ頂上の高さ＝サイドローブレベルは探索開始ノード依存で変動が予想されるが、これをどの程度安定して負に保つかが、評価関数自体の良し悪しの評価尺度を与える。特にサイドローブレベルが反転して正になれば、当該ノードにおいて、その評価関数は間違いなく神の一手を外すことに注意。(なお神の一手を外すとそこは対戦相手の神の手筋の始まりである。)
ここにLS3600さんに提示を求められた「たくさん読めば弱くなる」評価関数のさほど極端でない版を示す準備が整った。探索の深さが増すにつれ、サイドローブの頂上位置をじわじわ押し上げていくか、メインローブの頂上位置をじわじわ押し下げていく因子を付加しとけばいい
いや具体的にどうやるのかは知らんし未定(何
■追記
上記主張は撤回しますた(→id:GMA0BN:20100119#1263918278)
神は成長しない
「たくさん読めば強くなる」とは裏を返せば「十分たくさん読むまで神の一手を高い率で外してる」はず
だからたくさん読むことの必要性を書いていい場所はその評価関数の取扱説明書がせいぜいだろう、
