探索ゲーム

【たんさくげーむ (search game)】

概要

目標物と探索者の2人がプレイヤーとして参加する探索に関するゲームのこと. 1段階ゲームの潜伏探索ゲームや待ち伏せゲーム, 多段階ゲームの逃避探索ゲーム等がよく研究されている.

詳説

　一般にゲームと呼ばれる問題を数理的に定義する場合，参加者はだれか（プレイヤー），それぞれのプレイヤーのとる手の全体は何か（戦略），戦略の組合せ毎に各プレイヤーにはどのような利益があるか（支払(payo.)，または利得(reward)）を与えることが標準的な要件である．探索理論(search theory) は，その直接の起源が第２次大戦中の米海軍による対潜水艦戦に関する軍事研究であったため，多くの探索モデルで扱われるのは敵対する二人の意思決定者である．その一方は探索者(searcher)，他方は目標物(target) または逃避者(evader)と呼ばれる．探索者は目標物を見つけようとし，目標物は探索者による探知から逃れようとする．いくつかの例外はあるものの，探索ゲームにおけるプレイヤーはこれらの二人に設定される場合が多く，両プレイヤーの支払にゼロ和を仮定する２人ゼロ和(two-person zero-sum) ゲームの研究が大半である．オペレーションズ・リサーチのバイブルというべき著書「オペレーションズ・リサーチの方法(Methods of Operations Research[1])」には，海峡を通峡しようとする潜水艦とその阻止をねらう航空機による哨戒線の設定問題に関して，ゲーム理論を用いた記述がすでにある．

　探索問題が探索者側の最適戦略だけを求める最適化問題として研究された際には，まず静止目標物に対する最適探索が研究され，次に移動目標物に対する最適探索へと研究が移っていったが，探索ゲームに関する研究も，まず静止目標物と探索者との間の２人ゲームから始まり，移動目標物と探索者のゲームへと拡張されていった．前者のゲームを潜伏探索ゲーム(hide-and-search game)，あるいは隠れん坊ゲーム(hide-and-seek game) と呼ぶ．すなわち，目標物は一度どこかに隠れると，隠れたまま移動しないモデルである．後者のゲームは逃避探索ゲーム(evasion-and-search game) と呼ばれる．探索ゲームのモデルを特徴付ける要素として，上述した目標物の静止，移動の区別の他，探索者の戦略が何かで分類すると便利である．捜索者側の最適探索だけを議論する問題では，手持ちの探索資源の探索空間内への配分の最適化が取り扱われることが多いが，探索ゲームにおける探索者の戦略としては，探索資源配分より，どの地点に移動して探索を行うかの移動戦略を採用する研究の方が圧倒的に多い．

　潜伏探索ゲームの初期のモデルでNorris[2] が行ったのは，目標物は有限個のボックスのどこに隠れるかを決め，探索者はどの順番でボックスを探索してゆくかを決めるゲームであるが，目標物の存在するボックスを探索しても見逃す確率がある中で，探知に至るまでの探索回数を支払とするものである．潜伏探索ゲームは，上記のようにボックスを探索空間としたモデルとして記述されることが多いが，その変形モデルとして，直線上でプレイされる直線探索ゲーム(linear search game) と呼ばれるものがある．それは，直線上の一点を目標物は指定して潜伏し，探索者はある起点から右や左に連続的に移動しつつ探索し，目標物探知までの移動距離を競うゲームである．探索者の戦略が探索資源配分である潜伏探索ゲームでは，目標物は潜伏するボックスを選択し，探索者は一定総量の探索資源を分割して各ボックスでの探索に割り当てる．多くの探索資源が割り当てられるほど，そのボックスでの探知確率は大きくなるという仮定の下で，探知確率等を支払としてプレイされる[3]．ボックスに割り当てる探知資源をボックスを探索する回数とみて，離散的な資源を考えるゲームもあるが，最適化問題として捉える場合，このような離散変数の最適化は一般的に難しい．

　移動目標に対する逃避探索ゲームでは，ゲームの進行中に目標物及び探索者がともにその敵対者に関する情報を得ることがなければ，プレイヤーは自らの戦略を途中で変更する理由がないから，ゲームの初めに一度だけ戦略を決める１段階のゲームとなる．これに対し，ゲームのプレイ中に情報が得られる場合には，その情報を使って次の戦略を決める多段階のゲームとなり，これを逐次逃避探索ゲーム(sequential evasion-and-search game) と呼ぶ．通常，目標物の戦略は各時点における移動位置を決めることであるが，その移動に制約を課すことが多い．探索者が目標物と同じく移動戦略をとる逃避探索ゲームは多く，１段階ゲームでは，各時点における両プレイヤーの位置関係に依存した支払を設定することが多い．多段ゲームである逐次逃避探索ゲームに関しては，目標物が探索者の現在の位置を知って次回の移動位置を決めるように設定された研究が多く，Washburn[4] は探索者，目標物が同じ移動位置を選んだ場合に探知が起こるとし，探知までの移動コストや探索コストの大小を競うゲームを論じている．逃避探索ゲームに関するユニークな拡張として，探索空間上での目標物や探索者の連続的な動きが微分方程式で記述される場合には制御理論を用いて分析することが多いが，それらのゲームは微分ゲーム(differential game) と呼ばれる分野に分類される．探索者の戦略が探索資源の配分である逃避探索ゲームは，時に探索配分ゲーム(search allocation game)[5] と呼ばれることもあるが，移動戦略を探索者戦略とするゲームに比べるとその発表件数は少ない．１段階のゲームに関しては，目標物は自分の移動経路を１つ選択し，探索者は各時点で各位置に投入する探索資源量を決定するモデルが多い．探索配分ゲームの多段階ゲームモデルは皆無である．

　探索ゲームの主要なモデルに，両プレイヤーともに資源配分を行って競うゲームもある．その一例は，有限個の価値のある対象物に対し，一方のプレイヤーは発見ないし破壊を目的に自らの資源を個々の対象物に配分し，他のプレイヤーはそれを妨害ないし防御するために各対象物に資源を割り当てる．支払は，破壊される価値の量である．このゲームは，米国の開拓時代を舞台に，いくつかの砦を守る守備隊とそれらを攻めようとする攻撃側双方の兵力配分の均衡点を論じる物語に名を借りて，プロットー大佐のゲーム(Colonel Blotto’s game) とも呼ばれるが，米ソ冷戦時代における弾道ミサイル配備の観点から論じられたこともある．このゲームでは，資源配分に時間的な経過を考慮するモデルにはあまり現実性がないため，資源配分計画を１度だけ決定する１段階ゲームとすることが多い[6]．

　以上で探索ゲームの主要なモデルについて述べたが，その他に分類される特筆すべき探索ゲームを以下で説明しよう．待ち伏せゲーム(ambushing game) と呼ばれるゲームでは，探索者はある限られた区域の点上や線上で待ち伏せを行い，そこを通過する目標物を探知しようとするモデルである．例えば，探索者はある長さのロープを適当に切り離して待ち伏せ区域に設置し，目標物は区域内を通過するが，途中でロープに引っかかると探知されたと見なされる．この種の様々なモデルがRuckle[7] 等により研究されている．双探索ゲーム(search-and-search game) では２人の探索者がプレイヤーであり，相手に先んじて目標物や相手を見つけようとするゲームである．また，潜伏探索ゲームの一種として２分探索的なゲームもある．そこでは，潜伏した目標物に対し，探索者には，自らの推理した潜伏地点の番号が真の潜伏地点番号より大きいか小さいかの質問が許される．支払は真の潜伏地点番号を言い当てるまでの質問回数である．目標物に嘘の回答が許されるケースもある．査察者と被査察者の参加する査察ゲームや税関と密輸者の間の取締ゲームはともにインスペクションゲーム(inspection game)と呼ばれ，前者（後者）のゲームでは，非合法活動（密輸）により利益をあげようとする被査察者（密輸者）と，それを発見しようとする査察者（税関）がプレイヤーとなるが，支払はゼロ和でなく非ゼロ和とすることが多い．以上見 てきたようにほとんどの探索ゲームが非協力ゲームとして論じられており，また支払にゼロ和を仮定してプレイヤーの利害損得が正反対である問題設定をするモデルが多い．

---

参考文献

[1] P. M. Morse and G. E. Kimball, Methods of Operations Research, MIT Press, Cambridge, 1951.

[2] R. C. Norris, Studies in Search for a Conscious Evader, MIT Technical Report No.279, 1962.

[3] J . C. Gittins, ”An Application of Control Theory to a Game of Hide and Seek,” International Journal of Control, 30' (1979), 981-987.

[4] A. R. Washburn, “Search-Evasion Game in a Fixed Region,” Operations Research, 28 (1980), 1290-1298.

[5] R. Hohzaki, “Search Allocation Game,” European Journal of Operational Research, 172 (2006), 101-119.

[6] J. S. Croucher, “Application of the Fundamental Theorem of Game to an Example Concerning Antiballistic Missile Defence,” Naval Research Logistics Quarterly, 22 (1975), 197-203.

[7] W. H. Ruckle, R. Fennell, R. Holmes, and C. Fennesmore, “Ambushing Random Walks I: Finite Models,” Operations Research, 24 (1976), 314–324.