DCS Laboratory 3
追跡ゲームの実装

追跡ゲームの概要

追跡ゲームは4対1の探索対戦型のゲームである． このゲームは，以下の図のような16×16の2次元格子世界(grid world)で行わ れる．世界は自由格子(free grid)と障害物(obstacle)から構成され， そのいずれかの自由格子に四ひきの捕食者(predator)と一匹の獲物(prey)がいる． 捕食者達のミッションは「獲物の上下左右のグリッドを占有し生け捕りにする (捕獲する)」ことであり，獲物のミッションは，捕獲されずに逃れることであ る． 

          ....................
          .................@..
          ......@.............
          ..........#.........
          ..........#.........       @: predator
          ..........#.........       *: prey
          ..........#......*..       .: free grid
          ..........#.........       #: obstacle grid
          ..........#.........       
          ..........#.........       
          ....................       
          ..@.................       
          ....................       
          .............@......       
          ....................       
          ....................

この世界では，捕食者と獲物はいずれかの自由格子にいて「クロック」にし たがって動く同期系システムである．クロックとはこの世界を支配する時計で あり，離散的な時間単位である．初期状態は0クロック目と考え，以後順に1ク ロック目，2クロック目と1クロックずつ時間が進んでいく．

捕食者と獲物は1クロック後に現在自分がいる格子の上下左右 の隣接自由格子に移動することができる(斜め方向には動けない)．移動せずに 同じ格子にとどまっていることも許される．さらに，捕食者と獲物は，障害物 の置いてある格子や格子世界の外へは移動できない．また，一つのゲームの開 始から終了までの間，障害物は移動しないものとする．

このゲームでは，任意の初期状態(捕食者，獲物，そして複数の障害物の初期 位置により規定される)からスタートし，あるクロックにおいて獲物が動けな いように捕食者が上下左右の近傍グリッドを占有したら獲物が捕獲されたと解 釈して終了する(ただし，獲物が境界グリッドにいる場合は例外規定があり， それについては以下の説明で説明する)． また，捕食者と獲物の最初の位置や障害物の数や位置は初期状態により変化す る．初期状態はデータファイルにより規定される．

また， また，捕食者と獲物のいずれも，プログラム起動時に引数として与えられた 範囲(これを視界と呼ぶ)しか見えないものとする． (ディフォ ルトでは，各エージェントのいるグリッドを中心とした近傍の25個の正方形状 に配列されたグリッドだけが見えるものとする．これを上下左右2グリッドの 視界と呼ぶことにする．下図参照)


          .....
          .....
          ..@..
          .....
          .....
二人以上のエージェントが同一グリッドに入ることはできない．ある時点から 次の時点で，もしも捕食者と獲物がそれぞれが現在いるグリッドとは別の 同一グリッドに移動するよう決定した場合は捕食者の動作を優先する．ただし， いずれかのエージェントが「動かない」という決定をした場合は，そのエージェ ントを優先することとする．

また，あるクロックである捕食者と獲物が隣接グリッドにいた場合，次のクロッ クに互いにそのグリッドの場所を入れ換えわるような動作，つまり途中ですれ 違うことはないものとする．つまり，例えば，以下の(A)の状態から， 次のクロック時に(B)の状態になることはないものとする．2つのエージェント が上下の位置にいても同様とする． 


          .....          .....
          .....          .....
     (A)  .@*..      (B) .*@..
          .....          .....
          .....          .....
さらに，二人以上の捕食者が現在いるグリッドと異なる別の同一グリッドに入 ろうとした場合は，いずれかの捕食者を優先する(どの捕食者が優先されても 構わない)．

獲物は，上下左右のグリッドを捕食者に占有されるか，もしくは，境界グリッ ドにいる場合は近傍の残りのグリッドを捕食者に占有されて動けなくなったら 捕獲されたこととする．以下に例をしめす． 


          .....          .....          .....
          ..@..          ....@          .....
          .@*@.          ...@*          .....
          ..@..          ....@          ....@
          .....          .....          ...@*

捕食者も獲物も互いに相手がどういう戦略で動くかは不明である．初期状態か らはじめて，捕食者は，可能な限り少ないクロックで獲物をとらえることが要 求される．逆に，獲物は可能な限り長い間逃げまわることが要求される．

諸注意

  1. 提出物はプログラム(ソースコードとオブ ジェクト)，レポートである． 詳細は以下を参照のこと．

  2. プログラム全体は，以下の規定にあるようにいくつかの関数に分割して プログラミングする．

  3. ラボ3では，対戦の都合上，複数の関数をそれぞれ指定され たファイルにいれて，コンパイル・リンクする．どの関数をどの名前のファイ ルにいれるかの指定，そして複数のソースコードをコンパイルする方法は以下 を参照すること． 作成したすべてのソースコードとオブジェクトは ginga01.fun.ac.jpマシン上 の "/export/home/Fun/DCS/2023/lab/3/<学籍番号>/" ディレクトリの下にコピーしておくこと．ソースコードとオブジェクトのアク セス許可モードはそれぞれ644 (-rw-r--r--)，755(-rwxr-xr-x)とする．

評価時の規則

  1. 1クロックは実際には1秒で実装されている．つまり，捕食者関数，獲物 関数の呼出しから終了までは1秒とし，関数呼出しから1秒以内にリターンしな い場合は，その関数呼出しは強制終了される．

  2. 1回の対戦は2ゲームから構成される．まず，一方の学生の捕食 者用プログラム，他方の学生の獲物用プログラムでゲームを行い，次にその逆の組み合わせで対戦を行う．

  3. 各対戦の各ゲームにおいて，獲物として対戦したゲームで逃げ通したク ロック数(E)から，捕食者として対戦したゲームで捕まえるまでにかかったク ロック数(C)を引き点数とし，点数の高い方のプログラムの勝ちとする．

提出物

以下のものを提出すること．

期限

プログラムとレポートは2月6日(火)の23時を提出期限とする． プログラムはこの時間までに指定されたディレクトリにコピーしておく こと．それ以降は指定されたディレクトリは書き込み不可能となる． レポートはHOPEのラボ課題3に提出すること．

提出の遅延は認められない．

ラボ3詳細 -追跡ゲームの実装-

追跡ゲームの概要は先に述べた． ラボ課題3では，(1)捕食者の動作を決定する捕食者プログラム(predator.c)， そして(2)獲物の動作を決定する獲物プログラム(prey.c)を作成する．

プログラムを作成するに当り，以下の各仕様を守ること．

...Return