TD-Gammon - TD-Gammon

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

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

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

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

Алгоритм обучения TD-Gammon состоит в обновлении весов в своей нейронной сети после каждого хода, чтобы уменьшить разницу между оценкой позиций доски в предыдущих ходах и оценкой позиции доски в текущий ход - отсюда "обучение с разницей во времени ". Оценка любой позиции на доске представляет собой набор из четырех чисел, отражающих оценку программой вероятности каждого возможного результата игры: белые обычно выигрывают, черные обычно выигрывают, белые выигрывают окорок, черные выигрывают окорок. Для последней позиции на доске игры алгоритм сравнивает с фактическим результатом игры, а не с собственной оценкой положения доски.^[1]

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

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

куда:

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

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

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

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

Успехи в теории нардов

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

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

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

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

Рекомендации

1. Тесауро, Джеральд (март 1995). "Изучение временной разницы и TD-Gammon". Коммуникации ACM. 38 (3). Дои:10.1145/203330.203343. Получено 1 ноя, 2013.
2. Саттон, Ричард С .; Эндрю Дж. Барто (1998). Обучение с подкреплением: введение. MIT Press. С. Таблица 11.1.
3. «Нарды: как играть в первые ролики».