Остаюсь венцом мироздания

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

Собственно говоря, удивляться тут нечему. Шахматы, хотя их и называют игрой, по сути являются задачей на вычисление. Причем на очень простое вычисление, ограниченное абсолютно четкими правилами. Есть главная задача ? уничтожить короля. Всю игру прекрасно видно, где этот король стоит, видны все остальные фигуры противника и все клетки, на которые они могут пойти. В этой задаче нет неизвестных (кроме ходов противника, но обычно предполагается, что он будет делать самые сильные ходы). Здесь все ясно, и надо только рассчитать выигрышную комбинацию. Понятно, что в такой игре, при удвоении мощности процессоров каждые два года, люди были обречены на проигрыш машинам.

Лично я стабильно проигрывал уже 286-му процессору. Мастера спорта и кандидаты в них держались на пару лет дольше. Большинство проигравших утешалось мыслью, что в их проигрыше виноваты они сами, а не мощность машин. Коллективная гордость за человеческий род была гораздо сильнее личной гордыни, и сказать: «Просто я плохой шахматист» ? было куда легче, чем признать поражение всего человечества.

Но пришел 1997 год, и машина победила чемпиона мира. Большинство газет и журналов, а вслед за ними и общественное мнение, с разочарованием признало, что яйцо победило курицу. И если даже в игре, традиционно считающейся самой сложной, человек проиграл машине, то об остальных играх и говорить было нечего. Всем стало немного грустно. Не то чтобы мы были сильно против поражения Каспарова ? нет, но все произошло как-то слишком быстро. Ведь в прогнозах обычно назывались даты начала следующего века, а тут вдруг бац! ? весна 97-го, и интеллект человека повержен. Тогда зазвучали успокаивающие возгласы эрудитов: мол, в играх с элементом блефа (то есть обмана, то есть психологии), таких как бридж или покер, машина не обыграет человека до тех пор, пока не раскусит его лживую душу. Но, по правде сказать, такие игры ? совсем из другой оперы. Блеф ? это вотчина не столько интеллекта, сколько силы духа. На поле же логики (думал я вместе со всеми до последнего времени) человечество проиграло машине со счетом два с половиной на пять с половиной.

А теперь представьте, дорогие читатели, Американскую конференцию по искусственному интеллекту, проходящую в том же 1997 году в городе Провиденс (Род-Айленд). Здесь, кроме чтения докладов, проводятся соревнования новейших игровых программ, в том числе и с людьми. И вот против программы, играющей в некую абсолютно логическую игру безо всякого блефа и случайных событий и по простоте правил напоминающую шашки, садится играть человек (мастер, но не чемпион игры) ? и в начале матча дает программе фору в 27 фишек. Программа (сильнейшая в мире в этой игре) начинает играть с человеком и через пару часов проигрывает. Чтобы вам легче было понять ситуацию, можете представить, что в начале матча Deep Blue дали двадцать лишних пешек, и при этом он проиграл какому-нибудь Крамнику. Удивленные журналисты после матча расспрашивают участников конференции: «Что за дела? Ведь три месяца назад Deep Blue обыграл сильнейшего в мире шахматиста!» На что ученые, кисло улыбаясь, нехотя признаются: «Шахматы ? это ерунда, а вот в эту игру ЛЮБОЙ ЧЕЛОВЕК может за год научиться играть лучше сильнейшей программы на мощнейшем компьютере». Что же это за игра? Она называется го.

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

Почему же в такую простую, возможно даже ? примитивную логическую игру мощнейшие программы проигрывают даже начинающим, а опытные мастера го громят их с таким позором, что только диву даешься? Может быть, программы пишутся плохими программистами? Вряд ли ? каждый год на различных соревнованиях авторам го-программ выдаются десятки тысяч долларов призовых денег, а тайваньская организация Ing Foundation много лет подряд обещала награду в полтора миллиона за программу, которая смогла бы обыграть чемпиона-человека. Программа должна была быть представлена до 1 января 2000 года, но претендентов на соискание премии так и не нашлось.

Чтобы понять все трудности, встречающиеся на пути создания го-программ, лучше всего рассмотреть их в сравнении с программами шахматными. Шахматная доска состоит из 64 клеток, на которых находится (в начале игры) 32 фигуры. Компьютер просматривает по очереди все свои фигуры и перебирает их возможные ходы. На каждый ход своей фигуры он перебирает все возможные контрходы противника, затем свои контр-контрходы, затем опять ходы противника и т.д. Так строится «дерево комбинаций».

В обычной средней шахматной партии на каждом ходу имеется 25?35 возможных вариантов ходов с каждой стороны, и шахматная программа, просчитывающая ситуацию на 7 ходов вперед (7 ходов с каждой стороны ? это 14 ходов на доске), должна просмотреть 35 в 14-й степени комбинаций. Это больше миллиарда триллионов позиций, а при дальнейшем углублении «дерево комбинаций» растет взрывообразно. Такие вычисления под силу только суперкомпьютерам (тому же Deep Blue), а настольные машины перебирают по 35 в 6-й или 8-й степени позиций, глядя на 3?4 хода вперед.

Миллиарды триллионов возможных ходов ? огромные числа, но, как ни трудно в это поверить, для го ситуация ГОРАЗДО сложнее. «Дерево» го-комбинаций ветвится настолько густо, что даже самые мощные современные компьютеры не могут и близко подойти к глубине перебора простейших шахматных программ.

В самом начале игры на решетке го имеется 361 свободное пересечение. После первого хода их остается 360, затем 359 и так далее. На рис. 1 показана реальная комбинация, сложившаяся после 30 ходов. В ней имеется возможность сделать 331 различный ход, а к середине партии будет свободно примерно 200?250 мест, на каждое из которых игроки смогут ставить свои фишки.

Таким образом, если шахматная программа захочет просчитать шахматную позицию на два хода вперед (с каждой стороны), то она переберет полтора миллиона комбинаций (35х35х35х35 = 1 500 625). Просчет же на два хода всех возможных позиций в го потребует перебора уже полутора миллиардов (200х200х200х200 = 1,6 млрд.) комбинаций. О более глубоких просчетах на обычных процессорах не стоит и мечтать.

Люди, играя в такие игры, конечно, не перебирают в уме миллионы комбинаций, и шахматные программы тоже отошли (хотя и недалеко) от слепого перебора. Применение различных алгоритмов позволяет на ранних стадиях «подрезать» тупиковые ветви на дереве комбинаций и заметно сокращать число перебираемых вариантов. В результате тот же Deep Blue, обладая возможностью перебора двухсот миллионов комбинаций в секунду, в игре против Каспарова так эффективно обрезал свое дерево комбинаций, что просматривал ситуацию на 7?8 ходов вперед (с обеих сторон) за три минуты. К сожалению, даже применяя алгоритм, способный из двухсот возможных в го ходов выбрать 15?16 самых перспективных, Deep Blue будет анализировать свои 7 ходов не три минуты, а семьдесят лет.

На этом статью можно было бы и закончить ? очевидно, что для хорошей игры в го нужны невероятно быстрые компьютеры. Но скорость процессоров увеличивается чрезвычайно быстро, для мира компьютеров даже одно десятилетие ? огромный срок. Почему же тогда Дэвид Мехнер (Mechner), соавтор экспериментальной программы Turbo-Go (сам, кстати, являющийся хорошим игроком), в качестве возможной даты уравнивания в этой игре возможностей человека и машины называет лишь третье десятилетие нового века? То есть ? не ранее 2020 года.

Возможно, по той же причине, по которой игроки в го сравнивают шахматы с бухучетом, а свою игру ? с поэзией.

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

Для шахматных программ давно разработаны простые и вполне эффективные способы оценки позиций. Каждая фигура имеет свой рейтинг: скажем, пешка ? 1, ферзь ? 12. Для фигур, стоящих под боем, учитывается отрицательный поправочный рейтинг, для могущих взять фигуру противника ? положительная добавочная поправка. Кроме этого, учитываются безопасность короля, возможность развития фигур, количество клеток под боем и т.д. Набор таких правил, называемый эвристикой, далеко не безупречен, но с его помощью шахматные программы могут весьма неплохо оценивать ситуацию на доске.

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

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

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

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

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

На рис. 3 показана ситуация, сложившаяся на 63-м ходу реальной партии. Большинство го-программ испытывают большие сложности, пытаясь определить: жива ли группа А? Мертва ли группа В? Обречен ли камень С? В то же время опытный игрок-человек сразу скажет, что группа В жива и может себя защитить, камень С ? обречен, а группа А очень уязвима и скорее всего мертва. Такой игрок не станет защищать А и С и направит свои силы на атаку или защиту других групп ? и, безусловно, обыграет компьютер.

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

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

Р.S. Честно говоря, игры с блефом ? тоже игры. И уж в них нас не победит никакая машина. Искусство врать, разгадывая при этом вранье противника, ? это вам не какой-то перебор и распознавание узоров камней. Во лжи мы можем дать компьютерам такую фору, что их процессоры сгорят от расстройства. Кстати ? вон Дед Мороз летит!