Код
#статьи

Читерство ИИ в культовых настолках: как нейросети научились обыгрывать людей на интуиции

Как нейросеть из 1990‑х подарила компьютерам цифровую интуицию, обыграла всех в нарды и стала прообразом AlphaGo, разгромившей чемпионов по игре в го.

Фото: VCG / Getty Images

В сложных настольных играх даже огромная скорость вычислений суперкомпьютеров сама по себе не могла гарантировать победу. Уверенно громить людей в нардах и го программы смогли только после того, как нейронные сети позволили им обрести аналог человеческой интуиции. А началось всё с нейросети, которая показала людям, как надо играть в нарды.

ИИ научил экспертов играть в нарды

Люди играют в различные варианты нардов более пяти тысяч лет и, казалось бы, должны знать о них всё. Однако нейронная сеть, едва освоив эту древнюю игру, нашла несколько необычных комбинаций, которые включили в свой арсенал даже профессиональные игроки.

Исследователь ИИ из компании IBM Джеральд Тезауро посвятил 15 лет жизни тому, чтобы компьютер смог играть в нарды. Венцом его исследований, проводившихся с 1987 по 2002 год, стала нейросетевая программа TD-Gammon. Она впервые в мире могла на равных соревноваться с чемпионами мира.

Но добиться этого было непросто. В нардах (в отличие от шахмат или шашек), кроме возможных действий игроков, необходимо также учитывать элемент случайности. Многое в них зависит от результатов бросков игральных костей (выпавшие числа определяют, на сколько пунктов допускается передвинуть фишки по игровой доске). Из-за этого дерево игры в нардах расширяется гораздо быстрее, чем в шахматах.

Тезауро смог создать нейросеть, которой не требовалось объяснять правила или демонстрировать, как играют профессионалы. Его программа обучалась полностью самостоятельно, проводя тысячи партий против самой себя. Это выгодно отличало её от применявшихся ранее подходов к обучению нейронных сетей, в которых требовалось участие экспертов.

В TD-Gammon использовался вариант обучения с подкреплением (reinforcement learning, RL). Алгоритм подавал в нейросеть расположение фишек на игровой доске. Проанализировав возможные ходы, сеть выдавала для каждого из них оценку, определяющую, насколько хорошим он может быть. Программа выбирала из полученных оценок самую высокую и совершала соответствующий ей ход.

Нейронная сеть вновь оценивала изменившуюся игровую ситуацию и подстраивала свои параметры (веса межнейронных связей) в зависимости от того, улучшил ли её предыдущий ход шансы на выигрыш или нет. По результатам каждой проведённой партии сеть получала «вознаграждение» за победу и стремилась повторять те решения, которые вели к получению этого вознаграждения, но при этом «забывала» те, что вели к поражению.

Изначально весами сети были заданы случайные значения. Поэтому первое время программа играла очень плохо и партии могли длиться сотни или тысячи ходов. Однако уже после нескольких десятков партий качество игры значительно улучшилось. Для полноценного обучения нейросети потребовалось провести около 300 тысяч партий против самой себя.

В 1992–1995 годах Джеральд Тезауро представил свою разработку общественности и организовал ряд матчей, в которых TD-Gammon сражалась с лучшими игроками в нарды в мире. Программа не только показала уровень игры, сравнимый с уровнем профессионалов, но и смогла удивить мастеров свежими и нестандартными решениями.

«TD-Gammon оценивает игровые ситуации намного лучше, чем я. Только в некоторых технических моментах я могу претендовать на определённое преимущество перед этой программой. Её сильная сторона — это возможность оценки сложных игровых позиций, в которых ключом является предположение, а не точный расчёт. И в этом она превосходит людей.

Вместо глупых машин, которые просто могут вычислять быстрее человека (например, играющих в шахматы компьютеров), TD-Gammon учится на собственном опыте почти так же, как это делают игроки. При этом у неё нет эмоциональной предвзятости. Она способна изучить любую игровую позицию и дать ей правильную оценку. Люди не могут делать это с такой же степенью совершенства».

Кит Вулси,
вице-чемпион мира по нардам 1996 года (цитата)

Программа TD-Gammon оказала влияние на сообщество экспертов по нардам. Стиль её игры сильно отличался от традиционных стратегий — и во многих случаях оказывался эффективнее. Это привело к значительным изменениям в позиционном мышлении профессиональных игроков.

Например, TD-Gammon научилась разыгрывать определённые начальные позиции не так, как было принято среди экспертов. Когда при первом броске на костях выпадало сочетание 2–1, 4–1 или 5–1, профессиональные игроки до появления TD-Gammon практически всегда совершали типовой ход: они перемещали фишку с 6‑го пункта на 5‑й. Такой элемент игры называется «слоттинг». Однако нейросеть в той же ситуации предпочитала делать неожиданный манёвр: она сдвигала фишку с 24-го на 23-й пункт. Такой элемент игры противоположен предыдущему и называется «сплитирование».

Обычная начальная позиция в коротких нардах. До появления TD-Gammon при выпадании на костях, например, чисел 4–1 большинство профессионалов совершали типовой ход, перемещая первую фишку с 13-го на 9-й пункт и вторую — с 6-го пункта на 5-й. Однако нейросеть использовала более перспективный вариант: 13–9 и 24–23
Изображение: Gerald Tesauro / Temporal Difference Learning and TD-Gammon / Communications of the ACM, March 1995 / Vol. 38, No. 3

Последующий компьютерный анализ (метод, называемый Rollout) показал, что решение нейросети с большей вероятностью ведёт к улучшению игровой ситуации. Вдохновившись манерой игры TD-Gammon, профессионалы начали экспериментировать с первым ходом по примеру умной программы и добились успеха. Через несколько лет популярный ранее слоттинг практически исчез из дебютов турнирных игр. Так нейросеть способствовала изменению игры в нарды.

Секрет неожиданного успеха TD-Gammon заключался в том, что программа являлась «самоучкой». В процессе обучения игре в нарды она не имела доступа к каким-либо экспертным знаниям (а следовательно, и к скрытым в них стереотипам).

Программа при принятии каждого решения ориентировалась только на конкретную игровую ситуацию и в процессе обучения формировала алгоритм комплексной оценки положения фишек на доске, напоминающий человеческую интуицию.

Такой подход отличается от метода классических шахматных компьютеров, которые перебирают возможные комбинации действий на большую глубину. Отличается он и от манеры игры людей-экспертов, которые оперируют не только интуитивной оценкой игровой ситуации, но также предпочитают полагаться на шаблонные ходы, логические рассуждения и подсчёты.

«Вместо того чтобы пытаться подражать людям, TD-Gammon развивает собственное чувство позиционного суждения, учась на опыте игры против самой себя. Может показаться, что отказ от опыта мастеров-людей ставит нейросеть в невыгодное положение. Но на самом деле это освобождает её, в том смысле, что программе не мешают человеческие предубеждения и стереотипы, которые могут быть ошибочными или неэффективными. Мы видим на практике, что результатом процесса самообучения TD-Gammon является невероятно сложная функция оценки игровой ситуации, которая, по крайней мере в некоторых случаях, превосходит позиционное суждение людей — игроков мирового класса».

Джеральд Тезауро,
разработчик программы TD-Gammon (цитата)

В дальнейшем Тезауро успешно работал в команде программистов IBM, создавших суперкомпьютер Watson. Его богатый опыт по обучению нейросетей игре в нарды пригодился при подготовке ИИ Watson к участию в телепередаче Jeopardy! (американский аналог «Своей игры»). В 2011 году компьютер сыграл против чемпионов Jeopardy! Брэда Руттера и Кена Дженнингса и победил их. Это была настоящая сенсация!

Watson обыгрывает знатоков в Jeopardy!
Кадр: IBM Research / Watson and the Jeopardy! Challenge / YouTube

Сверхчеловеческие способности не для го

За годы, прошедшие с момента появления TD-Gammon, компьютеры достигли поистине сверхчеловеческих успехов в классических настольных играх.

Программа Chinook, разработанная командой во главе с канадским профессором Джонатаном Шеффером, удерживает звание чемпиона по шашкам среди людей и машин с 1994 года. В 1996 году её даже внесли в Книгу рекордов Гиннесса как первую программу, выигравшую чемпионат мира.

Шахматные компьютеры также не дают шансов гроссмейстерам с момента эпохальной победы IBM Deep Blue в 1997 году. Уже много лет гроссмейстеры не играют с вычислительными машинами, поскольку шансов на победу у людей попросту не осталось.

Чемпион мира по шахматам играет против компьютера Deep Blue в 1997 году
Фото: Bernie Nunez / Getty Images

Однако принципы работы компьютеров для чемпионской игры, созданных в 1990–2010 годах, не были похожи на TD-Gammon. Они не использовали нейросети, а полагались на поиск оптимального хода путём перебора возможных вариантов развития партии по дереву игры.

Такой подход зарекомендовал себя для шашек и шахмат, но не подходил для популярной в Азии игры под названием «го». Долгое время она оставалась последним оплотом человечества. До 2015 года лучшие программы могли похвастать лишь любительским уровнем игры. Специалисты по ИИ полагали, что создать программу, способную обыграть экспертов в го, удастся в лучшем случае не раньше 2025 года.

Проблема состояла в запредельной сложности игры, которую были неспособны просчитать компьютеры, работающие по классическим принципам шахматных программ. Наглядно проиллюстрировать сложность го относительно других настолок позволяет размер дерева игры, который можно оценить с помощью несложной формулы:

bd,

где b — примерное число возможных ходов в каждой позиции (степень ветвления дерева), d — средняя длина партии (глубина дерева игры).

В таблице приведём значения этих параметров для нескольких популярных игр.

Параметры сложности настольных игр

Название игрыСтепень ветвления дерева (b)Глубина дерева игры (d)
Крестики-нолики49
Шашки2,870
Шахматы3570
Нарды25055
Го250150

Теоретически, если построить полное дерево игры, то программа, работающая по нему, никогда не проиграет. Однако на практике просчитать такое дерево очень сложно.

Подставив в формулу значения из таблицы, мы легко убедимся, что для элементарных крестиков-ноликов его размер составит 49 = 262 144, а для шашек это уже будет 2,870 = 20001482841082030545089749452286.

Два начальных уровня дерева игры для крестиков-ноликов
Изображение: Wikimedia Commons

Создателям шашечной программы Chinook потребовалось 18 лет непрерывных вычислений для построения полного дерева игры. Над задачей одновременно работало несколько десятков компьютеров. На пике их число доходило до 200.

В 2007 году Джонатан Шеффер объявил о завершении вычислений. В статье с говорящим названием «Шашки решены» он доказал, что его программа имеет информацию обо всех мыслимых комбинациях действий в шашках. А следовательно, она даже теоретически не может проиграть.

Максимум, на что может рассчитывать её соперник, — это свести партию к ничьей. Но даже для достижения такого скромного результата человеку придётся действовать без единой ошибки, что практически невозможно.

Для шахмат построить полное дерево игры пока не представляется возможным. Поэтому компьютеры, подобные Deep Blue, работают с его версией, сокращённой и в «глубину», и в «ширину». Алгоритмы позволяют просматривать не все возможные комбинации до конца партии, а лишь наиболее вероятные на некоторое количество ходов вперёд. Этого оказалось достаточно для уверенной победы над любым гроссмейстером, поскольку человек не способен просчитывать действия на столь дальнюю перспективу.

Однако этот подход не позволяет программам достойно играть в го из-за огромной сложности игры. Если мы посмотрим на таблицу, то увидим, что размер дерева для го на 80 порядков превосходит аналогичный параметр дерева для шахмат, что больше числа атомов во Вселенной. Просчитать такое количество вариантов не способен ни один суперкомпьютер в мире.

AlphaGo: цифровая интуиция в действии

И тогда вместо описанного выше поиска «грубой силы» специалисты британского стартапа Deep Mind решили обратиться к опыту нейросетевой программы для игры в нарды TD-Gammon. Спустя 20 лет после её появления они сумели реализовать заложенные в ней идеи на новом, более высоком техническом уровне. Это позволило Deep Mind создать в 2015 году AlphaGo, показавшую чемпионские результаты в го.

Как и TD-Gammon, AlphaGo использовала нейронную сеть для оценки возможных действий. Для обучения сети использовался тот же подход с подкреплением (Reinforcement Learning). И сеть также обучалась самостоятельно, проводя тысячи партий против самой себя и получая «вознаграждения» за действия, приводящие к выигрышу.

Конечно, с момента появления TD-Gammon наука ушла далеко вперёд. Поэтому в распоряжении Deep Mind были более продвинутые технологии, чем у Джеральда Тезауро в 1995 году. В AlphaGo применили две очень сложные по своему внутреннему устройству нейросети и намного более совершенные методы их обучения (глубокое обучение). Но общие идеи построения программ были очень похожи.

Одна нейронная сеть AlphaGo, названная «стратегической» сетью (policy network), предсказывает следующий ход и используется для сужения поиска, чтобы рассматривать только те ходы, которые с наибольшей вероятностью приведут к выигрышу. Другая нейронная сеть, названная «оценочной» (value network), затем используется для уменьшения глубины дерева поиска — оценки вероятности победы в каждой позиции вместо поиска до конца игры.

Алгоритм поиска AlphaGo похож на мышление человека. В отличие от Deep Blue, который перебирал миллионы позиций, AlphaGo прогнозирует развитие ситуации, словно предвосхищая оставшуюся часть игры в своём нейросетевом «воображении». Стратегическая сеть предлагает варианты ходов, а оценочная сеть проницательно определяет качество каждого из них и выбирает самый перспективный. Некоторые эксперты по ИИ назвали этот метод «цифровой интуицией».

В 2015 году AlphaGo выиграла у трёхкратного чемпиона Европы Фань Хуэя со счётом 5:0. А в 2016 году прошёл эпичный матч программы против профессионала высшего ранга (величайшего игрока в го, выигравшего 18 международных титулов) Ли Седоля, завершившийся победой нейросети со счётом 4:1.

Ли Седоль играет против AlphaGo в марте 2016 года
Фото: Handout / Getty Images

И вновь эксперты, как и в истории с TD-Gammon, были поражены игрой программы. Энди Джексон, вице-президент Американской ассоциации го, назвал AlphaGo «чем-то вроде компьютеризированного афериста».

Нейросеть, оставаясь в рамках правил игры, раз за разом находила нестандартные ходы, ведущие к победе. Многие решения нейронной сети эксперты, комментировавшие матч, поначалу называли ошибками, но потом убеждались, что эти «ошибки» вели программу к победе и были частью успешной стратегии.

«Очевидно, что AlphaGo отличается прежде всего тем, что она играет не так, как играет человек. Всё совершенно не то, к чему я привык, и мне было трудно к этому приспособиться…

Вера в человеческое творчество и наши традиционные знания об игре го были поставлены под сомнение моим опытом игры против компьютера. И я понимаю, что мне есть над чем поработать в этом направлении…»

Ли Седоль,
профессиональный игрок в го (цитата)

Проигравший нейросети за год до того Фань Хуэй признался журналистам, что благодаря матчу против нейросети он стал лучше видеть элементы игры, которых не замечал ранее. Пересмотрев свои представления о го, эксперт изменил манеру игры и сумел улучшить собственный рейтинг на 300 позиций.

А одна из сильнейших женщин — игроков в го Чо Хе Ён, наблюдая за действиями компьютера, эмоционально заявила, что хотела бы учиться у AlphaGo.

«Я люблю AlphaGo! Я хочу учиться у неё и извлечь уроки из её игры! Кажется, что AlphaGo знает всё!»

Чо Хе Ён,
профессиональный игрок в го (цитата)

Несмотря на то, что Ли Седоль сумел выиграть одну партию, независимые комментаторы сошлись во мнении, что машина полностью переиграла человека. Некоторые ходы, сделанные AlphaGo, противоречили классической теории го, но доказали свою эффективность в матче против Ли Седоля. Сегодня профессионалы активно используют эти находки нейросети в своих партиях.

Выводы

Цифровая интуиция, сформированная нейросетями в процессе обучения с подкреплением, позволила им уверенно обыгрывать людей даже в самые сложные настолки. Это достижение отправило в утиль силовые подходы на основе перебора вариантов, применявшиеся успешными шахматными компьютерами предыдущих поколений.

Приобретая навыки в процессе игры против самих себя, новые системы искусственного интеллекта усвоили неожиданно эффективные способы оценки игровых ситуаций. Теперь у компьютеров есть интуиция, которая работает лучше человеческой.

Наблюдая за действиями машин, профессионалы смогут узнать много нового и интересного о тех играх, которым они посвятили жизнь. Пришло время не только учить ИИ, но и учиться у него.

Учись бесплатно:
вебинары по программированию, маркетингу и дизайну.

Участвовать
Школа дронов для всех
Учим программировать беспилотники и управлять ими.
Узнать больше
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована