Loading article…
探索ゲームは、探索空間と呼ばれる集合内で行われる2 人用のゼロサム ゲームです。探索者は、最大速度の制約の下で任意の連続軌道を選択できます。探索者も隠れている者も、互いの距離が発見半径以下になるまでは、他のプレイヤーの動きについて何も知らないものと常に想定され、その瞬間に捕獲が行われます。ゲームはゼロサムであり、報酬は探索に費やされた時間です。探索ゲームは、数学モデルとして、子供が遊ぶかくれんぼゲームや、一部の戦術的な軍事状況の表現などの分野に適用できます。探索ゲームの分野は、ルーファス アイザックスの古典的な本「微分ゲーム」[1]の最後の章で紹介され、シュムエル ガル[2] [3]とスティーブ アルパーン[3]によってさらに発展させられました。プリンセスとモンスターのゲームは、移動するターゲットを扱います。
戦略
グラフ（弧に長さがある）内の静止したターゲットを検索する自然な戦略は、グラフのすべての弧をカバーする最小の閉曲線 L を見つけることです。（L は中国郵便配達ツアーと呼ばれます）。次に、各方向に 1/2 の確率で L をトラバースします。この戦略は、グラフがオイラーグラフである場合にうまく機能するようです。一般に、このランダムな中国郵便配達ツアーは、グラフがツリー構造で接続されたオイラーグラフの集合で構成されている場合のみ、最適な検索戦略です。[4]このファミリーに属さないグラフの誤解を招きやすい単純な例は、3 つの弧で接続された 2 つのノードで構成されています。ランダムな中国郵便配達ツアー（3 つの弧をランダムな順序でトラバースすることと同等）は最適ではなく、これらの 3 つの弧を検索する最適な方法は複雑です。[2]
無制限のドメイン
一般に、オンライン アルゴリズムの場合のように、無制限のドメインを探索するための合理的なフレームワークは、正規化されたコスト関数(コンピュータ サイエンスの文献では競合比と呼ばれる)を使用することです。これらのタイプの問題のミニマックス軌道は常に等比数列 (または連続問題の場合は指数関数) です。この結果から、軌道空間全体を探索するのではなく、単一のパラメーター (この数列の生成元) を最小化することで、ミニマックス軌道を簡単に見つけることができるようになります。このツールは、数十年にわたって大きな注目を集め、探索ゲームとして分析されてきた線形探索問題、つまり無限線上のターゲットを見つけるために使用されました。[5]また、同時光線のセットを探索するためのミニマックス軌道を見つけるためにも使用されています。平面での最適な探索は、指数スパイラルを使用して実行されます。[2] [3] [6] 同時光線のセットを探索することは、後にコンピュータ サイエンスの文献で「牛の道問題」として再発見されました。[7]
参考文献
- ^ ルーファス・アイザックス『微分ゲーム』、ジョン・ワイリー・アンド・サンズ、(1965)
- ^ abc S. Gal, Search Games、Academic Press、ニューヨーク (1980)
- ^ abc S. AlpernとS. Gal、「探索ゲームとランデブーの理論」、Springer (2003)。
- ^ Gal, Shmuel (2001). 「グラフ検索のための単純な戦略の最適性について」International Journal of Game Theory . 29 (4): 533–542. doi : 10.1007/s001820000056 .
- ^ Beck, Anatole; Newman, DJ (1970). 「線形探索問題についてのさらなる考察」.イスラエル数学ジャーナル. 8 (4): 419–429. doi : 10.1007/BF02798690 .
- ^ M. Chrobak, 霧の中で泳ぎ怪物牛を探す王女、ACM Sigact news、35(2)、74–78 (2004)。
- ^ MY Kao、JH Reif、SR Tate、「未知の環境での探索：牛の進路問題に対する最適なランダム化アルゴリズム」、SODA 1993。