Компьютерные алгоритмы игры в шахматы
Почему результат игры в шахматы предопределен? Как происходило развитие шахматных программ? Чем различаются шахматные программы? На эти и другие вопросы отвечает кандидат физико-математических наук Дмитрий Дагаев.
В 1997 году состоялось знаменательное событие — компьютерная программа Deep Blue обыграла чемпиона мира по шахматам Гарри Каспарова в матче из шести партий со счетом 3½ на 2½. Это событие стало поворотным в истории противостояния человека и компьютера.
История началась намного раньше. Шахматы — одна из древнейших игр, которая дошла до наших дней. Первые прародители шахмат появились примерно в V–VI веках н. э. В том виде, в котором шахматы дошли до наших дней, они появились к концу XV века. Уже в 1886 году состоялся первый чемпионат мира по шахматам, в котором Вильгельм Стейниц обыграл Цукерторта и получил звание чемпиона мира. Со всеми оговорками, что соперники сами назвали этот матч чемпионатом мира, тем не менее стоит отметить, что, например, первый чемпионат мира по футболу пройдет лишь через 44 года после этой даты. Таким образом, шахматы действительно одна из самых древних, самых устоявшихся и самых традиционных в каком-то смысле игр.
В это же время начинает активно развиваться теория игр — область науки, которая занимается изучением стратегического взаимодействия агентов: людей, компаний, правительств. В 1913 году математик Эрнст Цермело опубликует на немецком языке работу, из которой следует, что результат игры в шахматы предопределен, а именно: если оба соперника играют правильно, то в каждой шахматной партии либо будут выигрывать белые, либо будут выигрывать черные, либо будет ничья. То есть не может произойти такого, что при правильной игре соперников в одной партии выиграют белые, а в другой партии выиграют черные. Это следует вот из какого соображения. На самом деле шахматы — конечная игра. Благодаря тому, что в шахматах есть положение, согласно которому в случае, если позиция повторяется три раза, фиксируется ничья. В результате этого и в силу конечности различных расстановок фигур на шахматной доске получается, что может быть сыграно хоть и большое, но тем не менее конечное число различных шахматных партий.
Поэтому чисто теоретически можно проделать следующее — можно нарисовать дерево игры в шахматы. Мы начинаем со стартовой позиции, с первого хода белых. Белые на своем первом ходу могут сделать двадцать различных ходов — шестнадцать ходов пешками и четыре хода конями. В ответ на это в каждом из этих случаев черные могут ответить тоже двадцатью различными способами. Таким образом, уже после первого хода в шахматах будет 400 различных возможных позиций. Дальше это дерево будет разрастаться, разрастаться и разрастаться.
Тем не менее в какой-то момент мы всегда придем к терминальной вершине, то есть к такой вершине, в которой игра закончится, но тогда можно проделать следующее. Давайте рассмотрим все поддеревья этого дерева, в которых остается сделать один-единственный ход. Тогда в таком поддереве можно понять, кто выигрывает, если позиция дошла до этого состояния. Игрок, которому принадлежит ход в таком поддереве, выбирает свое оптимальное продолжение, игра заканчивается, становится понятен результат, которым заканчивается игра в этой ситуации, и благодаря этому мы знаем, чем закончится игра, если она дойдет до этой вершины.
Но точно так же можно проанализировать все поддеревья последнего уровня. После этого можно сдвинуться на один уровень назад. Мы уже знаем, чем завершится игра на поддеревьях последнего уровня, поэтому мы сможем понять, чем завершится игра на поддеревьях предпоследнего уровня, и так далее.
Значит, мы однажды дойдем до самой первой вершины, с которой и начинается шахматная партия. Таким образом, будет понятно, кто же выигрывает в шахматах.
Проблема заключается в том, что, как я уже сказал, дерево очень большое и просчитать его человеку невозможно. В 1950 году Клод Шеннон высказывает идею о том, что если мы напишем компьютерную программу, которая сможет смотреть вдоль этого дерева на много ходов вперед, то рано или поздно мы просчитаем это дерево до конца. После этого в ведущих математических институтах мира начинается создание шахматных алгоритмов.
Первая шахматная программа была подготовлена в MIT. А уже в 1967 году состоялся первый шахматный матч между шахматными программами. В нем шахматная программа, которая была подготовлена специалистами Института теоретической и экспериментальной физики (ИТЭФ), обыграла со счетом 3:1 программу Стэнфордского университета. Чуть позже состоялся первый чемпионат мира по шахматам среди шахматных программ. К 1974 году были десятки различных алгоритмов, и шахматная программа «Каисса», написанная специалистами Института проблем управления, завоевала в этом турнире первое место, она выиграла все четыре партии из четырех. С тех пор чемпионаты мира среди шахматных программ проводятся регулярно.
В это время программы пока еще проигрывают человеку. В чем, собственно, проблема компьютерных программ? Есть два основных параметра, по которым программы различаются. Во-первых, это глубина просчета. Но эта глубина зависит в основном от мощности процессора. Таким образом, нужно не просто написать программу, которая хорошо играет в шахматы, а нужно, чтобы был достаточно мощный компьютер, который позволит просчитывать дерево игры в шахматы на как можно более далекое число ходов.
Второй компонент, которым различаются шахматные программы, — это оценка конкретной позиции. Чтобы оценить ту или иную позицию, недостаточно просто сравнить наличие одинакового количества фигур на шахматной доске. Нужно понять, у кого стратегическое преимущество, а это невозможно понять без просчета той же самой позиции на несколько ходов вперед. Чтобы адекватно оценить позицию, нужно фактически просмотреть дерево игры на как можно большее число ходов вперед, выбрать то продолжение, приносящее в этот момент стороне, которой принадлежит ход, оптимальную позицию, и присвоить этой ситуации, этой позиции значение оценки, которое получится достичь в лучшем возможном исходе через то количество ходов, на которое мы можем просчитать. Поэтому чем дальше умеет компьютер, программа просчитывать эту шахматную позицию, тем точнее будет ее оценка конкретной позиции и тем лучше она сможет выбирать из нескольких различных продолжений то, которое будет в каком-то смысле оптимальным. Если теоретически появится компьютер, который будет способен однажды досчитать дерево игры в шахматы до конца, то мы получим ответ на вопрос: «Какой же игрой на самом деле являются шахматы: выигрышные для белых, выигрышные для черных или при правильной игре соперников она будет заканчиваться вничью?»
На 2015 год не существует компьютера, который был бы способен просчитать дерево игры в шахматы до конца.
В 2007 году компьютеры закончили просчет дерева игры в шашки. Оказалось, что шашки — это ничейная игра. Что это означает? Это означает, что против компьютеров в шашки играть теперь абсолютно бесполезно. Компьютер в каждой возможной позиции знает, как играть правильно. Однако это не означает, что людям больше не интересно играть в шашки друг с другом. В каком-то смысле это вопрос, кто где будет ошибаться. Возможность выиграть партию будет означать, что выигравшая сторона сумела найти ошибочное решение другой стороны и эксплуатировать это решение.
В 2015 году была опубликована статья, в которой авторы объявили о том, что они завершили просчет дерева игры в самую простую версию покера. Эти деревья существенно меньше, чем дерево игры в шахматы.
За что сейчас идет борьба? За сокращение различных вариантов, которые нужно просчитывать. Дело в том, что для того, чтобы понять, что происходит в игре, не обязательно рассматривать абсолютно безнадежные позиции для того или иного игрока.
Если одна из сторон играет без ферзя и двух ладей, то, скорее всего, она не сможет добиться победы.
Тем самым можно существенно сократить размер дерева и упростить задачу для компьютера. Можно выбирать только те продолжения, в которых игроки по-прежнему находятся в игре, то есть борются за результат, и результат еще не предопределен. Однако уже на сегодняшний момент компьютерные программы зашли настолько далеко, что человеку против них играть бесполезно.
В 1996 году Deep Blue сыграл свой первый матч против Гарри Каспарова, и тогда человек был сильнее. Однако уже через год программисты Deep Blue обновили дебютную базу и тем самым существенно упростили задачу для программы — ей больше не нужно просчитывать первые несколько десятков ходов: у нее уже есть все известные варианты, и она понимает, какие из них являются хорошими, а какие нет. То есть она фактически может начинать работать не с первого хода, а с двадцатого, и просчитывать варианты, начиная с этого двадцатого хода. И такой обновленной программы оказалось достаточно, чтобы победить чемпиона мира. В 1997 году Гарри Каспаров признал свое поражение. С тех считается, что человек больше не может на равных противостоять компьютеру.
К 2015 году отдельно проводятся чемпионаты мира среди компьютерных программ, то есть среди софта, среди компьютеров, то есть среди железа и софта, и отдельно среди людей. Соревноваться друг с другом им уже не интересно.
Полный текст статьи читайте на Postnauka.ru
