Семь главных игр в истории человечества. Шашки, шахматы, го, нарды, скрабл, покер, бридж

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

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

Может возникнуть вопрос: зачем специалисту по вычислительным системам тратить свое дорогое время, энергию и деньги грантодателей на создание компьютерных программ для настольных игр? Специалисты обычно дают один из следующих дежурных ответов: игры – это испытательные стенды; игры обеспечивают контрольные задачи для оценки эффективности систем искусственного интеллекта; игры позволяют легко сравнивать результативность компьютера с результативностью человека; игры – это упрощенные модели аспектов «реального мира». Или (если специалист чуть более откровенен): игры – это увлекательно. Такие ответы хороши, но ни один из них не является до конца правдивым.

Истинная мотивация специалиста по вычислительным системам, разрабатывающего ИИ для игр, не слишком отличается от мотивации родителя, который тратит дорогое время и энергию на воспитание своего ребенка. Это творческий процесс. Придуманный Мэри Шелли доктор Франкенштейн, размышляя о своем творении, говорит: «Новая порода людей благословит меня как своего создателя; множество счастливых и совершенных существ будут обязаны мне рождением. Ни у одного отца нет стольких оснований на получение признательности ребенка, сколько будет у меня». Джонатан Шеффер испытал это чувство, когда одно из его алгоритмических творений впервые одержало над ним победу. «Мне удалось создать разумное поведение, – писал он. – Я испугался».

Шеффер, который родился в Торонто в 1957 году, с детства играл в разные игры. В книге «На шаг впереди» (One Jump Ahead), посвященной его шашечной одиссее и созданию игровой компьютерной программы, он живо рассказывает о своем детском увлечении шахматами с их «фигурами воинов короля Артура, отстаивающими королевскую честь» и «тщательно срежиссированным балетом». Шеффер отмечал сходство между своим пристрастием к этой игре и любовью, испытываемой знатоками «к изящным искусствам или музыке». В 16 лет он завоевал титул мастера спорта по шахматам. В Торонтском университете Шеффер сначала изучал математику, потом занялся физикой, а затем переключился на компьютерные науки, поверив в то, что даже если сам он никогда не станет чемпионом мира по шахматам, ему, возможно, удастся написать программу, которая сумеет завоевать этот титул. Он учился программированию, анализируя существующую шахматную программу, написанную на фортране, одном из первых языков программирования. В Университете Ватерлоо Шеффер тратил так много времени на программирование, стремясь научить компьютеры играть, что «запорол» свою диссертацию. Но это не имело значения. Он оформил в виде диссертации работу в области шахмат, дал ей академически корректное название «Эксперименты в области поиска и знаний» (Experiments in Search and Knowledge) и защитился в 1986 году.

Два года спустя, уже работая преподавателем в Университете провинции Альберта, он решил заняться шашками. По его представлениям, это не должно быть чем-то сложным (так же до него думал Сэмюэл). В конце концов, это всего лишь шашки. Шеффер не испытывал любви к этой игре, и его не трогали таящиеся в ней стратегические сокровища, привлекавшие Тинсли. В основе его интереса лежали приземленные побуждения. «Я мог бы привести множество научно обоснованных причин, но глубоко в душе у меня был настоящий ответ, – писал он. – Я мог победить». Шашки стали главным в жизни Шеффера.

Работа над системой, первоначально носившей название Beast, началась 2 июня 1989 года. Шеффер быстро обзавелся помощниками, подрядив двоих коллег, которые как-то за обедом нечаянно натолкнули его на идею заняться шашками. Он обратился к работам Сэмюэла, написанным три десятилетия назад. Кроме того, он разместил сообщение – по сути, крик о помощи – в конференции Usenet, посвященной шахматам (конференции, посвященной шашкам, не существовало).

Содержание сообщения было следующим: «Требуется функция оценки или рекомендации по ее разработке».

Единственный ответ пришел из Радиоастрофизической обсерватории Доминиона (Британская Колумбия) от Нормана Трелора, который на тот момент был безработным. Шеффер пригласил его в Эдмонтон. Трелор, «низкорослый, типичный англичанин в скромном костюме», внимательно прочитал работу Сэмюэла и заявил, что в ней есть серьезные изъяны, но он знает, как их исправить. Как оказалось, Трелор, в отличие от Шеффера и Сэмюэла, отлично играл в шашки.

Система Beast получила новое название – Chinook. Шеффер взял на себя разработку ее поисковой функции, а Трелор – алгоритм оценки. Они были готовы построить машину, способную взбираться на дерево шашек лучше, чем любой человек, даже сам Тинсли.

В августе 1989 года Шеффер сидел за столиком в лондонской пятизвездочной гостинице Park Lane, он покачивал ногой и грыз ногти. Денег, выделенных ему на исследования в области шашек, не хватало на то, чтобы снять номер в этой гостинице, поэтому, когда нужно было привести себя в порядок, он пользовался туалетом в холле. Каждое утро он вез Chinook на метро в Park Lane и устанавливал рядом с собой все это громоздкое оборудование, которое включало вычислительную машину Sun Microsystems с одним процессором и оперативной памятью 32 мегабайта. Созданная им и Трелором система уже достигла такого уровня, что сам Шеффер не мог ее обыграть.

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

Противниками Chinook в категории шашек были такие программы, как Colossus, Sage Draughts, Checker Hustler, Tournament Checkers и, наконец, просто Checkers. Последняя программа заслуживала особого внимания. Ее создателем был разработчик программного обеспечения, концертирующий пианист и редактор журнала Hang Gliding. Тем не менее Chinook оставила позади всех представителей искусственного интеллекта и завоевала в Лондоне золотую медаль.

Шеффер и Трелор праздновали победу, однако не забывали о том, что на лондонской площадке не было самого выдающегося игрока в шашки, Мариона Тинсли. К этому моменту второй этап триумфальной карьеры Тинсли длился уже почти два десятилетия. «Многое смущало меня, – недавно признался мне Шеффер. – Как обыграть Тинсли? Ведь речь идет не об обычном человеке. Речь идет – и я говорю это не в отрицательном смысле – об отклонении от нормы. Речь идет о человеке, наделенном экстраординарными способностями. Сама мысль о нем вселяла в меня ужас».

Помимо быстрого поиска и точной оценки для победы над мастером Шефферу нужно было встроить в Chinook еще два ключевых элемента: дебюты и эндшпили. Каждая партия игры в шашки начинается одинаково: с 24 фишек, расставленных по своим полям определенным образом, иначе говоря, с предсказуемой мозаикой возможностей. Большинство подобных игр заканчиваются тоже одинаково – истощением резервов игроков и победой одного из них или ничьей. Распространенность и типичность этих вариантов порождают обширную теоретическую литературу – горы книг, посвященных дебютам и эндшпилям игр. Типичные дебюты даже получили свои названия: дебют Хендерсона, сицилианская защита, фусэки Сюсаку. Поскольку к концу игры на доске остается очень мало фишек, зачастую можно выполнить всесторонний компьютерный анализ и предсказать итог. Например, в шахматах эндшпиль, в котором слон и конь противостоят слону, теоретически гарантируют ничью, что отлично известно хорошим игрокам. А вот миттельшпиль, чистилище между дебютом и эндшпилем, – это Дикий Запад – много фигур, масса возможностей. Вычисления чрезвычайно сложны, поэтому конкретной теории практически нет.

С точки зрения компьютерных вычислений обсчет каждой позиции эндшпиля в реальном времени обошелся бы слишком дорого. Гораздо рациональнее было обсчитывать корректные розыгрыши эндшпилей заранее и загружать эти знания в Chinook. Поначалу это легко. Если на доске одна шашка (рядовая ситуация для эндшпиля), возможных позиций всего 120: простая шашка может находиться на одном из 28 полей, а дамка – на одном из 32 полей; при этом фишка может быть белой или черной. Однако если шашек две, позиций уже 7000. При трех шашках их больше четверти миллиона. При четырех – семь миллионов, при пяти – 150 миллионов, при шести – два с половиной миллиарда, а при семи – 35 миллиардов.

Иными словами, Шефферу нужно было научить Chinook выполнять с помощью механических операций то, что ведущие игроки делали с помощью интуиции и опыта. Целый месяц Шеффер по два часа в день педантично загружал в компьютер дебютные ходы из семитомного справочника по шашкам. (И это было еще немного. Кен Томпсон, разработчик операционной системы Unix и шахматной машины Belle, три года по часу в день вводил с клавиатуры строки из «Энциклопедии шахматных дебютов».) Что касается эндшпилей, Шеффер запустил на машинах обсчет бесчисленных комбинаций шашек и результатов. Через два с лишним месяца вычислений эндшпили с четырьмя шашками были завершены – как раз к лондонскому турниру 1989 года. В те времена драгоценные базы данных хранили на магнитной ленте – носитель был похож на огромную аудиокассету. С этим необычным предметом Шеффер разъезжал по соревнованиям, проводившимся в разных уголках мира. Даже единственный поврежденный бит информации в его массиве – одна единица вместо нуля – делал всю базу данных бесполезной.