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

Проблема го

Архив
автор : Дэвид Мехнер   17.03.2003

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

Дэвид Мехнер [www.cns.nyu.edu/~mechner]

Дэвид Мехнер (David Mechner) — докторант Центра нейронаук Нью-Йоркского университета (New York University’s Center for Neural Science).

Автор перевода и врезок:
Владимир Николаевич
[Vnikolaevich@mail.ru]

Перевод публикуется с любезного согласия
Дэвида Мехнера.

В июле 1997 года на ежегодной конференции Американской ассоциации искусственного интеллекта, проходившей в Провиденсе (Род-Айленд), игроки мирового класса мерялись силами с компьютерными соперниками в шахматах, шашках и прочих играх. В большинстве случаев люди проигрывали машинам или побеждали их с огромным трудом. Все шло своим чередом до момента, когда двадцатисемилетняя Дженис Ким (Janice Kim) из Hью-Мексико бросила вызов компьютеру в древнейшей и наиболее сложной из всех игр — го.


Когда первые кадры с изображением игровой доски появились на огромных мониторах, установленных в зале «Hall of Champions», среди присутствующих послышались смешки; участники конференции и зрители недоуменно качали головами — перед началом игры компьютеру была дана фора в 25 фишек-камней. Дженис Ким выдающийся игрок, единственная женщина-профессионал го на Западе, но даже для нее такая фора казалась чрезмерной. Первый камень, который Дженис поставила на доску, напоминал одинокого парашютиста, заброшенного в центр вражеского гарнизона.

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

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

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

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

К несчастью, фора в 25 камней, упомянутая вначале, дает игре мало шансов показать свою глубину и красоту. После дюжины ходов камни Ким казались беспорядочно разбросанными там и тут. Было похоже, что Handtalk, лучшая тогда в мире го-программа, взяла контроль над всей доской и готовила Ким сокрушительное поражение. Кое-кто из зрителей уже считал, что партия обречена и фора оказалась слишком большой даже для профессионала.
Как комментатор, я разрывался между сочувствием к Ким и искушением согласиться со скептиками, но мое беспокойство было напрасным. Как только зрители стали терять терпение, компьютер сделал плохой ход. А Ким, как она сказала нам после игры, руководствовалась своим главным правилом: «Идти по доске маленькими шажками, шаг за шагом, и выиграть». И она выиграла!
Проигрыш лучшей в мире программы, имевшей фору в 25 камней, означает по принятой в го системе оценки, что эта программа играла на уровне 17-го кю — новичка с опытом в несколько месяцев. Вряд ли возможен больший контраст с игрой Deep Blue, ловко разгромившего в шахматы чемпиона мира Каспарова. Во время того знаменательного матча Каспаров вел себя так, будто его игра была эпохальным сражением в защиту человеческого интеллекта. По этому поводу программисты, занимающиеся го, могут лишь уныло усмехнуться: день, когда го-программа сможет поставить в тупик хотя бы среднего игрока-любителя, еще очень далек.
Почему же компьютеры, которые можно запрограммировать на победу в шахматах, так слабы в го?

Если говорить упрощенно, ответ в том, что «метод Deep Blue» не работает в го. Это слишком сложная и тонкая игра для относительно «слабоумного» компьютерного перебора. Чтобы научиться игре, го-программа должна думать гораздо более «по-человечески», чем шахматные программы. Это требование — большая проблема для программистов, но с другой стороны — отличный вызов для науки об искусственном интеллекте (ИИ).
В начале 1950-х годов таким вызовом были шахматы. Однако по мере развития и улучшения большинства шахматных программ их авторы уклонились от решения принципиальных вопросов, поставленных на заре науки об ИИ. Го возвращает исследователей к этим основам — пониманию обучения, представлению знаний, распознаванию образов и стратегическому планированию. Эта игра заставляет нас искать новые модели мышления (или хотя бы наших представлений о нем).

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

В конце 50-х годов, когда компьютерные программы начали в порядке эксперимента имитировать элементы человеческих рассуждений, создатели ИИ делали очень смелые прогнозы. Многие были уверены, что в течение десятилетия компьютеры станут разумными, как люди, — будут понимать английский язык и открывать новые математические законы. Увы, превратить вычисления в знания оказалось гораздо труднее.
Безусловно, интеллект требует знаний. Но большинство человеческих знаний так глубоко въелись в нас, что вовсе не кажутся знаниями. Например, мы знаем, что вода из перевернутой чашки растечется по столу, но не вызовет наводнения в Техасе или что покраска стены не изменит ее формы. Эти биты нашего здравого смысла встроены в нервную систему и оптимизированы миллионами лет эволюции. Воспроизвести такое знание в компьютерной программе до сих пор невозможно. ИИ-программы разрабатываются так, чтобы иметь дело с «пониманием» только некоторой части реального мира, игнорируя все остальное. Например, программа MYCIN может правильно диагностировать менингит, если у пациента наблюдаются соответствующие симптомы, но если вы опишете MYCIN пятна ржавчины на вашей машине, вероятно, у автомобиля тоже будет диагностирован менингит.
По этим причинам многие исследователи ИИ сфокусировались на «игрушечных вселенных» — очень упрощенных идеализированных мирах, в которых правила, управляющие действительностью, задаются системой аксиом.

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

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

Ing Foundation
Тайваньский мультимиллионер и филантроп Инь Чанг-ки (Ing Chang-ki) родился в Китае в 1913 г. Начав играть в вейчи (китайское название го) с восьми лет, он уже в двенадцать стал чемпионом родного города, однако до профессионалов не дорос. Позднее, уже будучи одним из богатейших тайваньских промышленников, г-н Чанг не забыл игру своего детства и основал в 1983 г. благотворительный фонд своего имени — Ing Chang-ki Wei-chi Education Foundation, главной задачей которого стало развитие го во всем мире.
Кроме выделения фонду солидных финансовых средств, г-н Чанг лично разработал поправки к правилам игры, постаравшись избавиться от некоторых недостатков, присущих региональным вариантам го. Предлагаемые фондом правила — SST Laws of Wei-chi — стали международным стандартом де-факто. С подачи фонда в практику были введены часы для контроля времени и инвентарь, облегчавший подсчет поставленных на доску и убранных с нее камней. В 1984 г. Ing Foundation организовал первый мировой чемпионат среди юниоров (World Youth Go Championship), ставший затем ежегодным. В 1988 г. был проведен World Ing Cup — первое мировое соревнование среди профессионалов, в котором приняли участие 24 сильнейших игрока, а призовой фонд составил полмиллиона долларов. С тех пор этот турнир, самый престижный в го, проводится раз в четыре года.
Фонд финансирует игровые школы в Сингапуре, Шанхае и Сан-Франциско и выделяет гранты для развития го на Западе. С 1987 г. Ing Foundation проводит ежегодный турнир среди компьютерных программ, победители которого получают крупные денежные призы. Самое известное предложение фонда: «The Ing Challenge» — 40 миллионов тайваньских долларов за программу, способную победить чемпиона среди тайваньских любителей.


1 (назад)«Какое величие быть королем, властвующим не по правам престолонаследия и не по случайности плебисцита, а в силу остроты своего ума» (Александр Куприн о чемпионе мира по шахматам). — Здесь и далее прим. пер.

Спустя сорок семь лет после того, как минимакс был предложен в качестве метода создания шахматных программ, 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 миллиона долларов за программу, которая сможет победить сильного игрока-любителя, однако еще очень долго этот приз будет в полной безопасности2.

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

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

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


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

 


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

Первую программу, сыгравшую всю партию от начала до конца, написал Альберт Зобрист (Albert L. Zobrist, США). 17 ноября 1968 года она сыграла против человека — Джорджа Коуэна — и победила с перевесом в семь очков (видимо, неважный был противник).

Первой научной статьей, посвященной компьютерному го, стала работа H. Remus. «Simulation of a learning machine for playng Go». Proceedings of IFIP Congress, Amsterdam, 1963.

Первые игры между двумя программами состоялись в августе-сентябре 1972 года. Соревновались программы Джона Даймонда (John Diamond, University of London) и Джека Лэнга (Jack Lang, University of Cambridge).

Первые коммерческие го-программы появились в 1984 г. Три из них — Acornsoft Go Бронислава Пржебылы (B. Przybyla, UK), Microgo 1 Алана Скарфа (A. Scarff, UK) и Nemesis Брюса Уилкокса (B. Wilcox, USA) — вышли почти одновременно, и установить сейчас чье-либо первенство затруднительно.

Nemesis Уилкокса первой попыталась сыграть с людьми в человеческом го-турнире, и она же стала программной основой для первого портативного го-компьютера — Igo Dojo, аналога карманных машинок, играющих в шахматы, шашки, реверси и т. п.


Го-рейтинг. Как оценивают людей и как оценивать программы

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

Во время игры положение на доске зависит от количества камней и территории, которую они контролируют. Чем больше камней и чем больше территория, тем больше перевес над противником. Очевидно, что перед партией можно заранее позволить слабому игроку поставить на доску несколько камней, чтобы он изначально имел некоторое преимущество. Камни, расставленные по-разному, контролируют разную территорию, поэтому в го строго определены места, куда нужно ставить камни, даваемые в качестве форы. На рисунке показано расположение пяти и семи таких камней (слабейший всегда играет черными).
Важность гандикапа в го трудно переоценить. Только благодаря ему новичок с годовым опытом может соревноваться, например, с человеком, изучающим игру десять лет, и при этом оба могут играть в полную силу. В шахматах такое трудно представить. Кроме того, плавно изменяя величину форы, можно точно оценить силу игроков, проведя между ними достаточное количество партий. Именно на этом основано присвоение го-разрядов.
Упрощенно их суть такова: если Петя может на равных играть с Васей, только получив от него фору в два камня, значит Петя слабее Васи на два разряда. Более того, третий игрок — Коля — может определить свою силу, сыграв с Петей, и, выяснив размер своей форы, узнать свой разряд, протянув цепочку расчетов от Васи через Петю. Все очень просто, хотя, конечно, не идеально. Как во всякой системе с гандикапом, пересчитывая разряд Коли через Петю, мы получаем небольшую ошибку, которая может накапливаться. Кроме того, в силу индивидуальных особенностей игроков возможны случаи, когда сильный постоянно проигрывает слабому из-за, например, психологического превосходства последнего и своих слабых нервов3. Однако эти исключения только подтверждают правило: ранжирование игроков определяется форой, которую они могут давать друг другу.
К сожалению, изначальную «точку отсчета» нельзя рассчитать объективно, поэтому игроки с одинаковыми разрядами из разных стран могут играть на разном уровне. Так, член Американской ассоциации го (AGA) с 9-м кю играет на уровне европейца с 10-м. При этом американцы на один разряд сильнее японцев, а самую суровую систему имеет Корейская ассоциация, дающая 1-й кю игрокам, которые в Европе получили бы 3–4-й дан4.
Простота определения разрядов позволяет любому игроку рассчитать уровень игры го-программы, сыграв с ней несколько партий. Однако многие из тех, кто пытается это сделать, сталкиваются с так называемым феноменом первой игры. Суть его в том, что первые игры у программы «получаются» лучше, чем последующие. На самом деле, конечно, машина играет всегда одинаково, но оценка ее игры человеком изменяется. Начав первую партию с любой из современных программ, игрок обычно видит, что ее ходы сильны и точны, и готов дать ей весьма высокий разряд. Однако если он продолжит играть с программой, то легко заметит ее слабые места. Чаще всего это шаблонность действий, неспособность к неожиданным решения, а иногда даже непонимание собственных ходов, из-за чего она допускает грубые промахи. Узнав таким образом болевые точки противника, через десяток партий человек способен давать программе фору в разы (!) большую, чем при первой игре, и все равно побеждать ее.
Что-то похожее, хотя не столь явное, есть и у шахматных программ. Их ходы достаточно специфичны, и некоторые гроссмейстеры утверждают, что способны «на глаз» отличить компьютерную игру от человеческой. На многих шахматных сайтах есть советы, как вынудить компьютер согласиться на ничью, или даже обстоятельные уроки на тему «Как побеждать машину». Другими словами, быстро обучающийся человек способен распознавать слабости ИИ и использовать их в своих целях.
Пожалуй, наиболее выпукло эта проблема проявляется в тестах Тьюринга, когда программы имитируют осмысленный диалог с человеком. Если на диалог с машиной пригласить «человека с улицы», то, потратив массу времени, он может так и не понять, с кем разговаривал. Но человеку, уже имеющему опыт подобного тестирования, для разоблачения машины может хватить всего трех-четырех вопросов.
Возникает вопрос: если го-программа в первой партии побеждает человека с форой в два камня, а в десятой партии проигрывает ему же с форой пятнадцать камней, как рассчитать ее разряд? По первой игре или по десятой? Ответ совсем не очевиден. Доводы за то, что «первое впечатление — самое верное», достаточно весомы. Проводя параллель с шахматами, можно сказать, что именно так был организован последний матч Каспарова с DeepBlue, когда чемпиона посадили против машины, о которой он не знал ничего, и вынудили играть, изучая ее слабости на ходу. «Противоположным» образом были проведены недавние матчи того же Каспарова с программой Deep Junior и Владимира Крамника с Deep Fritz. В обоих случаях люди поставили условие: заранее предоставить им точную копию будущего соперника. Условие было выполнено, и оба гроссмейстера смогли несколько месяцев в домашней обстановке «допрашивать» своих будущих противников.
Конечно, не слишком справедливо позволять человеку адаптироваться к программе, зная, что сама программа на ответные меры не способна. Но правильно ли оценивать ее только по сильным сторонам, не учитывая слабых? Вероятно, это дело вкуса. В 1997 году Японская ассоциация го официально присвоила третий кю программе Handtalk, подтвердив это специальным дипломом. Очевидно — это оценка именно по результатам первых партий, поскольку Корейская ассоциация оценивает тот же Handtalk максимум на 17-й кю. Рядовые игроки склоняются все-таки на сторону корейцев (ко второму способу оценки) и в своих собственных рейтингах дают лучшим го-программам кю из середины второй десятки.



Чемпион нашего времени
Как видно из таблицы, человеческая мысль не стоит на месте, и между го-программами идет постоянная конкуренция. В настоящий момент по результатам турниров и мнению пользователей сильнейшим игроком является Go4++, также известная как Go Professional. Эта программа в одиночку написана англичанином Майклом Рейсом5. Успех сольного проекта не должен удивлять — в сфере ИИ для игр так бывает сплошь и рядом, и шахматный Deep Fritz тоже был частным делом своего создателя, пока однажды не стал чемпионом. Удивить может лишь то, что автор Go4++ занимается программой уже почти двадцать лет.
По словам Майкла, однажды в 1983 году он заметил в витрине магазина какой-то журнал с рекламой конкурса для программистов, где сообщалось о призе в одну тысячу фунтов. Заинтересовавшись, он зашел в магазин, полистал журнал и увидел, что для победы надо написать программу, лучше всех играющую в го. Об этой игре Майкл ничего не знал, поэтому, найдя в Лондоне клуб ее игроков, обратился к ним с просьбой в стиле «Научите меня этой штуке — я хочу написать программу, которая смогла бы в нее играть». Неизвестно, что подумали о нем члены клуба, но с британской невозмутимостью они обучили Майкла основным правилам, и уже в январе 1984-го его программа вместе с дюжиной других лежала в редакции журнала. Она прошла предварительный отбор, оставивший восемь кандидатов для турнира по нокаут-системе, после чего была выбита из конкурса в первой же игре.
Для парня это был сильный удар — он был уверен в победе. Решив выяснить свой разряд, Майкл обнаружил, что он равен 25-му кю, из чего следовало, что разряд программы не превышает 35 кю. Очевидно, что ее поражение было неизбежным.
С тех пор прошло много лет. Рейс дорос до 1-го кю (по европейской шкале), но попыток написать хорошую программу не прекращал. Майкл утверждает, что ему не помогал никто из программистов, зато он много консультировался у лучших игроков. Титул «Сильнейшей го-программы в мире», впервые завоеванный в 1999 г., — достойная награда энтузиасту за долгие годы упорнейшей работы. Сейчас его беспримерный двадцатилетний труд представляет собой почти три мегабайта исходного кода — больше 110 тысяч строк на языке Си. Программа использует базу данных из семи тысяч реально сыгранных партий и трехсот тысяч партий, сгенерированных машиной. Оценка позиций частично проводится методами нейронных сетей6.
Популярность Go4++ среди пользователей (особенно японских) такова, что с 1995 г. Майкл живет на royalty — отчисления с продаж программы, уделяя своему детищу все свободное время. На вопрос «Кто вы по профессии?» он честно отвечает: «Го-программист». По рейтингу Igs.nuri.net — самого популярного гошного веб-сервера, Go4++ играет на уровне 16–14 кю.
Что же можно сказать о программе, которая получает от своего создателя фору в 14 камней и все равно ему проигрывает? Я бы сказал: «слабовато…» Между тем это чемпион мира, и хотя ему в затылок дышат полдесятка сильных конкурентов, опытный гошник смотрит на их соревнования, как Гулливер на прыжки в высоту среди лилипутов.
Го-программы пишутся уже давно, и, если окинуть взглядом их историю, выясняются две примечательные вещи. Во-первых: мастерство программ растет плавно, без заметных рывков. Во-вторых: скорость роста составляет примерно один разряд в год! Легко посчитать, что с такими темпами нынешнее поколение программистов может выйти на пенсию, а приз от Ing Foundation так и не получить. Между тем этот приз обещан за победу над 6-м даном среди любителей, а в го еще есть лига профессионалов — что-то вроде собрания академиков.
В отличие от шахматистов, давно имеющих мощные программы для количественной оценки и автоматического просчета игровых комбинаций (что, кстати, привело к исчезновению отложенных партий), у гошников ничего подобного нет. Они играют так же, как играли сто лет назад, полагаясь исключительно на интуицию и опыт.
Об основной причине такого «цифрового барьера» специалисты говорят кратко и туманно: дескать, «в отличие от многих логических игр го основана на неполной аксиоматике». В переводе на человеческий язык это значит, что многообразие возможных ситуаций в го настолько велико, что охватить их все законченной системой правил (не искажая сущности игры) чрезвычайно трудно. Поэтому часть ситуаций в игре так и называются — иррациональные ситуации. Подробно разбирать этот предмет в компьютерном журнале нет места, но беглый взгляд бросить надо.
Как было сказано, помимо захвата территорий, в го можно захватывать группы камней противника. Камни снимаются с доски, будучи полностью окружены противником (или прижаты к краю доски), но только если внутри кольца окружения (или окруженной группы) нет пустот. Если пустоты есть и они образовали «глаза» — группа неуязвима. Если же «глаза» еще не выстроены, то противник может снять окруженную группу, заполнив в ней все пустоты. Образно выражаясь — выдавить воздух из мешка. Это понятно и логично, однако во время партии узоры камней сплетаются в таком замысловатом танце, что становится непонятно, кто у кого в мешке.
Для иллюстрации рассмотрим следующий пример. На рисунке показана комбинация, где в правом верхнем углу черные окружили три камня белых, но сами попали в окружение белыми, а те еще раз были окружены черными. В этой ситуации очень трудно определить, является ли поле «О» (координаты G9) территорией черных или нейтральной? Между тем это важно знать, поскольку по завершении партии победитель определяется именно подсчетом территории и камней, и разница в одно поле (очко) может быть решающей.
Конечно, люди находят выход даже из более сложных ситуаций. По ходу игры спорные вопросы могут разрешаться сами собой, а если этого не происходит, то (в крайнем случае) для подсчета очков привлекается арбитр. Но что делать компьютерной программе, которая, перебирая вероятные комбинации, натыкается на такую иррациональность? Ведь не определив принадлежность территории, программа не сможет правильно рассчитать свои ходы.
Парадоксальные ситуации, подобные вышеприведенной, и позволяют сравнивать го с поэзией, делая эту игру одним из самых крепких орешков для программистов. Хотя, на первый взгляд, задача кажется куда проще шахматной — все фигуры ведь одинаковые, да еще и не двигаются!
Еще раз подчеркнем: суть проблемы не в количестве возможных комбинаций и не в мощности компьютеров, на которых выполняются программы. Го-программам нужны не мощные процессоры, а мощные алгоритмы, которые позволят им радикально улучшить понимание ситуации на доске и с которыми они, наконец, заиграют хоть немного по-человечески.


На сайте go.hobby.ru выложен цикл статей В. А. Асташкина и Г. И. Нилова «Школа го», печатавшихся в журнале «Наука и жизнь» с №8 за 1975 год по №7 за 1976 год. До сих пор это один из лучших источников о правилах и тонкостях игры на русском языке.
Сайты, посвященные го
www.goama.narod.ru (здесь продаются книги, го-инвентарь)
- igs.nuri.net
www.britgo.org (ссылки на множество го-программ для самых разных платформ, от Palm до Amiga)
www.smart-games.com/david.html (здесь можно скачать программу для доски 9х9)
Российские энтузиасты
го-программирования
- Юрий Беляев (Ижевск),
belgo@udmnet.ru
- Алексей Мисюрев (Москва),
aleksei@cognitive.ru
- Владимир Медведев (Москва), vrm@bk.ru


3 (назад)Несмотря на крайне аскетичный вид доски с камнями, представление о подлинной глубине переживаний, испытываемых игроками во время партии, может дать литература, посвященная го. Так, на go.hobby.ru помещен перевод романа «Мэйдзин» Ясунари Кавабаты, японского писателя, лауреата Нобелевской премии, о переломном для истории го моменте — многомесячной партии Мэйдзина Сюсаи, великого игрока старой школы, с Китани Минору, ставшим одним из основоположников современного го.
4 (назад) По словам Евгения Панюкова, вице-президента РФГ по детскому го, российские разряды примерно равны европейским.
5 (назад) Michael Reiss (www.reiss.demon.co.uk/misc/mick.htm).
6 (назад) Рейс — соавтор известного симулятора нейронных сетей Cortex-Pro.

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