Мы продолжаем рассказ о компьютерных шахматах, начатый в "Компьютерре" # 8. Речь пойдет о методах, которыми компьютер пользуется, чтобы выбрать ход, ведущий к выигрышу.

Шахматы придумали в Индии. По преданию, их создал Сета, подданный царя Шерама. Когда царь познакомился с игрой, то пришел в неописуемый восторг. – Ты можешь требовать любую награду, – сказал Шерам. – Повелитель, прикажи выдать за первую клетку одно пшеничное зерно, за вторую – два, за третью – четыре и так далее. -Возьми мешок! – воскликнул царь. – Прикажи исчислить количество зерен, мне лишнего не нужно.

Придворные математики объяснили, что выполнить просьбу Сеты невозможно. Число зерен, равное 2^64-1, превышает десять квинтильонов: 18446744073709551 615.

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

Чтобы сократить перебор ходов, количество которых далеко превышает число зерен, Клод Шеннон в 1950 году предложил две стратегии. В "Стратегии А" компьютер делает перебор до определенного хода, а затем выбирает лучший из них. Хоть полный перебор невозможен, но ведь и человек анализирует игру лишь на небольшое число ходов вперед. Чтобы компьютер мог отличить плохую позицию от хорошей и построить последовательность ходов, ведущих к выигрышу ("хорошей позиции"), ему нужен метод оценки позиции. Для этого используют "оценочную функцию", учитывающую ценность фигур, их расстановку, возможность атаки и другие факторы. Чем больше значение этой функции, тем лучше позиция. Как вы понимаете, универсального способа для оценки позиции нет. Моя функция считает ее хорошей, а функция в другой программе, возможно, сразу ее отбросит. Тем не менее, роль оценочной функции не очень значительна: компьютер играет тем лучше, чем больше ходов он проанализирует. Моргенштерни фон Нейман разработали в теории игр универсальный способ выбора лучшего хода. Все ходы и возможные позиции представляются в виде дерева. В вершине дерева наша текущая позиция, ветви – это возможные ходы, ниже находятся вершины, получаемые из текущей применением ходов. А потом из каждой вершины опять строятся все возможные ходы.

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

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

Разработано несколько способов улучшить стратегии "А" и "Б". "Альфа-бета отсечение" позволяет сократить время поиска. Если найден "хороший" ход, а другой ход в самом начале просмотра уже хуже, то просмотр можно прекратить и рассматривать следующий ход. "Метод подглядывания" не менее полезен. За века игры в шахматы разработаны оптимальные ходы для позиций, возникающих в начале партий; такие ходы заносятся в базу данных программы. АН алогичная база делается и для концовки партии. "Метод значительных ходов": изначально делается предположение, какие ходы являются очень хорошими и какие очень плохими, и они первыми проверяются с использованием альфа-бета отсечения. "Таблица ходов", часто серия ходов приводит к одной и той же позиции вне зависимости от того, в каком порядке эти ходы применялись. Чтобы избежать лишних вычислений, компьютер хранит часть позиций в памяти.

Сколько хитроумных решений' А ведь первый шахматный автомат, выигравший у Наполеона, работал уже в 1809 году. Сейчас мы считаем, что это была подделка и что на самом деле внутри сидел человек. Но кто знает, быть может, это было гениальное изобретение, опередившее свое время? И не погибни оно при пожаре, первый матч между человеком и компьютером состоялся бы на полтора века раньше... Впрочем, результат наверняка был бы тот же самый.

{НАЧАЛО ВРЕЗКИ}

1809. Автомат – Наполеон Бонапарт. Барон Вольфганг фон Кемпелен, живший в Югославии два века назад, изобрел шахматный автомат. Конечно, это была подделка (внутри автомата сидел человек). В 1809 году Наполеон играл против него и проиграл только на 24-м ходу.

1974. "Каисса". Убедительная победа со счетом 4:0 у программ-соперников. Программа разработана в 1971 году в Институте управления Михаилом Донским, Владимиром Арлазаровым и Георгием Адельсон-Вельским. В качестве тренировки программа сыграла с читателями "Комсомольской правды": из присланных ходов выбирался самый распространенный. Давид Бронштейн использовал базу данных концовок партий "Каиссы" для подготовки к матчу в Вильнюсе. В дальнейшем, когда в шахматных матчах гораздо принципиальней стала мощность машины, нежели программы, усовершенствование "Каиссы" прекратилось. Но версия для IBM PC все же успела появится на свет.

1988. Deep Thought – Гарри Каспаров. Первая встреча Каспарова и Deep Thought. Каспаров легко выиграл обе игры и выразил восхищение силой противника. Перед игрой он проанализировал предыдущие игры Deep Thought и пришел к выводу, что победить компьютер можно, если привести его к необычной позиции. "Если знаешь, как работает программа, то можно предсказать его ход".

1989. Deep Thought – Гарри Каспаров. Первая игра окончилась быстрой победой Каспарова. Во второй игре он продемонстрировал, как можно поставить компьютер в тупик.

1989. Гроссмейстер международного класса Бент Ларсен – Deep Thought. Историческая игра, в которой компьютер впервые победил гроссмейстера. Партия полна интересных "сумасшедших" ходов.

1990. Mephisto Lyon/68030 50 МГц – Echecs 1.9/486 33 МГц (ничья). "Ичекс" и "Мефисто" встретились в финале соревнования, победитель которого стал бы чемпионом. "Мефисто" сразу сделала ошибку в начале игры, и "Ичекс" взяла игру под контроль. "Ичекс" оставалось буквально несколько ходов до окончания партии, как она неожиданно закончила ничьей из-за повтора ходов. Разработчики слишком испугались "Мефисто" и сделали критерий ничьей очень высоким. Настолько высоким, что "Ичекс" пошла на нее при перевесе на четыре пешки!

1993. Deep Blue (IBM) – гроссмейстер международного класса Джудит Полгар. Джудит была приглашена для неформальной блиц-игры (30 минут на игру). Компьютер выиграл, а Джудит заметила: "Мне бы немного практики, и я бы победила".

1994. Гарри Каспаров – Chess Genius 2.95 (Intel)/ Pentium 90 МГц. Одна из самых известных игр. Chess Genius была первой программой, победившей чемпиона мира в быстрых шахматах. РичардЛанг, программист-разработчик программы, даже не ожидал, что она победит (Каспаров проиграл 1,5:0,5). Каспаров "отомстил", выиграв в быстрых шахматах у Chess Gemux/Pentium 120 в 1995 году.

1995. Прототип Deep Blue – FritzX/Pentium 90 МГц. Deep Blue проиграла PC-программе 0:1. "Фриц" победил благодаря лучшей библиотеке позиций. Deep Blue не могла отыскать в базе данных сложную позицию, которую трудно было просчитать.

1995. Star Socrates 2.0- Fritz X/Pentium 90 МГц. Оппонентом "Фрица" была программа Star Socrates, разработанная в MIT. Она работала на параллельном суперкомпьютере "Парагон", расположенном в Национальной лаборатории "Сандия". Длина этого компьютера – 15 метров, вес – 13 тонн, он использует 1824 процессора, каждый с 16 или 32 Мбайт памяти. Программы обменивались ходами через "Интернет".

1995. Deep Blue (IBM)-Star Socrates 2.0 (Intel). В одной из самых зрелищных партий Deep Blue выиграла 1:0, пожертвовав коня , слона и ладью.

Михаил Донской, один из разработчиков шахматной программы "Каисса", ныне президент фирмы "Диско", посетил редакцию "Компьютерры" и дал разъяснения нашим корреспондентам. По его мнению, разработчики современных шахматных систем идут по пути наращивания аппаратной мощности, оставив попытки моделировать человеческое мышление. "Но нет ни одного примера практической задачи, которая была бы решена с помощью методов искусственного интеллекта, – сказал он. –  Технология экспертных систем лишь удорожает конечный результат. Все работоспособные подходы так или иначе сводятся к перебору, к методу ветвей и границ".

Возможно, г-н Донской несколько преувеличивает. Например, преимуществом экспертных систем является экономия труда разработчика, а не вычислительных ресурсов. Тем не менее, его характеристика ситуации совпадает с тем, что нам стало известно о созданной в IBM системе Deep Blue, с которой недавно играл Гарри Каспаров.

{КОНЕЦ ВРЕЗКИ}