探索ゲームとは?

Weblio 辞書 > 同じ種類の言葉 > 文化 > 娯楽 > ゲーム > 探索ゲームの意味・解説 

探索ゲーム

読み方たんさくげーむ
【英】:search game

概要

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

詳説

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


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


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


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


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


 以上で探索ゲームの主要なモデルについて述べたが,その他に分類される特筆すべき探索ゲームを以下で説明しよう.待ち伏せゲーム(ambushing game) と呼ばれるゲームでは,探索者はある限られた区域の点上や線上待ち伏せ行い,そこを通過する目標物探知ようとするモデルである.例えば,探索者はある長さロープ適当に切り離して待ち伏せ区域設置し,目標物区域内を通過するが,途中でロープ引っかかると探知されたと見なされる.この種の様々なモデルがRuckle[7] 等により研究されている.双探索ゲーム(search-and-search game) では2人探索者プレイヤーであり,相手先んじて目標物相手を見つけようとするゲームである.また,潜伏探索ゲーム一種として2分探索的なゲームもある.そこでは,潜伏した目標物に対し,探索者には,自らの推理した潜伏地点番号真の潜伏地点番号より大きい小さいかの質問が許される.支払真の潜伏地点番号言い当てるまでの質問回数である.目標物に嘘の回答が許されるケースもある.査察者と被査察者の参加する査察ゲームや税関密輸者の間の取締ゲームはともにインスペクションゲーム(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.




探索ゲームと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「探索ゲーム」の関連用語

探索ゲームのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



探索ゲームのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2019 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2019 Weblio RSS