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

Марков Сергей Николаевич

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

602

1996 3-Move Nationals Location: Danville, Virginia / The American Checker Federation // https://www.usacheckers.com/nats1996.php

603

Schaeffer J. (2008). One Jump Ahead: Computer Perfection at Checkers. Springer US // https://books.google.ru/books?id=IVumOsLLqgAC

В 1800

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

604

Westerveld G. (2013). The History of Checkers (Draughts). Lulu.com // https://books.google.ru/books?id=wwotBgAAQBAJ

605

Sturges J. (1800). Guide to the Game of Draughts: Containing Five Hundred Select Games, Together with One Hundred and Forty Striking Situations, Exhibiting Games Drawn, and Won, by Critical Strokes; Comprising Almost Every Possible Variety which the Board Can Display… // https://books.google.ru/books?id=jmR2ugEACAAJ

606

Dunn A. (1998). The Ontology of Checkers / The New York Times, February 25, 1998 // http://movies2.nytimes.com/library/cyber/surf/022598mind.html

607

Grayson B. (2007). The Next Jump in Artificial Intelligence: Computer program is unbeatable at checkers / Dicsover, July 19 // https://www.discovermagazine.com/technology/the-next-jump-in-artificial-intelligence

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

608

Blanvillain X. A. P. (2012). Oware: The Oldest Game of the World Will Not Be Solved by Computers // https://www.slideshare.net/XavierBlanvillain/abstract-oware-solutionxavierblanvillain120226

609

Romein J. W., Bal H. E. (2002). Awari is solved / ICGA Journal Vol. 25, Iss. 3 // https://icga.org/icga/journal/contents/content25-3.htm#AWARI%20IS%20SOLVED

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

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

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

610

Schaeffer J., Bjornsson Y., Burch N., Lake R., Lu P., Sutphen S. (2003). Building the Checkers 10-piece Endgame Databases / Advances in Computer Games 10, Kluwer Academic Publishers, pp. 193—210 // https://www.researchgate.net/publication/220717027_Building_the_Checkers_10-Piece_Endgame_Databases

611

Bjornsson Y., Schaeffer J., Sturtevant N. (2005). Partial Information Endgame Databases / Advances in Computer Games 11, Lecture Notes in Computing Science #4250, Springer-Verlag, 2005, pp. 11—22 // https://www.researchgate.net/publication/220716997_Partial_Information_Endgame_Databases

612

Schaeffer J. (2008). One Jump Ahead: Computer Perfection at Checkers. Springer US // https://books.google.ru/books?id=IVumOsLLqgAC

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

Построенное системой Шеффера дерево доказательств показывает идеальные линии игры, необходимые для достижения ничьей (т. е., если одна из сторон допускает ошибку, ведущую к проигрышу, дерево не обязательно покажет, как именно можно выиграть). Также Шеффер сохранил только верхнюю часть дерева игры, включающую около 10 млн позиций. Так было сделано, потому что сохранение полного дерева доказательств, в котором каждый терминальный узел соответствует позиции из базы данных окончаний, потребовало бы многих десятков терабайт дискового пространства, которых у Шеффера не было.

613

Schaeffer J., Burch N., Bjornsson Y., Kishimoto A., Muller M., Lake R., Lu P., Sutphen S. (2007). Checkers Is Solved / Science, Vol. 317 (5844), pp. 1518—1522 // https://doi.org/10.1126/science.1144079

614

The Scientist News Staff (2007). The Runners-Up / Science, Vol. 318, Iss. 5858, pp. 1844—1849 // https://science.sciencemag.org/content/318/5858/1844.1.full

Если пользователь системы запрашивает доказательство для одного из терминальных узлов этого урезанного дерева, то программа осуществляет перебор вариантов для поиска решения (в среднем такой перебор предполагает рассмотрение также около 10 млн позиций; в 2007 г. использованному Шеффером компьютеру требовалось на это в среднем около двух минут).

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

Самый длинный вариант, содержащийся в усечённом дереве решений системы Шеффера, содержит 154 полухода, а позиция, возникающая в результате этой последовательности ходов, требует анализа ещё более чем на 20 полуходов, чтобы достичь базы данных окончаний. При этом некоторые позиции в этой базе, достигнутые в результате такого анализа, предполагают продолжение игры в течение ещё пары сотен полуходов. Этот пример подтверждает сложность игры как для компьютеров, так и для людей.

< image l:href="#"/>

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

Проект Шеффера стал триумфом переборных методов ИИ и массивных параллельных вычислений и внёс существенный вклад в оба этих направления. Аналогичные подходы в наши дни используются, в частности, при решении задач из области биоинформатики — там, где ограниченность наших знаний сочетается с большой комбинаторной сложностью исследуемых систем. Решение шашек раздвинуло границы возможного для алгоритмов, основанных на интенсивном переборе [615] .

615

Schaeffer J., Burch N., Bjornsson Y., Kishimoto A., Muller M., Lake R., Lu P., Sutphen S. (2007). Checkers Is Solved / Science, Vol. 317 (5844), pp. 1518—1522 // https://doi.org/10.1126/science.1144079

Поставлена ли таким образом точка в области компьютерных шашек? Вопрос интересный, ведь сильного решения игры до сих пор не существует. Быть может, однажды, благодаря появлению более дешёвых и объёмных хранилищ данных, а также новых продвинутых алгоритмов сжатия, эта задача также будет решена. В конце концов, трудно поверить, что такой человек, как Джонатан Шеффер, может окончательно успокоиться.

3.5 Шахматы

Мир я сравнил бы с шахматной доской:

То день, то ночь. А пешки? Мы с тобой.

Подвигают, притиснут и — побили.

И в тёмный ящик сунут на покой.

Омар Хайям