TD-Gammon ── 自己対戦で学び、人間の定跡を変えたバックギャモン AI

TD-Gammon は、IBM トーマス・J・ワトソン研究所の Gerald Tesauro が開発したバックギャモンのプログラムである。人間の名手の棋譜を教材にせず、ニューラルネットワークが自分自身と対局を繰り返し、勝ち負けの結果から局面の良し悪しを学んだ。学習法は Richard Sutton の TD(λ)（時間的差分学習）で、Sutton と Barto の教科書は、これを 強化学習 の応用のなかで最も印象的なものの一つに数えている。最初の論文は1992年5月の Machine Learning 誌に載り、同じ1992年に、2手先読みを加えた版が世界大会の場で一流選手とエキシビションで対局した。TD-Gammon の判断は人間の定跡を書き換え、自己対戦で学ぶという方法は、のちの AlphaGo や AlphaZero へとつながっていく。

1992年の論文 ── 知識ゼロから学ぶ

1992年5月の論文「Practical issues in temporal difference learning」（Machine Learning 8巻、257〜277ページ）の要旨で、Tesauro は、Sutton の TD(λ) のような時間的差分法がニューラルネットワークの訓練で現実の複雑な問題に使えるかを調べたと書く。題材は、自己対戦の結果からバックギャモンを学ぶことだった。要旨によれば、これは複雑で自明でない課題にこのアルゴリズムを使った、おそらく最初の例である。知識を何も組み込まなくても、ネットワークは一からゲーム全体をかなり強い中級の水準まで学び、市販のプログラムをはっきり上回り、人間の専門家の大量の棋譜で訓練した同等のネットワークをも超えた。

背景には Tesauro 自身の前作がある。1995年の Communications of the ACM の解説によれば、前作の Neurogammon は専門家の対局記録を使って 誤差逆伝播法 で訓練され、いくつかの手作りの特徴も入力に含めていた。Neurogammon は1989年のコンピュータ・オリンピアードで優勝したが、強さは強い中級の水準にとどまった。人間の知識を教え込む方法の限界を超えられるかが、TD-Gammon の問いだった。

どう学んだか

ネットワークは盤面を入力として受け取り、白と黒のどちらが普通の勝ちまたはギャモン（二倍勝ち）を収めるかの見込みを出力する。1局ごとに、ある局面での予測と次の局面での予測の差を誤差とみなし、その誤差で重みを少しずつ直す。過去の局面の見積もりも、時間とともに減衰させながら修正する。最終的な報酬は対局の勝敗だけで、どの手が良かったかを教える教師はいない。

CACM の解説によると、最初の数千局でネットワークは相手の駒を打つ、安全に指す、新しいポイントを作るといった基本を覚え、より高度な概念は数万局を経て現れた。ネットワークの大きさと学習量を増やすほど強くなるという性質も見つかった。Tesauro は、学習した重みの中に、知識エンジニアなら有用な特徴と呼ぶであろうパターンが現れたとして、これを「特徴の自動発見」の例とした。

Sutton と Barto の教科書『Reinforcement Learning』第2版は、各版の成績を次のようにまとめている。

教科書は、これらの結果と名手たちの分析から、3.0版は世界最強の人間に近いか、それを上回る可能性のある強さだったとまとめている。

CACM の解説によれば、1.0は1991年末に元世界王者の Bill Robertie と Paul Magriel、当時世界11位の Malcolm Davis と計51局を指し、1局あたり約4分の1点の負けにとどまった。2手先読みを加えた2.0は、1992年のバックギャモン・ワールドカップで公の場に初めて登場し、Kent Goulding、Kit Woolsey、元世界王者の Joe Russell らとのエキシビション38局で7点の負けだった。

人間の定跡が変わった

TD-Gammon の影響は、プログラムの強さより、人間の指し方に現れた。CACM の解説によると、2-1、4-1、5-1 の出目で始まる序盤では、それまで約30年間、6のポイントから5のポイントへ駒を1つ動かす「スロット」がほぼ全員の選択だった。1992年に Robertie が Inside Backgammon 誌に書いた TD-Gammon の記事は、ロールアウト分析によってスロットが後方の駒を24-23に分ける「スプリット」に劣ることを示した。数人の一流選手が試して大会で結果を出すと支持が広がり、解説が書かれた1995年には、スプリットがほぼ全員の選択になり、スロットは大会からほとんど姿を消したという。

一流選手の Kit Woolsey は Tesauro への書面の評価で、"There is no question in my mind that its positional judgment is far better than mine." と書いた。ただし同じ評価で、駒の接触がない局面などでは、人間が計算で上回ることもあるとしている。

Sutton と Barto の教科書によれば、TD-Gammon に触発された自己学習型のプログラム Jellyfish、Snowie、GNU Backgammon が広く出回ったことで、ニューラルネットワークの生んだ新しい知識が一気に広まり、人間の大会の水準は大きく上がった。教科書は、バックギャモンが世界中で大会が開かれ、多額の金銭を賭けて遊ばれることも多いゲームだとも書いている。機械が人間の専門家の知識を学ぶのではなく、人間が機械から学び直すという関係が、ここで早くも現れた。

その後 ── Watson と AlphaGo へ

Tesauro は TD-Gammon の手法をその後の仕事にも使った。Sutton と Barto の教科書によれば、2011年にクイズ番組で人間の王者に勝った IBM の Watson で、賭け金を決める「デイリーダブル」の戦略は、Tesauro らが TD-Gammon を応用して作ったものだった。

自己対戦と強化学習でゲームを覚えるという筋道は、1959年の Samuel のチェッカー から TD-Gammon を経て、2016年の AlphaGo、人間の棋譜を使わない2017年の AlphaZero へと続く。ただし Tesauro 自身は1995年の解説で、成功の一因としてバックギャモンの性質を挙げている。サイコロの偶然が学習中の局面に変化を与えるため、自己対戦でも広い範囲の局面を経験できる。決定論的なゲームでは、自己対戦で学ぶシステムが局面空間のごく狭い部分しか探索せず、ひどい戦略に落ち着いてしまうおそれがある、と Tesauro は書いた。AlphaGo と AlphaZero は、自己対戦による強化学習にモンテカルロ木探索を組み合わせている。それぞれの仕組みは各ページにある。