いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その1)

ゲームを作っていくときに必要となるのが、AIの作成。

変種オセロを作っているときにもいくつかの探索アルゴリズムを実装したけれど、盤面の評価については単純に「出来るだけ自分の色が多く、そして相手の色が少ない方がいい」としただけだった。
ただ、これだと辺や隅をとることの重要性をまったく理解できず、人に簡単に辺や隅を取られてしまう。
なので、途中までは実利が大きくても、最後には辺や隅の力で実利がひっくり返されるということがよく起きて、なかなか勝てなかったりする。
そこで、AIをより強くするには、盤面をより正確に評価できるようにする必要がある。

盤面の評価方法

盤面をどのように評価するかーーすなわち、盤面の評価関数をどのように作るかーーというのには、いくつかの方法が考えられる。

人の手による方法

まず考えられるのは、盤面の特徴的な値に対して、それぞれ評価の重みを決めておき、それらを掛けて合算した値を盤面の評価値とする方法。
(なお、何を特徴的な値とするかや、その特徴の評価の重みは、人が調整していくことになる)

例えば、自分の色のコマ1個につき+1点、相手の色のコマ1個につき-1点、自分のコマが辺にあれば、1個につき+5点、相手のコマが辺にあれば、1個につき-5点、自分のコマが隅にあれば、1個につき+10点、相手のコマが隅にあれば、1個につき-10点、といった具合に決めておいて、それらを合算した値を盤面の評価値とする。

この場合、例えば

[005] turn: O, token: -
    1   2   3   4   5   6   7   8   9
  +---+---+---+---+---+---+---+---+---+
1 |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+---+
2 |   |   |   |   |   | O | X |   |   |
  +---+---+---+---+---+---+---+---+---+
3 |   |   |   |   |   | X | O |   |   |
  +---+---+---+---+---+---+---+---+---+
4 |   |   |   | - | X | O |   |   |   |
  +---+---+---+---+---+---+---+---+---+
5 |   |   |   | X | O | O |   |   |   |
  +---+---+---+---+---+---+---+---+---+
6 |   |   |   | O | X | - |   |   |   |
  +---+---+---+---+---+---+---+---+---+
7 |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+---+
8 |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+---+
9 |   |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+---+

という盤面で、(1, 7)という場所にOを置くと、盤面は

[006] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   | O | - |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   | X | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | X | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   |   | X | O | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+

となり、評価値は、7*(+1) + 4*(-1) + 1*(+5) + 0*(-5) + 0*(+10) + 0*(-10) = 8点となる。

代わりに、(5, 3)という場所にOを置くと、盤面は

[006] turn: X, token: -
     1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   | O | X |   |   |
   +---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   | X | O |   |   |
   +---+---+---+---+---+---+---+---+---+
 4 |   |   |   | - | X | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 5 |   |   | O | - | O | O |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 6 |   |   |   | O | X | - |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+

となって、評価値は、7*(+1) + 4*(-1) + 0*(+5) + 0*(-5) + 0*(+10) + 0*(-10) = 3点となる。

なので、いずれの盤面も0とXの数は同じだけれど、前者の方が後者よりもいいと評価され、辺や隅を取りやすくなる。

※変種オセロ、YWFについては、変種オセロを考えてみた。(まとめ) - いものやま。を参照。

ただ、問題となるのは、

  • 何を盤面の特徴的な値とすればいいのか
  • 盤面の特徴的な値に対する評価の重みをどれくらいにすればいいのか

というのが分からないので、試行錯誤を繰り返して、適切なパラメータを発見する必要が出てくるということ。

直感的には、辺や隅が大事だということは分かるのだけど、それがどれくらい大事なのかを数値として表現するのは難しいし、あるいは、辺や隅という要素以外にも重要な要素があるかもしれないのに、それらを見落としている可能性もある。

そこで出てくるのが、機械学習を使ってーーつまり、コンピュータに「学習」を行わせることによってーー評価関数を作るという方法。

機械学習による方法

機械学習というのは、コンピュータに「学習」を行わせて、ある課題に対するコンピュータの「判断能力」を向上させていくための方法のこと。

例えば、今回の話であれば、コンピュータに学習を行わせることで、盤面の評価をより正確に出来るようにしていくことになる。

さて、機械学習と一言に言っても、そこにはいくつかの方法がある。
代表的なものとして、「教師あり学習」と「教師なし学習」、それに「強化学習」だ。

「教師あり学習」とは、課題に対する「正解」を教えてもらえるので、その正解の情報を使って判断能力を向上させていく方法だ。
といっても、ゲームの場合、何が「正解」なのかは(理論上は存在したとしても)分からないことが多い(というか、それが簡単に分かってしまうのなら、ゲームにならない)ので、プロや強い人の手を「とりあえずの正解」として、その手に出来るだけ近づけるように学習していくことになる。

一方、「教師なし学習」の場合、課題に対する「正解」は教えてもらえない。
そこで、自分の中で何かしらの基準を決めて、その基準の値を改善していくように学習していくことになる。
ゲームに応用するならば、いろんな盤面を眺めて、「これとこれは似てる・・・」「これとこれは似てない・・・」と分類していくことで、そのゲームの特徴を見つけ出していき、判断能力を向上させるといったことになるだろう。

じゃあ、「強化学習」はというと、これは「教師あり学習」とも「教師なし学習」とも、ちょっと違う。
というのも、「教師なし学習」と同じように課題に対する「正解」は教えてもらえないのだけど、代わりに「評価」だけは教えてもらえる。
そして、「教師なし学習」のように自分の中で決めた基準に従って判断能力を向上させていくのではなく、教わった「評価」の情報を使って判断能力を向上させていくことになる。
(言葉遣いに気をつけると、本当は「評価」ではなくて「報酬」が与えられるんだけど・・・これについては後述)
ゲームの場合は、最終的に勝てば100点、負ければ0点、引き分けなら50点などといった評価が与えられて、その評価から、より高い評価が得られる(=より勝ちやすくなる)ように学習をしていくことになる。

これだけだと「教師あり学習」と「強化学習」の違い(「正解が教えられる」と「評価が教えらえる」の違い)が分かりにくいかもしれないので、もう少し具体的な例を出してみる。

例えば、次のような課題があるとする。

【課題】
ある規則にしたがって5つの数字が並べられているので、次にくる数字を答えよ。

これに対して、次のようにいくつかの例題が用意されていて、コンピュータはそれらの例題を使って学習を行い、判断能力を向上させるとする。

(例題1)
 1, 3, 5, 7, 9 [正解は11]
(例題2)
 5, 8, 11, 14, 17 [正解は20]
(例題3)
 10, 9, 8, 7, 6 [正解は5]

「教師あり学習」の場合、例題を解いているときに、正解がなんなのかを教えてもらえるので、それを使って学習していくことになる。
例えば、1, 3, 5, 7, 9と来たら、次は11だということを教えてもらえるので、次に同じ問題が出たときには11と答えられるようにして、他の例題についても同様の類推を行えるようにすることを目指していく。

一方、「強化学習」の場合、例題を解いているときに正解は教えてもらえず、評価だけ教えてもらえることになる。
例えば、例題1で11と答えられれば「10点だよ」と教えてもらえて、それ以外の答えを言った場合には「残念、0点」ということしか教えてもらえない。
そうなると、間違えた場合、何が正解なのかは試行錯誤してみないと分からないことになる。
それに、仮に10点をもらえたとしても、それが本当に最高点なのか分からない。
もしかしたら100点満点で、部分点で10点をもらえただけなのかもしれない。
なので、ある程度の評価をもらえたとしても、よりよい評価をもらえる可能性を考えて、たまには別の答えにチャレンジしてみる必要があるかもしれない。

これが「正解」を教えてもらえるのかそうでないかの違い。
「正解」を教えてもらえる場合は、その正解を答えられるように調整していけばいいだけ(といっても、それだけでも結構難しいんだけど・・・)なのに対して、「正解」を教えてもらえない場合は、正解を答えられるように調整するだけでなく、何が正解なのかを模索する必要も出てくる。

こうやって書くと「教師あり学習」の方が簡単そうに思えるかもしれないけれど、必ずしもそうではないのが難しいところ。
というのも、「教師あり学習」の場合、当然「正解」を用意しなければならないわけだけれども、ゲームの場合、「何が正解か」なんていうのはハッキリしないわけで。
プロだって間違える可能性はあるし、そもそもプロがいなかったり、十分なデータがなければ、学習を行うことは困難になってくる。
一方、「強化学習」であれば、「正解」を用意する必要はないので、最終的に勝てば100点、負ければ0点といったふうに点数をつけるだけで、学習を進めていくことが出来る。
もちろん、正解の模索を行わなければならないので、学習にはかなりの試行錯誤が必要になってくるけど。


(追記)
最初、「強化学習」を「教師なし学習」の一種として説明していたけれど、それは違うのではという指摘があったので、修正した。


今回学んでいこうとしているのは、「強化学習」。
すなわち、正解の行動は教えてもらえないけれど、行動に対する評価(正しく言うと、報酬)だけは与えられる状態で、コンピュータの判断能力を向上させていく方法について学んでいく。
ただし、盤面の数は膨大なので、評価関数を構築していく際に、「教師あり学習」の手法を部分的に用いるということは出てくる。(関数近似

強化学習を学んでいくときに参考にした本は、以下。

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る

この本の流れをベースにして、所々で実際にプログラムを書きながら進めていきたいと思う。

今日はここまで!