Автор Фредерик Фридель
Как компьютеры играют в шахматы, как они «думают»? В нашем ответе на этот вопрос мы встретимся с некоторыми большими числами - некоторыми очень, очень большими числами. Вы будете удивлены.
Но давайте начнем с модуля, который нужен всем шахматным программам: генератора ходов. Чтобы играть, машина должна знать правила игры, она должна знать, как движутся фишки. Сформулировать эти правила - кропотливая задача: если вы не поймете правильных правил, рыцари перепрыгнут через край доски на другую сторону, иначе правила рокировки будут нарушены. Я рассказал забавную историю о молодом шахматном гении, двенадцатилетнем и уже имеющем силу гроссмейстера, который продемонстрировал неспособность шахматистов (и шахматных программистов) правильно сформулировать правила продвижения, хотя бы на словах.
В любом случае, как только машина поймет правила, она сможет сгенерировать список всех разрешенных ходов в любой позиции. После этого можно начинать «взгляд в будущее». Это то, что делают все шахматные программы - и, кстати, все люди: если я играю в это, а он играет в то, я могу играть в это, и если он играет то, я могу захватить его коня. Звучит знакомо? Конечно, машины делают это с невероятной скоростью и обычно для каждой возможной комбинации движений. Это приводит к очень большим числам, с которыми, как я сказал, мы будем иметь дело.
Многие знают очень большое количество, связанное с шахматами. Легенда гласит, что игра была изобретена Сиссой ибн Дахиром, и его король Ширхам был так благодарен, что сказал, что его визирь может получить в награду все, что он пожелает. Просто немного пшеницы, - сказала Сисса, - одно зерно на первом квадрате доски, два на втором, четыре на третьем и так далее. Короля удивила необъяснимая скромность этого желания - до тех пор, пока он не вычислил общее количество зерен, которое получит Сисса. Математики говорят нам точное число: 18 446 744 073 709 551 615. Это 18½ квинтиллионов (10¹⁸), и сегодня это соответствует мировому производству пшеницы на протяжении многих веков. Послушайте, как Стивен Фрай описывает это.
Сисса, по-видимому, понимала геометрическую прогрессию - как числа растут экспоненциально при умножении на обычное отношение (грубое определение). Это играет роль в общем понимании шахмат: сможем ли мы когда-нибудь решить эту партию? Можем ли мы разработать идеальную выигрышную стратегию, исследуя каждую возможную последовательность ходов? Ответ - решительный нет!
Давайте посмотрим: в обычной шахматной позиции у игрока будет в среднем 40 возможных ходов на выбор. На каждый из них противник может сыграть один из 40 различных ответов. Это дает 1600 различных последовательностей после одного хода для каждой из сторон. И цифры растут экспоненциально: после двух ходов для каждой стороны возможны 102 миллиона различных последовательностей, после трех ходов это 4,1 миллиарда - больше, чем возраст человека в секундах. Число Сиссы достигается всего за шесть ходов, а через семь ходов мы приближаемся к количеству звезд во Вселенной. Предположим, что средняя игра в шахматы длится 40 ходов. На данный момент количество последовательностей достигло 10¹²⁸. По сравнению с этим количество частиц в известной Вселенной, около 10⁸⁶, совершенно незначительно. Действительно.
Таким образом, игра никогда не будет решена полностью - ничто не сможет рассчитать все возможные последовательности ходов. Но на самом деле в этом нет необходимости. Если вы можете проработать каждое продолжение до определенной степени, вы уже начнете играть в разумную игру. Именно это и делают компьютеры: выполняют последовательности движений на заданную глубину, оценивают результирующую позицию, систематически изменяют последовательность и сравнивают оценку всех позиций на этой глубине. В конце концов, они делают первый ход в последовательности, ведущей к наиболее выгодной позиции. По сути, это то, что делают и люди. Но они делают это гораздо медленнее, чем компьютеры. Шахматный гроссмейстер прорабатывает в уме одно или два продолжения в секунду; компьютер может управлять несколькими миллионами одновременно. Так как же люди могут соревноваться?
Интеллект против грубой силы
Разница между людьми и компьютерами состоит в том, что опытные шахматисты будут рассматривать только значимые продолжения - они инстинктивно знают, что большое количество ходов можно безопасно игнорировать. Эти ходы ни к чему не приводят. Поэтому вместо того, чтобы проверять все возможные продолжения, люди смотрят только на вероятные. Фактор ветвления в прогнозе не 40, а всего несколько ходов. Компьютеры же, как правило, должны проверять все.
Этот подход «грубой силы» казался обреченным на провал. Действительно, в первые дни, когда компьютеры все еще выполняли неглубокий поиск, они играли как рядовые любители. Поэтому программисты пытались реализовать «интеллектуальную обрезку», чтобы отрезать менее значимые ветви, чтобы программа могла перемещаться по более тонкому дереву поиска и глубже проникать в позиции.
Одним из таких примеров была MacHack, шахматная программа, разработанная в Массачусетском технологическом институте Ричардом Гринблаттом (сидит наверху с ничьей). Он написал «генератор вероятных ходов», который ограничивал количество ветвлений компьютера до 15 на первых двух ходах и 9 для остальной части дерева. Таким образом, пятислойный поиск привел к 127 575 позициям, которые необходимо было оценить, а не к 102 миллионам, которые требовались программам чистого перебора.
MacHack достиг высокого любительского уровня мастерства и сыграл сотни игр против людей, в том числе три, по слухам, против Бобби Фишера. Наибольшую известность он получил благодаря победе в партии против Хуберта Дрейфуса, философа и критика искусственного интеллекта, который предсказал, что компьютеры никогда не смогут победить десятилетнего ребенка в шахматах. MacHack доказал, что он ошибался.
Я посетил команду Массачусетского технологического института примерно в 1980 году, когда МакХак достиг игровой силы более 1500 очков Эло и фактически стал почетным членом Шахматной федерации США. У Гринблатта был небольшой кризис, потому что его программа все еще была слишком подвержена ошибкам. Чтобы исправить это, он разработал то, что он описал мне как «блокировщик грубых ошибок и искатель гениальности». Это была шахматная стойка, которая параллельно с MacHack выполняла поиск методом перебора. Хеопс, как он это назвал, должен был предупредить MacHack о тактике, которую эвристическая программа иначе пропустила бы. Я не знаю, как далеко он продвинулся и насколько полезным оказалось это сочетание интеллекта и грубой силы.
Еще одна (более известная) попытка использования интеллектуального метода в шахматах была предпринята бывшим чемпионом мира (с 1948 по 1963 год с двумя короткими перерывами) Михаилом Ботвинником. По профессии он был инженером-электриком и мечтал управлять советской экономикой с помощью искусственного интеллекта.
Вместе с командой компьютерных ученых Ботвинник разработал очень избирательную шахматную программу PIONEER, которая использовала общие принципы шахмат, чтобы резко ограничить поиск. В Советском Союзе проекту не хватало компьютерных мощностей, но он получил широкую огласку на Западе и, по крайней мере, выпустил основополагающую книгу по искусственному интеллекту.
Я посетил Ботвинника и его команду в Москве и встречался с ним несколько раз в Германии, Голландии и США. Ему было явно больно, что конкурирующая советская программа KAISSA была намного сильнее Pioneer и фактически стала первым чемпионом мира по компьютерным шахматам в 1974 году. Kaissa была программой чистой силы. .
Причина, по которой неизбирательные программы победили, заключается в том, что ученые придумали ряд уловок, которые позволили им уменьшить количество последовательностей, которые необходимо было учитывать при поиске по дереву , не влияя на результат. Ярким примером является Альфа – Бета обрезка. Программисты поняли, что если у вас есть окончательный счет за один ход и вы начинаете считать другой, как только вы найдете строку, которая уступает первой, вы можете покинуть эту ветвь дерева поиска. Не нужно тратить время на то, чтобы точно определить, насколько хуже второй ход. Затем они обнаружили, что если вы заказываете последовательность ходов, которую программа искала на основе предыдущего, более поверхностного поиска, вы получаете значительно больше отсечок. Это называется итеративным углублением.
Используя этот и еще дюжину других очень умных алгоритмов, шахматные программы могли искать все глубже и глубже, становясь все сильнее и сильнее. Все попытки в целом определить осмысленные ходы в шахматных программах были оставлены, интеллектуальный (также известный как тип Шеннона B) метод шахматного программирования потерпел неудачу. И действительно резкое ускорение компьютерного оборудования за эти годы способствовало триумфу метода грубой силы. Это позволило компьютерным программам вскоре посоревноваться, а затем и полностью превзойти человеческие шахматные способности. Об этом рассказывалось в моей предыдущей статье (см. Ссылку ниже).
Конец истории? Нисколько. За прошедший год в шахматном программировании произошли радикальные изменения, актуальные не только для игры, но и для человечества в целом. Это тема заключительной статьи.
Предыдущая статья в этой серии
Эти статьи воспроизводятся с любезного разрешения Spiegel Online, там, где они впервые появились (на немецком языке). Автору было предложено сделать серию персонализированной, описать развитие шахматного программирования не как академический трактат, а как личный рассказ о том, как он это испытал.
Приключение в шахматном программировании (Часть 1)
Знаете ли вы, что первая шахматная программа была написана Аланом Тьюрингом за несколько лет до появления первых компьютеров построен. Первой шахматной программой, которая действительно запускалась на машине, была программа MANIAC, написанная в 1951 году учеными, занимавшимися атомной бомбой в Лос-Аламосе. Пятьдесят лет спустя компьютеры бросили вызов чемпионам мира, и сегодня для любого человека бессмысленно играть против цифрового противника.
