Шахматные программы. 
Интеллектуальные системы

Алгоритм минимакса даже при использовании альфа-бета отсечения все же требует спуска до терминального состояния по многим ветвям, следовательно, его применимость сильно ограничена. Иными словами, на практике он не используется, за исключением совсем простых случаев. Более практичным является применение эвристических оценок каждой позиции без спуска до нижних листов дерева. Такой подход используется, например, в шахматных программах, где шахматистами давно отработана методика оценки как отдельных фигур, так и позиций в целом. Так, пешка имеет стоимость 1, конь или слон — 3, ладья — 5, ферзь — 9. Оцениваются также такие характеристики, как безопасность короля, хорошая пешечная структура и т. д. Таким образом, каждый ход может быть сразу оценен. Это не значит, что можно ограничиться глубиной поиска в один ход. Хорошая позиция может быть достигнута через 5—8 ходов.

Модификация альфа-бета отсечения в этом случае заключается в том, чтобы ограничить верхнее значение оценки альфа (но принципу «от добра добра не ищут») и нижнее значение бета (минимально допустимое временное ухудшение позиции). Здесь все же всегда есть риск пропустить отличный ход или, наоборот, «зевнуть».

Более надежный подход заключается в использовании итеративного углубления в пределах отведенного времени. В этом случае в любой момент времени имеется все более совершенное решение, но выбор точки останова лежит вне программы, что нельзя признать удовлетворительным. Машина будет одинаково долго думать над простыми и сложными ходами.

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

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

Первая шахматная программа была разработана в 1951 г. Аланом Тьюрингом. Эта программа практически не эксплуатировалась, а ее алгоритм проверялся путем моделирования вручную.

Первой успешной отечественной программой стала Kaissa, разработанная в 1974 г. в Институте теоретической и экспериментальной физики под руководством экс-чемпиона мира по шахматам М. Ботвинника. Это программа победила на первом чемпионате мира по компьютерным шахматам в Стокгольме.

Шахматной программой, которая победила Гарри Каспарова в 1997 г., является Deep Blue, созданная в компании IBM. Программа работала на параллельном компьютере с 30 процессорами IBM /?5/6000. На этом компьютере эксплуатировались средства «программного поиска» и 480 специализированных СБИС (сверхбольшие интегральные системы) шахматных процессоров, вырабатывающих ходы. На этом компьютере программа Deep Blue в среднем осуществляла поиск 126 млн узлов в секунду, а пиковая скорость составляла 330 млн. На каждый ход программа формировала до 30 млрд позиций, достигая глубины поиска 14. Основой программы является обычный альфа-бета поиск с итеративным углублением, но ключевая особенность программы — способность углублять поиск в интересных позициях до 40 ходов. Помимо обычного поиска программа использовала справочник дебютов из 4000 позиций, большую базу эндшпилей и базу из 700 000 игр гроссмейстеров. Только такая добавка к программе позволила уравнять ее с чемпионом мира, который также обладает подобными знаниями и использует шаблонные решения.

Группа разработчиков Deep Blue отказалась от предложенного Каспаровым реванша. Вместо этого на соревнованиях в 2002 г. против Владимира Крамника выступила программа Deep Fritz, уже на обычном персональном компьютере. Deep Fritz — это разработка Франса Морха (Голландия) и Матиаса Фиеста (Германия). В этой программе применена техника нулевого хода (null move), заключающаяся в том, что в ходе поиска игроку позволяется сделать два хода подряд (другой игрок пропускает ход). Благодаря этому легче обнаруживаются слабые ходы. Матч из восьми игр против Deep Fritz закончился ничьей, что позволило Крамнику заявить: «Теперь очевидно, что это лучшая шахматная программа и чемпион мира играют на равных».

Следует отметить, что, несмотря на впечатляющий прогресс в области шахматных программ, эти результаты не могут распространяться на другие задачи. Этот вывод подтверждается гем фактом, что после победы над Каспаровым компания IBM демонтировала и более нс использовала программно-аппаратный комплекс Deep Blue, хотя ранее заявляла, что он будет использоваться для решения практических задач.