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

Начиная с первого Североамериканского чемпионата АСМ по компьютерным шахматам, проведенного в 1970 году, между шахматными программами разгорелась серьезная конкуренция. Программы, разработанные в начале 1970-х годов, стали чрезвычайно сложными, насыщенными всевозможными ухищрениями, которые были предназначены для устранения некоторых ветвей поиска, выработки приемлемых ходов и т.д. В 1974 году в Стокгольме проводился первый чемпионат мира по компьютерным шахматам, в котором победила Kaissa [5], еще одна программа, разработанная в ИТЕФ. В программе Kaissa использовался гораздо более прямолинейный подход к организации исчерпывающего альфа-бета-поиска в сочетании с поиском спокойных позиций. Перспективность этого подхода была подтверждена убедительной победой программы Chess 4.6 на чемпионате мира по компьютерным шахматам в 1977 году. Программа Chess 4.6 исследовала до 400 000 позиций за каждый ход и имела рейтинг 1900.

Последняя версия разработанной Гринблаттом программы МасНаск 6 была первой шахматной программой, которая эксплуатировалась на специализированном аппаратном обеспечении, разработанном специально для шахмат [1094], но первой программой, в которой удалось добиться заметного успеха благодаря использованию заказного аппаратного обеспечения, была программа Belle [286]. Применявшееся в программе Belle аппаратное обеспечение для выработки ходов и оценки позиции позволяло ей исследовать несколько миллионов позиций за каждый ход. Программа Belle достигла рейтинга 2250 и стала первой программой уровня мастера. В университете CMU бывшим чемпионом мира по игре в шахматы по переписке Хансом Берлинером и его студентом Карлом Эбелингом была разработана система Hitech, также представлявшая собой компьютер специального назначения, который обеспечивал быстрое вычисление функций оценки [428], [108]. Система Hitech, которая вырабатывала около 10 миллионов позиций за ход, стала чемпионом Северной Америки по компьютерным шахматам в 1985 году и оказалась первой программой, которая смогла победить гроссмейстера-человека в 1987 году. Система Deep Thought, которая также была разработана в университете CMU, явилась еще одним шагом в направлении чистого ускорения поиска [697]. Она достигла рейтинга 2551 и стала предшественником системы Deep Blue. В 1980 году была основана премия Фредкина (Fredkin), в которой было предложено 5000 долларов за первую программу, достигшую уровня мастера, 10 000 долларов за первую программу, достигшую рейтинга 2500 USCF (United States Chess Federation — Шахматная федерация США) (что примерно соответствует уровню гроссмейстера), и 100 000 долларов за первую программу, победившую чемпиона мира по шахматам. Премию 5000 долларов получила программа Belle в 1983 году, премию 10 000 долларов — система Deep Thought в 1989 году, а премию 100 000 долларов — система Deep Blue за победу над Гарри Каспаро-вым в 1997 году. Необходимо учитывать, что успех Deep Blue был обусловлен не только усовершенствованием аппаратных средств, но и применением лучших алгоритмов [216], [696]. Применение таких методов, как эвристика нулевого хода [90], привело к созданию программ, которые стали весьма избирательными в своих поисках. В последних трех чемпионатах мира по компьютерным шахматам, проводившихся в 1992, 1995 и 1999 годах, победили программы, работающие на стандартных персональных компьютерах. По-видимому, наиболее полное описание современной шахматной программы предоставлено Эрнстом Хейнцем [644], чья программа DarkThought получила самый высокий рейтинг среди некоммерческих программ для персональных компьютеров на чемпионате мира 1999 года.