Форма реальности. Скрытая геометрия стратегии, информации, общества, биологии и всего остального

ПЬЯНОЕ-ПЬЯНОЕ ГО

Все вышеизложенное возвращает нас к компьютерному го. Игра го намного старше шашек и шахмат и (просто для разнообразия!) действительно древняя и китайская. С другой стороны, машины, играющие в го, появились позже автоматов для других игр. Еще в 1912 году испанский математик Леонардо Торрес-и-Кеведо построил машину «Шахматист» (El Ajedrecista), которая умела разыгрывать некоторые шахматные эндшпили, а Алан Тьюринг изложил план функционального шахматного компьютера в 1950-х годах. Сама идея автомата, играющего в шахматы, еще старше: она восходит к «Шахматному турку» Вольфганга фон Кемпелена, чрезвычайно популярному автомату в XVIII и XIX веках, который вдохновлял Чарльза Бэббиджа, озадачивал Эдгара По[275] и ставил мат Наполеону, однако на самом деле управлялся человеком небольшого роста, скрытым внутри механизма[276].

Первая компьютерная программа, играющая в го, появилась только в конце 1960-х: ее написал Альберт Зобрист в рамках свой диссертации по информатике в Висконсинском университете. В 1994 году, когда «Чинук» на равных сражался с Марионом Тинсли, машины были бессильны против профессиональных игроков в го. Но, как выяснил Ли Седоль, все быстро изменилось.

Что делает высококлассная машина для игры в го (например, AlphaGo) без притаившегося внутри маленького человека, двигающего детальки? Она не маркирует каждый узел дерева го буквой В или П (буква Н не нужна, потому что в стандартном варианте го нет ничьих). Дерево го очень высокое и густое, никто не может справиться с этой чертовой штукой. Однако, как и в тесте Ферма, мы можем ограничиться приближением – функцией, которая присваивает каждой позиции на доске определенное число с помощью какого-то легкого вычисления. Это число должно быть большим, если позиция хороша для игрока, собирающегося делать ход, и маленьким, если ситуация на доске благоприятна для его противника. Наличие такой оценки предлагает стратегию: среди всех доступных ходов вы выбираете тот, который оставляет противнику позицию с наименьшим числом, так вы ставите противника в наихудшее из потенциально возможных положений. Полезно представить себя внутри подобного алгоритма. Вы занимаетесь повседневными делами и каждый раз, принимая какое-то решение (например, я хочу шоколадный круассан, миндальный круассан или бейгл?), быстро перебираете все имеющиеся варианты. Для каждого почти мгновенно высвечиваются какие-то числовые значения и складываются в общую оценку каждого вида выпечки: вкус плюс насыщение минус цена минус количество углеводов и т. д. Это звучит одновременно и грандиозно, и фантастически устрашающе.

В основе всего, что мы делаем в области искусственного интеллекта, лежит компромисс. Чем точнее оценочная функция, тем больше времени обычно требуется для ее вычисления; чем она проще, тем менее точно отражает тот параметр, для которого предназначена. Разумнее всего было бы присвоить 1 каждой выигрышной позиции и 0 каждой проигрышной; это обеспечило бы абсолютно идеальную игру, но у нас нет реальных способов вычислить такую функцию. С другой стороны, мы могли бы присвоить каждой позиции одно и то же число («Да я не знаю, вся выпечка кажется отличной»). Это число было бы очень просто вычислять, но мы не получили бы вообще никаких полезных подсказок о том, как нам играть дальше.

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

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

Важная математическая тактика: когда вы понятия не имеете, что попробовать, пробуйте то, что кажется очень глупым. Вот что вы делаете. В данной позиции вы представляете, что Акбар и Джефф начинают сильно пить – так сильно, что теряют всякое понимание стратегии и желание выиграть, хотя в каком-то темном уголке сознания помнят правила игры. Другими словами, они ведут себя подобно пьянице на открытой местности, которого воображал Карл Пирсон. Каждый игрок по очереди наугад выбирает разрешенный ход, пока игра не закончится и оба не рухнут под стол, полностью обессиленные. Игроки совершают случайное блуждание по дереву го.

Пьяное го легко смоделировать на компьютере, поскольку оно не требует тщательных рассуждений – достаточно просто знать правила и беззаботно крутить колесо для случайного выбора одного из доступных ходов. Вы можете смоделировать игру, а после окончания партии смоделировать ее снова: один раз, два, миллион – неизменно начиная с одной и той же позиции. Иногда побеждает Акбар, иногда Джефф. И тогда оценка, которую вы присваиваете позиции (мера того, насколько она выгодна для Акбара), – это доля смоделированных партий, выигранных Акбаром.

Какой бы грубой ни была эта мера, она не совсем бесполезна. Рассмотрим такую метафору. Допустим, мертвецки пьяный Акбар стоит в длинном коридоре, у которого два выхода – спереди и сзади. Он бесцельно бродит взад-вперед, пока не натыкается на один из выходов. Разумно предположить, что чем ближе Акбар стоит к передней двери, тем выше вероятность, что он наткнется именно на нее, даже если не пытается добраться до нее или куда-то еще. И мы можем использовать это рассуждение в обратном порядке: если Акбар выходит через парадную дверь, это подтверждает (хотя, естественно, не доказывает), что его исходная точка была к ней ближе.

Подобные рассуждения были частью теории случайных блужданий задолго до того, как Пирсон дал им название. Можно считать, что такая схема восходит к Книге Бытия, где Ной, которому надоело сидеть законопаченным в ковчеге с несколькими сотнями пар животных, отправляет ворона, который «отлетал и прилетал» в поисках земли, оставленной отступающей водой. Ворон ничего не нашел. Тогда Ной отправил голубя, и тот тоже вернулся, не найдя суши. Но когда голубь в следующий раз отправился в случайный полет и вернулся с масличным листом в клюве, Ной понял, что земля где-то рядом[277].

Случайные блуждания появлялись при изучении игр в течение многих веков, особенно в азартных играх, где блуждание по дереву всегда случайно, по крайней мере частично. Пьер де Ферма в перерывах между написанием писем о простых числах обсуждал с математиком и мистиком Блезом Паскалем задачу о разорении игрока. В этой игре Акбар и Джефф играют в кости, причем у обоих по 12 монет. Они по очереди бросают по три кости. Каждый раз, когда Акбар выбрасывает 11 очков, он получает одну из монет Джеффа. Каждый раз, когда Джефф выбрасывает 14 очков, он забирает одну из монет Акбара. Игра заканчивается, когда один из игроков лишается всех монет и «разоряется». Каковы шансы, что Акбар выиграет?[278]

Это просто вопрос о случайном блуждании, которое начинается в тот момент, когда у игроков поровну монет, и заканчивается, когда у одного из них денег не остается. При бросании трех костей вероятность выпадения 11 очков примерно вдвое выше, чем 14 очков, – просто потому, что существует всего 15 исходов, когда сумма чисел на трех костях равна 14, и целых 27 исходов, когда сумма чисел на трех костях равна 11. Поэтому разумно предположить, что Джефф находится в невыгодном положении. Но насколько невыгодном? Этот вопрос Паскаль задал Ферма. Оказалось[279] (как сразу же ответил Паскалю Ферма, а Паскаль раздраженно дал понять, что уже сообразил), что шансы Джеффа на разорение больше в тысячу с лишним раз! Небольшой сдвиг в случайном блуждании превращается в задаче о разорении игрока в колоссальное неравенство. Джеффу может повезти, и он пару раз выбросит 14 до того, как Акбар выбросит 11, однако его преимущество вряд ли будет длительным, не говоря уже о разорении соперника.

Самый простой способ посмотреть, как это работает на практике, – заменить задачу более простой (детским примером, как ее любят называть математики). Предположим, Акбар и Джефф играют в игру, где шансы Акбара на победу в одной партии равны 60 %, и побеждает игрок, который первым выиграет две партии. Вероятность того, что это сделает Акбар (и тем самым выиграет в целом), составляет 0,6 × 0,6 = 0,36, или 36 %. А вероятность, что Джефф выиграет первые две партии подряд (и тем самым игру в целом), равна всего 0,4 × 0,4 = 0,16, или 16 %. В оставшихся 48 % случаев игроки выиграют по одной партии и игра продолжится. Акбар выиграет следующую партию в 60 % от этих 48 % случаев, то есть в 28,8 % игр (0,6 × 0,48 = 0,288). В оставшихся 40 % от этих 48 % случаев, то есть в 19,2 % игр (0,4 × 0,48 = 0,192), победит Джефф. Следовательно, общие шансы Акбара на победу (со счетом 2:0 или 2:1) составляют 36 % + 28,8 % = 64,8 %. Это несколько выше, чем его шансы выиграть каждую отдельную партию. Если игра ведется до трех побед в отдельных партиях, то вы можете убедиться, что шансы Акбара на общую победу возрастают примерно до 68,3 %. Чем длительнее игра, тем выше шансы, что победит более умелый игрок[280].

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

Вместо этого теннисный сет продолжатся до тех пор, пока один из игроков не выиграет шесть геймов с опережением как минимум на два гейма. Это трудно описать словами, поэтому давайте посмотрим на рисунок.

Вы можете представлять теннис как случайное блуждание по этой сетке; каждый раз после сыгранного гейма вы перемещаетесь вправо или вверх и останавливаетесь, когда ударяетесь об одну из границ, то есть «разоряете» одного из игроков (конец сета). Если игрок А чуть-чуть лучше, чем игрок В (то есть вероятность шага вверх больше, чем вправо), то шанс закончить матч на верхней границе выше, чем на нижней[281]. Поскольку длинный диагональный коридор на диаграмме бесконечен, для продолжительности сета не установлено никаких ограничений. Если игроки не будут одинаково сильны, то крайне маловероятно, чтобы блуждание зайдет очень далеко по коридору, не ударившись о его стенки. Тем не менее такое бывало. Например, матч Джона Изнера и Николя Маю 23 июня 2010 года на Уимблдоне[282]. Два игрока то выходили вперед, то сравнивали счет – гейм за геймом. Шли часы. Солнце стало садиться. Табло на корте выключилось при счете 47:47, поскольку это был максимум, на который оно запрограммировано. Примерно в 21:00 при счете 59:59 темнота помешала играть дальше. На следующий день Изнер и Маю ее возобновили, продолжая брать геймы на своей подаче. Наконец, очередной удар Изнера[283] принес ему выигрыш 138-го гейма и общую победу 70:68 в пятом сете (и в матче). Изнер сказал: «Ничего подобного больше не повторится. Никогда»[284].