В конце прошлого века компьютер шаг за шагом начал громить сначала чемпионов по шашкам, а затем и лучших гроссмейстеров, которые отдали шахматам всю свою жизнь. Но добравшись по исторической лестнице до го, компьютер вдруг перестал быть непобедимым, хотя поначалу казалось, что тут ему тоже не будет равных. Просто в тот момент против него выступили так называемые «цифровые кентавры».
Под катом краткая история победного шествия компьютера, рассказ про появление «цифровых кентавров» и почему они играют в го.
Сначала были шашки
Сколько времени существуют компьютеры, столько же развиваются алгоритмы, способные состязаться с человеком в логических играх. Для каждой из игр путь развития алгоритма был своим. Но в большинстве случаев все начиналось с набора эвристик, которые было сравнительно легко «поймать». Пытаясь усложнить решение, применяли метод Монте-Карло для поиска по дереву и различные гибридные подходы — это позволило улучшить качество ботов и даже играть наравне с человеком. А рост доступных аппаратных мощностей в некоторых играх окончательно передал победу машине.
К примеру, шашки были решены полностью в 2007 году. На фоне других логических игр шашки просты в просчете, количество комбинаций в них — порядка 10 в 20 степени.
Разработка программ для игры в шашки началась с середины 50-х годов прошлого века. Наиболее известная среди них — Chinook, созданная Джонатаном Шеффером. На Хабре есть статья, рассказывающая историю создания и триумфа этой программы.
Chinook была представлена на компьютерной олимпиаде в 1990 году. А в 1992 году программа сыграла в международном чемпионате по шашкам против многократного чемпиона мира Мариона Тинсли и выиграла у него два матча.
На тот момент Chinook видела игру на 14–17 шагов вперед и могла полностью просчитать все возможные позиции, если на доске оставалось восемь шашек.
По мере развития техники глубина просчета увеличивалась, как и база данных окончаний игр. К началу 2000-х годов программа знала все возможные окончания матча, если на доске оставалось 10 шашек.
А в 2007 году появилась публикация, в которой сообщалось, что шашки решены полностью. На эту задачу у Шеффера ушло 19 лет.
Затем вычислительные алгоритмы продолжили покорять другие игры с большим числом комбинаций. Решения на основе старых подходов быстро уперлись в «комбинаторный взрыв» и вычислительную сложность. Поэтому им на смену пришли архитектуры, основанные на нейронных сетях.
Но и они не панацея. В той же го полностью детерминированное решение — это NP-полная задача, которая не может быть решена численно в рамках существующих архитектур компьютерных систем и алгоритмов.
Человек подходит к игре принципиально иначе, нежели вычислительный алгоритм. Он использует интуицию, предположения о противнике и его прошлых играх, невербальные коммуникации с ним. В итоге не перебирая все варианты, а работая с образами, он находит выигрышную стратегию. И в этом может быть выход.
«Цифровой кентавр» — сочетание человека и алгоритмов — структура, которая берет лучшее от обоих «миров». Компьютер просчитывает ближайшие возможные шаги, но человек принимает решение, каким именно путем пойти.
Фактически «цифровой кентавр» — это демонстрация поддержки принятия решений, которая может пригодиться вне логических игр: в энергетике, в медицине, в управлении транспортом, в юриспруденции, в администрировании сложных систем: городов и государств и пр.
Как кентавры пришли в шахматы
Шахматы намного сложнее шашек. Количество возможных комбинаций фигур на поле — 10 в 46 степени. Однако здесь компьютер тоже победил человека.
Попытки создать «шахматную» программу предпринимаются более 30 лет. Различных идей было настолько много, что в конце 1980-х уже проходили отдельные чемпионаты для компьютеров, играющих в шахматы.
11 мая 1997 года IBM Deep Blue обыграл Гарри Каспарова в матче из шести партий. Компьютер использовал поиск по шахматному дереву, а для ускорения процесса применялись специально разработанные под шахматы процессоры, которых насчитывалось в системе 480 штук. Каждый из них перебирал от 2 до 2,5 миллионов шахматных позиций в секунду, что примерно в сто раз больше, чем у аналогичных по частоте универсальных процессоров того времени.
Казалось бы, тот матч должен был поставить точку в состязании человека с компьютером на шахматном поле. Играть с абсолютным противником нет смысла. Но именно Каспаров предложил ввести в игру «цифровых кентавров», ведь шоу должно продолжаться!
Кентавры учитывают нюансы взаимодействия людей с машинами, сохраняя присутствие человека. Последнее приносит в игру своего рода «шумы» — дает оригинальность решений и игровых состояний.
Скорее всего, «цифровой кентавр» не выиграет у полноценного искусственного интеллекта для игры в шахматы, если тот будет создан. Участие человека не сделает его более эффективным. Однако система «кентавра» помогает человеку совершать меньше ошибок.
В 1998 году прошло первое соревнование «шахматы кентавров». Игроки использовали программы, которые подсказывали им следующие ходы.
Победа в игре «кентавров» определяется уже не возможностями человека, а в том числе потенциалом софта и интерфейсом взаимодействия с ним. Человек отвечает за стратегическое планирование в игре, может различать значимые и бесполезные ходы (чего машина сделать пока не может) и анализирует партию. Компьютер же использует базы партий и просчитывает возможные позиции — аппаратные ресурсы бытового уровня позволяют перебирать миллионы комбинаций за секунды.
Присутствие «кентавров» повысило общий уровень игры в шахматы. А стороннему наблюдателю работа «кентавра» позволяет понять, как действует профессиональный игрок: как он оценивает ситуацию и принимает решение. Так что шахматы стали зрелищнее.
Почему го не сразу покорилась машине
До недавнего времени человек легко обыгрывал машину в го. В этой игре на стандартной доске 19 на 19 слишком много комбинаций — 10 в 171 степени (это больше, чем атомов на Земле, — их всего 10 в 80 степени), так что доступные вычислительные мощности даже с ИИ не могут с ними справиться.
Настоящим прорывом в этой области стала разработка AlphaGo. Компания Google DeepMind вкладывала в развитие этой нейросети огромные ресурсы, обучая ее на статистике матчей ведущих мировых игроков.
И в 2015 году AlphaGo выиграла 499 из 500 партий с другими программами для го. По результатам этого теста AlphaGo признали достойной сражения с человеком.
В том же году она выиграла у Фань Хуэя — трехкратного чемпиона Европы, а в 2016 у Ли Седоля — лучшего мирового игрока десятилетия.
AlphaGo осталась закрытым проектом и с 2017 года не участвовала в чемпионатах. Google DeepMind не планирует выпускать новые версии или возвращаться в игру. Однако они все-таки опубликовали данные игр AlphaGo, на основе которых можно было обучать свои нейросети.
В 2017 вышла бесплатная программа для го с открытым исходным кодом — Leela Zero. Ее автор — Джан-Карло Паскутто из Бельгии. На уровне кода в нее заложены правила игры, а тренировалась она, играя сама с собой. Leela Zero можно рассматривать как наследника AlphaGo, однако и ее время уже проходит — в феврале 2021 года проект распределенного обучения был закрыт. Сегодня сообщество продолжает тренировать KataGo — еще одно открытое решение, по некоторым параметрам превосходящее Leela Zero.
Пока существующие ИИ продолжают тренироваться, в го пришлась ко двору идея «цифровых кентавров», которые уже активно выступали в шахматах. Например, компании Vova.pro и AmberCore развернули свои многопользовательские сервера, где можно было играть с человеком или ИИ на уменьшенных досках — 13 на 13 вместо оригинальной 19 на 19. Был и гибридный режим работы, когда играющий человек получал подсказки от Leela Zero. Так началась «подстройка» программ для игры в го под роль советчика.
Главная задача при разработке цифровой составляющей кентавра — обеспечить максимум полезной информации (и выигрыш) при минимуме подсказок на основе аналитики от ИИ. Подсказки могут рекомендовать определенную часть поля для следующего хода, подсказывать сами ходы или прикидывать шансы на победу в том или ином случае. Вопрос лишь в том, как представить эту информацию игроку, чтобы он принял верное решение.
Как плодятся «кентавры» в России
В России идея «цифровых кентавров» в го нашла себя в 2019 году. Разумеется, в студенческой среде, где много свободных и пытливых умов. Затем она стала развиваться в рамках одного из проектов Кружкового движения НТИ. Ее принес туда известный ученый Александр Горбань, который сейчас руководит Центром искусственного интеллекта Университета Лестера в Великобритании.
Весной этого года под крылом того же проекта прошел хакатон для школьников и студентов, целью которого было создание интерфейса программ-подсказчиков для участия в логической игре. Участники решали, какая минимальная информация необходима игроку и в какой форме ее требуется преподнести. В финале принимали участие 20 команд, лучшие из которых продолжили развивать свои решения для участия в реальных соревнованиях по го.
Первый международный «матч кентавров» в го состоялся чуть позже в рамках Чемпионата мира по го во Владивостоке, на площадке Дальневосточного федерального университета.
В общей сложности провели 70 игр. Учитывая количество игроков и ограничения доступных ресурсов, игра шла на поле 13х13. С этим упрощением для обеспечения работы платформы «цифровых кентавров» был задействован достаточно мощный сервер с видеокартой Tesla v100 и 32 Gb видеопамяти.
В двух матчах ИИ против «кентавров» участвовали Илья Шикшин и Александр Динерштейн. Это одни из сильнейших игроков в Европе. Итог весьма любопытен.
На доске 13 на 13 «кентавры» выиграли у ИИ Leela Zero.
По сути, «кентавры» в го только начинают свой путь. И покуда нет возможности полностью просчитать эту игру, она остается отличным плацдармом для проработки идей экспертных систем, помогающих принимать решения в совершенно других отраслях. Ну и еще напоминая, что человек все равно остается в деле.
