Сегодня не будет тяжких раздумий о настоящем и будущем компьютерной индустрии. Сегодня я хочу рассказать об одном из своих хобби. Я играю в массу разных игр: футбол, хоккей, теннис (большой и маленький), покер, преферанс, биржа и т.п. Но мой “профильный” вид спорта — шахматы. Дальше кандидата в мастера моя карьера на этом поприще не продвинулась, но любовь к древней игре я сохраняю уже 4 десятка лет. Интересно, что она вполне “ужилась” с другим увлечением – программированием, породив интерес к искусственному интеллекту и теории игр. И разумеется, последние прорывы в этой области связанные с феноменальными успехами проекта AlphaZero не могли пройти мимо меня.
Тогда я просто сидел и восхищался партиями AlphaZero против Stockfish. А сейчас вернулся к теме в связи с задачей оптимизации нейронных сетей, которой иногда приходится заниматься по работе (увы, меньше чем хотелось бы). Как мне кажется, задачи эти могут оказаться тесно связанными, поэтому захотелось как то систематизировать свои идеи.
Шахматы – игра с полной информацией, основанная на переборе вариантов (так же как шашки, го и т.п.).
Проблема однако в том, что дерево вариантов в шахматах растет достаточно быстро (хотя и значительное медленнее, чем в го). Например, при полной доске фигур в спокойной позиции у каждой стороны есть примерно по 10 разумных продолжений. Таким образом, всего за 3 хода черных и белых (6 полуходов) мы можем получить миллион позиций из данной. Также, примем во внимание то, что средняя партия между людьми продолжается 40-50 ходов (между компьютерами ― 80-100). Таким образом, мы придем к выводу, что полный просчет дерева вариантов для большинства позиций невозможен – а значит мы должны ориентироваться на частичное обрезание дерева перебора, как по ширине, так и в глубину. А теперь давайте посмотрим, как люди и машины справлялись с этой проблемой. Начну я с небольшого исторического обзора.
«Белковые шахматы».
Шахматы известны порядка 1400 лет, но первые большие турниры по ним начали проводиться в середине XIX века. Это было время открытых и романтических сражений. Соперники старались побыстрее ввести в бой фигуры, вскрыть позицию и начать атаку на короля. С материальными и позиционными уступками никто особенно не считался. Но как ни удивительно, первым официальным чемпионом мира стал антагонист романтических шахмат – Вильгельм Стейниц.
Он заложил основы позиционной игры. Во многом благодаря Стейницу мы стали оперировать такими понятиями, как «пешечная структура», «сильные и слабые поля», «хорошие и плохие фигуры». Именно это и привнесло в шахматы элемент стратегии, основанной на долгосрочных преимуществах. Стейниц развивал позиционный подход и неумолимо наказывал своих противников за материальные жертвы и позиционные огрехи. О первом чемпионе очень хорошо сказал Эммануил Ласкер, сменивший его на шахматном троне: «Одаренность Стейница как практического игрока была ниже, чем одаренность Блэкберна или Цукерторта, которых он все же победил, ибо был великим мыслителем, а они – нет». Стейниц сформулировал базовые принципы оценки позиции и вытекающие из них планы игры на языке высокого уровня (в данном случае немецком). Соответственно, он сделал их доступными для изучения другими людьми. Это и сформировало то, что мы называем человеческим подходом к шахматной игре. Мы очень серьезно обрезаем дерево вариантов в шахматах, основываясь на позиционных принципах. Какие-то ходы отбрасываются потому, что ведут к плохой позиции на просчитываемом горизонте. Kакие-то ― потому что ведут к долговременным уступкам, другие ― потому что являются бесцельными. В итоге мы просчитываем совсем небольшую часть возможных вариантов.
Дальнейшее понимание шахмат было по сути развитием идей, заложенных первым чемпионом. Появились такие понятия как блокада, профилактика, доминация. Шахматисты стали изучать принципы разыгрывания типовых позиций, возникающих из различных дебютов(замкнутые цепи, изолированная пешка и т.п.). Так или иначе, изучались позиции близкие к материальному равновесию. Но бывали и исключения – например, молодой Михаил Таль играл в ином стиле. Он создавал острые несбалансированные позиции с нарушением соотношения материала (позднее подобную игру демонстрировал и Гарри Каспаров). Не привыкшие к подобной игре противники пасовали один за другим. Таль стал чемпионом мира в 1960, но год спустя проиграл матч-реванш. Во второй половине ХХ века фокус исследования сместился в сторону начала партии – дебюта. С легкой руки Mихаила Ботвинника (6-го чемпиона мира) и Гарри Каспарова (13-го) львиную долю своего времени шахматисты стали уделять проработке конкретных дебютных вариантов. Все больше используя компьютеры в этом процессе. В результате многие варианты в популярных дебютах разработаны вплоть до позиций, где результат игры предопределен. Это приводит к определённому выхолащиванию шаxмат, а также к необходимости запоминать огромное количество вариантов, чтобы не быть разгромленным уже в дебюте. Неудивительно, что последнее время маятник качнулся в обратную сторону. Нынешний чемпион мира Магнус Карлсен скорее стремится к тому, чтобы получить по итогам дебюта не перевес, а игровую позицию, не “заезженную вдоль и поперек” компьютерными движками. Тяжесть борьбы переносится на более поздние стадии партии (миттельшпиль, эндшпиль).
«Силиконовые шахматы».
По меткому выражению Александра Кронрода, шахматы являются «дрозофилой» искусственного интеллекта. Их изучение началось с появлением первых компьютеров и привлекало таких пионеров как Алан Тьюринг и Клод Шеннон. Именно Шеннон выдвинул первую оценку стоимости шахматных фигур «Король =200, Ферзь =9, Ладья = 5, Слон = 3, Koнь =3, Пешка =1». Как ни странно, именно эта простая оценка определила развитие шахматного программирования на следуюшие 70 лет. Также Шеннон предугадал разделение шахматных программ на «быстрые» (brute force) и «умные» (clever). «Быстрые» программы полностью перебирают все возможные варианты на определенную глубину, оценивают позицию с помощью простой оценочной функции (вроде соотношения материала) и выбирают наилучший ход с помощью принципа минимакса. «Умные» программы используют более сложные алгоритмы и варьируют глубину перебора примерно так же, как это делает человек. Созданием подобного алгоритма в последние годы жизни занимался 6-й чемпион мира Михаил Ботвинник. Однако без особого успеха, как и многие другие создатели «умных» программ. Ибо в третьем своем предсказании Шеннон ошибся – «умные» программы постоянно терпели неудачу в борьбе с «быстрыми». Причина в том, что перебор очень хорошо параллелится и оптимизируется. А простая оценка Шеннона оказалась достаточно устойчивой и робастной. Ибо как известно шахматистам, любой позиционный перевес рано или поздно трансформируется в материальный. В то время как принципы оценки позиции поддаются формализации гораздо хуже. Они требуют громоздких последовательных вычислений и плохо оптимизируются. В результате с ростом производительности компьютеров «быстрые» программы стали доминировать. Так сформировался mainstream компьютерных шахмат, разительно отличающийся от человеческих – перебор на определенную глубину с использованием aльфа-бета отсечения (и еще кой-каких эвристик) и оценка позиции по Шеннону. Также программы стали активно развивать и использовать дебютные (когда игра еще не ушла далеко от начальной позиции) и эндшпильные (когда количество фигур мало и дерево вариантов может быть просчитано полностью) базы. А производительность компьютеров все время росла, и программисты тоже не сидели без дела, постоянно оптимизируя движки. 11 мая 1997 года произошло эпохальное событие компьютер Deep Blue победил чемпиона мира Гарри Каспарова в матче из 6 партий.
Сразу после этого IBM прикрыла этот ни разу не дешевый проект. Специально для Deep Blue были созданы чипы, ускоряющие шахматные расчеты! Впрочем, и без них превосходство компьютера над человеком уже было очевидным. Deep Fritz, Deep Junior, Rybka, Komodo, Stockfish стали беспощадно громить ведущих гроссмейстеров, даже давая им материал вперед… Между собой они, впрочем, играли с переменным успехом ― результаты чемпионатов мира среди программ можно найти тут.
Все изменилось, когда создатели AlphaZero, победив чемпиона мира по игре в го Ли Седоля, взялись наконец за шахматы. Результат оказался феноменален – после 4 часов игры с самим собой AlphaZero разгромил StockFish, выиграв 28 партий и сведя вничью 72. Через год DeepMind провел более чистый эксперимент, разрешив Stockfish пользоваться дебютной и эндшпильной книгами. И все равно результат +155 -6 =839 не оставляет сомнений в том, кто является сильнейшим игроком в мире на данный момент.
Давайте разбираться, как устроено это новое чудо. (Для желающих поковыряться в python-скриптах есть уже целая книга). Основной алгоритм – поиск по деревьям Монте Карло. Это тоже, конечно, перебор, что роднит AlphaZero c другими шахматными программами. Но слово Монте Карло не должно вводить в заблуждение – поиск управляется нейронной сетью(для го была 80-слойная, здесь не знаю какая) и является узконаправленным. АlphaZero обрезает дерево перебора, исходя из позиционных соображений, так же как это делает человек! По сравнению со Stockfish Alphazero перебирает в почти в 1000 раз меньше вариантов. Она лопатит гораздо меньше «мусора», но наиболее вероятные сильнейшие варианты просчитывает глубже и точнее. Поэтому выигрывает даже имея меньше времени или на более слабом железе. Ну и самое главное – АlphaZero «изучала» шахматы исключительно на «собственном опыте». У нее не было никакой априорной информации. Ее “понимание” не испорчено «Шенноновской оценкой». У неё своё уникальное понимание видение шахмат и стиль игры, зачастую игнорирующий материальное соотношение (как молодой Таль!).
Какие выводы мы можем сделать из этого замечательного эксперимента?
1. Он решительно опровергает все соображения о выхолащивании шахмат. Самое появление игрока, который играет в невиданном до сих пор стиле и демонстрирует тотальное превосходство над конкурентами свидетельствует о том, что возможности игры еще далеко не исчерпаны.
2. Показывает насколько мало все же мы знаем о шахматах. За 4 часа тренировки искусственный интеллект сумел понять об игре много больше чем мы («тупые белковые») за полторы тысячи лет! Пытаясь как то осознать этот феномен я нашел такую аналогию – наше знание о шахматах похоже на разложение функции в степенной ряд (типа Тейлора-Маклорена) вблизи нуля. Где нулевой точкой является материальное равновесие. Применимость такого представления падает по мере удаления от материального равенства. В то время как AlphaZero видит всю картину(функцию) целиком.
3. Ставит главный вопрос – что же дальше? Конечно можно идти экстенсивным путем – увеличивая время тренировки, используя все более мощное железо, оптимизируя софт и т.п. Но мне кажется, что гораздо важнее другое направление. Для AlphaZero – натренированная нейронная сетка – это все лишь набор чисел –коэффициентов. Как мы можем извлечь из этого набора чисел новое знание об игре? В каком то смысле мы должны решить задачу, сродни той, которую решил Стейниц полтора века назад. Описать знание об игре, используя человеческий язык. И сделать его доступным для изучения другими людьми. Это именно то с чем я столкнулся при оптимизации нейронных сеток и называю обратной задачей искусственного интеллекта. А решать ее нам придется во многих областях. И если мы не сумеем призрак SkyNet станет чуть менее далеким и чуть более зловещим… Ну а пока я был бы благодарен за ссылки, статьи и идеи как подступиться к этой проблеме.
PS. А партии вы все же посмотрите. Я получил ни с чем не сравнимое удовольствие.
Тогда я просто сидел и восхищался партиями AlphaZero против Stockfish. А сейчас вернулся к теме в связи с задачей оптимизации нейронных сетей, которой иногда приходится заниматься по работе (увы, меньше чем хотелось бы). Как мне кажется, задачи эти могут оказаться тесно связанными, поэтому захотелось как то систематизировать свои идеи.
Шахматы – игра с полной информацией, основанная на переборе вариантов (так же как шашки, го и т.п.).
Проблема однако в том, что дерево вариантов в шахматах растет достаточно быстро (хотя и значительное медленнее, чем в го). Например, при полной доске фигур в спокойной позиции у каждой стороны есть примерно по 10 разумных продолжений. Таким образом, всего за 3 хода черных и белых (6 полуходов) мы можем получить миллион позиций из данной. Также, примем во внимание то, что средняя партия между людьми продолжается 40-50 ходов (между компьютерами ― 80-100). Таким образом, мы придем к выводу, что полный просчет дерева вариантов для большинства позиций невозможен – а значит мы должны ориентироваться на частичное обрезание дерева перебора, как по ширине, так и в глубину. А теперь давайте посмотрим, как люди и машины справлялись с этой проблемой. Начну я с небольшого исторического обзора.
«Белковые шахматы».
Шахматы известны порядка 1400 лет, но первые большие турниры по ним начали проводиться в середине XIX века. Это было время открытых и романтических сражений. Соперники старались побыстрее ввести в бой фигуры, вскрыть позицию и начать атаку на короля. С материальными и позиционными уступками никто особенно не считался. Но как ни удивительно, первым официальным чемпионом мира стал антагонист романтических шахмат – Вильгельм Стейниц.
Он заложил основы позиционной игры. Во многом благодаря Стейницу мы стали оперировать такими понятиями, как «пешечная структура», «сильные и слабые поля», «хорошие и плохие фигуры». Именно это и привнесло в шахматы элемент стратегии, основанной на долгосрочных преимуществах. Стейниц развивал позиционный подход и неумолимо наказывал своих противников за материальные жертвы и позиционные огрехи. О первом чемпионе очень хорошо сказал Эммануил Ласкер, сменивший его на шахматном троне: «Одаренность Стейница как практического игрока была ниже, чем одаренность Блэкберна или Цукерторта, которых он все же победил, ибо был великим мыслителем, а они – нет». Стейниц сформулировал базовые принципы оценки позиции и вытекающие из них планы игры на языке высокого уровня (в данном случае немецком). Соответственно, он сделал их доступными для изучения другими людьми. Это и сформировало то, что мы называем человеческим подходом к шахматной игре. Мы очень серьезно обрезаем дерево вариантов в шахматах, основываясь на позиционных принципах. Какие-то ходы отбрасываются потому, что ведут к плохой позиции на просчитываемом горизонте. Kакие-то ― потому что ведут к долговременным уступкам, другие ― потому что являются бесцельными. В итоге мы просчитываем совсем небольшую часть возможных вариантов.
Дальнейшее понимание шахмат было по сути развитием идей, заложенных первым чемпионом. Появились такие понятия как блокада, профилактика, доминация. Шахматисты стали изучать принципы разыгрывания типовых позиций, возникающих из различных дебютов(замкнутые цепи, изолированная пешка и т.п.). Так или иначе, изучались позиции близкие к материальному равновесию. Но бывали и исключения – например, молодой Михаил Таль играл в ином стиле. Он создавал острые несбалансированные позиции с нарушением соотношения материала (позднее подобную игру демонстрировал и Гарри Каспаров). Не привыкшие к подобной игре противники пасовали один за другим. Таль стал чемпионом мира в 1960, но год спустя проиграл матч-реванш. Во второй половине ХХ века фокус исследования сместился в сторону начала партии – дебюта. С легкой руки Mихаила Ботвинника (6-го чемпиона мира) и Гарри Каспарова (13-го) львиную долю своего времени шахматисты стали уделять проработке конкретных дебютных вариантов. Все больше используя компьютеры в этом процессе. В результате многие варианты в популярных дебютах разработаны вплоть до позиций, где результат игры предопределен. Это приводит к определённому выхолащиванию шаxмат, а также к необходимости запоминать огромное количество вариантов, чтобы не быть разгромленным уже в дебюте. Неудивительно, что последнее время маятник качнулся в обратную сторону. Нынешний чемпион мира Магнус Карлсен скорее стремится к тому, чтобы получить по итогам дебюта не перевес, а игровую позицию, не “заезженную вдоль и поперек” компьютерными движками. Тяжесть борьбы переносится на более поздние стадии партии (миттельшпиль, эндшпиль).
«Силиконовые шахматы».
По меткому выражению Александра Кронрода, шахматы являются «дрозофилой» искусственного интеллекта. Их изучение началось с появлением первых компьютеров и привлекало таких пионеров как Алан Тьюринг и Клод Шеннон. Именно Шеннон выдвинул первую оценку стоимости шахматных фигур «Король =200, Ферзь =9, Ладья = 5, Слон = 3, Koнь =3, Пешка =1». Как ни странно, именно эта простая оценка определила развитие шахматного программирования на следуюшие 70 лет. Также Шеннон предугадал разделение шахматных программ на «быстрые» (brute force) и «умные» (clever). «Быстрые» программы полностью перебирают все возможные варианты на определенную глубину, оценивают позицию с помощью простой оценочной функции (вроде соотношения материала) и выбирают наилучший ход с помощью принципа минимакса. «Умные» программы используют более сложные алгоритмы и варьируют глубину перебора примерно так же, как это делает человек. Созданием подобного алгоритма в последние годы жизни занимался 6-й чемпион мира Михаил Ботвинник. Однако без особого успеха, как и многие другие создатели «умных» программ. Ибо в третьем своем предсказании Шеннон ошибся – «умные» программы постоянно терпели неудачу в борьбе с «быстрыми». Причина в том, что перебор очень хорошо параллелится и оптимизируется. А простая оценка Шеннона оказалась достаточно устойчивой и робастной. Ибо как известно шахматистам, любой позиционный перевес рано или поздно трансформируется в материальный. В то время как принципы оценки позиции поддаются формализации гораздо хуже. Они требуют громоздких последовательных вычислений и плохо оптимизируются. В результате с ростом производительности компьютеров «быстрые» программы стали доминировать. Так сформировался mainstream компьютерных шахмат, разительно отличающийся от человеческих – перебор на определенную глубину с использованием aльфа-бета отсечения (и еще кой-каких эвристик) и оценка позиции по Шеннону. Также программы стали активно развивать и использовать дебютные (когда игра еще не ушла далеко от начальной позиции) и эндшпильные (когда количество фигур мало и дерево вариантов может быть просчитано полностью) базы. А производительность компьютеров все время росла, и программисты тоже не сидели без дела, постоянно оптимизируя движки. 11 мая 1997 года произошло эпохальное событие компьютер Deep Blue победил чемпиона мира Гарри Каспарова в матче из 6 партий.
Сразу после этого IBM прикрыла этот ни разу не дешевый проект. Специально для Deep Blue были созданы чипы, ускоряющие шахматные расчеты! Впрочем, и без них превосходство компьютера над человеком уже было очевидным. Deep Fritz, Deep Junior, Rybka, Komodo, Stockfish стали беспощадно громить ведущих гроссмейстеров, даже давая им материал вперед… Между собой они, впрочем, играли с переменным успехом ― результаты чемпионатов мира среди программ можно найти тут.
Все изменилось, когда создатели AlphaZero, победив чемпиона мира по игре в го Ли Седоля, взялись наконец за шахматы. Результат оказался феноменален – после 4 часов игры с самим собой AlphaZero разгромил StockFish, выиграв 28 партий и сведя вничью 72. Через год DeepMind провел более чистый эксперимент, разрешив Stockfish пользоваться дебютной и эндшпильной книгами. И все равно результат +155 -6 =839 не оставляет сомнений в том, кто является сильнейшим игроком в мире на данный момент.
Давайте разбираться, как устроено это новое чудо. (Для желающих поковыряться в python-скриптах есть уже целая книга). Основной алгоритм – поиск по деревьям Монте Карло. Это тоже, конечно, перебор, что роднит AlphaZero c другими шахматными программами. Но слово Монте Карло не должно вводить в заблуждение – поиск управляется нейронной сетью(для го была 80-слойная, здесь не знаю какая) и является узконаправленным. АlphaZero обрезает дерево перебора, исходя из позиционных соображений, так же как это делает человек! По сравнению со Stockfish Alphazero перебирает в почти в 1000 раз меньше вариантов. Она лопатит гораздо меньше «мусора», но наиболее вероятные сильнейшие варианты просчитывает глубже и точнее. Поэтому выигрывает даже имея меньше времени или на более слабом железе. Ну и самое главное – АlphaZero «изучала» шахматы исключительно на «собственном опыте». У нее не было никакой априорной информации. Ее “понимание” не испорчено «Шенноновской оценкой». У неё своё уникальное понимание видение шахмат и стиль игры, зачастую игнорирующий материальное соотношение (как молодой Таль!).
Какие выводы мы можем сделать из этого замечательного эксперимента?
1. Он решительно опровергает все соображения о выхолащивании шахмат. Самое появление игрока, который играет в невиданном до сих пор стиле и демонстрирует тотальное превосходство над конкурентами свидетельствует о том, что возможности игры еще далеко не исчерпаны.
2. Показывает насколько мало все же мы знаем о шахматах. За 4 часа тренировки искусственный интеллект сумел понять об игре много больше чем мы («тупые белковые») за полторы тысячи лет! Пытаясь как то осознать этот феномен я нашел такую аналогию – наше знание о шахматах похоже на разложение функции в степенной ряд (типа Тейлора-Маклорена) вблизи нуля. Где нулевой точкой является материальное равновесие. Применимость такого представления падает по мере удаления от материального равенства. В то время как AlphaZero видит всю картину(функцию) целиком.
3. Ставит главный вопрос – что же дальше? Конечно можно идти экстенсивным путем – увеличивая время тренировки, используя все более мощное железо, оптимизируя софт и т.п. Но мне кажется, что гораздо важнее другое направление. Для AlphaZero – натренированная нейронная сетка – это все лишь набор чисел –коэффициентов. Как мы можем извлечь из этого набора чисел новое знание об игре? В каком то смысле мы должны решить задачу, сродни той, которую решил Стейниц полтора века назад. Описать знание об игре, используя человеческий язык. И сделать его доступным для изучения другими людьми. Это именно то с чем я столкнулся при оптимизации нейронных сеток и называю обратной задачей искусственного интеллекта. А решать ее нам придется во многих областях. И если мы не сумеем призрак SkyNet станет чуть менее далеким и чуть более зловещим… Ну а пока я был бы благодарен за ссылки, статьи и идеи как подступиться к этой проблеме.
PS. А партии вы все же посмотрите. Я получил ни с чем не сравнимое удовольствие.
