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

Москва. 15 сентября. INTERFAX.RU - Студент из Имперского колледжа в Лондоне создал шахматную компьютерную программу Giraffe, которая полностью построена на принципах машинного обучения и не использует вручную настроенные инструменты для анализа партии. Giraffe обучалась в ходе игры с самой собой и за рекордные 72 часа достигла уровня, соответствующего двум верхним процентам рейтинга по версии Международной шахматной ассоциации. Об этом сообщает издание N+1 со ссылкой на препринт магистерской диссертации с описанием программы, доступный на arXiv.org.

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

Традиционно в шахматных программах применяется метод, основанный на максимальной длине ветвей. Например, на каждом ходе алгоритм проанализирует все доступные ветви не далее, чем на 10 ходов. В Giraffe автор вместо длины ветви использовал значение вероятности того, что данная ветвь приведет к наиболее длинной цепочке ходов. Таким образом, анализировались только те ветви, в которых эта вероятность была выше определенного порога.

За таким методом существует следующее объяснение: поиск наилучшего хода основан на том предположении, что противник также выберет наилучший ход. Таким образом, партия будет развиваться настолько долго, насколько это возможно. При этом некоторые ситуации на доске (к примеру, шах или размен ценных фигур) требуют обязательных ответных ходов, таким образом ограничивая число возможных продолжений. Если, например, в данной партии происходит размен ферзей, алгоритм, основанный на глубине ветви, будет анализировать в том числе и все доступные ветви, где ферзя все-таки не взяли, просто потому, что все эти ветви окажутся короче пороговой величины. При этом алгоритм на основе вероятностей наоборот, — будет двигаться в сторону наиболее длинной ветви с наименьшим числом развилок.

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

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