ゼミのお話/N本腕バンディットを解くプログラムの作成
はじめに †
古くから,暇な時などに楽しむものとしてゲームは人々に親しまれている.現在では家庭用ゲーム機などに代表されるコンピュータゲームを主に指す言葉として知られているが,もちろんそれだけではない.100m走や幅跳び,砲丸投げなど身体能力を競う競争や競技も"ゲーム"である.また将棋やチェスといった知力を競う"ゲーム"も長い歴史を持ち,その延長上としてコンピュータゲームが登場し,次第に独自の文化を築いている.
特に知力を競うゲームを考えると,その起源は戦争の代替・練習のものとしてあると考えられている.そのためか,ゲームの基本性質として"対戦相手"が存在し,それに"勝利"することが共通した目的がある.ゲームはいくつかのタイプに分類することができるが,常勝(常に勝つ)のための方法・方策について様々な研究が行われ,学問にもなっている\cite{beasley1}.学問的に研究している学者も,プロ・アマ問わずそのゲームの競技者も,基本的にはまずゲームをプレイしルールに慣れ試行錯誤を行うところから始まる.次第に経験を通して勝つためのルールを自分なりに作成していき,常勝への道の探求を行うものである.
本演習では,簡単なゲームを対象にして,ゲームに"勝てる"方法を考え,アルゴリズム化(演算の定型化)を行い,プログラムにすることを目標とする.
製作対象 †
目的 †
N本腕バンディットに対して,よい成績(スコア)を得ることができるプログラムの作成を目標とする.
N本腕バンディットって何? †
N本腕バンディットとは,N本のレバーのあるスロットマシンのようなものである.各レバーには当たり確率等が設定されており,レバーを引くことによって"当たり"または"はずれ"が決定する."当たり"となると,報酬(お金など)をもらうことができる.
N本腕バンディット問題とは,プレーヤーはいかに多くの報酬を獲得するか,という問題であり,バンディットとプレーヤー間の競争ゲームとなる.
製作方法 †
解く対象のN本腕バンディット一覧 †
NetBSD amd64用(S-JIS,CRLF) †
- 共通:
- ヘッダファイル
- バンディットプログラム
- made by K.K
Windows用(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は前回選択した腕でいくら報酬がもらえたか,である.試行の第1回目は"前回"がないので,この場合には"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