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