Приложения методов обучения к ведению игр
Первое реальное приложение метода обучения с подкреплением оказалось также первой практически применимой программой из всех возможных типов таких программ; речь идет о программе игры в шашки, написанной Артуром Самюэлом [1349], [1350]. Самюэл впервые использовал для оценки позиций взвешенную линейную функцию, в которой одновременно применялось до 16 термов. В его программе обновление весов осуществлялось на основе некоторой версии уравнения 21.11. Тем не менее методы, применяемые в его программе, имели определенные существенные отличия от современных методов. Первое отличие состояло в том, что для обновления весов использовалась разность между значениями для текущего состояния и зарезервированным значением, сформированным путем полного опережающего просмотра в дереве поиска. Такой подход оказался очень успешным, поскольку он равносилен подходу, в котором пространство состояний рассматривается с разными степенями детализации. Второе отличие состояло в том, что в программе Самюэла не использовались какие-либо наблюдаемые вознаграждения! Это означает, что значения терминальных состояний игнорировались. Таким образом, существовала реальная возможность, что вычисления в программе не будут сходиться, или по крайней мере сходиться к стратегии, позволяющей выиграть, а не проиграть. Но автор программы сумел избежать подобного неблагоприятного развития событий, соблюдая такое требование, что вес материального преимущества должен всегда быть положительным. Замечательно то, что этого оказалось достаточно, чтобы всегда направлять программу в область пространства весов, соответствующую успешной игре в шашки.
Возможности методов обучения с подкреплением особенно наглядно показала система TD-Gammon Герри Тесауро [1499]. В одной из более ранних работ [1501] Тесауро попытался определить с помощью обучения некоторое представление функции Q(a, s) в виде нейронной сети непосредственно на примерах ходов, которым были присвоены относительные значения экспертом-человеком. Но, как оказалось, этот подход требовал исключительно высоких трудозатрат со стороны привлеченного эксперта. Применение такого подхода привело к созданию программы под названием Neurogammon, которая оказалась сильнее, чем другие программы игры в нарды, существовавшие в то время, но не выдерживала соревнования с опытными игроками в нарды. Проект TD-Gammon стал попыткой обучения программы исключительно в игре с самой собой. Единственный сигнал вознаграждения предоставлялся в конце каждой игры. Функция оценки была представлена в виде полносвязной нейронной сети с единственным скрытым слоем, содержащим 40 узлов. Программа TD-Gammon сумела в результате обучения достичь значительно более высокого уровня игры по сравнению с Neurogammon путем повторного применения уравнения 21.11, даже несмотря на то, что входное представление содержало только грубые оценки позиции на доске, без вычисленных характеристик. Для обучения программы потребовалось проведение около 200 ООО учебных игр и две недели машинного времени. Хотя такое количество игр может показаться очень большим, оно фактически составляет лишь исчезающе малую долю пространства состояний. После того как к входному представлению были добавлены предварительно рассчитанные характеристики с применением сети, включающей 80 скрытых элементов, в результате 300 000 учебных игр удалось достичь уровня игры, сравнимого с уровнем трех ведущих людей-игроков во всем мире. Кит Вулси, ведущий игрок и аналитик, сказал: "У меня не было малейшего повода, чтобы усомниться в том, что эта программа оценивает позицию гораздо лучше по сравнению со мной".