ゲーム木における探索手法の一種のscout法の挙動がよくわかりません。
scout法について書かれたスライドでは、scout法は以下のTEST関数とSCOUT関数によって構成されると書いてありました。
procedure TEST(position p, value v, condition c ): // c is comparison operator like ‘<’ or ‘>’ determine the successor positions p1...pd if d = 0, then // terminal return TRUE if f(p) > v // f is eval function return FALSE otherwise for i := 1 to d do if p is a MAX node and TEST(pi, v, c ) is TRUE, then return TRUE if p is a MIN node and TEST(pi, v, c ) is FALSE, then return FALSE if p is a MAX node, then return FALSE if p is a MIN node, then return TRUE procedure SCOUT(position p): determine the successor positions p1, . . . , pb if b = 0, then return f(p) else v = SCOUT(p1) // SCOUT the first branch if p is a MAX node for i := 2 to b do if TEST>(pi, v) is TRUE, // TEST first for the rest of the branches then v = SCOUT(pi) // find the value of this branch if it can be > v if p is a MIN node for i := 2 to b do if TEST<(pi, v) is TRUE, // TEST first for the rest of the branches then v = SCOUT(pi) // find the value of this branch if it can be < v return v
上のコードを以下の1番目の画像1の木に適用すると、alpha-beta法では枝刈りは起きませんが、scout法ではノードKで呼び出されたTEST(K, 5, >)が10の評価値を持つKの子ノードによりTRUEをノードPに返し、8の評価値のノードを探索せずに済むようになります。これは上のアルゴリズムをそのまま実行することでわかります。
しかし2番目の画像2では、ノードBでTEST(B, 25, <)が呼び出されています。上記したTEST関数の中では、呼び出し元からの引数vの更新はなく、最初のTEST関数の呼び出しの際の引数v(今回であればルートノードの最初の子ノードの評価値10)を使いまわすはずです。ですが画像2では、再帰的なTEST関数呼び出しの過程でvが更新されているように思われます。なぜTEST関数の再帰的な呼び出しの中で、vが変化するのでしょうか。
参考にしたスライド資料は以下の2つです。
https://homepage.iis.sinica.edu.tw/~tshsu/tcg/2017/slides/slide7.pdf
https://kti.mff.cuni.cz/~bartak/ui_seminar/talks/2012/HraniHer.pdf
あなたの回答
tips
プレビュー