TD-Gammonは、1990年代にIBMのトーマス・J・ワトソン研究所でジェラルド・テサウロによって開発されたコンピュータバックギャモンプログラムである。その名前は、時間差学習、具体的にはTD-Lambdaを用いて訓練された人工ニューラルネットワークの使用に由来する。それは人間が追求していなかった戦略を探求し、正しいバックギャモンのプレイ理論の進歩をもたらした。1993年、TD-Gammon（バージョン2.1）は150万ゲームの自己対戦で訓練され、当時のトップ人間バックギャモンプレイヤーにわずかに及ばないレベルのプレイを達成した。1998年、100ゲームシリーズ中、それは世界チャンピオンにわずか8ポイントの差で敗れた。いくつかのオープニング戦略に対するその型にはまらない評価は、専門家プレイヤーによって受け入れられ、採用された。TD-Gammonは、強化学習とニューラルネットワークの初期の成功例として一般的に引用され、深層Q学習やAlphaGoに関する論文で参照された。
プレイと学習のアルゴリズム
プレイ中、TD-Gammonは各ターンで可能なすべての合法手とそのすべての可能な応手（先読み探索）を調べ、結果として得られる各ボード位置をその評価関数に入力し、最高スコアを得たボード位置につながる手を選択する。この点で、TD-Gammonは他のほとんどすべてのコンピュータボードゲームプログラムと変わらない。TD-Gammonの革新は、その評価関数をどのように学習したかにあった。
TD-Gammonの学習アルゴリズムは、各ターン後にニューラルネットワークの重みを更新して、前のターンのボード位置の評価と現在のターンのボード位置の評価との差を減らすことから成る。したがって「時間差学習」と呼ばれる。任意のボード位置のスコアは、各可能なゲーム結果の可能性のプログラムの推定を反映する4つの数値のセットである：白が通常勝利、黒が通常勝利、白がギャモン勝利、黒がギャモン勝利。ゲームの最終ボード位置については、アルゴリズムは自身のボード位置の評価ではなく、ゲームの実際の結果と比較する。
TD-Gammonの中核は、3層のニューラルネットワークである。入力層には2種類のニューロンがある。1つの種類はボード位置をコード化する：0から15までの非負整数で、各ボード位置の白または黒のチェッカーの数を示し、それぞれに99個の入力ニューロンがあり、合計198個のニューロンとなる。もう1つの種類は、Neurogammonで以前使用された手作りの特徴をコード化し、「高度なアンカー」、「封鎖の強さ」、「ホームボードの強さ」、および「ブロット」（単一チェッカー）がヒットされる確率など、人間の専門家が使用する標準的な概念をエンコードする。隠れ層には隠れニューロンが含まれ、後のバージョンではより多くが含まれる。出力層には4つのニューロンが含まれ、現在のボードが白の通常勝利、白のギャモン勝利、黒の通常勝利、黒のギャモン勝利につながる確率（「エクイティ」）のネットワークの推定を表す。バックギャモン勝利は非常に稀であるため、テサウロはそれを表現しないことを選択した。
各ターン後、学習アルゴリズムは次の規則に従って各重みを更新する：w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k、ここでalphaは学習率、Y_tはターンtでの評価、lambdaは減衰パラメータである。小さなlambdaを選ぶと性能がほぼ同等に良く、大きなlambdaは性能を低下させることがわかった。このため、1992年以降、TD-Gammonはlambda = 0で訓練され、標準的なTD学習に退化し、計算を2倍節約した。
開発の歴史
バージョン1.0は単純な1プライ探索を使用した：すべての次の手がニューラルネットワークによってスコアリングされ、最高スコアの手が選択される。バージョン2.0と2.1は2プライ探索を使用した：まず1プライ分析で可能性の低い手を除去（「前方枝刈り」）、次に可能性のある手のみに対して2プライミニマックス分析を行い、相手の21の可能なサイコロの出目のそれぞれで確率重み付けされた最良の手を選択する（非ダブルをダブルの2倍に重み付け）。バージョン3.0と3.1は3プライ探索を使用し、21ではなく21^2 = 441の可能なサイコロの出目を使用した。最後のバージョン3.1は、1998年のAAAIチャンピオンの殿堂でのマルコム・デイビスとのエキシビションマッチのために特別に訓練された。それは-8ポイントで敗れ、主に1つの失策によるもので、TD-Gammonはダブルを選択し、-32ポイントでギャモンされた。
実験と訓練の段階
Neurogammon（これもテサウロによって書かれた）のような以前のニューラルネットワークバックギャモンプログラムとは異なり、専門家が各位置の「正しい」評価を供給してプログラムを訓練したが、TD-Gammonは当初「知識なし」でプログラムされた。初期の実験では、人間が設計した特徴なしの生のボードエンコーディングのみを使用して、TD-GammonはNeurogammonに匹敵するプレイレベルに達した：中級レベルの人間バックギャモンプレイヤーのそれである。
TD-Gammonは独自に洞察に富んだ特徴を発見したが、テサウロはNeurogammonのような手設計の特徴を使用することでそのプレイが改善されるかどうか疑問に思った。実際、専門家設計の特徴を持つ自己訓練のTD-Gammonは、すぐにすべての以前のコンピュータバックギャモンプログラムを上回った。それは、専門家設計の特徴をエンコードする198個の入力ユニット、80個の隠れユニット、および勝利の予測確率を表す1つの出力ユニットを持つ3層ニューラルネットワークを使用して、約150万ゲーム（自己対戦）後に改善を停止した。
バックギャモン理論の進歩
TD-Gammonの自己対戦のみによる排他的な訓練（模倣学習ではなく）により、人間が以前に考慮していなかったか、誤って除外していた戦略を探求することができた。型にはまらない戦略でのその成功は、バックギャモンコミュニティに大きな影響を与えた。1991年後半、ビル・ロバーティ、ポール・マグリエル、およびマルコム・デイビスがTD-Gammon（バージョン1.0）と対戦するよう招待された。合計51ゲームがプレイされ、TD-Gammonは-0.25 ppgで敗れた。ロバーティはTD-Gammonが強い人間プレイヤーのレベルにあると感じ、その型にはまらない手は後に専門家によって採用され、オープニング戦略の理解を変えた。
遺産と影響
TD-Gammonは、機械学習と人工知能の画期的な成果として広く認識されており、ニューラルネットワークが自己対戦と時間差学習を通じて複雑な戦略ゲームを学習できることを実証した。その成功は、深層QネットワークやAlphaGoの開発を含む、その後の強化学習の研究に影響を与えた。人間が見逃していた新しい戦略を発見するプログラムの能力は、ゲームプレイにおいて人間の直感を超えるニューラルネットワークの可能性を強調し、それはAI研究の歴史における古典的な例として残っている。