Программа за 72 часа сама себя научила играть в шахматы

Студент из Имперского колледжа в Лондоне создал шахматную компьютерную программу Giraffe, которая полностью построена на принципах машинного обучения и не использует вручную настроенные инструменты для анализа партии. Giraffe обучалась в ходе игры с самим собой и за рекордные 72 часа достигла уровня, соответствующего двум верхним процентам рейтинга по версии Международной шахматной ассоциации. Препринт магистерской диссертации с описанием программы выложен на arXiv.org.
Автор использовал два подхода, принципиально отличавших Giraffe от аналогичных шахматных программ. Во-первых, для оценки позиции на доске алгоритм автоматически отбирал наиболее значимые признаки в ходе игр с самим собой (пример машинного обучения с подкреплением). При этом программа не имела доступа к предварительно заложенным рекомендациям, известным, например, из привлечения шахматных экспертов к разработке или предварительного анализа большого числа партий.
Во-вторых, в Giraffe использовался качественно новый подход к анализу дерева решений. Так как в ходе типичной шахматной партии может возникнуть огромное число допустимых вариантов хода, для того, чтобы проанализировать их все, необходимы вычислительные мощности, доступные только на суперкомпьютерах. Для того, чтобы снизить объем вычислений, алгоритм на каждом ходе анализирует лишь часть дерева решений.
Традиционно в шахматных программах применяется метод, основанный на максимальной длине ветвей. Например, на каждом ходе алгоритм проанализирует все доступные ветви не далее, чем на 10 ходов. В Giraffe автор вместо длины ветви использовал значение вероятности того, что данная ветвь приведет к наиболее длинной цепочке ходов. Таким образом, анализировались только те ветви, в которых эта вероятность была выше определенного порога.
За таким методом существует следующее объяснение: поиск наилучшего хода основан на том предположении, что противник также выберет наилучший ход. Таким образом, партия будет развиваться настолько долго, насколько это возможно. При этом некоторые ситуации на доске (к примеру, шах или размен ценных фигур) требуют обязательных ответных ходов, таким образом ограничивая число возможных продолжений. Если, например, в данной партии происходит размен ферзей, алгоритм, основанный на глубине ветви, будет анализировать в том числе и все доступные ветви, где ферзя все-таки не взяли, просто потому, что все эти ветви окажутся короче пороговой величины. При этом алгоритм на основе вероятностей наоборот, — будет двигаться в сторону наиболее длинной ветви с наименьшим числом развилок.

В итоге Giraffe в течение 72 часов обучался в ходе игры с самим собой, а его окончательная сила проверялась на специальном наборе из 15000 позиций, в которой все доступные ходы проранжированы от 0 до 10, где 10 соответствует лучшему ходу. Из девяти популярных алгоритмов для настольных компьютеров и небольших серверов Giraffe занял второе место по эффективности, обнаружив 9641 «правильный» ход из 15000. Первое место заняла программа Stockfish 5, которая нашла 10505 наилучших решений.

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

Шахматные компьютеры разрабатывались с середины XX века, однако лишь в 1990-х годах они достигли уровня гроссмейстеров. В 1997 году суперкомпьютер

в шести партиях обыграл действующего чемпиона мира Гарри Каспарова. С тех пор шахматные компьютеры становились только сильнее, и на сегодняшний день игроки-люди не могут соревноваться с топовыми программами. Тем не менее, существуют классические настольные игры, в которых человек до сих пор обыгрывает даже самые мощные суперкомпьютеры. Наиболее известным примером является

 — игра, появившаяся в Китае несколько тысяч лет назад.