Сейчас мы подбираемся ко второй из шести ключевых идей в области искусственного интеллекта на сегодняшний день. Это способ решить, что делать, когда весь мир против тебя. В соревновательной среде тебе нужно выбрать наилучший возможный ход, предполагая, что твой противник выберет сделать свой наилучший возможный ход.
Опять-таки, это настолько просто, что звучит очевидно. Позвольте мне объяснить. Находясь в ситуации конкуренции, когда ваш противник выигрывает, вы проигрываете. Следовательно, наилучший возможный ход вашего соперника – наихудший возможный ход для вас. Эта идея также не новая. Мы все так действуем, когда играем. Если я пойду конем и атакую черного короля, тогда наилучший ход для черных – пожертвовать ладьей. И это даст мне ощутимое преимущество.
Давайте сыграем в «21», чтобы продемонстрировать эту идею. Вам не нужно пить во время игры, но будет намного веселее, если вы нальете себе стаканчик. Игра начинается с нуля. Каждый игрок по очереди добавляет один, два или три к предыдущему числу и озвучивает новое. Конечное число не должно быть больше 21. Тот игрок, который назовет 21, проигрывает и должен выпить.
Илл. 9–10. Чертеж Nimatron из Патентного бюро США и его фотография 1940 года
Хорошо, я буду первым.
Я: 1
ВЫ: 4
Я: 7
ВЫ: 8
Я: 9
ВЫ: 12
Я: 14
ВЫ: 16
Я: 17
ВЫ: 20
У меня нет другого выхода, как назвать 21. И это означает, что вы выиграли, загнав меня в угол!
Давайте применим концепцию выбора наилучшего возможного хода для игры в «21», учитывая, что ваш противник сделает то же самое. На самом деле, это позволит сыграть нам в эту игру идеально. Мы сталкиваемся с первой проблемой: ваш наилучший возможный ход зависит от всех последующих шагов обоих игроков. И как же нам разрубить этот гордиев узел?
Алгоритм на основе искусственного интеллекта минимакс позволяет разрешить эту проблему. Минимакс думает наперед о наилучшем возможном ходе, начиная с конца игры. Он берет начало в конце потому, что в конце игры становится понятно, кто выиграл, а кто проиграл. Каждый раз минимакс возвращается назад, к предыдущему ходу, и рассматривает, как вы, игрок МАКС, можете выиграть, пока я, игрок МИНИ, прилагаю все усилия к вашему проигрышу. В конце игры, если вы называете 21, вы проигрываете. Следовательно, для шанса на победу ваше последнее названное число должно быть меньше 21. Предположим, что это число 20. Тогда я буду вынужден назвать 21 и вы выиграете. Следовательно, ваша цель теперь не назвать 21, а назвать 20. Давайте думать в обратном направлении, начиная с вашей цели назвать 20. Если я назову 17, 18 или 19, тогда вы сможете назвать 20 и выиграть на следующем ходе. Получается, что ваша цель теперь не назвать 20, а сделать так, чтобы я назвал 17, 18 или 19.
Снова думаем в обратном от вашей цели направлении, чтобы я назвал 17, 18 или 19. Если вы назовете 16, тогда я могу назвать 17, 18 или 19 и у вас будет возможность оказаться победителем. Теперь ваша новая цель – это назвать 16. Вы знаете, что сможете одержать победу на следующем ходу, при условии, что хорошо играете. Сейчас вы снова можете применить обратное мышление, отталкиваясь от цели назвать 16. Если я назову 13, 14 или 15, тогда вы сможете назвать 16 и в итоге выиграть. Если вы назовете 12, тогда мне нужно будет назвать 13, 14 или 15 и вы сможете выиграть. Следовательно, теперь ваша цель – это назвать 12.
Вы можете продолжить повторять двигаться в обратном направлении, сменяя вашу цель с 12 до 8, а после до 4. Это в точности та же стратегия, что была в самом начале игры: вы назвали 4, 8, 12, 16 и 20. Называя числа кратные 4, вы гарантированно сможете выиграть в «21». Конечно же, ваш противник будет придерживаться той же стратегии. Чем больше игроков, тем сложнее становится стратегия. Тем не менее принцип минимакс найдет наилучший способ выиграть.
Мы можем применить концепцию обратного мышления и к более сложным играм, например к шахматам. Однако шахматы обладают более сложным древом возможных ходов. В среднем на каждый ход в шахматах приходится более 30 возможных ходов, в то время как на каждый ход в «21» всего три. Компьютеры хороши в выполнении таких задач. Такое обратное мышление сегодня заложено в сердце даже самого мощного компьютерного движка для игры в шахматы.
Принцип обратного мышления помогает в решении не только шахмат и «21», но и других проблем реальной жизни, которые могут быть представлены в качестве игры против оппонента. Где мне контролировать транспортную сеть, учитывая, что «зайцы» быстро поймут, какие территории меньше всего находятся под присмотром? Какие облигации мне купить, чтобы минимизировать риск инвестиций, учитывая, что рынок может выступить против меня? Какое профилактическое обслуживание мне необходимо выполнить для моего авиапарка, учитывая, что эрозии и изнашивание деталей могут быть причиной поломок? Жизнь сама по себе уже игра.
Вариаций шахматных партий больше, чем атомов во Вселенной. Шахматные движки используют множество трюков, чтобы избавиться от рассмотрения каждой возможной партии. Количество возможных шахматных партий обозначается числом Шеннона, значение которого составляет от 10111 до 10123. Его впервые вычислил Клод Шеннон в своей работе 1950 года «Программирование компьютера для игры в шахматы». Эта работа поспособствовала развитию области компьютерных шахмат. Шеннон принимал участие в Дартмутском семинаре 1956 года и более известен как «отец теории информатики». В 1937 году в своей магистерской диссертации он доказал, что логика Буля может быть применена к электрическим реле, тем самым подготовив почву для проектирования цифровых схем компьютера. Профессор когнитивистики и педагогики в Гарвардском университете Говард Гарднер оценил его диссертацию как «возможно, самую важную, а также самую известную магистерскую работу столетия».
Самая первая игра, созданная на базе искусственного интеллекта, была одной из вариаций игры на выпивание, которую мы недавно рассмотрели. Корпорация Westinghouse Electric в 1940 году разработала Nimatron[35] (Ниматрон) и продемонстрировала его на ежегодной Всемирной выставке в Нью-Йорке [1]. Более 44 миллионов человек посетили выставку, темой которой стал «Мир завтрашнего дня». Посетителям обещали показать мир будущего, в который входил и Nimatron, электрорелейная машина для древней китайской игры в ним. По правилам этой игры участники по очереди берут камни, разложенные на несколько кучек, но за один ход могут взять камни только из одной кучки. Игрок, поднявший последний камень, проигрывает. Nimatron – двумерная версия игры в «21».
Nimatron не был полноценным компьютером, а только лишь машиной для игры в ним. Следовательно, он и не являлся тем, что впоследствии мы назовем машиной Тьюринга. Тем не менее это было впечатляющее творение, весом более тонны и с четырьмя линиями по семь лампочек со стороны человека-игрока и с каждой из четырех сторон верхнего дисплея для зрителей. Игроки по очереди играли с автоматом, гася одну или более лампочек до тех пор, пока не погаснут все.
Nimatron требовалось всего несколько миллисекунд, чтобы сделать свой ход. В целях избежания деморализации человеческого противника, запрограммировали задержку, с учетом которой у машины на обдумывание уходила пара секунд. Даже с учетом этой искусственной задержки Nimatron был в некоторой степени подавляющим. За время всемирной выставки было сыграно более 100 000 партий. В девяти из десяти игр победителем становился Nimatron. При этом большинство поражений ему нанесли операторы машины: они запоминали выигрышные стратегии, чтобы показать толпе, что Nimatron и правда можно обыграть.
Nimatron вдохновил инженерную компанию Ferranti на создание другой машины для игры в ним, Nimrod, который представили на фестивале Британии в 1951 году.
Nimrod тесно связан с Австралией, поскольку был разработан австралийцем Джоном Мейкписом Беннеттом, работающим в то время в компании Ferranti. После он вернулся на родину, стал первым профессором информатики и основателем Австралийского компьютерного сообщества.
Среди всех различных игр, в которые мы играем сегодня, шахматы занимают особое место в развитии искусственного интеллекта. В 1941 году, через год после изобретения Nimatron, в Блетчли-парке Алан Тьюринг начал обсуждать со своими коллегами по взламыванию кодов возможность создания машины, способной играть в шахматы и выполнять другие «умные» задачи. К моменту окончания Второй мировой войны Тьюринг был убежден, что теоретически компьютер способен воспроизвести все, на что способен человеческий мозг, в том числе и игру в шахматы.
В 1948 году он начать применять свою идею на практике. Он и его коллега из Кембриджского королевского колледжа Дэвид Чемперноун написали первую шахматную программу, названную Turochamp в честь фамилий создателей. Turochamp использовал алгоритм минимакса для определения стратегии игры, просчета всех возможных собственных ходов и всех возможных ходов противника. Чтобы избавить компьютер от необходимости просчитывать игру до конца, счет объявлялся в середине игры. Счет велся путем добавления очков в разных категориях, включая захват фигур, их мобильность и безопасность, а также угрозу постановки мата.
Поскольку игра просчитывалась только на два хода вперед, Turochamp играл на уровне начинающего. Даже учитывая эту особенность, для компьютеров того времени такие вычисления все еще были сложны, и при жизни Тьюринга запустить программу на реальном компьютере и вовсе не удалось. Вместо этого он мучительно моделировал программу вручную, тратя по полчаса или больше на просчет каждого хода.
Тем не менее в 2012 году удалось протестировать программу на компьютере. Turochamp была воссоздана и продемонстрирована на конференции в честь столетия со дня рождения Алана Тьюринга в Манчестере. Бывший мировой чемпион по шахматам Гарри Каспаров с легкостью обыграл программу за 16 ходов. Но 15-ю годами ранее, играя против более продвинутого компьютера, Каспаров не смог одержать победу. В 1990-х компания IBM переняла многие идеи Turochamp и вывела их на новый уровень, создав шахматный компьютер Deep Blue. Целью создания было стремление попасть в книгу рекордов и завоевать славу.
Deep Blue оказался сложным инженерным проектом, в среднем просчитывающим от шести до восьми ходов вперед, а в некоторых случаях и более 20. Он работал на базе рабочих станций IBM RS/6000 и имел специальное программное обеспечение для более быстрого просчета ходов. Выглядел такой компьютер впечатляюще: он представлял собой черный моноблок, как будто прямо с места съемок фильма «2001 год: Космическая одиссея» Стэнли Кубрика. В 1996 году IBM провела первый на тот момент матч с чемпионом мира по шахматам Каспаровым. Со счетом 4:2 Каспаров одержал победу и забрал призовой фонд в 400 000 долларов. Год спустя в Нью-Йорке был организован второй матч из шести партий, а призовой фонд был в три раза больше. Улучшенный Deep Blue (сейчас носит название Deeper Blue) обыграл Гарри Каспарова.
Игра была настолько напряженной, что до конца не было понятно, кто выиграет. Каспаров выиграл первую партию, а Deep Blue – вторую. После игры был проведен анализ, в результате которого было вынесено предположение, что Каспаров мог сыграть вничью[36]. Следующие три партии были сыграны вничью. Вся надежда была на финальную, шестую партию. Каспаров неудачно разыграл дебют, вероятно, он хотел вывести Deep Blue за рамки базы стандартных начальных ходов. Вместо того чтобы нанести удар компьютеру, Каспаров нанес его сам себе. На 19-м ходу он объявил поражение. Эта игра стала самой короткой, которую он когда-либо играл против Deep Blue. Машина одержала победу над человеком. Уезжая домой, Каспаров в качестве утешительного приза забрал еще 400 000 долларов, половину всего призового фонда.
Несмотря на проигрыш, Каспаров остается одним из лучших игроков в истории шахмат. Он стал самым молодым чемпионом мира и оставался обладателем титула дольше, чем любые другие мировые чемпионы. Жестокая ирония заключается в том, что он остался на страницах учебников по истории как первый чемпион мира по шахматам, проигравший компьютеру. После своего поражения он отметил:
«Я играл со многими компьютерами, но никогда не испытывал ничего подобного. Я чувствую и ощущаю новый вид интеллекта на другом конце стола. В течение всего турнира я играл настолько хорошо, насколько это было в моих силах, и тем не менее проиграл. Машина играла легко и непринужденно и с легкостью одержала победу» [2].
На сегодняшний день наилучший шахматный движок – это Stockfish, 14-кратный победитель чемпионата ведущих шахматных движков. Последняя версия Stockfish просчитывает от 80 до 100 ходов вперед. В серии из шести партий против Stockfish, учитывая его показатели игры, даже у лучшего игрока в шахматы шанс выиграть один на триллион.
Буду откровенен. Человечество, игра окончена. Во всяком случае, это касается шахмат.
Гарри Каспаров, может, и был первым чемпионом мира по шахматам, проигравшим в турнире компьютеру, но он не был первым мировым чемпионом, потерпевшим поражение от компьютерной программы. Луиджи Вилла, профессиональный игрок в нарды из Милана, получил такую славу за 18 лет до проигрыша Каспарова. 14 июля 1979 года Луиджи Вилла стал победителем ежегодного чемпионата мира по нардам в первый и последний раз. Соответственно, поскольку нарды – азартная игра, то соревнование проходило в Монте-Карло. Времени для того, чтобы насладиться первенством и выпить шампанского, у Виллы не было. На следующий день после победы он проиграл со счетом 7:1 на тренировочном матче против компьютера, призовой фонд которого составил 5000 долларов.
Его противником была программа Ханса Берлинера BKG 9.8. Берлинер был профессором Университета Карнеги – Меллона в США и бывшим мировым чемпионом по заочным шахматам. В течение пяти лет Берлинер пытался обучить компьютер играть в нарды, в результате чего создал BKG 9.8. В таком противостоянии человека против машины Вилле не хватило немного удачи. В самом деле, по результатам последующего анализа игры было сделано предположение, что, по всей вероятности, он играл лучше, чем BKG 9.8. Но, к сожалению, игральные кости – независимое лицо, которое было более благосклонно к машине. В такой короткой игре из восьми партий у удачливого аутсайдера есть все шансы выиграть.
Новоиспеченный чемпион мира был безутешен. San Francisco Chronicle сообщила, что он с отвращением топнул ногой, крича о несправедливости, и что «это разочарование разделили несколько друзей итальянцев, которые после турнира были частью возмущенной и активно жестикулирующей толпы и сыпали оскорблениями в адрес машины» [3]. О том, как отреагировал компьютер на эти оскорбления, не сообщалось.
В какой-то степени для компьютера нарды – задача посложнее, чем шахматы. При каждом ходе есть 21 возможная комбинация игральных костей и около 20 возможных способов бросить кости. Следовательно, необходимо учитывать 400 вариантов хода. Играя в нарды, программа не способна предугадывать такое же количество ходов, как при игре в шахматы, где нужно учитывать только 30. В отличие от шахмат, в нардах речь также идет о принятии решений в неопределенном мире, где от броска игральных костей зависит многое, поскольку, как выяснил Лиуджи Вилла, судьба – дама капризная. Возможно, из-за этой неопределенности компьютерам не удается также хорошо обыгрывать людей, как у них это получается в шахматах. Тем не менее, основываясь на их рейтингах, лучшей современной программе в игре с текущим мировым чемпионом по нардам удалось бы вести со счетом 2:1.
15 июля 1979 года – день, когда BKG 9.8 повезло немного больше, чем другим, оставил глубокий след в истории искусственного интеллекта, а также в истории человечества. Отныне мы не лучшие. Человечество понесло поражение в одной из изобретенных им игр. Нам остается только задаваться вопросом: было ли это началом конца для нас, людей?
Двумя преимуществами компьютеров перед человеческим мозгом являются их грубая сила и точность. Они могут работать намного быстрее и просматривать гораздо большие массивы данных, чем люди, при этом выполняя все без ошибок. В соответствии с четко определенной задачей это означает, что компьютеры могут принимать наилучшие решения для победы над человеком.
Шашки – один из наилучших примеров, иллюстрирующих данную проблему. Игра проводится на доске 8×8, а игрокам, передвигаясь по диагонали, необходимо захватить все шашки противника, перепрыгнув на свободную клетку. В 1995 году компьютерная программа Chinook практически стала победителем в мировом чемпионате по шашкам между людьми и компьютерами. Почти 20 лет программу создавала команда из Университета Альберты под руководством профессора Джонатана Шеффера. В игре из 32 партий Chinook одержала победу над гроссмейстером Доном Лафферти, выиграв предпоследнюю партию, а все остальные сыграли вничью. Шашки – одна из тех игр, где очень просто сыграть вничью.
Однако успех к программе пришел немногим ранее, во время игры против легендарного Мариона Тинсли[37]. Несомненно, он лучший игрок в шашки за всю историю человечества. За свою 45-летнюю карьеру Тинсли не проиграл ни одного мирового турнира и проиграл лишь в семи партиях, две из которых были против Chinook, а во время других двух он был пьян! В 1991 году Тинсли отошел от игры на чемпионатах и стал обладателем почетного титула чемпиона мира, подтвердив свой статус практически непобедимого и доминирующего игрока. В 1992 году он обыграл Chinook со счетом 4:2, сыграв 33 партии вничью. В 1994 году состоялся матч-реванш между Тинсли и улучшенной версией Chinook. Шесть партий они снова сыграли вничью, а после Тинсли отказался продолжать по состоянию здоровья, любезно передав Chinook титул мирового чемпиона. В 1995-м он выразил желание вновь сыграть против компьютера, но, к сожалению, скончался от рака поджелудочной железы до того, как смогли организовать матч.
Илл. 11. Джонатан Шеффер (представляющий Chinook) в игре против Мариона Тинсли
Тем не менее сейчас нет смысла в тестировании Chinook против Тинсли или любого другого человека, поскольку программа и так продемонстрировала идеальную игру. В 2007 году команда разработчиков Chinook предоставила исчерпывающее доказательство, что программа никогда не сможет оказаться в проигрыше [4]. «Исчерпывающее» – самое подходящее слово для описания их «доказательства». Команде потребовалось несколько десятилетий вычислений на более чем 200 компьютерах, чтобы изучить все возможные варианты партий в шашки и показать, что независимо от того, насколько хорошо или плохо играет человек, его максимум в игре против Chinook – это ничья.
Существует множество других, менее сложных игр, где искусственный интеллект также продемонстрировал идеальную игру: ним, четыре в ряд, реверси и, несомненно, крестики-нолики [5]. Конечно, идеальная игра не всегда возможна. Такие игры, как шахматы, скорее всего никогда не будут сыграны идеально из-за своей сложности. Тем не менее, когда дело касается интеллекта, грубая сила иногда одерживает верх. И это хорошие новости для компьютеров.
Чтобы быть успешным не только в играх, но и в жизни, необходимо уметь справляться с неопределенностью. Покер, одна из самых популярных азартных игр, – прекрасный пример.
В таких играх, как шахматы, оба игрока видят доску и, следовательно, точно знают положение дел. Вероятность случайности отсутствует. Чего нельзя сказать о покере, ведь во время игры карты скрыты. Поэтому покер – это игра вероятностей и психологии. Вам необходимо понимать стратегию ваших противников. Когда они блефуют? Когда могут спасовать? Эти две отличительные черты делают покер для искусственного интеллекта задачей намного сложнее, чем шахматы. Вследствие этого, после успеха Deep Blue, для создания хорошего бота для игры в покер потребовалась еще пара десятков лет. Тем не менее на сегодняшний день искусственный интеллект уже очень хороший покерный игрок. Поэтому советую вам не делать ставки на его проигрыш.
В 2015 году Майкл Боулинг и его коллеги из университета Альберты разработали ИИ-бот Cepheus для игры в техасский холдем один на один. Поскольку ставки ограничены, а игроков всего двое, игра становится намного проще, чем при неограниченных ставках и с бóльшим количеством игроков. Учитывая ту роль, которую играет в покере случайность, невозможно выигрывать деньги в каждой раздаче: вам могут просто выпасть несчастливые карты. Команда университета Альберты провела восемь миллионов часов[38] за вычислениями, чтобы показать, что стратегия, разыгрываемая ботом Cepheus, практически безупречна и его невозможно победить. На протяжении всей своей игровой карьеры программа так и не будет повержена.
Два года спустя, в 2017 году, профессор университета Карнеги – Меллона Туомас Сандхольм и его коллеги разработали программу под названием Libratus для игры в более сложную и популярную игру один на один в безлимитный техасский холдем. Libratus сыграл против четырех профессиональных игроков в Питтсбурге, штат Пенсильвания, в борьбе за приз в 200 000 долларов. Они поучаствовали в трехнедельном марафоне из 120 000 раздач. Поскольку на протяжении всего турнира было огромное количество раздач, каждая из которых разыгрывалась в обе стороны, чтобы у каждого игрока было как можно больше как хороших, так и плохих комбинаций, мы с уверенностью можем сказать, что конечный результат не был случайным. Libratus вел с первого дня и безоговорочно стал победителем турнира.
Libratus – еще один пример могущества грубой силы математики. Для разработки программы потребовалось более 15 миллионов часов вычисления на суперкомпьютере в Питтсбургском суперкомпьютерном центре. Во время турнира Libratus каждую ночь тратил еще четыре миллиона часов на вычисления для усовершенствования своей стратегии, анализа предыдущих игровых дней, особое внимание уделяя проигрышам. Дон Ким, один из профессиональных игроков, играющих против компьютера, был поражен результатом. «До сегодняшнего дня я не осознавал, насколько он хорош. Я как будто играл против того, кто все время жульничал и видел все мои карты. Я не обвиняю программу в шулерстве. Это действительно было невероятно» [6].
Несмотря на то что некоторые игры по-прежнему представляют проблему для компьютеров, они все же сыграли важную роль в истории искусственного интеллекта. Их четкие правила и очевидные победители делают игры хорошим выбором для автоматизации, а для победы необходим высокий уровень интеллекта. Таким образом, игры предлагают простой, но идеализированный мир, в котором можно разрабатывать мыслящие машины и количественно оценивать достигнутый прогресс.
Игры также протестировали возражение Ады Лавлейс о том, что компьютеры могут делать только то, что им велено. Как компьютеры могут победить лучшего в мире шахматного или покерного игрока, если они всего лишь делают то, на что другой человек запрограммировал их? Ответ заключается в том, что компьютеры не делают в точности то, что им приказано делать. Компьютер может играть сам по себе, а затем, после каждой игры, обновлять стратегию для поиска наилучших и выигрышных ходов и избегания плохих, которые могут привести к поражению. Следовательно, компьютеры могут обучаться самостоятельно. В довершение всего мы также используем высокую скорость компьютера, чтобы играть в игры намного быстрее, чем это может делать человек. Количество сыгранных партий у Libratus намного больше, чем когда-либо сможет сыграть человек за всю жизнь, проводя каждый вечер за игрой в покер.
На самом деле, Libratus обучался довольно медленно, но этот недостаток компьютеры могут компенсировать своей скоростью и способностью играть в другие игры. Человеку необходимо 10 000 часов, чтобы развить, как говорит герой Лиама Нисона в фильме «Заложница», «много необычных способностей»[39] [7]. Искусственный интеллект, напротив, гораздо медленнее. Ему требуется более десяти миллионов часов для освоения покера, но, как знаменитая черепаха из басни, впоследствии он сможет опередить человека. Можете делать на это ставки.