質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

0回答

551閲覧

ゲーム木探索のScout法アルゴリズムのTEST関数の挙動がわかりません。

yamatan

総合スコア8

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2022/01/02 03:24

ゲーム木における探索手法の一種の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が変化するのでしょうか。

scout法を適用したゲーム木例(左:画像1、右:画像2)

参考にしたスライド資料は以下の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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問