Студент Имперского колледжа Лондона Мэтью Лай (Matthew Lai) разработал компьютерную программу Giraffe, которая трое суток играла в шахматы сама с собой — и смогла извлечь все предметно-ориентированные знания, необходимые для игры на уровне международного мастера ФИДЕ. Для этого ей достаточно вычислительных ресурсов нормального компьютера. Обучение нейросети происходило 72 часа в 20 тредов на машине с двумя 10-ядерными процессорами Xeon E5-2660.
В научной работе автор пишет, что после тренировки в течение 72 часов программа выбирала наилучший возможный ход в 46% случаев, а один из трёх наилучших ходов — в 70% случаев. Это очень неплохой результат даже для обычных шахматных программ.
Всем известен факт, что компьютеры лучше людей играют в шахматы, но не все понимают, за счёт чего они добиваются победы, ведь простого брутфорса недостаточно для перебора всех 10123 возможных ходов и ответов противника.
Во-первых, шахматные программы ограничивают максимальную глубину расчёта ветвей. Во-вторых, начиная с Deep Blue и заканчивая нынешним чемпионом среди компьютерных шахмат Komodo, они вряд ли победили человека, если бы настройку модуля оценки позиции не проводил гроссмейстер или очень хорошо разбирающиеся в шахматах люди, как группа разработчиков Deep Blue из компании IBM. В программу изначально закладывают базу дебютов и характерные приёмы игры, вроде защиты короля пешкой или атаки на короля в открытой позиции с разноцветными слонами.
Грамотная оценка позиции позволяет программе выбрать более предпочтительную ветвь для развития партии.
В связи с этим становится понятнее, почему новая программа Giraffe так отличается от остальных. Её никто не настраивал, она сама училась играть. К тому же, вместо банального брутфорса ветвей с ограничением по глубине, программа использует «вероятностный» подход. Она более глубоко прорабатывает те ветви, для которых больше вероятность длинного продолжения.
На иллюстрации показано дерево решений. Жёлтым цветом обозначены узлы дерева, видные стандартному алгоритму с ограничением на длину ветвей. Зелёным цветом — узлы, видные только алгоритму с ограничением по вероятности (Giraffe). Красным цветом обозначены узлы, видные для обоих алгоритмов.
Такой алгоритм основан на предпосылке, что соперник тоже ответит лучшим ходом среди возможных — и партия затянется на максимальное количество ходов. Именно такие ветви Giraffe выбирает для более глубокого анализа. В каком-то смысле логика работы программы похожа на логику опытных шахматистов, которые «интуитивно» чувствуют наиболее выгодные пути развития партии.
Получается, что на сегодняшний день прогресс в разработке нейросетей достиг такого уровня, что один студент может написать программу, способную за три дня самостоятельно научиться играть в шахматы на очень высоком уровне. На следующей диаграмме показана архитектура нейросети, которую изначально заложил автор. Он также составил набор начальных позиций для обучения программы.
Вот как в программе представляется позиция.
P.S. Профессор компьютерных наук Себастьян Трун (Sebastian Thrun) одним из первых в мире применил нейросети в шахматных программах. В середине 90-х он разработал программу NeuroChess. Впрочем, как и нынешняя программа Giraffe, та разработка тоже не могла обыграть лучших представителей «классической школы».
Комментарии (25)
ankh1989
17.09.2015 10:38+7И это всего лишь магистерская диссертация. Британские ученые не так просты как может показаться. А вообще интересно разобраться в том, что же придумал этот Мэтью: я тут уже пол года бьюсь с решалкой тсумего и никак не могу придумать способ которым бы эта решалка могла запоминать и применять разные трюки (хитрые ходы) для решения.
Psychopompe
17.09.2015 11:35+2Напишите ему, e-mail же есть.
ankh1989
20.09.2015 02:35Прочитал его статью. Ничего не понял. Как обычно бывает в таких диссертациях, цель не объяснить как это работает, а перечислить алгоритмы которые для этого использовались и сдобрить всё это таблицами где в подробно показано насколько новое решение превосходит старые.
Email мне архив не показывает — требует регистрироваться.Psychopompe
20.09.2015 03:54Ну так никто же листинг кода не будет приводить, не имеет смысла.
Не так уж сложно зарегистрироваться. Выслал в ДМ.
gaki
21.09.2015 11:40Да вы не напрягайтесь так. Как обычно бывает в научных работах, скорее всего там вообще нихрена не работает. Пруфы-то хоть есть там? В чём они заключаются?
ankh1989
22.09.2015 10:14Всё же я склонен считать, что в этом случае всё таки работает. Пруф тут: bitbucket.org/waterreaction/giraffe
lucius
17.09.2015 17:29+5Пусть на игру Го натравит.
ankh1989
20.09.2015 12:15+1К слову, Мэтью говорит, что его идея применима к Го и уже были некие подвижку в эту сторону (хотя там идея была не совсем такая в «жирафе»): arxiv.org/pdf/1412.3409v2.pdf
Vig7
18.09.2015 17:44-4Не вижу ничего особенного. Ну, научилась, да. Но в шахматах X полей, Y фигур и ограниченное количество ходов для каждой фигуры.
ankh1989
20.09.2015 01:48Чтобы лучше осознать крутизну того, что он придумал — попробуйте решить более простую задачу, когда на доске несколько фигур и нужно найти лучший ход который приведет к мату в 3-4 хода. Когда это сделать не получится в общем случае, представьте насколько сложнее решить более общую задачу — на любой доске найти лучший ход. Вот Мэтью умудрился как то это сделать.
potan
22.09.2015 12:47+1В книге «Новый ум короля» Пенроуза приводится шахматная позиция, в которой пешки образуют зигзаком непроходимую стену, у черных две ладьи, одна из которых под боем, у белых кроме пешек только король. Человеку очевидно, что ладью брать нельзя. Пенройз утверждал, что шахматные программы ее берут и проигрывают. Интересно, а как в этой позиции себя поведет нейронная сеть?
potan
22.09.2015 14:13Восстановленная по памяти позиция.
Rom77
25.09.2015 21:24Современные шахматные программы ладью уже не берут. Они досчитывают позицию буквально до мата и такой вариант отбрасывают. Оценку позиции, правда, показывают неправильную, но ходы делают верные. Книга Пенроуза написана достаточно давно (я так понимаю — в 1989 году), так что положение вещей уже десять раз поменялось. Другой разговор, что всё ещё можно найти позиции, где компьютер делает неверный выбор. Их число с каждым годом сокращается, но видимо никогда не станет равно нулю, поскольку до идеальной игры всё же ещё очень далеко.
sandricmora
anloop
А я бы спросил так: почему в паре 8ядерных\16потоковых процессоров использовалось всего 20 потоков?\
Процессоры таки 8ядерные (если мы говорим конкретно про E5-2660)
http://ark.intel.com/ru/products/64584/Intel-Xeon-Processor-E5-2660-20M-Cache-2_20-GHz-8_00-GTs-Intel-QPI
Coob
Они бывают разные. v2 и v3 по 10 ядер.
ark.intel.com/ru/products/75272/Intel-Xeon-Processor-E5-2660-v2-25M-Cache-2_20-GHz
ark.intel.com/ru/products/81706/Intel-Xeon-Processor-E5-2660-v3-25M-Cache-2_60-GHz
Sadler
Может быть, студент хотел оставить немного ресурсов для собственных нужд?
ilyanik
По-моему, это недостаток перевода, и имелось в виду, что «вычислительных ресурсов нормального компьютера» достаточно «для игры на уровне международного мастера ФИДЕ», а не для процесса обучения.