DCS Laboratory 2
繰り返し囚人のジレンマゲーム

リーグ戦の手順

ラボ2を開始するにあたっての注意

ゲームの概要

  |  C  |  D  |
--+-----+-----+
  |   3 |   5 |
C |     |     |
  | 3   | 0   |
--+-----+-----+
  |   0 |   1 |
D |     |     |
  | 5   | 1   |
--+-----+-----+  

上記の利得行列における戦略Cは協調(Cooperate)を，そしてDは裏切り (Deception)を意味している．「協調」と「裏切り」の意味は下記の説明を参 照のこと．ラボ2では，このゲームを繰り返し行い可能な限り高い総利得をあ げるプレイヤーのプログラムを作成することを目的とする．

まず，囚人のジレンマゲームの背景について説明する． 囚人のジレンマゲームは，1950年頃 Merrill Flood と Melvin Dresher によって発案され，後に A.W. Tuckerによって定式 化された二人プレーヤによるゲームである． このゲームが囚人のジレンマと呼ばれるゆえんは， それが以下に述べる様な状況をもとにして説明された事情による．

その状況とは，仮にあなたがもう一人の共犯者と何らかの犯罪を犯して，逮捕され， 拘置されているとする．裁判を前にして二人は別々の独房に入れられている (二人の間に通信はないとする)．そこであなたのところへ検事がやってきて， ある取り引きを持ち掛ける．検事が言うには，その取り引きは共犯者にも持ち かけられているという(これは二人の犯罪者に共通の状況とする)．取り引きに 関して検事が言った内容はおおよそ以下のようなことである．

「状況証拠からして，あなたが無実を主張しても，検事側はあなた達の有罪を 証明して２年の刑にする自信がある． しかしあなたが罪を認めて，あなたの共犯容疑者の 罪状をあばく証言をしてくれれば，検事側はあなたを無罪放免にする．その場 合，共犯容疑者には５年の刑を求刑する．ただし両方とも自白した場合は４年 の禁固刑はかたいだろう．」

この状況で，各プレーヤは協調(無実を主張すること)，もしくは裏切り(罪を 認めること)という２つの選択肢をとることができる．互いに，相手が次にと る行動を知らないままに，自分の次の行動を選ばなくてはならない． 両者が協調した場合の利得は双方にR，両者とも裏切った場合は双 方にP，一方が協調し他方が裏切った場合は，協調した方にS，裏切った方 にTの利得を与える．ここで各利得 T, R, P,S は T > R > P > S お よびR > (T + S)/2 を満足するようにとる．最初に与えた利得行列は T = 5, R = 3, P = 1, S = 0　という具体的なケースで，これは囚人のジレン マゲームの一例である．

今回のラボでは，囚人のジレンマゲームをプレーするプレーヤプログラムを作 成し，二人のプレーヤで囚人のジレンマゲームを繰り返し行い，総利得を競う． ゲームの繰り返し回数Nは不明である．
( 注意: 現在のプログラムでは繰り返し回数がデフォルト で200回になっているが，講義での実験時は回数を変更する(何回になるかはわ からないものとする))．

　　 また，今回の対戦では乱数によるエラーを導入し，各プレイヤが選択した戦略 がある確率で反転してしまうこととする．エラー率は数%程度とし，それは以下 で説明するゲーム管理プログラム(master.c)の中で扱われる．
( 注意: 現在のプログラムではエラー率が2，3%に設定され ているが，講義での実験時は変更になる可能性がある)． 各プレイヤプログラムはエラーの発生を制御することはできない．　 このエラーがあることにより，ある回の対戦でプレイヤーが協調を選んだとし ても，その意図に反して，実際には裏切りという戦略に転換されてしまうこと がある．その逆もありうる．また，このエラーは，双方のプレイヤにある確率 でランダムに生じる．

さて，このゲームを繰り返し行なう場合，それぞれどのような行動選択の戦略 を取るべきか？どうしたらエラーからリカバーし泥仕合になることを避けられ るか？相手の戦略決定メカニズムを推定するか学習することで優位な立場をと れるか？

諸注意

1. 進化ゲーム(pdf形式)を読むと，TIT FOR TATというプログラ ムが紹介されているが，今回のラボではこのプログラムは禁止とする（TIT FOR TATをプログラムとして作成して提出しても成績はつかない）．また，常 に裏切るとか常に協調する傾向にあるプログラム，また，講義で紹介した収益 最大可原理や，時おり相手を裏切りような卑劣な戦略も禁止とする．つまり， オリジナルな戦略を考えること．

   TIT-FOR-TATに関しては実際に， 今回の対戦ではエラーが導入されているので，TIT FOR TATは必ずしも有効なプ ログラムとは言えない．また，乱数を使ってランダムに戦略を選ぶ，常に協調する， 常に裏切るなどの単純なプログラムも禁止とする．エラーからのリカバリや相 手の過去の戦略から戦略決定メカニズムを推定するなどの工夫が必要である．

2. 12月20日は対面講義で，すべてのプログラムでリーグ戦を行う．リーグ戦の詳細は以下を参照のこと．

3. リーグ戦上位のプログラムに関しては，プログラム作成上のアイデアに関して簡単な発表をしてもらう予定．　

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

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

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

提出物

レポート


レポートはHOPEから提出すること．

レポートには，タイトル，クラス名，学籍番号，氏名，目次をつける こと．レポート本体には，プログラムの概要，個々の関数の概要と詳細， 戦略のアルゴリズムや戦略決定上で工夫した点やそれに関する考察などが 必要である．戦略は，規則や他の数理的手法を用いてモデル化すること． 特に戦略決定に関しては，なぜそれが有効であると考え たのかに関する考察が必要である．その有効性を示すためには， 様々な種類の戦略プログラムを自分で実装し，それらと対戦させた結果や その結果に関する考察などが必要である．

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

ソースコード


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

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

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

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

*/

なお，繰り返しゲームの進行を管理するプログラムmaster.c は ginga01.fun.ac.jpマシンの以下の ディレクトリにあるものを用いること．　

/export/home/Fun/DCS/2023/resource/2/master.c

期限

プログラムとレポートは12月18日(月)の午後23時を提出期限 とする．この時間までに指定されたディレクトリにプログラムをコピーしてお くこと．さらにHOPEにレポートを提出すること． それ以降は指定されたディレクトリは書き込み不可能となり，HOPEへのレポー ト提出はできなくなる．．

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

ラボ2詳細 -プレイヤプログラムの作成-

ゲーム管理プログラム(master.c)(これは今回の課題では与え られるので作成する必要はないが，プレイヤプログラムを作成するために は読んでおく必要がある)


(詳細は 　 /export/home/Fun/DCS/2023/resource/2/master.c を参照のこと)

ゲーム管理プログラム(master.cファイル)には，対戦回数，各回の対戦の利得， 総利得，戦略を反転させるためのエラー発生などを管理し，他の関数を呼び出 す　main 関数を含むようにしてある．　

main関数の中では，ディフォルトで200回の対戦を行うループが構成さ れている．この対戦回数は，プログラム起動時にオプションパラメータで 10,000以下の任意の回数に設定できる．各回の対戦で，Player1関数と Player2関数を呼び出して，各プレイヤの戦略を受け取り，その対戦回の 双方の利得を計算し，初回からの総利得を更新する．指定された回数の ゲームが終了したら，双方のプレイヤの総利得を表示して終了する．

戦略を反転させるためのエラー発生に関しては，乱数のシードを Linux 組み込みのsrand関数で設定しているので，プログラムを起動するたびに 違うパターンの乱数となる．
(注意: master.cの中で乱数のシードを設定するためにsrand関 数を呼び出している．この関数をplayerプログラムの中で再度呼んでし まうとシードの再設定が行われ，不都合が生じる．よって，皆さんが作 成するplayerプログラムの中では srand関数は利用しないで下さい ) 　　

関数とファイル


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

関数の仕様

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


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

% gcc master.c  player1.c  player2.c 

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

% gcc master.c  player2.c  player1.o 

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

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

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

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

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

   ファイル間にまたがる関数に関しては，master.c ファイル内のプログラムから，player1.c ファイルの Player1関数，そして player2.cファイル内のPlayer2 関数を呼び出すだけであり，それ以外の異なるファイルにまたがる関 数呼出しは禁止する．特に，player1.cの中で Player2 関数を呼び出す，また，player2.cの中で Player1関数を呼び出すこと は厳禁とする．これを守らないと無限ループに落ちる可能性が ある．

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