up



はじめに

古くから,暇な時などに楽しむものとしてゲームは人々に親しまれている.現在では家庭用ゲーム機などに代表されるコンピュータゲームを主に指す言葉として知られているが,もちろんそれだけではない.100m走や幅跳び,砲丸投げなど身体能力を競う競争や競技も"ゲーム"である.また将棋やチェスといった知力を競う"ゲーム"も長い歴史を持ち,その延長上としてコンピュータゲームが登場し,次第に独自の文化を築いている.

特に知力を競うゲームを考えると,その起源は戦争の代替・練習のものとしてあると考えられている.そのためか,ゲームの基本性質として"対戦相手"が存在し,それに"勝利"することが共通した目的がある.ゲームはいくつかのタイプに分類することができるが,常勝(常に勝つ)のための方法・方策について様々な研究が行われ,学問にもなっている\cite{beasley1}.学問的に研究している学者も,プロ・アマ問わずそのゲームの競技者も,基本的にはまずゲームをプレイしルールに慣れ試行錯誤を行うところから始まる.次第に経験を通して勝つためのルールを自分なりに作成していき,常勝への道の探求を行うものである.

本演習では,簡単なゲームを対象にして,ゲームに"勝てる"方法を考え,アルゴリズム化(演算の定型化)を行い,プログラムにすることを目標とする.

製作対象

目的

N本腕バンディットに対して,よい成績(スコア)を得ることができるプログラムの作成を目標とする.

N本腕バンディットって何?

N本腕バンディットとは,N本のレバーのあるスロットマシンのようなものである.各レバーには当たり確率等が設定されており,レバーを引くことによって"当たり"または"はずれ"が決定する."当たり"となると,報酬(お金など)をもらうことができる.

N本腕バンディット問題とは,プレーヤーはいかに多くの報酬を獲得するか,という問題であり,バンディットとプレーヤー間の競争ゲームとなる.

N本腕バンディット問題.png

製作方法

解く対象のN本腕バンディット一覧

NetBSD amd64用(S-JIS,CRLF)

Windows用(S-JIS,CRLF)

Mac用

ヘッダ・オブジェクトファイル使用方法

  • 配布ファイル
    • ヘッダーファイル名: 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)
      • 選択可能な腕の数を知るための数.必要があれば使用.
      • 返り値:選択可能な腕の数.
  • 注意
    • srandは使用しないこと!
      • 乱数を使用する場合,srand()とrand()を使用する.ここで,srand()は乱数を使用するための初期化処理であり,プログラム中に一回のみの実行となる.一方,rand()は乱数を発生する関数であり,乱数が欲しい場合には毎回呼び出す.ここで,srandはinit_bandit()関数の中で実行しているので,プログラム中では絶対に使用しないこと!

ヘッダ・オブジェクトファイル使用例

評価方法

他人と競う時の,スコア計算方法

N本腕バンディットに対して,プレーヤーはより多くの報酬を得ることを目標とする.本演習では,プレーヤーは人ではなくN本腕バンディットを解くプログラムである.このプログラムが得た報酬を用いてプレーヤー(プログラム)のスコアを考える.

プレーヤーがN本腕バンディットのレバーを一回選択する行為を"1試行"という.この時,連続した10000試行の結果得た報酬の合計をプレーヤーのスコアとする.ただし,第一回目の試行から計算する必要はなく,試行途中の好きな時点からの試行でよい.

スコア計算法.png

基本的には,一回目の試行から計算を行い,全試行を通して最大の報酬をスコアとする.全試行数10,連続した3試行の結果得た報酬の合計をスコアとした場合の例を以下に示す.

スコア計算法例.png

公平なスコア計算を実現するために

スコアの計算方法が人によって異ならず,他の人と同様にスコア計算することは,公平な競技では重要である.ここでは,公平なスコア計算を行うために,以下のことを考える.

  • プレーヤー(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をするのに使う.
  • 上記関数を以下のファイルで実装し,オフィシャルに提供する
    • player.h
      • 上記関数の定義
    • player.o
      • gcc -c player.c で作成
      • player.cは関数decision_making(...)の実装を行う.
  • オフィシャル(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 ....を行わない方がよい.

過去の成績

スコアランキング一覧