Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Библиографические и исторические заметки
Библиографические и исторические заметки

Ранняя история развития механических средств ведения игр была запятнана многочисленными случаями мошенничества. Наиболее известным из них был "Турок" барона Вольфганга фон Кемпелена (1734-1804). Это устройство выдавали за автомат для игры в шахматы и смогли с его помощью обмануть очень многих, в том числе Наполеона. Лишь в дальнейшем выяснилось, что это устройство представляет собой хитроумный ящик фокусника, в котором сидит человек, хорошо играющий в шахматы [919]. Игры с участием этого устройства проводились с 1769 по 1854 годы. В 1846 году Чарльз Бэббидж (который был в восторге от "Турка") участвовал в одной из первых серьезных дискуссий на тему осуществимости задачи ведения игр в шахматы и шашки с помощью вычислительного устройства [1089]. Он также спроектировал, но не построил машину специального назначения для игры в крестики-нолики. Первая настоящая машина для ведения игры была построена примерно в 1890 году испанским инженером Леонардо Торресом и Кеведо. Она была специально предназначена для ведения шахматного эндшпиля "KRK" (King and Rook vs. King — король и ладья против короля) и гарантировала победу из любой позиции в игре с этими тремя фигурами.

В качестве первоисточника идеи алгоритма минимаксного поиска часто называют статью, опубликованную в 1912 году Эрнстом Цермело, основоположником современной теории множеств [1642]. К сожалению, эта статья содержала несколько ошибок, а алгоритм минимаксного поиска не был в ней описан правильно. Солидный фундамент теории игр был создан в оригинальной работе Theory of Games and Economic Behavior [1546], которая содержала анализ, показывающий, что для некоторых игр требуются стратегии, которые являются рандомизированными (или становятся непредсказуемыми для противников по каким-то иным причинам). Дополнительная информация на эту тему приведена в главе 17.

На заре компьютерной эры возможность создания компьютерных шахмат интересовала многих важных деятелей в этой области. Конрад Цузе [1651] (первый, кто спроектировал программируемый компьютер) разработал довольно подробные предложения, касающиеся того, как может быть решена эта задача. Во влиятельной книге Cybernetics {Кибернетика) Норберта Винера [1589] обсуждался один возможный проект создания шахматной программы и были высказаны идеи минимаксного поиска, останова на заданной глубине и применения функций оценки. Клод Шеннон [1395] изложил основные принципы создания современных программ ведения игр гораздо более подробно, чем Винер. Он ввел понятие поиска спокойной позиции, а также высказал некоторые идеи в отношении избирательного (неисчерпывающего) поиска в дереве игры. Слейтор [1430] и комментаторы его статьи также рассматривали возможности ведения игры в шахматы с помощью компьютера. В частности, Гуд [574] разработал понятие спокойной позиции независимо от Шеннона.