Проблема го

Спустя сорок семь лет после того, как минимакс был предложен в качестве метода создания шахматных программ, Deep Blue смог оценивать 200 миллионов позиций в секунду. Эта грубая сила, объединенная с отшлифованным алгоритмом системы в целом, позволяет Deep Blue думать на 14–15 ходов вперед (по семь ходов с каждой стороны), а иногда и дальше. Как результат — победа над Каспаровым, бесспорно — сильнейшим шахматистом-человеком. На вызов, брошенный в свое время шахматами, теперь дан ответ. К несчастью, множество вопросов так и осталось нерешенными.

Создатели ИИ в течение десятилетий привыкли получать от жизни неожиданные и неприятные сюрпризы, поэтому многие из них приветствовали успех Deep Blue как проблеск света во тьме. Но на других ученых Deep Blue не произвел впечатления. Они высмеивают использованную им «грубую силу», не имеющую ничего общего с человеческим интеллектом. Если задача ИИ состоит в изучении разума с целью создания разумных компьютерных программ, то, как считает пионер таких исследований Джон Маккарти (John McCarthy, профессор информатики из Стэнфордского университета), у компьютерных шахмат мало общего с ИИ, и Deep Blue — это торжество инженерии. Вместо учета миллиардов позиций настоящие шахматисты учитывают лишь несколько. Когда у бывшего чемпиона мира Капабланки спросили, сколько вариантов тот обдумывает во время игры, Капабланка ответил: «Только один, но он всегда единственно верный».

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

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

Можно подумать, что главная трудность для компьютера заключается в комбинаторике. Доска го намного обширнее шахматной, поэтому возможных ходов значительно больше. В любой момент шахматной партии игрок имеет выбор примерно из двадцати пяти возможных ходов. Различные улучшения алгоритма позволяют программе анализировать только пять или шесть наилучших ходов, отбрасывая остальные. В го (в среднем) игрок выбирает один ход из 250 возможных. Даже если бы го-алгоритм смог сократить это число до 15–16, перебирая 200 миллионов позиций в секунду, Deep Blue потребовалось бы семьдесят лет, чтобы проанализировать ситуацию так же глубоко, как он это делает в шахматах за три минуты.

Можно возразить, что скоро компьютеры станут достаточно мощными для такого анализа. Но настоящая проблема лежит глубже. Го-программы не только не могут оценивать по 200 миллионов го-позиций в секунду — они не могут точно оценить даже одну-единственную позицию.

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

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

Группа камней может быть окружена и захвачена, но она может принимать и особый защитный строй, оберегая себя от дальнейших захватов в игре. Это называется «стать живой». Чтобы «стать живой», группа должна образовать в себе две ячейки незанятой территории — так называемые «глаза». Однако игроку не обязательно тратить ходы на построение «глаз» — ему достаточно знать, что он сможет сделать это, если группа будет атакована. (Так охрана замка поднимает мост только при приближении неприятеля.) Аналогично этому группы камней называют «мертвыми», когда у них нет надежды «стать живыми». Невозможность для группы «стать живой» означает, что противник всегда сможет захватить ее. Но он может и не делать этого — зачем тратить ходы на захват того, что уже (почти) захвачено?

Теперь возьмите одну из трех групп, показанных на рисунке справа. Как компьютер должен оценивать ее? Группа А мертва? Тогда территория, которую она занимает, уже принадлежит черным (формально еще нет, но это лишь вопрос желания черных). Может быть, группа жива? Тогда территория этой группы принадлежит белым. Ответы на такие вопросы зависят от ряда тонкостей. Надежно ли защищена эта группа? Надо ли тратить ходы, защищая ее, или можно нападать в другом месте? Умение игрока анализировать такие факторы и определяет, насколько хорошо он играет в го.

По мере накопления опыта, люди могут научиться оценивать группы быстро и точно. Но как превратить эти оценки в числа, которые сможет использовать компьютер? Люди удивительно хорошо сравнивают образы — они могут узнавать лица под разными углами, в тени и на свету, улыбающимися и хмурящимися; они могут узнать голос в гудящем автомобилями тоннеле или по трещащей телефонной линии. Но для оценки позиций го надо научиться объединять свои способности сравнения образов с логикой и знанием, чтобы проводить глубокие, но очень узкие поиски по дереву игры. С другой стороны, го-программы в оценке групп камней зависят (в основном) от грубой эвристики или других примитивных методов. Эта тактика работает в простых ситуациях, но когда она используется для оценки хоть сколько-нибудь сложных позиций, ее может ждать катастрофический провал.

Игра Дженис Ким против Handtalk прекрасно продемонстрировала эту проблему. Вначале Ким перехватила два камня противника таким образом, что могла захватить их в любое время. Handtalk понял, что эти камни потеряны и попытка их освобождения будет бессмысленной. Но конфигурация Ким несла в себе другую, скрытую угрозу — ее камни могли не только захватить камни противника, но еще и стать «живыми», тем самым угрожая всем окружающим камням. Handtalk не стал обращать внимания на двойственную природу этой атаки, сочтя ситуацию изолированной потерей двух камней, не мешающей защищать другие камни.

Я могу посочувствовать Handtalk — премудрости го я изучал дважды. Сначала как честолюбивый игрок, а затем как программист, пытающийся обучить этой игре компьютер. Когда в восемнадцать лет я приехал в Токио, то чувствовал себя умственно отсталым старшим братом других четырех учеников, чей возраст составлял от одиннадцати до семнадцати лет. Каждый уик-энд вместе с полусотней других претендентов мы проводили в игровом зале Японской ассоциации го, готовясь к турниру, определяющему, кто получит статус профессионала, а кто будет бороться за него в следующем году. В то время я был единственным представителем Запада в Лиге. Большинство молодых людей, с которыми я соперничал, были чрезвычайно талантливы и начинали играть с восьми лет. Многие из них, чтобы сконцентрироваться на игре, бросили школу. Но дом моего учителя даже среди этих профессиональных учеников считался самым серьезным. Он был, возможно, последним, неукоснительно следующим старинным японским традициям строгости. Целыми днями мы сидели на коленях перед досками, изучая законы игры и размышляя над победами и поражениями в прошлый уик-энд. Изредка играли в бейсбол в парке или заглядывали в магазин на углу, но подразумевалось, что нам запрещено иметь других друзей и другие интересы.

Вернувшись в Штаты, я поступил в колледж, попытался играть с существующими го-программами и ужаснулся их недостаткам. Обменявшись идеями, я и мой старый друг Тим Клингер (Tim Klinger, сейчас он готовится к защите диссертации по информатике в Hью-Йоркском университете) приступили к созданию нашей собственной го-программы.

Как опытный игрок я знаю, что определенные конфигурации камней возникают на доске снова и снова. Тим и я решили включить такие комбинации в нашу программу в виде множества правил «если — то» (если на доске появляется комбинация X, то Y будет хорошим ходом для достижения цели Z). Поскольку я мыслю во время игры группами камней, то и наша программа тоже оперирует группами и распознает их. Этот подход на основе копирования моделей человеческого знания и процессов принятия решений можно назвать традиционным для компьютерного го — его используют все лучшие го-программы.

Поскольку «жизнь» и «смерть» — критические аспекты в го, по большей части мы концентрировались именно на них. Наш «жизне-смертный» программный движок выполняет глубокий, но узкий поиск. В отличие от шахмат, где возможны почти все ходы, наша программа в начале партии ничего не допускает. Прежде всего алгоритм устанавливает цель поиска, например «захват камня A». Затем эта цель разбирается на составные части — подцель, под-подцель и так далее. Строится «дерево задач», а не «дерево ходов». Если «дерево задач» построено, программа может определить набором своих правил «если — то», куда лучше всего ставить камень для достижения подцели каждого хода. После определения и сравнения всех промежуточных ходов программе остаются только несколько возможных вариантов, достигающих главной цели с наибольшей вероятностью.

Дерево задач позволяет быстро распознавать бесполезные комбинации и отказываться от плохих вариантов игры. Например, программа выясняет, что для достижения окончательной цели C она должна обязательно достигнуть подцелей A и B. Тогда, если программа не сможет найти возможности достижения А, она остановится и не будет тратить время на поиск ходов для достижения В.

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

Мы испытывали невероятное искушение написать программу, которая бы самообучалась, анализируя игры других игроков или играя сама с собой. Эта идея может показаться слишком глупой, чтобы сработать, но пара замечательных программ уже научили сами себя играть в разные игры. Программа TD-Gammon — лучший в мире игрок в триктрак, написанная физиком Джеральдом Тезауро (Gerald Tesauro) из исследовательского центра IBM, вначале делала ходы наугад. Сыграв с собой миллионы партий, она стала почти непобедимой. Нейронная сеть, в которой закодированы знания TD-Gammon, требует для оценки позиции гораздо большего времени, чем принято по шахматным стандартам, — за пятнадцать секунд программа может провести поиск только на три хода вперед. Но позиционные знания, закодированные в ней, так богаты, что ее выбор почти всегда верен.

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

Программировать го трудно, вне зависимости от применяемого подхода. К счастью, это трудности хорошего сорта — они заставляют программистов быть изобретательными и развивать основы искусственного интеллекта.

Каждый год на соревнованиях го-программ в виде премий выдается несколько десятков тысяч долларов, но этого явно недостаточно для поддержки даже одного программиста. Самый щедрый спонсор компьютерного го — тайваньский Ing Foundation — предлагает целых 1,6 миллиона долларов за программу, которая сможет победить сильного игрока-любителя, однако еще очень долго этот приз будет в полной безопасности².

Так уж сложилось, что в компьютерном го доминируют преданные этой игре любители. Handtalk был написан не группой ученых и инженеров, финансируемых корпорацией, и не группой исследователей из государственного университета, а отставным профессором химии из китайской провинции Гуаньчжоу, и реализован на древнем PC на ассемблере (!!!), поскольку у профессора не было Cи-компилятора. Узкое место го-компьютеров не в мощи их процессоров, а в идеях.

Тем не менее, полностью разделяя надежды ИИ-оптимистов, я предсказываю, что через тридцать лет компьютер выиграет в го у игрока класса Ким. Будет ли сущность интеллекта понята и выражена в абстрактных символах, станет ли грубый перебор широко использоваться где-либо за пределами игр, смогут ли самообучающиеся машины когда-нибудь решать проблемы из реальной жизни — все это открытые вопросы. Но каковы бы ни были ответы, изучение проблемы го уже является неотъемлемой частью процесса познания нашего мира.

P.S. С момента написания этой статьи прошло пять лет, но на веб-странице Дэвида до сих пор нет упоминаний об успехах его программы. — В.Н.

2(назад) Статья написана в 1998 году. Предложение Ing Foundation остается в силе до сих пор и, судя по всему, сделано бессрочным.