Как кентавры обыгрывают ИИ: история про симбиоз компьютера и человека в логических играх
На Хабре размещен материал о том, как в конце прошлого века компьютер шаг за шагом начал громить сначала чемпионов по шашкам, а затем и лучших гроссмейстеров, которые отдали шахматам всю свою жизнь. Добравшись до го, компьютер вдруг перестал быть непобедимым потому, что против него выступили так называемые цифровые кентавры.
Сначала были шашки Сколько времени существуют компьютеры, столько же развиваются алгоритмы, способные состязаться с человеком в логических играх. Для каждой из игр путь развития алгоритма был своим. Но в большинстве случаев все начиналось с набора эвристик, которые было сравнительно легко «поймать». Пытаясь усложнить решение, применяли метод Монте-Карло и различные гибридные подходы – это позволило улучшить качество ботов и даже играть наравне с человеком. А рост доступных аппаратных мощностей в некоторых играх окончательно передал победу машине.
Создатель программы для игры в шашки Chinook Джонатан Шеффер К примеру, шашки были решены полностью в 2007 г., ведь на фоне других логических игр шашки просты в просчете, количество комбинаций в них – порядка десяти в двадцатой степени.
Разработка программ для игры в шашки началась с середины 50-х годов прошлого века. Наиболее известная среди них – Chinook, созданная Джонатаном Шеффером.
Chinook была представлена на компьютерной олимпиаде в 1990 г. А два года спустя программа сыграла в международном чемпионате по шашкам против многократного чемпиона мира Мариона Тинсли и сумела его победить два раза, проиграв, правда, при этом четыре раза, а 33 партии сведя в ничью.
На тот момент Chinook видела игру на 14–17 шагов вперед и могла полностью просчитать все возможные позиции, если на доске оставалось восемь шашек. По мере развития техники глубина просчета увеличивалась, как и база данных окончаний игр. К началу 2000-х гг. программа знала все возможные окончания матча, если на доске оставалось 10 шашек. А в 2007 г. появилась публикация, в которой сообщалось, что шашки решены полностью. На эту задачу у Шеффера ушло 19 лет.
Матч между чемпионом мира по шашкам Мариона Тинсли (справа)с программой Chinook в 1992 г. Затем вычислительные алгоритмы продолжили покорять другие игры с большим числом комбинаций. Решения на основе старых подходов быстро уперлись в «комбинаторный взрыв» и вычислительную сложность. Поэтому им на смену пришли архитектуры, основанные на нейронных сетях. Но и они не панацея. Человек подходит к игре принципиально иначе, нежели вычислительный алгоритм. Он использует интуицию, предположения о противнике и его прошлых играх, невербальные коммуникации с ним. В итоге, не перебирая все варианты, а работая с образами, он находит выигрышную стратегию. И в этом может быть выход.
Цифровой кентавр – сочетание человека и алгоритмов – структура, которая берет лучшее от обоих миров. Компьютер просчитывает ближайшие возможные шаги, но человек принимает решение, каким именно путем пойти.
Как цифровые кентавры пришли в шахматы Шахматы намного сложнее шашек. Количество возможных комбинаций фигур на поле – 10 в 46 степени. Однако здесь компьютер тоже победил человека.
IBM Deep Blue обыгрывает чемпиона мира по шахматам Гарри Каспарова (слева), 1997 г. Попытки создать «шахматную» программу предпринимаются более 30 лет. Различных идей было настолько много, что в конце 1980-х уже проходили отдельные чемпионаты для компьютеров, играющих в шахматы.
11 мая 1997 г. IBM Deep Blue обыграл чемпиона мира Гарри Каспарова в матче из шести партий. Компьютер использовал поиск по шахматному дереву, а для ускорения процесса применялись специально разработанные под шахматы процессоры. Казалось бы, тот матч должен был поставить точку в состязании человека с компьютером на шахматном поле. Но именно Каспаров предложил ввести в игру цифровых кентавров, ведь шоу должно продолжаться!
Кентавры учитывают нюансы взаимодействия людей с машинами, сохраняя присутствие человека. Последнее приносит в игру своего рода шумы: дает оригинальность решений и игровых состояний.
Скорее всего, цифровой кентавр не выиграет у полноценного искусственного интеллекта для игры в шахматы, если тот будет создан. Участие человека не сделает его более эффективным. Однако система «кентавра» помогает человеку совершать меньше ошибок.
В 1998 г. прошло первое соревнование «шахматы кентавров». Игроки использовали программы, которые подсказывали им следующие ходы.
Почему го не сразу покорилась машине До недавнего времени человек легко обыгрывал машину в го. В этой игре на стандартной доске 19 на 19 слишком много комбинаций – 10 в 171 степени – так что доступные вычислительные мощности даже с ИИ не могут с ними справиться.
Настоящим прорывом в этой области стала разработка AlphaGo. Компания Google DeepMind вкладывала в развитие этой нейросети огромные ресурсы, обучая ее на статистике матчей ведущих мировых игроков. И в 2015 г. AlphaGo выиграла 499 из 500 партий с другими программами для го. По результатам этого теста AlphaGo признали достойной сражения с человеком.
В том же году она выиграла у Фань Хуэя – трехкратного чемпиона Европы, а в 2016 г. у Ли Седоля – лучшего мирового игрока десятилетия. Итоговый счет оказался разгромным – 4:1 в пользу AlphaGo.
Ли Седоль (справа) играет с AlphaGo AlphaGo осталась закрытым проектом и с 2017 г. не участвовала в чемпионатах. Google DeepMind не планирует выпускать новые версии или возвращаться в игру.
В 2017 г. вышла бесплатная программа для го с открытым исходным кодом Leela Zero. Ее автор – Джан-Карло Паскутто из Бельгии. На уровне кода в нее заложены правила игры, а тренировалась она, играя сама с собой. Однако и ее время уже проходит: в феврале 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.
Илья Шикшин и Александр Динерштейн – участники матча «кентавров» (поставить два фото с одной подписью) По сути, «кентавры» в го только начинают свой путь. И пока нет возможности полностью просчитать эту игру, она остается отличным плацдармом для проработки идей экспертных систем, помогающих принимать решения, причем в совершенно разных отраслях.