17.03.2003

Проблема го

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

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

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

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

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

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

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

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

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

Почему же компьютеры, которые можно запрограммировать на победу в шахматах, так слабы в го?

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

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

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

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

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

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

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

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

В 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. computerra.ru