人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

TD-Gammon

TD-GammonはIBMのTesauroさんが作ったプログラムである。強化学習の TD(λ) というアルゴリズムを用いて、バックギャモンというゲームの戦略を「自動的に」獲得する。このTD-Gammonによって強化学習が注目されるようになったという経緯がある。

今までバックギャモンというゲームは全く知らなかったのだが、何とWindowsに「インターネットバックギャモン」というのが入っているではないか。気づかなかった・・・試しにルールを見てやってみた。バックギャモンは日本語で西洋すごろくとも言うらしいが、さいころを振って移動させたり、振り出しにもどるなどすごろくっぽいところがある。チェスより歴史は古く、競技人口やプロの数も多いらしい。「すごろくにプロとかあるの?」という感じがするが、相当奥が深いみたい。

で、このバックギャモンを強化学習を使って鍛えるわけだが、状態数が10の20乗もあるため、表形式では対応できない(10の20乗の配列なんて用意できない)。そこで、巨大な状態空間に対応するための関数近似として3層パーセプトロンを用いている。3層パーセプトロンは非線形関数近似と呼ばれ、扱うのはかなり難しいらしい(SuttonさんのFAQ参照)。自分は線形関数近似さえ実装の仕方がいまいち分からないのでそれ以前。

それで、学習はどうやるかと言うと、自己対戦させる。つまり、自分自身と何度も何度も対戦させることを繰り返す。Tesauroさんの論文によると、1500000回自己対戦ゲームをさせると世界チャンピオンに匹敵する強さが出るらしい。何かすさまじい回数だ。学習に一体何日かけたのか。

このTD-Gammonのすごいところはルール以外の知識与えていない点。従来のゲームプログラミングではプロの知識(ヒューリスティクス)を直接プログラムしたり、プロの棋譜データをもとに教師あり学習をさせていた。TD-Gammonではプロの知識も与えないし、プロの棋譜データも教師信号として与えない。何もないところから試行錯誤だけで、プロ級の能力を獲得している(そのために学習に時間がかかるという欠点がある)。

この強化学習の能力は、非常に重要だと思う。強化学習は応用上期待できることとして、

  • 直接プログラミングしなくても目標状態に報酬を置いておくだけで、それに到達する最適な経路を自動的に獲得できる。
  • 人がコーディングするより、優れた解を発見できる可能性がある。

などが挙げられている*1。このTD-Gammonは複雑な実問題でそれを実現した先駆者となっている。ここで注意しておきたいのが、「成功と言ったってたかがゲームじゃないか」という人がいることである。それは違う(「らしい」としか言えない)。確か、松原仁さんだったと思うけど(どの論文か記事かは忘れた)、ゲーム(チェス、将棋、碁など)は閉じていて明確な規則のある世界だが、実問題に引けをとらないほど状態数、分岐数が多く、十分複雑であると述べていた

参考

*1:木村, 宮崎, 小林: 強化学習システムの設計指針, 計測と制御, Vol.38, No.10, 1999