Охота на электроовец. Большая книга искусственного интеллекта - Сергей Сергеевич Марков

ещё вернёмся к теме компьютерных шахмат, когда будем говорить об успехах нейросетевых технологий во время новой весны искусственного интеллекта, а также в главе 6.5 о социальном искусственном интеллекте. Несмотря на кажущуюся простоту настольных игр для современных интеллектуальных систем и постепенный уход от технологий GOFAI, шахматы по-прежнему остаются важным испытательным полигоном для новых технологий в области искусственного интеллекта.

3.6 Грубая сила машины: отделяем правду от вымысла (второе отступление)

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

Первая книга Царств 17:4-7

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

Это представление в массовом сознании часто переносят на вообще все шахматные программы. Многие из наших соотечественников, интересовавшихся в детстве и юности шахматами, черпали представления о шахматном программировании из книг и статей Ботвинника, обладавшего в шахматной среде серьёзным авторитетом. Отстаивая собственные идеи, Михаил Моисеевич называл программы своих идейных соперников «полнопереборными». Рассуждая об успехах Deep Thought, которые не мог игнорировать, он не обошёлся без характерной для него колкости: «Здесь мы имеем не искусственный интеллект, а мы имеем очень работоспособного идиота»[858].

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

Представим на мгновение, что Deep Blue действительно был бы программой, перебирающей все возможные варианты. Взяв из шахматного учебника задачу с матом в шесть ходов, которая под силу практически любому перворазряднику, прикинем, сколько потребовалось бы времени Deep Blue, чтобы решить её методом полного перебора. В среднестатистической шахматной позиции возможно примерно 35 различных ходов. Чтобы с гарантией найти мат в один ход, нужно рассмотреть 35 возможных альтернатив, мат в два хода (т. е. в три полухода) — уже 353 = 42 875 вариантов и так далее. При глубине в 11 полуходов, необходимой для гарантированного нахождения мата в шесть ходов, машине потребовалось бы перебрать 96 549 157 373 046 875 позиций, на что при скорости перебора в 200 млн позиций в секунду понадобилось бы около 15 лет. А ведь отдельные комбинации шахматных мастеров простираются на 10–15 ходов! Если бы Deep Blue действительно был «работоспособным идиотом» такого рода, то вряд ли мог бы соревноваться даже с любителями.

Наверняка многие из вас слышали притчу о зёрнах и шахматной доске. В одной из её версий изобретатель шахмат (в некоторых источниках — Лахур Сесса или Сисса бен Дахир, древнеиндийский мудрец) в награду за своё изобретение просил правителя выдать ему зёрна пшеницы, положив одно зерно на первую клетку шахматной доски, два на вторую, четыре на третью, восемь на четвёртую и так далее. Правитель в ответ сначала смеётся над изобретателем, попросившим столь скудный приз за блестящее изобретение, а затем оказывается потрясён после того, как придворные казначеи сообщают, что общее количество зёрен во много раз превышает все запасы правителя. В итоге в различных версиях окончания притчи изобретателя либо производят в высокопоставленные советники, либо казнят[859]. Примерные подсчёты показывают, что масса зерна должна была составить около 1,2 трлн тонн, что примерно в 1500 раз больше мирового производства зерна в 2017 г.[860]

Теперь представьте себе ту же самую задачу с зёрнами, в которой на каждое следующее поле выкладывается не в два раза, а в 35 раз больше зёрен, чем на предыдущее. Клод Шеннон в своё время попытался прикинуть нижнюю границу числа возможных шахматных партий. Предположив, что один ход, составленный из двух полуходов, предоставляет порядка 1000 = 103 альтернатив, при средней продолжительности партии в 40 ходов Шеннон получил оценку в 10120 различных партий[861]. Это число сегодня называют «числом Шеннона». Позже голландский информатик Виктор Аллис уточнил эту оценку[862], увеличив её на три порядка — до 10123. Для сравнения: число атомов в наблюдаемой части Вселенной составляет порядка 1080, то есть в 1043 раз меньше[863]. Правда, различных позиций в шахматах существенно меньше: около 4,5 × 1046 (современная оценка сверху)[864], а значит, если бы мы научились хранить в одном атоме кремния информацию о том, является ли шахматная позиция выигранной, проигранной или ничейной, то нам бы потребовалось примерно два квинтиллиона тонн кремния, чтобы сохранить сильное решение шахматной игры. В принципе, это не так много, порядка 3% массы Луны. Возможно, наши далёкие потомки когда-нибудь воплотят в жизнь подобный проект ради забавы — конечно, если будут обладать соответствующим чувством юмора. Пока же ни о каком «полном переборе» говорить не приходится.

Для иллюстрации работы современных шахматных программ я проделал небольшой эксперимент. Взяв одну из позиций последней партии второго матча Каспарова с Deep Blue, я заставил свою программу анализировать эту позицию в течение часа. За это время программа успела просмотреть примерно 2 млрд позиций, и самый длинный вариант, изученный ею в процессе анализа, простирался от стартовой позиции на 62 полухода. Это означает, что в игровом дереве глубиной в 62 полухода на один изученный вариант приходилось примерно 3 × 1086 отброшенных. И это не предел: современные программы, использующие