ТД-Гаммон

TD-Gammon — компьютерная программа для игры в нарды, разработанная в 1992 году Джеральдом Тезауро в IBM компании Исследовательском центре Томаса Дж. Уотсона . Его название происходит от того факта, что это искусственная нейронная сеть, обученная методом обучения временной разности , в частности TD-Lambda .

Окончательная версия TD-Gammon (2.1) была обучена с помощью 1,5 миллионов игр самостоятельно и достигла уровня игры чуть ниже уровня лучших игроков в нарды того времени. Он исследовал стратегии, которые люди не использовали, и привел к прогрессу в теории правильной игры в нарды.

В 1998 году в серии из 100 игр она проиграла чемпиону мира с перевесом всего в 8 очков. Его нетрадиционная оценка некоторых дебютных стратегий была принята и принята опытными игроками.

Алгоритм игры и обучения

Во время игры TD-Gammon на каждом ходу проверяет все возможные допустимые ходы и все возможные ответы на них (двойной просмотр вперед ), передает каждую результирующую позицию на доске в свою функцию оценки и выбирает ход, который приведет к положению на доске, получившему наивысшую оценку. счет. В этом отношении TD-Gammon ничем не отличается от почти любой другой программы для компьютерных настольных игр. Инновация TD-Gammon заключалась в том, как она научилась выполнять свою функцию оценки.

Алгоритм обучения TD-Gammon состоит в обновлении весов в нейронной сети после каждого хода, чтобы уменьшить разницу между оценкой позиций доски предыдущих ходов и оценкой позиции доски текущего хода — отсюда « обучение с временной разницей ». Счет на любой позиции на доске представляет собой набор из четырех чисел, отражающих оценку программой вероятности каждого возможного результата игры: белые выигрывают в обычном режиме, черные выигрывают в обычном режиме, белые выигрывают окорок, черные выигрывают окорок. Для окончательного положения доски в игре алгоритм сравнивает ее с фактическим результатом игры, а не с собственной оценкой положения доски.

После каждого хода алгоритм обучения обновляет каждый вес в нейронной сети согласно следующему правилу:

$w_{t+1}-w_{t}=\alpha (Y_{t+1}-Y_{t})\sum _{k=1}^{t}\lambda ^{t-k}\nabla _{w}Y_{k}$

где:

$w_{t+1}-w_{t}$	— это сумма, на которую изменится вес по сравнению с его значением на предыдущем ходу.
$Y_{t+1}-Y_{t}$	это разница между оценками доски текущего и предыдущего хода.
$\alpha$	является параметром « скорости обучения ».
$\lambda$	— это параметр, который влияет на то, насколько текущая разница в оценках совета директоров должна быть связана с предыдущими оценками. $\lambda =0$ заставляет программу корректировать только оценку предыдущего хода; $\lambda =1$ заставляет программу попытаться исправить оценки на всех предыдущих ходах; и ценности $\lambda$ от 0 до 1 определяют разные скорости, с которыми важность более старых оценок должна «угасать» со временем.
$\nabla _{w}Y_{k}$	— это градиент выходных данных нейронной сети по отношению к весам: то есть насколько изменение веса влияет на выходные данные.

Эксперименты и этапы обучения

В отличие от предыдущих программ игры в нарды с использованием нейронных сетей, таких как Neurogammon (также написанная Тезауро), где эксперт обучал программу, предоставляя «правильную» оценку каждой позиции, TD-Gammon сначала была запрограммирована «без знаний». В ранних экспериментах, используя только необработанную кодировку доски без каких-либо функций, разработанных человеком, TD-Gammon достиг уровня игры, сравнимого с Neurogammon: уровня человека, играющего в нарды среднего уровня.

Несмотря на то, что TD-Gammon сама обнаружила полезные функции, Тезауро задался вопросом, можно ли улучшить ее игру, используя функции, разработанные вручную, такие как Neurogammon. Действительно, самообучающаяся TD-Gammon с специально разработанными функциями вскоре превзошла все предыдущие компьютерные программы для игры в нарды. Он перестал улучшаться примерно после 1 500 000 игр (самостоятельная игра) с использованием трехслойной нейронной сети со 198 входными блоками, кодирующими разработанные экспертами функции, 80 скрытыми блоками и одним выходным блоком, представляющим прогнозируемую вероятность выигрыша.

Достижения в теории нард

Эксклюзивное обучение TD-Gammon посредством самостоятельной игры (а не опеки) позволило ему исследовать стратегии, которые люди ранее не рассматривали или исключали ошибочно. Успех компании в использовании неортодоксальных стратегий оказал значительное влияние на сообщество игроков в нарды.

Например, в дебютной игре общепринятое мнение заключалось в том, что при выпадении 2-1, 4-1 или 5-1 белые должны переместить одну шашку из пункта 6 в пункт 5. Это явление известно как «прорезь». Техника меняет риск попадания на возможность развить агрессивную позицию. TD-Gammon обнаружил, что более консервативная игра 24-23 была лучше. Турнирные игроки начали экспериментировать с ходом TD-Gammon и добились успеха. Через несколько лет слоттинг исчез из турнирной игры, хотя в 2006 году он снова появился со счетом 2-1.

Эксперт по нардам Кит Вулси обнаружил, что позиционное суждение TD-Gammon, особенно соотношение риска и безопасности, превосходит его собственное или суждение любого человека.

Превосходная позиционная игра TD-Gammon была подорвана случайной неудачной игрой в эндшпиле. Финал требует более аналитического подхода, иногда с обширным прогнозом. Ограничение TD-Gammon на двухслойный просмотр вперед ограничивало возможности TD-Gammon в этой части игры. Сильные и слабые стороны TD-Gammon были противоположностью символических программ искусственного интеллекта и большинства компьютерных программ в целом: он был хорош в вопросах, требующих интуитивного «чувства», но плох в систематическом анализе.

См. также

• Всемирная федерация нард

Ссылки

Цитируемые работы

• Саттон, Ричард С.; Барто, Эндрю Г. (2018). «11.1 ТД-Окорок» . Обучение с подкреплением: Введение (2-е изд.). Кембридж, Массачусетс: MIT Press.
• Тезауро, Джеральд (март 1995 г.). «Обучение с временными различиями и TD-гаммон» . Коммуникации АКМ . 38 (3): 58–68. дои : 10.1145/203330.203343 .

Внешние ссылки

• TD-Gammon в IBM
• TD-Gammon на GitHub