DCS Laboratory 1
2人追跡ゲームの作成

トーナメントの手順

ゲームの概要

2人追跡ゲーム(2 players pursuit game)は探索対戦型のゲームである． このゲームは，以下の図のような8×8の2次元格子世界(grid world)で行わ れる．世界は自由格子(free grid)と障害物(obstacle)から構成され， そのいずれかの自由格子に一人の捕食者(predator)と一匹の獲物(prey)がいる． 捕食者のミッションは獲物をとらえて食べることであり，獲物のミッションは， 捕食者から逃れることである．

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

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

このゲームでは，任意の初期状態(捕食者，獲物，そして複数の障害物の初期 位置により規定される)からスタートし，あるクロックにおいて捕食者と獲物 が同じ格子に入ったら獲物が食べられたと解釈して終了する． また，捕食者と獲物の最初の位置や障害物の数や位置は初期状態により変化す る．初期状態はデータファイルにより規定される．

捕食者と獲物は移動の過渡状況(今のクロックと次のクロックの間)において， すれ違うような状況になることがあるが，その場合は捕獲されないと解釈する． 具体的に述べると次のようなことである． 例えば，あるクロックにおいて捕食者と獲物が左右に隣接していたと する．次のクロックにおいて捕食者は右側の格子に，そして獲物は左側の格子 に移動しようとしたとする．この場合，今の状態と次のクロックの状態の間 (過渡状況)で二人がすれ違うことになるわけだが，その場合は捕食者は獲物を 捕獲できない．あくまで両者の移動先が確定した段階で，捕獲できたかどうか を判断するものとする．

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

諸注意

1. 11月8日（水）の講義のとき，すべてのプログラムでトーナメント戦を行う．
   マシンは学内のファイルサーバ ginga01.fun.ac.jpを用いる．トーナメントの詳細は以下を参照のこと．

2. トーナメントの成績が上位のプログラムに関しては，プログラム作成上 のアイデアに関して簡単な発表をしてもらう予定．

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

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

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

トーナメントの規定

1. トーナメントの初回対戦組み合わせはくじ引きにより決める．

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

3. 1回の対戦は2ゲームから構成される．まず，一方の学生の捕食 者用プログラム，他方の学生の獲物用プログラムでゲームを行い，次にその 逆の組み合わせでゲームを行う．ただし，一つのゲームは最長30クロックで終 了するものとする(30クロック目でゲームを強制終了する)． 以下の採点方式で勝ち負けを決める．

4. 各対戦の各ゲームにおいて，もしも捕食者が30クロック以内に獲物を捕 まえられたら捕食者の勝ちとし，そうでない場合は獲物の勝ちとする． 2勝した方の勝ちとする．
   もしも1勝1負の場合は，獲物として対戦したゲームで逃げ通したクロック数 (E)から，捕食者として対戦したゲームで捕まえるまでにかかったクロック数 (C)を引き点数とし，点数の高い方のプログラムの勝ちとする．
   同点の場合はジャンケンで決着をつける．

5. さらに，トーナメントにおいては，獲物の動作周波数(1ク ロック時間の逆数)を捕食者のそれの2/3に落として対戦することとする．これ は，捕獲を可能にするためである．なぜなら，捕食者と獲物が同じ周波数で動 作する場合，捕獲できる保証はないからである．

6. 獲物の動作周波数を2/3に落とす場合，これはpursuit.c 内 で行う．predator.cファイルや prey.cファイル内でクロックを操作する ことを禁ずる． この規則に従わないプログラムはトーナメント戦にお いて高い確率で負けることになる．

提出物

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

レポート


レポートはPDFの形式でHOPEの「課題・ラボ」に提出すること．

レポートには，タイトル，クラス名，学籍番号，氏名，目次をつけること． レポート本体には，プログラムの概要，個々の関数の概要と詳細，アルゴリズ ム上で工夫した点(図などを用いて詳細に説明すること)，実験データ，実験デー タの評価およびそれに関する考察などが必要である．

さらに，レポートの最後にはソースコードを資料として添付すること．

ソースコード


ソースコードは上記の諸注意項目5で指定されたディレクトリに "predator.c"，そして"prey.c"という名前のファイルとして 置いておくこと．各ファイルの内容物は以下で規定されるが,"predator.c"ファ イルには以下の Predator関数， そして，"prey.c"ファイルには以下のPrey関 数を必ずいれておくこと．必要に応じてそれらのファイル内に他の関数を含ん でも構わないが，関数名に関しては以下のコンパイルに関する注意をよく読ん で，その指示に従うこと．

また，各プログラムには，以下のようなコピーライトをつけ，また，各関数は 先頭でそれが何であるかを説明し，プログラムには十分にコメントをつけるこ と．

/* 
 Author:       Itoh Keisuke
 Student ID:   b1200XXX
 Class:        F
 Created:      October 20, 2004
 Language:     C

 Function:     swap(char *S, char *T)
 Description:  swap string S with string T.

*/

なお，"pursuit.c"は ginga01.fun.ac.jpの以下のディレクトリにあるものを用いること．

/export/home/Fun/DCS/2023/resource/1/pursuit.c

期限

プログラムとレポートは11月6日(月)の23:00を提出期 限とする．プログラムはこの時間までに指定されたディレクトリ (ginga01.fun.ac.jpマシンの"/export/home/Fun/DCS/2023/lab/1/<学籍番号>/" ディレクトリ)にコピーしておくこと．それ以降は指定されたディレクトリは書き込み不可能とな る．プログラム提出期限をトーナメントの前の週にするのは，トーナメントの ための事前確認と調整などを行うためである．

レポートはHOPEの「課題・ラボ」にPDF形式で提出すること．

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

ラボ1詳細 -2人追跡ゲームの作成-

2人追跡ゲームの概要は先に述べた． ラボ課題1では，ゲームの進行と格子世界を管理 するゲームマネージャプログラム(pursuit.c)，は提供されるもの(ginga01.fun.ac.jp:/export/home/Fun/DCS/2023/resource/1/pursuit.c)を用い， (1)捕食者の動作を決定する捕食者プログラム (predator.c)，そして(2)獲物の動作を決定する獲 物プログラム(prey.c)を作成する．

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

格子世界の管理(これは今回の課題では与えられるので直接は関係ない)


(以下，詳細は ginga01.fun.ac.jp:/export/home/Fun/DCS/2023/resource/1/pursuit.c を参照 のこと)

まず，格子世界を管理するプログラム(pursuit.cファイル)には，クロックの 計時や格子世界の状態(自由格子，障害物，捕食者，獲物の位置)を管理し，他 の関数を呼び出す main 関数を含むようにしてある．

main関数の中では，ディフォルトで30クロックを計時するループが構成されて おり，各クロックにおい て捕食者と獲物の次の動作を得て，格子世界を更新 し，表示する．ゲームが終了したら，以下のmain関数の規定で与えられた仕様 の通りのメッセージを出力してプログラムを終了するようになっている．

pursuit.cファイルには他に，(1)ファイルから格子世界の初期状態をデータと して読み込む関数，各クロックにおいてPredator関数お よびPrey関数を呼び出して両者の次の動作を得た後に(2)クロックが一つ進ん だとして世界の状態を更新する関数，(3)ゲームの終了を 判定する関数，そして，(4)現在のクロック数と格子世界を 表示する関数などが含まれている．

格子世界は整数型の8×8の二次元配列として実装してある． 各配列の値は整数で，自由格子の場合は"0"，障害物は"-1", 捕食者は"1"， 獲物は"10"と規定する．クロックは初期値が整数の0で，1クロック毎にインク リメントされている．

初期状態データファイル


初期状態はデータファイルとして読み込む．ファイルの中のデータに関 しては以下の仕様を参照すること．

データ形式の仕様

関数とファイル


各関数の仕様については以下を参照すること．

関数の仕様

複数のソースコードファイルのコンパイルおよびオブジェクト(再配置可 能形式，リロケータブルモジュール)とのリンク


"pursuit.c", "predator.c", "prey.c" の三つのソースコードは以下の方法で コンパイルできる．以下の例ではオブジェクト(実行可能形式，ロードモジュー ル)は "a.out" になる．

% gcc pursuit.c  predator.c  prey.c 

また，既にコンパイル済みのリロケータブルモジュール "prey.o" (gcc に "-c"オプションを与えることでリンケージエディタを起動しないようにし て作成する) と，ソースコードの "pursuit.c" そして "predator.c"は以下の 方法でコンパイルできる．以下の例ではオブジェクト(実行可能形式)は "a.out" になる．

% gcc pursuit.c  predator.c  prey.o 

コンパイル時に警告がたくさん出て煩わしい場合は gcc に "-std=c99" というオプションを与えるとうまくいくかも知れない．

プログラム作成およびコンパイル時の諸注意

1. 今回のプログラムでは，プログラムを 三つのファイル(pursuit.c, predator.c, prey.c)に分けてプログラミングす る．異なるファイルに同じ名前の関数や外部変数(広域変数)があるとコンパイ ル時に衝突を起こす．よって，pursuit.c の中で定義する 関数，定数，外部変数以外のもの，つまり，predator.c と prey.c の中の すべての関数，外部変数，そして広域的型定義には名前の先 頭に必ずそれぞれ"predator",もしくは "prey"をつけること．

   例えば predator.c の中で，"count"という関数を定義したい場合は名前を "predator_count" などとすること．外部変数や広域的な型定義の場合も同様 に先頭に "predator"をつけた名前とすること．

   同様に，prey.c ファイルの場合は，Prey関数以外の全ての関数，外部変数， および広域な型定義には，必ず"prey"を名前の先頭につけること．

   ファイル間にまたがる関数に関しては，pursuit.c ファイル内のプログラムか ら，predator.c ファイルの Predator関数，そして prey.cファイル内のPrey 関数を呼び出すだけであり，それ以外の異なるファイルにまたがる関数呼出し は禁止する．これを守らないとコンパイル時にエラーとなる．

   同一ファイル内では，関数呼出しは自由に行ってよい．例えば，predator.c ファイルで Predator関数を定義することが要求されているが，Predator関数 はこのファイル内部で定義された他の関数(先の注意にあるように，名前は "predatorFoo"のように"predator"で始まるものに限る)を呼出してもよい． prey.cファイルに関しても同様である．

テストデータと評価用サンプルプログラム


プログラムの動作を検証するために，テスト用の初期状態デー タとテスト用のmain関数を含むpursuit.c, predator.o，およびprey.o ファイルが以下のディレクトリに用意されている．これらのプログラムは 各人の作成したプログラムが仕様を満たしているかどうかを確認するため に用いる．テスト用のプログラムとリンクして正しく動作しないプログラムは 上記の仕様を満たしていないことになる． 評価用プログラムの使い方に関しては READ_ME_FIRST を読むこと． 以下にある評価用の pursuit.c を用いる場合は,コンパイルの時に pthreadラ イブラリというのをリンクしなければならないので 最後に必ず "-lpthread" という引数を与えること．詳細 は READ_ME_FIRST に書いてある．
• テスト用初期データ:
  ginga01.fun.ac.jp:/export/home/Fun/DCS/2023/resource/1/battlefield.dat

• 評価用プログラム:
  ginga01.fun.ac.jp:/export/home/Fun/DCS/2023/resource/1/{pursuit.c,predator.o,prey.o}