Архивы: по дате | по разделам | по авторам

Игра, похожая на жизнь

Архив
автор : Александр Битман   18.03.2003

Шахматы и го — интеллектуальные игры с достаточно сбалансированными элементами стратегии и тактики, чем и объясняется их привлекательность и живучесть (шахматам около пятисот лет, го — примерно четыре тысячи лет).

Александр Битман — соавтор знаменитой шахматной программы «Каисса», мастер спорта по шахматам с 1969 г., любитель игры го с 1979 г.

Шахматы и го — интеллектуальные игры с достаточно сбалансированными элементами стратегии и тактики, чем и объясняется их привлекательность и живучесть (шахматам около пятисот лет, го — примерно четыре тысячи лет). В то же время это игры-антагонисты по духу, по ментальности (Запад — Восток), по «вкусовым ощущениям».

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

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

Мы не знаем исхода оптимальной партии, его знает только Бог. По этой причине величина коми устанавливается исходя из многолетней практики ведущих игроков-профессионалов. Поскольку мы все равно не знаем точного значения коми, то его полагают дробным, а го становится, соответственно, боевой игрой, где нет ничьих. Справедливости ради надо сказать, что и в случае целого коми вероятность ничьей в партиях профессионалов была бы не более 1/30, а в партиях любителей и того меньше. Долгое время значение коми принималось равным 5,5 очка, но в последние годы под влиянием корейских профи и с учетом статистики перешли на коми 6,5 очка.

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

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

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

Почему же существует такой разрыв между уровнем игры шахматных и го-программ?

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

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

Отметим еще несравнимо меньшую, чем в шахматах, зависимость хода игры от разработанных схем в начале и середине партии.

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

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

Среди причин, которые усложняют го-программирование, обычно упоминают еще две: большую размерность и некоторую неоднозначность правил. Просторы доски 19х19 действительно не оставляют шансов для грубого перебора, однако и на доске 9х9, соизмеримой с шахматной, добиться успеха пока не удается. Что же касается существования в го некоторых иррациональных позиций, то это никому еще не мешало играть в го или создавать компьютерные программы, и мнение, что это усложняет задачу, является чистым мифом.

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

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

Коль речь зашла о загадках го, вот еще одна, на сей раз вполне земная. Почему ни один европеец, или более широко, «белый человек», не может достичь уровня игры профессионалов, не обучаясь в течение нескольких лет в Японии или Корее? Если сравнивать с шахматами, то гроссмейстерами, не приезжая в СССР, становились где угодно, вплоть до Кубы и Филиппин.

В минувшем году, кстати, произошло знаменательное событие — в России появились первые профессионалы. Александр Динерштейн и Светлана Шикшина после четырехлетней стажировки в Сеуле получили 1-й профессиональный дан. В этом же году на Европейском го-конгрессе в Загребе Саша в третий раз стал чемпионом Европы, а чуть позже в Сеуле Света сотворила сенсацию, обыграв профессионала 5-го дана. Кстати, и Динерштейн, и Шикшина имеют свои странички в Интернете.

Интерес к феномену го в последнее время постоянно растет. Недавно газета «Нью-Йорк Таймс» поместила статью, в которой, упоминая о победе Deep Blue над Каспаровым, ставит как научную проблему создание го-программы, способной противостоять человеку.

Эммануил Ласкер, бывший чемпион мира по шахматам, столкнувшись с го, назвал ее космической игрой, игрой будущего. Сейчас го все чаще называют игрой XXI века. В Сеуле в 2001 году была проведена 1-я Международная конференция по го, организованная университетским департаментом, который целиком специализируется на изучении го.

Показательно, что многие известные фирмы, среди которых LG, Samsung, Toyota, Fujitsu и другие, являются организаторами и спонсорами международных турниров по го в своих странах и за их пределами. Так, LG ежегодно организует в Москве розыгрыш «LG Cup», на который съезжаются более четырехсот участников из России и стран СНГ. Фирма заключила контракт с профессионалом 9-го дана, который проводит регулярные занятия с ее ведущими сотрудниками. Руководство LG считает это лучшим способом повышения квалификации своих менеджеров и управленцев, что, кстати, является общепринятой практикой в Корее.

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

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

Создание хорошей го-программы — слишком трудоемкая работа для одиночки, к тому же необходим постоянный обмен идеями. На группу разработчиков достаточно одного-двух хороших игроков в го и возможности консультаций с профессионалами. Успех будет зависеть в основном от творческого потенциала программистов.

Правила го

Для игры используется доска с нанесенной на нее сеткой 19х19 линий (новички могут использовать доски меньших размеров — 13х13 или 9х9).

Имеются два комплекта камней, один — черного цвета, другой — белого.
- Игра начинается с пустой доски, ходят по очереди, начинают черные.
- Ход состоит в постановке камня в перекрестие линий (будем называть его дальше «полем»).
- Свободное поле, соседнее (вдоль линии) с камнем, будем называть «точкой дыхания» этого камня (в центре доски таких точек у камня — четыре).
Для камней одного цвета, стоящих на соседних полях, точки дыхания становятся общими. Камень, поставленный в единственную точку дыхания камней противника, приводит к немедленному их снятию с доски (см. рис.).
- Запрещается делать ход, ведущий к повторению позиции («правило ко»).
- Когда оба игрока говорят «пас», партия заканчивается и начинается подсчет очков. Активом игрока является число свободных пунктов огороженной им территории плюс количество съеденных (пленных) камней. Разница активов определяет результат. При подсчете белым добавляют 6,5 очка (так называемое коми), что компенсирует право выступки черных.

На рисунке символом D обозначены точки дыхания (степени свободы) двух одиночных и группы из трех камней. Ходом в A белые могут съесть два черных камня. Если черные ходом в B возьмут белый камень, то белые не смогут в ответ съесть черный камень ввиду повторения позиции. Это — одна из иллюстраций к правилу ко (в углу картинка будет выглядеть иначе). Если белым важно произвести ответное взятие, то они сделают отвлекающий ход в другой части доски (нанесут ко-угрозу), и если противник среагирует там, то они смогут взять одиночный камень, после чего черные окажутся перед той же дилеммой. Так возникает ко-борьба.

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

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

Простые правила го напоминают известную компьютерную игру «Жизнь». Фактически они регламентируют только процедуру взятия камней — и все! А дальше на этом пустом месте непостижимым образом возникает надстройка исключительной красоты и убеждающей силы, которая с полным основанием может считаться моделью жизни. Японцы так и говорят: «Го учит жить».
Камни выступают в роли примитивных организмов некоей популяции, которая борется за жизненное пространство в условиях конкуренции. Из правила взятия камней с необходимостью вытекает принцип выживания группы — возможность образования двух «глаз», совсем как в живой природе.

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


Проект «Го-банк»

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

Трудно привести полную статистику по странам, но число активных игроков только в Корее, в которой сейчас наблюдается настоящий бум го, оценивается в 10 млн. человек, а число игровых го-сайтов — более двадцати. Эти цифры позволяют предположить, что основная часть фонда будет создана за счет мелких анонимных поступлений от многочисленных поклонников го.

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

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

Главное, чтобы за это дело взялась солидная федерация. Условия проекта должны быть сформулированы и обнародованы на го-сайтах, а в азиатских странах — в прессе и на ТВ. Возможно, что после оповещения о проекте держатели фонда Инга ($1,6 млн.) станут одними из первых вкладчиков го-банка и сразу существенно продвинут весь процесс и активизируют вкладчиков.
Исключительно простые и естественные правила го порождают игру невообразимой сложности. История ее происхождения теряется во тьме тысячелетий, и с тех пор человеческий разум не смог изобрести что-либо подобное. Можно считать, что го, которое все чаще называют игрой XXI века, приходит на смену шахматам при разработке систем искусственного интеллекта.

Сейчас лучшие го-программы играют не сильнее 10-го кю. Есть шанс, что по мере накопления фонда и улучшения го-программ будет достигнут уровень 5–6 кю, что уже позволило бы организовать коммерческую продажу микрокомпьютеров, а приличную программу для доски 9х9 можно было бы встраивать в телефоны и калькуляторы. Часть прибыли шла бы на пополнение фонда и обслуживание грантов, стимулируя дальнейшие разработки.

Когда размер фонда составит 5–10 млн. долларов, можно будет считать, что цель — привлечь внимание к компьютерному го — достигнута. Желающих сорвать джек-пот будет достаточно, чтобы неуклонно, шаг за шагом совершенствовать го-программы, а уж до какого предела — тут трудно строить догадки.

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

© ООО "Компьютерра-Онлайн", 1997-2024
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.