ゼミのお話/N本腕バンディットを解くプログラムの作成
はじめに †
古くから，暇な時などに楽しむものとしてゲームは人々に親しまれている．現在では家庭用ゲーム機などに代表されるコンピュータゲームを主に指す言葉として知られているが，もちろんそれだけではない．100m走や幅跳び，砲丸投げなど身体能力を競う競争や競技も"ゲーム"である．また将棋やチェスといった知力を競う"ゲーム"も長い歴史を持ち，その延長上としてコンピュータゲームが登場し，次第に独自の文化を築いている．
特に知力を競うゲームを考えると，その起源は戦争の代替・練習のものとしてあると考えられている．そのためか，ゲームの基本性質として"対戦相手"が存在し，それに"勝利"することが共通した目的がある．ゲームはいくつかのタイプに分類することができるが，常勝(常に勝つ)のための方法・方策について様々な研究が行われ，学問にもなっている\cite{beasley1}．学問的に研究している学者も，プロ・アマ問わずそのゲームの競技者も，基本的にはまずゲームをプレイしルールに慣れ試行錯誤を行うところから始まる．次第に経験を通して勝つためのルールを自分なりに作成していき，常勝への道の探求を行うものである．
本演習では，簡単なゲームを対象にして，ゲームに"勝てる"方法を考え，アルゴリズム化(演算の定型化)を行い，プログラムにすることを目標とする．
製作対象 †
目的 †
N本腕バンディットに対して，よい成績(スコア)を得ることができるプログラムの作成を目標とする．
N本腕バンディットって何？ †
N本腕バンディットとは，N本のレバーのあるスロットマシンのようなものである．各レバーには当たり確率等が設定されており，レバーを引くことによって"当たり"または"はずれ"が決定する．"当たり"となると，報酬(お金など)をもらうことができる．
N本腕バンディット問題とは，プレーヤーはいかに多くの報酬を獲得するか，という問題であり，バンディットとプレーヤー間の競争ゲームとなる．
製作方法 †
解く対象のN本腕バンディット一覧 †
NetBSD amd64用(S-JIS,CRLF) †
- 共通:
- ヘッダファイル
- バンディットプログラム
- made by K.K
bandit.hWindows用(S-JIS,CRLF) †
- 共通:
- ヘッダファイル
- バンディットプログラム
- made by K.K
Mac用 †
- 共通:
- ヘッダファイル
- バンディットプログラム
- made by K.K
- made by Y.K
ヘッダ・オブジェクトファイル使用方法 †
- 配布ファイル
- ヘッダーファイル名: bandit.h
- オブジェクトファイル名:bandit**.o
- **は任意の数字
- 使用可能関数
- void init_bandit(void)
- バンディットの初期化．最初に一回使用する必要あり．
- double bandit(int arm)
- バンディットのゲームを1回行う
- 引数:arm:選択する腕．N本腕の場合には，1〜Nの数．
- 返り値:報酬は正の値．はずれている場合は0.0となる．選択した腕(arm)がおかしい場合は-1.0となる．
- int get_arm_num(void)
- 選択可能な腕の数を知るための数．必要があれば使用．
- 返り値:選択可能な腕の数．
- void init_bandit(void)
- 注意
- srandは使用しないこと！
- 乱数を使用する場合，srand()とrand()を使用する．ここで，srand()は乱数を使用するための初期化処理であり，プログラム中に一回のみの実行となる．一方，rand()は乱数を発生する関数であり，乱数が欲しい場合には毎回呼び出す．ここで，srandはinit_bandit()関数の中で実行しているので，プログラム中では絶対に使用しないこと！
- srandは使用しないこと！
ヘッダ・オブジェクトファイル使用例 †
評価方法 †
他人と競う時の，スコア計算方法 †
N本腕バンディットに対して，プレーヤーはより多くの報酬を得ることを目標とする．本演習では，プレーヤーは人ではなくN本腕バンディットを解くプログラムである．このプログラムが得た報酬を用いてプレーヤー(プログラム)のスコアを考える．
プレーヤーがN本腕バンディットのレバーを一回選択する行為を"1試行"という．この時，連続した10000試行の結果得た報酬の合計をプレーヤーのスコアとする．ただし，第一回目の試行から計算する必要はなく，試行途中の好きな時点からの試行でよい．
基本的には，一回目の試行から計算を行い，全試行を通して最大の報酬をスコアとする．全試行数10，連続した3試行の結果得た報酬の合計をスコアとした場合の例を以下に示す．
公平なスコア計算を実現するために †
スコアの計算方法が人によって異ならず，他の人と同様にスコア計算することは，公平な競技では重要である．ここでは，公平なスコア計算を行うために，以下のことを考える．
- プレーヤー(n本腕バンディットを解く人)は，解くプログラムを以下のように関数化する
- void init_player();
- なんか初期化するのに使う.
- void set_arm_num(int arm_num);
- バンディットの腕の数(n)を知るための関数
- int decision_making(double previous_reward);
- decision_makingとは，意思決定の意味である．つまり，バンディットのどの腕を選択するかを考える関数である．この関数の返り値は，選択する腕である．
- 引数は，意思決定(次にどの腕を選ぶか)を考え行うために必要と思われる情報とした．
- 引数 previous_rewardは前回選択した腕でいくら報酬がもらえたか，である．試行の第１回目は"前回"がないので，この場合には"0.0"が与えられる．
- void close_player();
- なんか終了処理をする.特にポインタなどを使っている場合、この中でfreeをするのに使う.
- void init_player();
- 上記関数を以下のファイルで実装し，オフィシャルに提供する
- player.h
- 上記関数の定義
- player.o
- gcc -c player.c で作成
- player.cは関数decision_making(...)の実装を行う．
- player.h
- オフィシャル(n本腕バンディットを作って提供する人)はプレーヤーから提供された関数を元に，以下のプログラムによってスコア計算を行う．
- gcc -o game collect.c player.c bandit**.o での作成が慣れてきたら，以下を行い，公式スコアに登録してみる
- cp player.c /mnt/public/YakanEnshuB/bandit/******/player.c
- *****は自分の学籍番号．例えば学籍番号100000なら cp player.c /mnt/public/YakanEnshuB/bandit/1000000/player.c
- 中間モニタにて公式スコアを計算し続けているので、自分のスコアを確認
- 注意
- 自分のスコアを計算している時には，cp player.c ....を行わない方がよい．
- cp player.c /mnt/public/YakanEnshuB/bandit/******/player.c
編集
差分
バックアップ