В какие игры компьютер не обыграл человека
Мы продолжаем выкладывать конспекты интересных подкастов «Запуск завтра», потому что «Практикум» — партнёр подкаста, а мы — дети «Практикума». Сегодня история об искусственном интеллекте. Слушайте полную версию или читайте текст.
Герой подкаста — Сергей Бортунов, исследователь в Google DeepMind, занимается машинным обучением. Сергей расскажет, как игры в StarCraft и го помогут машинам решать проблемы человечества.
Жертвуя всем
Я примерно знал как играют новички. Я поднял свой рейтинг с нуля до четырёхсот. На этот раз это был чистый рейтинг наработанный мною. Я имел стратегию и тактику. Я играю чёрными.
Довольно стандартное начало.
А вот здесь на ход коня я двигаю пешку на h6, чтобы конь не занял поле g5. Естественно вражеский конь съедает незащищённую пешку по центру. Я полностью ломаю дебют, теперь у новичка нет теории как играть дальше. Нет тиктоков, нет ютубов и книги.
Я нападаю на королевский фланг. Там нет коня. Я блокирую пешку f2 и она не может двигаться, так как защищает короля. Естественно моего ферзя отгоняют ходо g3. Но я также атаковал не только короля, но и центр. Съедаю пешку по центре и атакую короля.
4. g3 Qxe4+ 5. Be2 Qxh1+ 6. Bf1 Qxh2
Не желая терять в начале игры ферзя, белые защищаются слоном. Если я съем ферзём слона, логично, что я потеряю своего ферзя, поскольку тот будет съеден ферзём белых. Тем более, какой нормальный человек ходит ферзём в начале игры? Ням-ням, я съедаю ладью и даю королю шах. А потом подъедаю пешечку. Но самое главное атакую пешку на f2.
Белые хотят сделать вилку конём. Атакуя ладью и. Пустое место. Знаете, это очень опасно терять ладью. Не все решатся ходить как-то иначе чем ладьёй.
Спокойно атакую короля и подъедаю пешечку. Играя в шахматы, я крепко осознал, что иногда последовательность ходов важна. И в одном порядке я смогу получить больше, вынуждая соперника сделать ход, нежели в другом
Хладнокровно отдаю ладью. Ход d6 позволяет мне вывести слона. А конь стоит на краю доски и никак мне не мешает.
Вывожу слона и атакую короля. Белые попадают под неприятную связку и теряют ферзя.
11. Kd3 Bxd1 12. Bf7+ 0-1
0 - 1 победа чёрных
Белые атаковали и я хотел увести короля, чтобы не попадать под "вечные шахи" с компенсацией фигур. Конечно никаких вечных шахов нет, но ощущается позиция именно так. Я увожу короля - попадаю под коня, снова увожу - попадаю под слона. А потом и под вилочку коня с потерей ферзя. У меня было странное ощущение, что если сделаю неверный ход так и будет.
Игры, в которые люди играют лучше машин
В мире есть две игры, в которые люди исторически играют гораздо лучше, чем машины, — шахматы и го. В 1970-е годы начали писать программы, которые играют в шахматы. Сначала они играли совсем плохо, потом чуть лучше, но гроссмейстеры всегда выигрывали у машин.
В 1997 году компьютер компании IBM обыграл чемпиона мира по шахматам Гарри Каспарова. Люди к этому шли десятилетиями. А в 2016 году программа и команда AlphaGo, которая как раз является проектом DeepMind, обыграла чемпиона мира по игре в го.
Победа в шахматах в некотором смысле не очень интересна, потому что это победа перебором. Deep Blue победил Каспарова только потому, что лучше перебирал ходы.
А с определённого момента в шахматах можно просчитать все ходы до самого конца.
Кто-то посчитал, что количество возможных досок в игре го больше, чем количество атомов во Вселенной. Это невозможно перебрать.
Ребятам из DeepMind в некотором смысле удалось прописать и перебор, и интуицию алгоритму для игры в го. Нейросеть AlphaGo, с одной стороны, отвечала за интуитивную оценку полезности тех или иных ходов и состояний досок. А с другой — перебирала возможные варианты.
Например, нам кажется, что этот ход хороший. Давайте проверим нашу гипотезу. Давайте представим, что делаем такой ход. Чем на это может ответить соперник? Дальше мы строим небольшое дерево перебора, которое останавливаем в определённый момент. Но вместе с тем в каждом листе этого дерева всё равно есть интуитивная функция,
с помощью которой мы оцениваем выгоду хода или состояния доски. Если немного приукрасить, то можно сказать, что мы правда научили алгоритм пользоваться интуицией.
Как нейросети учатся играть и становятся лучше
Компьютер играет в игры — в шахматы или в го — на основе того, как в них играли люди. Первые версии AlphaGo были обучены на записанных партиях. Потом от этого удалось отказаться. Довольно быстро подключили элемент софтплей, когда сеть играет против самой себя и учится выигрывать.
В настольных играх удалось отказаться вообще от использования каких-то данных для обучения. Так алгоритмы, которые учились выигрывать только на играх друг с другом, превзошли те, что были обучены на партиях между людьми.
7. StarCraft 2
Программа AlphaStar, разработанная компанией DeepMind, успешно обыгрывает профессиональных геймеров в StarCraft 2 «в сухую» – со счётом 10:0. Правда, у ИИ было одно преимущество, которое не совсем честное. Дело в том, что он всегда может видеть полную карту, тогда как геймерам приходится для этого прокручивать экран.
👇 Первое правило любой игры: играй с соперником, который сильнее тебя. Подписывайтесь на канал, оценивайте публикацию . 👇
4. Покер
В покере невозможно увидеть карты играющего, пока он их сам не покажет, и поэтому задача программистов, поставивших цель создать ИИ, способный обыгрывать человека, существенно усложняется. Однако нейросеть DeepStack, имеющая нечто похожее на интуицию, смогла добиться больших успехов, ежедневно играя и анализируя проведённые игры.
Тренировки
Первым делом я начал тренироваться. Скачал программу и начал тренировать мат в один ход. Также зашёл на старую учётную запись и начал намеренно снижать рейтинг ELO со стартовых 400 до 100, ниже не получилось. Меня чуть за это не забанили, но мне нужен был чистый результат игры с самого низкого рейтинга.
В день я решал около ста задач на мат в один ход. Также я опускал своё ELO играя рандомно. Я выбирал случайные ходы и смотрел, как на них реагируют мои соперники. Также я немного учился перебирать ходы как компьютер.
Минимакс
Компьютер перебирает ходы по очень простой схеме. У каждой фигуры есть ценность. Думаю о ценности фигур подробнее вы сможете узнать в других статьях. Выбирает ход, делает его. Выбирает ход противника. А потом смотрит результат. Например, я сходил пешкой, враг сходит пешкой. Нулевой результат. Потом я снова хожу пешкой, враг выбирает ферзя. Снова нулевой результат. Потом я снова хожу пешкой и враг съедает мою пешку ферзём. Минус один. Я съедаю ферзя пешкой плюс восемь. Из этого делается вывод, что враг не будет есть пешку на этом ходу, ведь тогда потеряет ферзя. Значит он сделает другой ход.
Я перебирал варианты медленно. Очень медленно. Поэтому вместо обычного перебора всех вариантов я выбирал несколько и смотрел на результат. Но даже так я перебирал варианты очень медленно. Надо было ускорять игру и я тренировался.
Матуя в один ход, я научился быстро перебирать ходы одной фигурой. Если компьютер в начале партии на пешку тратил 2 такта, то есть сначала выбирал ход e2-e3, а потом e4, то я тратил на ход один мозговой такт: я сразу видел все варианты куда может ходить пешка. Я сразу видел все два варианта. Уже сейчас я чувствовал как превосхожу компьютер в вычислительной мощи. Однопоточный
Я начал наседать на решение задач в мат в один ход. Меня начало тошнить. Мне начали мерещиться ходы фигурами в обыденных вещах. Например, просматривая сериал, я видел на месте главного персонажа ферзя и как он защищает фигур рядом с ним. Я осознавал, что нейросеть в моём мозгу учится, ещё с первых двух задач нейросеть обучилась мату в один ход, проблема в человеческих мозгов в том, что они очень быстро учатся, но плохо закрепляют и улучшают изученное. То есть я сначала сыграл в две игры сделал рывок в 50%, а потом застопорился и сыграл сотни задач, прежде чем закрепить изученное на минимально приемлемом уровне.
Тем временем я научился в шахматах бегать по кругу избегая мата королём. Было забавно, на низких рейтингах не умеют ставить мат и получалась ничья повторением ходов или пат. Также я понял основы дебюта, вроде захвата центра и конртигры.
Я не учил дебют механически. Я просто ходил рандомно и подмечал сильные первые ходы. Так я отыграл несколько дебютов, даже не зная их. Из смешных моментов могу подметить, как меня не раз ловили в дебютные ловушки, дело в том, что я тогда видел ходы на один шаг вперёд и часто попадался на ловушки людей, которые заучили дебют по мемам.
Наконец-то мой рейтинг начал расти. Опыт тоже стал увеличиваться. И однажды играя в полную силу я сыграл с точностью выше 90%. Это сравнение игры с сильнешим шахматным движком.
Тем не менее рандом меня подводил. И иногда игра получалась хаотичной.
3. Кубик Рубика
Среднестатистический человек может собирать кубик Рубика несколько часов. И хорошо, если удастся собрать хотя бы одну грань. Но если постоянно тренироваться, можно сократить время сбора до нескольких минут или даже секунд. Мировой рекорд среди представителей нашего биологического вида – 4,69 сек. Но робот с ИИ, появившийся пару лет назад, собирает кубик в 12 раз быстрее. Ему на это требуется меньше половины секунды.
Чем сворачивание белка похоже на игру в StarCraft
Если абстрагироваться от деталей и тонкостей, то го, StarCraft и много чего в человеческой деятельности сводится к тому, чтобы решать сложные задачи оптимизации и предсказывать результат.
Буквально всё в нашем мире — это результат решения тех или иных задач оптимизации. Планирование авиарейсов и сворачивания белков — задачи оптимизации. Они отличаются по своей природе, и их нужно решать по-разному. Но если мы научимся решать и те и другие, то сможем решить и третьи, потому что принцип у оптимизации один — выбор наилучшего варианта из возможных.
Любую задачу на свете можно решить, перебрав все варианты. Проблема в том, что этих вариантов так много, что никакой человек и никакой компьютер никогда в жизни не успеет это сделать.
Мы учим машину предугадывать оптимальные варианты, основываясь на предыдущем опыте, не делая перебора. То, что человек называет интуицией, мы учимся повторять с помощью компьютера.
В чём сложность StarCraft для машин
Стратегия, в которой нужно двигать юниты, строить здания и уничтожать врагов, в ряде аспектов определённо сложнее, чем шахматы.
В шахматах мы видим всю доску: и чёрных, и белых. От нас невозможно скрыть, что происходит на другой стороне. В StarCraft почти всю карту скрывает «туман войны», и игрок не видит, что делает его оппонент. Большая часть игры в этом и заключается — нужно шпионить за своим соперником: смотреть, какие здания он строит, какой армией на нас пойдёт. От этого будет зависеть стратегия, которая приведёт к победе.
Шахматы — это линейная игра, в которой делают ходы по очереди. Ты сделал ход, машина сделала ход. В StarCraft всё происходит непрерывно: ты строишь базу и готовишь армию на одной части карты, а соперник в это же время готовится к сражению на другой.
В го мы можем моделировать действия среды. Даже если среда содержит в себе какого-то мощного оппонента, он один, мы за ним наблюдаем и имеем доступ к полному состоянию доски.
В StarCraft мы не видим, что делает оппонент, поэтому нам нужно действовать в условиях неопределённости. Это означает, что перебирать варианты становится практически невозможно.
2. Jeopardy
Jeopardy – это телевикторина, аналогом которой на нашем телевидении является «Своя игра». Лучший игрок – БрэдРаттер однажды сразился с компьютером Watson и… проиграл.
Примечательно, что робот не был подключён к Интернету и находил ответы даже на те вопросы, которые были поставлены неоднозначно. В итоге он получил 80 тыс. долларов, и эти деньги, конечно же, пошли на благотворительные цели.
6. Pac-Man
Pac-Man – одна из самых старых и хорошо всем знакомых компьютерных игр. Существует огромное количество её вариаций. Немалую популярность в своё время имела версия Ms. Pac-Man, выпущенная для консоли Atari 2600. Враги здесь ведут себя совершенно непредсказуемо, из-за чего прохождение уровней существенно усложняется. Даже человек после долгих тренировок смог набрать не многим более 250 000 очков.
Но недавно компания Maluuba, принадлежащая корпорации Microsoft, разработала программу, которая смогла набрать максимально возможные 999 999 очков.
Что такое StarCraft?
Это — научно-фантастическая стратегическая игра про войну (на компьютере). Игрок даёт указания своим солдатам, строит инфраструктуру, собирает ресурсы и уничтожает соперников.
Как Сергей попал в DeepMind
Про DeepMind мне рассказал студент, которого я курировал, когда был аспирантом.
Потом я попал на конференцию ICML, где познакомился со спикерами из компании лично.
ICML — International Conference on Machine Learning, это одна из престижных конференций в этой области. Там были интересные доклады людей из DeepMind. Мне понравилось то, о чём говорили ребята, и я попросился к ним на стажировку.
В тот момент Google покупал DeepMind. Я этого не знал, меня слабо интересовала внутренняя подоплёка, просто хотелось попасть на хорошую стажировку.
Во время стажировки мне сделали предложение о работе. Теперь я живу в Лондоне, и в моём контракте написано, что я работаю в Google UK Limited.
Один, два, много.
На самом деле у коня только два поля для отступления и попав под шах коня, я съедаю слона белых в любом случае. Размениваться нельзя, поэтому белые отступают слоном на поле c4. А дальше мат в "много ходов". Дальше одного хода я считать не умею, а два хода только при сильной концентрации и то слабо. Поэтому мат в много ходов. Однако белые тоже умеют считать до "много" отчего сдались и мне была засчитана победа.
5. Dota 2
Лучшим искусственным игроком в Dota 2 является OpenAlFive. Лучшие результаты система показывает в матчах «один на один». Боты становятся всё более совершенными, учась на своих же ошибках. Но их слабая сторона – стратегия. Они реагируют лишь на те события, которые происходят в данный момент и способны планировать свои действия не более чем на 15 мин. вперёд.
Что такое го?
Го — это древние восточные шахматы с некоторыми отличиями. Игра существовала уже 2 500 лет назад. С точки зрения математики и вероятностей эта игра гораздо сложнее шахмат.
Чем лучше машины играют в игры, тем лучше мы понимаем, как функционирует наш организм
Люди — органические существа. Всё, что в нас происходит, — это сворачивание белков. Растут мышцы — сворачиваются какие-то белки. Принимаем лекарство — это молекулы, которые заставляют белки вести себя определённым образом.
У нас есть белок, развёрнутый линейно. Представьте себе, что мы его отпускаем, и он сворачивается по своим законам. Например, потому, что какие-то молекулы любят друг с другом соединяться. Отсюда есть более и менее вероятные состояния белка. В одномерной структуре надо предсказать 3D-структуру, когда белок уже свернётся.
Если мы научимся быстро и качественно предсказывать, как сворачивается белок, то начнём быстрее изобретать лекарства и эффективнее бороться с болезнями. Это фундаментальный механизм, по которому функционирует наше тело, и было бы неплохо в нём разобраться.
Без машинного обучения предсказать, как поведёт себя белок, сложно и дорого. У аспиранта может быть тема диссертации: «Сворачивание какого-то конкретного белка», может, нескольких белков. Получается, что он 3–5 лет своей жизни потратит, чтобы свернуть 3–5 белков.
Итоги
Я старался максимально понятным способом объяснить алогритм Минимакс, а также другие термины. После прочтения этой статьи у вас должно появиться хотя бы минимальное понимание некоторых вещей. Например, что современные шахматные движки играют как люди, то как они выбирают ходы. Пусть я играл не идеально, и делал грубые ошибки, мой соперник делал грубые ошибки, но я и мой соперник считаем на глубину один ход. Я намеренно играл плохо, словно вижу на один ход вперёд, и словно мой соперник также видит на один ход вперёд. Самое главное то, что я могу сделать ловушку в дебюте и мне не надо учить ловушки наизусть, чтобы потом теряться, если противник сделает не тот ход, что я ожидаю. Я просто сделаю новую ловушку.
Я играл творчески с полным пониманием происходящего на доске. Пусть и на уровне новичка. Собственно шахматы из этого и состоят. И я рад, что хотя бы раз в жизни сыграл такую красивую для новичка партию.
А ещё я понимаю дебюты, и даже не зная как они называются и какие там ходы, однажды я со 100% аккуратностью разыграл дебют, узнав об этом постфактум. Но самое главное я не растраиваюсь из-за того, что не могу обыграть компьютер и он считает мои ходы ошибкой. На самом деле ошибок на том уровне игры, который есть у меня, нет. Всё, что мне остаётся это доводить точность (Accuracy) игры до 100%, то есть тренировать органическую нейросеть на несколько миллионов позиций и может быть однажды я буду играть на уровне мощных шахматных программ. Также я понял, что человеческие методы игры не бесполезны.
Я сыграл красивую партию полную неточностей. Моя мечта исполнилась, желаю вам того же!
Реми Кулом (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото Ёды
В 1994 году компьютер обыграл чемпиона мира по шашкам, в 1997 году — по шахматам. Сегодня компьютеры превосходят людей абсолютно во всех популярных играх с полной информацией, кроме одной — го.
У классической игры с 2500-летней историей очень простые правила, но компьютерные программы даже близко не могут подобраться к победе над лучшими гроссмейстерами, пишет Wired.
Древнюю игру можно считать «восточной версией шахмат». Как и шахматы, это игра с полной информацией, то есть в любой момент игры все игроки имеют полную информацию о состоянии игры и воздействуют на игру дискретными действиями. Здесь успех не зависит от удачи или скорости реакции.
Несмотря на рост вычислительной мощи компьютеров (чемпион мира по шахматам сегодня, вероятно, проиграет даже вашему домашнему ПК), алгоритмы игры в го на экспертном уровне остаются нерешённой и одной из самых интересных задач ИИ. Проблема ещё и в том, что очень немногие способны подняться до девятого дана в игре. Для этого нужно несколько лет обучаться в Японии или Корее. Там талантливых детей забирают из дома для обучения в академии го примерно с 9 лет.
Продвинутые любители почти всегда застревают на определённом уровне игры и не могут улучшить результат: «Требуется некий ментальный прыжок, чтобы снять эту блокировку, и в разработке программ та же проблема, — объясняет Дэвид Фотлэнд (David Fotland), главный разработчик процессора PA-RISC в компании Hewlett Packard в 70-е годы. Он тестировал программу го на процессоре своей разработки. — Вопрос в том, как оценивать всю доску, а не отдельные фрагменты».
Игра давно пользовалась популярностью не только на востоке, но и на западе, особенно среди математиков и физиков. Например, Эйнштейн частенько играл в го, также как знаменитые математики Джон Нэш и Алан Тьюринг.
Компьютерные программы для го разрабатывают уже 45 лет, этой проблеме уделяли почти столько же внимания, сколько и шахматным программам. Первую написал гений теории игр Альфред Зобрист в 1968 году. Она могла обыграть абсолютного новичка, который только что познакомился с правилами (запись первой игры человек-компьютер). Начало казалось оптимистичным. В следующие четыре десятилетия было потрачено огромное количество времени и интеллектуальных усилий, но даже с учётом прогресса в вычислительной мощности программы так и не смогли одолеть даже продвинутого любителя.
Причину можно понять, если сравнить го с шахматами. В начале шахматной партии у белых есть 20 возможных ходов, а у чёрных — 20 возможных вариантов ответа. После первого хода на доске может быть 400 различных позиций. А теперь сравните цифры в го: на доске 19х19 у чёрных есть 361 возможных начальных ходов, а у белых 360 вариантов ответа. Это означает 129 960 возможных комбинаций только после первого раунда.
Так называемый «фактор ветвления» — среднее количество ходов, доступных в каждом раунде — в шахматах составляет 35, в го — 250. Игры с сильным ветвлением затрудняют работу стандартных алгоритмов, использующих правило минимакса для создания дерева возможных комбинаций. Даже с учётом анализа не всех, а только перспективных ветвлений для более глубокого анализа. То, что работает в шашках и шахматах, не работает в го. Выбор перспективных ветвлений в дереве возможных комбинаций го — часто совершенно таинственный процесс. Даже игроки не понимают, как они это делают: «Просто смотришь на доску и знаешь», говорят они.
Опять же, в шахматах почти всегда можно понять, кто выигрывает, хотя бы по числу фигур. В го ситуацию могут толковать только эксперты.
Среднее количество ходов в игре: в шахматах — около 40, в го — 200. Учитывая фактор ветвления и эту статистику, становится понятным бессилие компьютеров.
Талантливый французский программист Реми Кулом (Rémi Coulom) добился первого успеха с программой Crazy Stone в 2006 году, когда догадался совместить минимакс и метод Монте-Карло. Новый алгоритм расчёта дерева ветвлений он назвал Monte Carlo Tree Search или MCTS. Француз выиграл чемпионат среди компьютерных программ UEC Cup в 2007 и 2008 годах, но это так и не принесло ему известности, и Реми забросил разработку. Но в 2010 году он получил предложение от японского игрового разработчика Unbalance — и в 2011 году вышла первая коммерческая версия Crazy Stone. В 2013 году Реми победно вернулся на чемпионат.
Однако, в 2014 году случилась неудача. В финальном противостоянии против программы Zen зрители поняли, что творится нечто странное уже после третьего хода. Программа Zen, после стандартной постановки двух камней по углам вдруг поставила третий камень около центра. Так никто не играл, это было явно «нечеловеческое» решение. Вскоре уровень победных ожиданий у Crazy Stone вырос до неприлично высоких значений, более 60%. Судя по всему, программа считала безопасной группу камней в правом верхнем углу, хотя она не была безопасной. Поскольку успешная стратегия напрямую зависит от правильной оценки доски, зрители начали шептаться о возможном поражении Crazy Stone. Так оно и вышло: на 186 ходу Crazy Stone признала поражение, а Zen стал новым чемпионом UEC Cup.
Впрочем, у Кулома осталась возможность реванша. Как финалист, он получил право играть против настоящего гроссмейстера-человека с форой в четыре камня. В этом году на турнир приехал Норимото Ёда. Японский гроссмейстер сел за стол в традиционном зелёном кимоно. Реми Кулом — в очках без оправы и синем свитере, в которых был и на прошлом чемпионате.
Комментаторы-профессионалы, которые сопровождали онлайн-трансляцию партии, сошлись во мнении, что Crazy Stone играет неплохо и даже имеет преимущество. Ёда был исключительно раздражён и выглядел сурово, а Кулом суетился, посматривая то на ноутбук, то на игровую доску, то на хронометр — куда угодно, только не на Ёду.
Обидное поражение Crazy Stone потерпела в самой концовке. Выигрывая 11 камней, любой человек сделал бы несколько очевидных защитных ходов, чтобы не дать противнику отыграться и сохранить преимущество. Но Crazy Stone была запрограммирована только на победу. Поэтому её алгоритм состоял в том, чтобы в ситуации выигрыша делать бессмысленные ходы в собственной зоне, ожидая, когда соперник признает поражение. Но здесь такой фокус не прошёл — и Ёда сумел отыграться. Во втором матче против Zen он уже выглядел получше и выиграл у программы четыре камня.
Реми Кулэм всё равно был счастлив — и пообещал к следующему чемпионату доработать алгоритм действий в концовке.
Но даже если компьютеры и выиграют в го, нельзя говорить о «падении последнего интеллектуального бастиона», где доминирует человек, как это писали газеты после победы Deep Blue в шахматах. Программы для го — это просто узкоспециализированные инструменты для решения конкретных задач. Они весьма далеки от человеческого разума и не пытаются эмулировать работу мозга. «Для меня это просто развлечение, — говорит Кулом, — не более того».
В те времена люди без особого труда одерживали победу над исскуственным интеллектом. Но сегодня мощные программы, способные просчитывать миллионы ходов, обыгрывают людей, не оставляя им шансов.
Впрочем, на практике нет никакого смысла обыгрывать компьютерные программы. Попытки предпринимаются, конечно, только ради забавы. А тем, насколько стремительно совершенствуются компьютерные программы, мы, люди, создающие их, можем только гордиться.
Приведём пример 7-ми игр с самым мощным ИИ, для которого человек не соперник.
Го – ещё более сложная игра, чем хорошо всем знакомые шахматы. Здесь есть более 350 способов начать матч, тогда как в шахматах их всего 20. А уже после 1-го хода появляется почти 130 тыс. разных комбинаций. В шахматах же после начального хода может быть одна из 400 позиций.
Если хочется на личном опыте убедиться, что современный ИИ невозможно обыграть в Го, то можно сразиться с AlphaGo. Так называется алгоритм, разработанный компанией Google. Самая современная версия – Zero бесконечно тренировалась, проводя игру сама с собой и всего за несколько дней стала лучше всех своих предшественников.
Мат в два хода
Когда шахматы начали сниться мне во сне, а это означает, что мой мозг начал более глубокий анализ моего шахматного опыта, я начал тренировать мат в два хода. Я начал более-менее чувствовать шахматы и очень быстро видеть все угрозы и нападения в один полуход. И тренируя мат в два хода, я также тренировал анализ игры в два полухода, мой и врага. Конечно тот факт, что ход я выбирал я рандомно сказывался на том, что иногда я зевал фигуру и проигрывал партию, просто потому что не увидел этого варианта, поскольку не просчитывал, но ощущение позиции со временем усиливалось и я начинал видеть больше. Для ускорения обучения я начал смотреть шахматные партии сильных игроков.
Чтобы разгрузить мозги я смотрел смешные ролики. По шахматам. Вроде типичных шахматистов такого-то рейтинга с показом ошибок. С анимацией револьверов, когда фигура делает вилку.
Выводы
Исходя из найденного, я осознал, что новейшие шахматные движки думаю как люди. И за счёт этого побеждают обычный перебор вариантов. Это меня невероятно сильно вдохновило. То есть вся человеческая теория шахмат не является пустым звуком. Есть смысл учить человеческие методы игры в шахматы.
Чем больше я читал, тем больше в этом убеждался. Один шахматный блогер упомянул, что новейший Stockfish с нейросетью оценивают игру старых мастеров выше, чем это оценивает старый Stockfish. Потом я посмотрел за игрой гроссмейстера, где тот разрывал других гроссмейстеров за десять минут и причитал: о, эта позиция мне нравится. И да там был мат в восемь и более ходов. Мат гроссмейстер упустил, и потом долго думал, где ошибся, но ошибки не было, просто надо было перебирать слишком много вариантов и играть с компьютерной точностью. Однако даже так гроссмейстер просто продавил оппотента, потихоньку улучшая свою позицию.
Но ещё сильнее мне понравилась игра, где нейросеть жертвует материалом, позицией, делает всё, на что не пойдёт нормальный человек и старый движок, чтобы победить и побеждает. Я задался целью повторить подобное хотя бы раз в жизни.
Полная версия подкаста
Слушайте на Яндекс-музыке по подписке «Яндекс-плюс». Думали, в сказку попали?
На написание этого обзора натолкнул пост «Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?», опубликованный 25 мая. В самом посте, и, тем более, в комментариях, было много сказано по поводу компьютерных шахмат вообще и матча Deep Blue — Каспаров (1997) в частности. Понятно, что сейчас, спустя уже без малого двадцать лет, мало кому интересны все подробности того матча: компьютеры развиваются с колоссальной скоростью, современные смартфоны легко дадут фору компьютерам того времени, да и возможно, сами шахматы несколько утратили популярность последнее время — по каким причинам — это уже тема отдельного разговора.
Впрочем, некоторые подробности, судя по всему, действительно неизвестны, а подробности эти таковы, что заголовки о “падении последнего интеллектуального бастиона” — не более, чем газетный прием, ибо случившийся по итогам матча, по сути, скандал, в силу своей шахматной специфичности вряд ли был бы интересен широкой публике. Нет, я, несмотря на то, что всегда являлся поклонником Гарри Кимовича Каспарова (исключительно в шахматном плане), не собираюсь его оправдывать за то поражение и пытаться доказать, что все было совсем не так, как сейчас общеизвестно. И уж тем более целью не является опровержение некоторых комментариев на шахматную тему к посту хабраюзера alizar. Единственная цель — рассказать некоторые подробности того, что именно произошло в Нью-Йорке в начале мая 1997 года, и почему результат этого противостояния, по мнению автора, на самом деле никому ничего не доказал.
Сразу оговорюсь: автор не является высококвалифицированным шахматистом. Возможно, некоторые, чисто шахматные моменты в данном материале, могут быть раскритикованы людьми, занимающимися шахматами профессионально. Также, увы, автор не силен ни в теории игр, ни в шахматном программировании, и попытается лишь высказать мнение частично шахматиста, частично знакомого с компьютерами, а не создать Всемирную и всемерную энциклопедию Шахматного Программирования.
Недостаточно быть хорошим игроком; вы также должны хорошо играть
(З.Тарраш)
История шахматного программирования началась, по сути, сразу же с обычным программированием. Искусственный интеллект, возможность его создания, волновали людей издавна, и программируемая вычислительная техника оказалась более подходящим средством для поиска такой возможности, чем человек, который обыгрывал Наполеона, сидя в тумбочке. Первые шахматные программы были, впрочем, соперниками лишь друг другу: в силу огромного количества вариантов шахматных партий, речи о полном переборе не было, и нет, кстати, и по сей день. (И не предвидится (с) Швондер.) Это не мешало шахматным программам периодически удивлять профессиональных шахматистов как неожиданно лучшими ходами (что объясняется в первую очередь тем, что форсированные варианты компьютер считает все же быстрее и точнее), так и внезапными просмотрами мата в пару-тройку ходов ради спасения ферзя. Однако, если в тактике даже сравнительно слабые компьютеры были вполне себе сильны, то вот в позиционной игре все было очень печально — если еще как-то можно было научить программу, что ферзь дороже пешки (что в некоторых случаях приводило к вышеупомянутым просмотрам мата), то научить оценке позиции, на которой, собственно, вся партия и держится, возможным не представлялось. Это и неудивительно — правильная оценка позиции — это задача непростая даже для шахматистов-разрядников, единого рецепта нет, даже две практически одинаковые позиции, отличающиеся лишь положением одной пешки, могут иметь противоположные оценки.
С течением времени, впрочем, прогресс стал брать свое. Дебютные библиотеки позволили программам не “плавать” в начальной стадии партии — такие “плавания” нередко приводили к окончанию партии еще в дебюте — все же, несколько столетий опыта и рост дебютной теории с начала ХХ века давали человеку немалую фору. Дебютные библиотеки эту фору не просто устранили — в отличие от человека, компьютер теперь мог разыграть абсолютно любой дебют, уйти от любой дебютной ловушки, да и сам, соответственно, мог в любую ловушку поймать! Шахматистов, знающих все дебюты, не бывает — есть понятие “дебютный репертуар” — это некоторое количество начал, использующихся шахматистом. Человек может этот репертуар расширять, пополнять, готовить, например, новые дебюты к новому турниру, но с появлением у компьютеров в памяти дебютной энциклопедии человек стал проигрывать в этом компоненте. Кстати, фора тут вышла двойная: в отличие от компьютера, который по сути, играет по дебютной библиотеке, человек в ходе партии подсмотреть в дебютную энциклопедию не может. Единственный вариант уравнять тут шансы — неправильные начала, не внесенные в энциклопедии, причем, максимум шансы получится именно уравнять — человек ведь также не имеет возможности применить багаж своих дебютных знаний.
Надо сказать, что проблема дебютных знаний и их чрезмерной распространенности и доступности волновала и самих шахматистов. Так, совершенно нормальными в профессиональных шахматах стали ситуации, когда игроки сделали по 30-40 ходов, и ничего нового в них не было — все эти ходы уже были в другой партии. (Тут, конечно, дело касается не только дебюта, но, как правило, такие ситуации были связаны в первую очередь с дебютными спорами, и некий вариант мог отстаиваться и в глубоком миттельшпиле, и даже в эндшпиле!) Либо ситуации из партий гросс- и супергросс- мейстеров — партия до 20 ходов, обычно — 16-18, все “из книжки” и соглашение на ничью — потому что позиция теоретически ничейна. Спасением виделись Шахматы Фишера, они же Шахматы-960, где фигуры в начальной позиции могут располагаться произвольным образом. Увы (или к счастью?), обычные шахматы этот вариант вытеснить не смог. Почему — сказать сложно, но рискну предположить, что профессиональным шахматистам он не был вполне интересен, им и в стоковых дебютах хватало, чем заняться, а остальным — не давал никаких преимуществ — см. комментарий Каспарова. В самом деле, дебютные принципы не поменялись — “развивай фигуры как можно быстрее и безопаснее и мешай делать то же самое сопернику”, и тот, кто эти принципы понимал в стандартных шахматах — не перестал их понимать и в фишеровских, а кто двигал фигуры исключительно по памяти из справочника и при любом отклонении впадал в панику — стал в эту самую панику впадать гораздо быстрее, на 2-3 ходу.
Гораздо лучше в теории дела обстояли с эндшпилем. Особенно с малофигурными окончаниями — чем меньше фигур — тем лучше. Такие ситуации, в отличие от дебютов, просчитывались куда как проще: фигур-то гораздо меньше! Да и ограничения по количеству ходов способствовали (см. Правило 50 ходов). Так или иначе, компьютеры получили возможность пользоваться Эндшпильными таблицами Налимова и это, пожалуй было еще большей победой, нежели дебютные библиотеки. Впрочем, человек тут имел свои козыри — например то, что множество вариантов шахматных окончаний можно было играть, практически не считая варианты, а пользуясь известными алгоритмами, самый знаменитый пример (первый этюд, вероятность возникновения подобных мотивов в реальной партии достаточно высока).
А вот в миттельшпиле человек оставался хозяином положения. Да, совершенствовались алгоритмы для оценки позиции, да, компьютеры считали все дальше и глубже, но оставалось одно, то, из-за чего компьютеры так пока что и не стали ни писателями, ни композиторами: план. Если в дебюте компьютер мог двигать фигуры исключительно “по книжке”, а в эндшпиле — придерживаться неких алгоритмов, то с планом были трудности. Да, очевидно, если при оценке позиции машина находила у соперника слабые места — то могла делать ходы, направленные на их использование. Если слабые места были у машины — то она могла предпринимать действия для защиты. Однако, живой шахматист не будет руководствоваться только своим планом — он попытается определить планы соперника. Замечательная задача для ИИ. Вот только выполнимая ли?
В 1996 году представители компании IBM предложили Гарри Каспарову сыграть матч против их шахматной программы «Дип Блю» с призовым фондом в $500 тыс. «Дип Блю» — суперкомпьютер на базе системы RS6000, состоящий из 32 узлов, каждый из которых состоял из 512 процессоров, аппаратно оптимизированных для шахматной программы. Производительность «Дип Блю» соответствовала 11,38 GFLOPS, и компьютер мог оценивать до 200 млн позиций в секунду (Википедия).
Тринадцатый чемпион мира Гарри Каспаров всегда считал свое занятие прежде всего творчеством. То есть, тем, что машине недоступно и не будет доступно никогда. Каспаров говорил:
“Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу.”
По иронии судьбы, именно Каспаров стал первым чемпионом мира, проигравшим компьютеру. Первая же партия матча Deep Blue — Каспаров (Филадельфия, февраль 1996 г.) принесла сенсацию — Чемпион Мира повержен машиной. Увы для поклонников ИИ — уже во второй партии чемпион мира реваншировался, а после еще двух партий, завершившихся вничью, выиграл дважды, доказав таким образом, что чемпион мира — это чемпион мира. Все же, было уже понятно, что компьютерные шахматы — это реальная сила, и что во втором матче, который IBM предложила спустя чуть более года, чемпиону-человеку придется постараться, чтобы защитить человеческую расу.
Второй матч Каспарова с “Темно-синим” начался, наверное, даже с огорчительного для любителей интриги результата — Каспаров выиграл белыми легко, избрав неправильное начало (точнее, этот дебют вполне можно классифицировать, как Дебют Рети). Казалось, все ясно, идея Каспарова проста — лишить соперника первого козыря, дебютной библиотеки, и играть просто в шахматы, что машине не дано. Конечно, отойти от теории при игре черными гораздо сложнее, тон ведь задают белые, и тут Каспаров, вероятно, надеялся на Испанскую партию, ту самую, которую в количестве восемнадцати штук играл сам Остап Бендер — старинный дебют, где отыграть по книжке сам дебют мало, надо уметь играть миттельшпиль. И тут-то и началось.
Тот не шахматист, кто, проиграв партию, не заявляет, что у него было выигрышное положение
(И.Ильф)
Итак, сначала — только игровые факты. Партии игрались с контролем 2 часа на 40 ходов (классический контроль времени). Играя черными, Каспаров попытался оживить позицию с помощью жертв, машина эти жертвы отклонила, и в итоге, чемпион мира, оказавшийся в сложнейшей позиции, сдался. Все просто и ясно. Далее часть описания и цитат заимствована отсюда (там же можно посмотреть всю партию №2), часть — описана автором.
По мнению чемпиона, первый звоночек прозвенел на 35 ходу — суперкомпьютер, до этого тративший не более трех минут на ход, задумался на четверть часа. Еще шесть минут — над следующим ходом. Результат был еще более неожиданным — компьютер отклоняет жертву пешек черными.
По условиям, после каждой партии IBM предоставляла распечатки анализов, которые компьютер производил во время каждой партии. По словам Каспарова, вариант, избранный машиной, ей же был оценен, как неясный, в отличие от принятия жертвы, которое машина оценивала как выгодное для себя. “Очень мило. Мы имеем дело с уникальным событием, Машина отказывается от выигрыша трех пешек, потому что ей якобы “неясно” — Г.Каспаров.
Партия продолжалась, и двигалась к логическому финалу, который в конце концов и наступил — Каспаров сдался. Однако чудеса на этом не закончились. Как выяснилось практически сразу — чемпион мира сдался в ничейной позиции. Казалось бы, обвинять тут некого, кроме самого потерпевшего. Но все не так просто. Каспаров сдался, просто поверив, что машина непогрешима. И ошибся. Своим последним ходом в партии машина допустила грубейшую тактическую ошибку, после чего черные могли закончить партию вничью. Удивление Каспарова после партии вполне понятно: машина, нашедшая сильнейший позиционный ход, который оказался не под силу даже многим белковым шахматистам, то есть, обошедшая людей на их же территории — в позиционной игре, тут же проиграла на своей территории, где она не может ошибаться — допустив элементарный тактический зевок?
Эти вопросы до сих пор остаются вопросами, а матч, тем не менее, продолжался. Три партии завершились вничью. Была ли шестая партия для Каспарова своеобразным финалом? Финалом в матче за честь и ум человеческой расы.
В шахматах выигрывает тот, кто ошибается предпоследним
(С.Тартаковер)
Пожалуй, с точки зрения компьютерных шахмат, в шестой партии не произошло ничего интересного. Вопросы в этой партии в основном к чемпиону мира — каким образом он мог сделать ход 7.… h6? Компьютер тут же пожертвовал коня и позиция черных покатилась под откос. После 19-го хода белых Каспаров сдался. Единственное его достижение в данной партии — это то, что официально она не стала самым быстрым поражением в его карьере — шахматные статистики не учитывают партии человека с компьютером. Хотя формально, как вы поняли, это именно такая партия.
Дальше было менее интересно — якобы, IBM отказалась предоставлять логи анализов этой партии, что, судя по всему, неправда (см. ссылки внизу), а предложение Каспарова сыграть еще один матч было встречено корпорацией оригинально — герой матча (Deep Blue) был демонтирован и сдан в утильмузей. Впрочем, это как раз легко объяснить тем, что так или иначе, но чемпион мира был побежден, цель достигнута, а выкладывать еще раз круглую сумму для утешения Каспарова в IBM как-то не очень хотели.
И все же, что доказали эти матчи? Что человек повержен? Если брать оба матча Каспарова с DB — то счет остался в пользу Каспарова — 6,5-5,5. Если даже брать только второй — то во-первых, наверное, статистически результат 2-1 в пользу одной стороны (без учета ничьих) ничего не доказывает. Во-вторых, поражение Каспарова в шестой партии — из-за явного зевка — вряд ли на основании такой грубейшей ошибки (я молчу про сдачу Каспаровым второй партии в ничейной позиции) можно доказывать силу шахматной программы.
После переезда Deep Blue в музей, люди, разумеется, не перестали играть в шахматы с компьютером. Однако, о подобных матчах вообще не слышно, гроссмейстеры теперь предпочитают более экзотические виды использования компьютера. Может, ведущие гроссмейстеры просто боятся поражений от машины? Почему тогда владельцы суперкомпьютеров, авторы мощных шахматных программ, не заявляют, мол, вот мы предложили матч, а чемпион мира отказался? Скорее всего дело действительно в падении интереса к шахматам, интереснее сейчас ставить другие задачи перед ИИ, а поражение от машины в шахматы, пусть даже и чемпиона мира — кому оно интересно, ведь “уже давно машина выиграла у чемпиона мира”.
Однажды я решил научиться шахматам, взял в библиотеке книгу, купил маленькую шахматную доску и начал изучать. Научился ходить фигурами, разыграл один гамбит сам с собой, а потом решил сыграть против приложения на телефоне. Естественно проигрывал независимо от уровня сложности, но это не самое страшное: даже если я выигрывал у компьютера, я не очень то понимал смысл ходов. То есть мой уровень игры оставался одним и тем же, независимо от того как я играю.
Тогда я прочёл парочку журналов, где указывалось на победу компьютера над человеком в шахматах, то насколько он делает неочевидные для человека ходы. В итоге я решил, что компьютер не обыграть, а если обыграть, то ты не поймёшь сути ходов и это ничего тебе не даст. Тогда я бросил шахматы и больше к ним не возвращался.
И вот одним вечером, я наткнулся на статью в хабре, где было сказано, что ИИ победил тупой перебор вариантов. Я заинтересовался, как ИИ это сделал, и там рассказывалось, что некий Alphazero использует метод Монте-Карло и оценку позиции нейросетью. И я примерно представлял как нейросеть оценивает позицию, какие методы использует.
Обыграл компьютер
Меня завораживала жертва всего ради победы. Даже гроссмейстер в одной из партии пожертвовал фигуру с полной компенсацией в дальнейшем. Уже сейчас мой мозг оценивал позицию более гибко. Ферзь мог иметь нулевую ценность, и я легко им мог жертвовать, матуя в два хода, а в зависимости от того, где вражеский король, в какую сторону тот рокировался, цена коней на правом и левом фланге менялась. В интернете я наткнулся на партию, где человек обыгрывает шахматную программу. Я решил повторить его ходы, и у меня получилось. Вот только у меня возникли проблемы со Stockfish.
Он учится. Stockfish учится и больше не повторяет ошибок с жадным поеданием материала. Придётся очищать память, чтобы повторить трюк.
© мысли автора
Важно другое, я научился играть как компьютер с плохим ИИ на два шага вперёд. Самое главное я отошёл от рандомного перебора вариантов. Теперь выбираю следующий ход я сам, точнее нейросеть в моей голове. И пусть я думаю всего на ход вперёд, и не очень хорошо, но я могу красиво обыграть новичка.
Что такое го?
Го — это древние восточные шахматы с некоторыми отличиями. Игра существовала уже 2 500 лет назад. С точки зрения математики и вероятностей эта игра гораздо сложнее шахмат.
Метод Монте-Карло и Нейросеть
Для начала поймём, как выбираются ходы. Этот метод благодаря которому следующие ходы выбираются. Рандомно! Именно так выбирал ходы я в попытках обыграть приложение: судорожно метался, перебирая случайные варианты. Осталось понять по каким критериям Нейросеть выбирает лучшие ходы.
О тут всё тоже очень просто! Метод называется нравится-не нравится. Нейросеть смотрит на позицию и выдаёт оценку, а потом выбирается наилучшая позиция на следующем ходу. Оценка позиции меняется, если ход оказывается не самым лучшим и из этой позиции можно проиграть.
Всё что надо делать, это натаскать нейросеть на множество позиций. Ну и не забывать об алгоритме поиска наилучших путей.
Какая практическая польза человечеству от побед машин
в играх
Игры — удобный полигон для оттачивания наших методов. В отличие от реальной жизни игру можно масштабировать и ускорить. Например, нам ничего не мешает запустить сразу миллион StarCraft и ускорить игру. Так мы получим большое количество опыта, на котором можем обучиться.
В реальной жизни у человека есть 80, может быть, 100 лет. Всё это время мы учимся.
Читайте также: