Охота на электроовец. Большая книга искусственного интеллекта
Шрифт:
Третье и последнее выступление «Каиссы» на чемпионате мира состоялось в 1980 г., где она поделила 6–11-е места. Примечательно, что первое место в чемпионате досталось не Chess 4.9, которая была, наряду с «Каиссой», одной из двух главных претенденток на победу, а программе Кена Томпсона — Belle. Из 18 участников III чемпионата восемь были из США, трое из Великобритании и трое из Канады. Социалистический лагерь был представлен одной лишь «Каиссой» [725] , [726] .
725
3rd World Computer Chess Championship / ICGA Tournaments: Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more // https://www.game-ai-forum.org/icga-tournaments/tournament.php?id=68
726
Resena historica del ajedrez por computadora (VI) // http://www.anacadigital.com/historia/anaca5_1_89.htm
В 1990 г. команда из девяти программистов, возглавляемая Донским, выпустила новую версию «Каиссы», написанную на языке Си для операционной системы MS-DOS. Обновлённая программа участвовала во Второй компьютерной олимпиаде, разделив 4–6-е места (из 11 участников) [727] , [728] .
Сегодня сложно дать однозначный ответ на вопрос о том, почему «Каисса» не смогла сохранить лидерство. Сами авторы считали, что дело было в отставании аппаратной базы: машина, которую использовала «Каисса», была медленнее, чем у конкурентов [729] . Кроме того, команда «Каиссы» щедро делилась алгоритмическими находками с сообществом шахматных программистов — принципы работы
727
Horvath Z. (1990). Report on the 2nd Computer Olympiad. ICCA Journal, Vol. 13, No. 3.
728
2nd Computer Olympiad, Chess / ICGA Tournaments: Tournaments between computer programs: chess, draughts, checkers, Go, backgammon, and more // https://www.game-ai-forum.org/icga-tournaments/tournament.php?id=142
729
Костинский А. (2002). Компьютерные программы как конец спортивных шахмат / Радио Свобода // https://www.svoboda.org/a/24203756.html
730
Арлазаров В. Л., Битман А. Р. (1968). Обыграет ли машина человека? / Шахматы в СССР. № 2. С. 9—11.
731
Адельсон-Вельский Г. М., Арлазаров В. Л., Битман А. Р., Животовский А. А., Усков А. В. (1969). О программировании шахматной игры / Труды первой зимней школы по математическому программированию. Вып. II. С. 216—252.
732
Адельсон-Вельский Г. М., Арлазаров В. Л., Битман А. Р., Животовский А. А., Усков А. В. (1970). О программировании игры вычислительной машины в шахматы / Успехи математических наук. Т. 25, вып. 2 (152). С. 221—260 // http://www.mathnet.ru/links/e353ff456f77590009af6ba9f008f4cb/rm5324.pdf
733
Adelson-Velsky G., Arlazarov V., Donskoy M. (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Ingelligence, Vol. 6, No. 4, pp. 361–371.
734
Adelson-Velsky G., Arlazarov V., Donskoy M. (1977). On the Structure of an Important Class of Exhaustive Problems and Methods of Search Reduction for them. Advances in Computer Chess 1
735
Адельсон-Вельский Г. М., Арлазаров В. Л., Битман А. Р., Донской М. В. (1983). Машина играет в шахматы. — М.: Наука // http://www.computer-museum.ru/books/kaissa.pdf
Рискну предположить, что результат первых чемпионатов был во многом случайным. Каждая из программ-участниц сыграла в каждом из турниров всего по четыре партии. При приблизительно равной силе игры лучших программ распределение мест между ними могло быть практически каким угодно. К сожалению, организовать эксперимент из многих тысяч или хотя бы сотен игр для установления исторической истины сегодня вряд ли представляется возможным. Одно можно сказать с уверенностью: алгоритмы, изобретённые авторами «Каиссы», были действительно революционными для своего времени и её создатели внесли огромный вклад в развитие компьютерных шахмат.
4.5.6 Рассуждения о теоретической основе шахматного программирования и идеи Ботвинника
С 1970-х гг. создатели шахматных программ постепенно отходят от парадигмы, предложенной Шенноном. Можно ли сказать, что «Каисса» была программой шенноновского типа A, как её предшественница из ИТЭФ, или же она относилась к типу B? Ответ на этот вопрос не так прост.
С одной стороны, благодаря эвристике пустого хода или «модели активной игры», при использовании которой в некоторых узлах дерева перебора анализировались только «активные» ходы, программа исключала часть ветвей дерева из рассмотрения. В принципе, исключение ветвей происходит и при альфа-бета-отсечении, но оно, в отличие от упомянутых ранее эвристик, является «безопасным», то есть не может изменить оценку программой позиции по сравнению с полным перебором вариантов. Казалось бы, в силу селективности перебора «Каиссы» её следовало бы отнести к типу B, однако использование метода «итеративного углубления» приводит к тому, что ходы, отброшенные при анализе позиции на n– й итерации, могут быть изучены на (n+1)-й. В зависимости от особенностей реализации эвристика пустого хода может исключить некоторые ходы из перебора «безвозвратно», но это происходит не всегда. Словом, программы второго поколения, такие как «Каисса», активно использовали подход, при котором более перспективные варианты рассматривались более глубоко. Целый сонм правил управлял в таких программах принятием решений о сокращении или же, наоборот, продлении перебора для тех или иных ходов. Например, шахи, ходы пешек на предпоследнюю горизонталь, размены, взятия, приводившие к переходу в пешечный эндшпиль, иногда даже просто взятия могли увеличивать глубину перебора на один полуход или даже на нецелое количество полуходов, скажем на 1/2 полухода (к примеру, два взятия приводят к продлению перебора на один полуход). С другой стороны, для бесперспективных ходов глубина рассмотрения уменьшалась — под «сокращение» могли попадать «тихие» ходы в позициях с нехваткой материала (обычно трудно отыграть материал, совершая пассивные ходы — не совершая взятий, шахов или ходов проходных пешек), просто предположительно слабые ходы (например, помещённые в конец списка ходов эвристиками, отвечающими за упорядочивание ходов на основе статистических данных о том, как часто те или иные ходы становились лучшими в процессе перебора) и так далее. Второе поколение шахматных программ стало золотым веком изобретателей эвристических правил. Их создание часто ограничивалось только полётом фантазии: творческое озарение, поспешная реализация, несколько десятков (в лучшем случае) тестовых партий — и вот уже программа оснащена новым, доселе невиданным знанием. Этот подход не был уникальной чертой шахматного программирования — он был распространён в самых разных областях ИИ вплоть до конца 1980-х или даже до 1990-х. Сегодня мы часто называем этот период временем GOFAI — Good Old-Fashioned Artificial Intelligence (Старого доброго искусственного интеллекта). Этот термин был предложен профессором Джоном Хогландом в книге «Символьные вычисления. Искусственный интеллект: сама идея» (Symbolic Computation. Artificial Intelligence: The Very Idea, 1985) для обозначения символьного подхода в ИИ, доминировавшего в эти годы [736] . Сторонники этого подхода стремились изложить человеческие знания в виде наборов правил и алгоритмов.
736
Haugeland J. (1985). Symbolic Computation. Artificial Intelligence: The Very Idea. MIT Press // https://books.google.ru/books?id=UuQbnAEACAAJ
На заре шахматного программирования бытовало забавное заблуждение о том, что программист не может создать программу, которая будет играть в шахматы сильнее своего создателя. Тьюринг сравнивал это с утверждением, что ни одно животное не может проглотить животное тяжелее себя [737] . Возражения Тьюринга, в его время разумеется, могли носить только теоретический характер — на протяжении многих десятилетий машины играли в шахматы на любительском уровне, выполняя для шахматных экспертов роль безропотных учеников, в точности следующих рекомендациям учителей. Проблема, как и в случае процесса обучения людей, заключается в том, что рассказ эксперта о своём методе вовсе не равен самому методу. Обычно человек способен отличить на картинке хрен от пальца, но стоит вам попросить его объяснить, как именно он это делает, а потом начать следовать описанному способу, как вы немедленно запутаетесь и в хрене, и в пальцах.
737
Turing A. (1953). Digital computers applied to games. n.d. Turing's contribution to “Faster than thought”, ed. B. V. Bowden, London 1953. Published by Pitman Publishing. TS with MS corrections. R.S. 1953b / The Turing digital archive // http://www.turingarchive.org/viewer/?id=461&title=1
Однако вплоть до 1990-х гг. преимущество «человеческого» способа игры в шахматы было очевидным, а возможность изобретения принципиально иного подхода — нет. Именно поэтому, создавая шахматные программы, их авторы в той или иной мере пытались подражать в них
738
Carrera P., Cherubino G., Tortelli M., Rossi G. d., Romano G. (1617). Il gioco de gli scacchi di D. Pietro Carrera diuiso in otto libri, ne' quali s'insegnano i precetti, le vscite, e i tratti posticci del gioco, e si discorre della vera origine di esso. Con due discorsi, l'vno del padre D. Gio. Battista Cherubino, l'altro del dottor Mario Tortelli, opera non meno vtile a' professori del gioco, che diletteuole a' gli studiosi per la varieta' della eruditione cauata dalle tenebre dell'antichita'. per Giouanni de' Rossi da Trento // https://books.google.ru/books?id=RPvGROWRIikC
739
Lolli G. (1763). Osservazioni teorico-pratiche sopra il giuoco degli scacchi ossia il Giuoco degli Scacchi: esposto nel sus miglian lume. Stamp. di S. Tommaso d'Aquino // https://books.google.ru/books?id=zych5drFRuQC
Интерес к компьютерным шахматам развился у Михаила Моисеевича довольно рано. В 1958 г. по приглашению гроссмейстера Макса Эйве, пятого чемпиона мира по шахматам, Ботвинник посетил Нидерланды, где стал гостем телепередачи, посвящённой компьютерам и перспективам их применения. На вопрос Эйве «Будет ли машина играть в шахматы сильнее человека?» Ботвинник не задумываясь ответил: «Да!» [740] , [741]
740
Ботвинник М. (1979). От шахматиста — к машине. М.: Физкультура и спорт // https://books.google.ru/books?id=W8aptgEACAAJ
741
Phony Benoni. Wageningen Caltex (1958) / Chessgames.com: online chess database and community // http://www.chessgames.com/perl/chesscollection?cid=1026124
Эйве был не только блестящим шахматистом, но и специалистом в области компьютерных технологий. В 1956 г. он занял пост консультанта в нидерландском отделении компании Remington Rand — одного из ведущих разработчиков первых ЭВМ [742] . Тремя годами позже Эйве стал директором Исследовательского центра по автоматической обработке данных, а ещё через два года — главой созданной Евратомом [743] комиссии, изучавшей шахматный потенциал компьютеров [744] .
742
Мюннингхофф А. (1979). Макс Эйве / Пер. с нидерландского В. И. Мурахвери — М.: Физкультура и спорт.
743
* Европейское сообщество по атомной энергии.
744
O'Connor J. J., Robertson E. F. (2003). Machgielis Euwe. School of Mathematics and Statistics University of St Andrews // http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Euwe.html
Вспоминая в книге «От шахматиста к машине» телеинтервью 1958 г., Ботвинник писал: «Известно, что всё начинается от Евы… Но в моей творческой деятельности многое начиналось не от Евы, а от Эйве. Именно он осенью 1934 года выхлопотал приглашение на рождественский турнир в Гастингс — это был мой первый международный турнир. И вот теперь после вопроса Эйве я стал думать, как же обучить компьютер хорошо играть в шахматы?»
В ноябре 1960 г. с подачи директора XIV шахматной олимпиады Герберта Гретца Ботвинник прочитал лекцию в Университете Гумбольдта [745] , которая позже была опубликована в советской прессе под названием «Люди и машины за шахматной доской» [746] . В начале 1960-х активно обсуждался вопрос о том, можно ли создать машину, способную играть в шахматы на гроссмейстерском уровне. Первые программы играли на уровне слабых любителей, и было неясно, что именно нужно сделать для того, чтобы преодолеть этот разрыв. Было ясно, что задачу нельзя решить при помощи полного перебора (пусть даже и с альфа-бета-отсечениями) — количество рассматриваемых вариантов нужно было сокращать самым радикальным образом. При этом было понятно, что подобное агрессивное сокращение дерева перебора возможно лишь ценой заведомо «некорректных», потенциально опасных отсечений. Именно такого рода ошибки допускают люди-шахматисты, упуская в своём анализе тот или иной важный вариант. Гроссмейстер, рассчитывающий комбинацию из двадцати полуходов, анализирует разве что несколько десятков позиций. Но это значит, что его анализ включает лишь порядка одной из 1028 возможных альтернатив. Лучшие шахматные программы начала 2010-х гг., несмотря на все достижения в области селективного перебора, рассматривали примерно в миллион раз больше позиций для достижения того же результата.
745
Ботвинник М. (1979). От шахматиста — к машине. М.: Физкультура и спорт // https://books.google.ru/books?id=W8aptgEACAAJ
746
Ботвинник М. М. (1961). Люди и машины за шахматной доской / Шахматы в СССР. № 3.
Впрочем, в этих сравнениях есть достаточно много условностей. Под рассмотрением шахматистом той или иной позиции в ходе расчёта вариантов мы понимаем только сознательное рассмотрение, дипломатично умалчивая о том, что часть анализа происходит и на бессознательном уровне. Если шахматист оценил последовательность из нескольких взятий на некотором поле, значит ли это, что он рассмотрел соответствующее число позиций? Так же и при подсчёте количества позиций, принятых в рассмотрение машиной, существует множество разночтений в способах такого подсчёта. В зависимости от принятых соглашений число вариантов, рассматриваемых машиной, можно уменьшить или увеличить на несколько порядков. Кроме того, в определённых ситуациях оценочная функция может успешно подменять собой рассмотрение конкретных вариантов. Оценочные функции шахматных программ второго поколения могли включать в себя, например, «правило квадрата» — простой геометрический принцип, позволяющий оценить, успевает ли король перехватить проходную пешку в пешечном эндшпиле. Тот же результат мог быть получен анализом конкретных вариантов, причём в ряде случаев этот анализ нужно было бы осуществить на достаточно большую глубину. То же самое можно сказать о таблицах окончаний: программа просто извлекает из базы точную оценку позиции без всякого перебора. Обладая некоторой фантазией, можно представить себе сложную оценочную функцию, позволяющую эффективно заменить перебор вариантов. Например, в современных программах оценочная функция может ценить сильную атаку на короля или сильные проходные пешки куда выше, чем несколько лишних пешек или даже лишнюю фигуру, благодаря чему программа способна без глубокого перебора принять решение об осуществлении вполне «талевской жертвы» (Михаил Таль, восьмой чемпион мира по шахматам, любил острую игру и часто осуществлял некорректные жертвы. Однако при этом Таль часто побеждал, потому что противнику при ограниченном временном контроле и волнении опровергнуть такую жертву было непросто. Тогда говорили: «У соперников Таля всегда находится выигрыш, причём всегда… лишь в анализе после партии!»). Сам Таль относился к этому с присущим ему юмором: «Есть два вида жертв: корректные и мои!» [747] Также программы второго поколения могли включать в рассмотрение довольно длинные цепочки «форсированных» ходов, например шахов, взятий, превращений пешек и так далее. Поэтому даже программа ИТЭФ вполне могла найти сравнительно длинную выигрывающую комбинацию при глубине перебора всего в три полухода, если, например, после трёх «тихих» ходов следовала цепочка из десяти форсированных [748] .
747
Жанна Михайловна Таль, персональные коммуникации.
748
В шахматы «играет» ЭВМ. Телевизионные новости. Эфир 24.11.1968 // https://www.youtube.com/watch?v=LZEd6ZtSxCo