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

Шеффер так описал произошедшие на следующий день события: «За несколько минут до официального времени начала седьмой партии, Марион прибывает в зал турнира. Он прогуливается своей обычной медленной размеренной походкой, одетый в тот же зелёный костюм, который, кажется, носит всегда. Подняв глаза от клавиатуры, я вижу его улыбку — он обменивается с кем-то приветствиями. Затем он подходит ко мне и садится в своё кресло на противоположной от меня стороне шахматной доски. <…> Тинсли садится, его голова опущена. Он приподнимает голову, чтобы посмотреть в глаза, но останавливается. Вместо этого, оставляя очки направленными вниз, в сторону игровой доски, он двигает вверх зрачки — до тех пор, пока наши взгляды наконец не пересекаются. Я бодро говорю: „Доброе утро, Марион“, и он без колебаний отвечает: „Позвольте мне предложить немыслимое. Что, если Дон Лафферти закончит матч за меня?“»

Тинсли был вынужден прервать матч из-за тяжёлых болей в области желудка, которые изматывали его и не давали спать по ночам. Проведённые быстро анализы подтвердили самые худшие опасения — у Тинсли обнаружили рак поджелудочной железы. Он был вынужден сдать матч и уступить титул Chinook.

Тинсли боролся с болезнью ещё полгода и ушёл из жизни 3 апреля 1995 г. — так и не побеждённый за игровой доской.

Место Тинсли в Бостоне занял Дон Лафферти, с которым был организован матч из 20 партий. Он сыграл 18 партий вничью, выиграл одну партию (воспользовавшись дебютной заготовкой, созданной Тинсли) и одну проиграл, что сделало результат матча ничейным [601].

3.4.6 Нахождение слабого решения шашек

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

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

В 1995 г. Британская федерация шашек (British Draughts Federation, BDF) — недавно созданная организация, которая, в отличие от EDF, признавала за машинами право на завоевание чемпионского титула, — и ACF организовали новый матч Chinook против Лафферти, в котором программа победила в одной партии при 31 ничьей. В 1996 г. Chinook с большим отрывом выиграл у чемпиона мира в игре по переписке Джерри Чайлдерса — восемь побед и 12 ничьих, традиционно победил в Открытом чемпионате южных штатов, а затем — в Американском национальном чемпионате, оторвавшись от Рональда Кинга на целых восемь очков [602]. Матч из двух партий с Рональдом Кингом годом позже (одна победа программы и одна ничья) стал последним публичным выступлением Chinook. С 1995 г. программа не потерпела ни одного поражения в турнирах [603].

В 1800 г. в книге Джошуа Стёрджеса [604] «Руководство по игре в шашки» (Guide to the Game of Draughts) была опубликована позиция, в отношении которой утверждалось, что при идеальной игре обеих сторон в ней побеждают белые [605]. Позиция вызвала обширные дебаты среди шашечных экспертов, которые не утихали в течение ста лет, и лишь публикация 1900 г. окончательно убедила общество в том, что белые действительно побеждают. В честь многолетнего спора этюд получил название «столетней позиции». В 1997 г. Лафферти попросил Шеффера проверить выводы экспертов. В течение нескольких секунд Chinook определил, что позиция в действительности является ничейной. Взглянув на решение, Лафферти обнаружил, что общепринятое доказательство содержало ошибку на третьем ходу, пропущенную десятками экспертов-шашистов. С этого момента этюд Стёрджеса более известен под именем «200-летняя задача» [606] или даже, что более точно, «197-летняя позиция» [607].

Победа над Тинсли была навязчивой идеей Шеффера на протяжении многих лет. Работая с маниакальным упорством, он и члены его команды достигли, казалось, невозможного — и лишь для того, чтобы надежда в последний момент ускользнула из их рук. Программа была близка к совершенству: после выхода из длинных дебютных вариантов глубокий перебор быстро достигал позиций из восьмишашечных таблиц окончаний. Однако насколько можно было полагаться на эти дебютные варианты? Насколько хороши были те немногие ходы, в которых машина не успела за выделенное ей время получить точную оценку позиции? Более поздний опыт программ для игры авари (разновидности игры оваре, созданной в 1991 г. [608]) показал, что разница между сверхчеловеческой и идеальной игрой может быть весьма внушительна. После того как Джон Ромейн и Генри Бал полностью решили игру авари, они использовали построенные таблицы для проверки того, насколько хорошо играли программы Softwari и Marvin на Компьютерной олимпиаде 2000-го. Обе программы выполняли перебор примерно на 20 полуходов и использовали таблицы окончаний для 34 семян (фишки для игры в оваре обычно называют семенами, поскольку традиционно для игры использовались семена цезальпинии). Анализ показал, что программа Softwari выбирала идеальный ход лишь в 87% случаев, а победитель матча Marvin и того хуже — в 82% случаев. Много раз ошибки приводили к изменению ожидаемого победителя игры, но программы не осознавали этого [609]. Однако при этом обе программы играли в авари гораздо сильнее людей.

Словом, работа команды Шеффера не была завершена — ведь шашки ещё не были решены! В 2003 г. Шефферу и его коллегам удалось создать 10-шашечные таблицы окончаний для случая 5 на 5 шашек [610], а в 2005 г. — полные 10-шашечные таблицы, а также таблицы с неполной информацией для 12-шашечных окончаний (в этих таблицах точные оценки были известны лишь для некоторой части позиций) [611].

По расчётам Шеффера, для сильного решения шашек (т. е. создания полных 24‑шашечных таблиц) необходимо хранилище данных объёмом около 1000 петабайт. В 2008 г. стоимость хранилища ёмкостью 1 петабайт составляла порядка миллиона долларов (сегодня такое же хранилище стоило бы примерно в 10–15 раз меньше), что, разумеется, не укладывалось в бюджет исследовательского гранта [612]. Однако для того, чтобы получить слабое решение, достаточно было выполнить перебор лишь для некоторых поддеревьев игры таким образом, чтобы полученная в корне дерева оценка была основана только на оценке позиций, имевших точные оценки, то есть на табличных позициях или финальных позициях игры.

В таком ограниченном виде задача оказалась разрешимой, и в 2007 г. необходимые расчёты были завершены. Команде Шеффера удалось доказать, что при правильных действиях обеих сторон шашки являются ничейной игрой. Результаты были опубликованы в журнале Science [613] и стали одним из самых крупных научных результатов, полученных в 2007 г. [614]