Разработка программного модуля искусственного интеллекта для игры в шахматы
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµленных строк, используя накопленные шахматные знания, чтобы подрезать неинтересные ветви
Первый компьютер был спроектирован фон Нейманом для ведения сложных расчетов при создании ядерного оружия. В 1950 году появился первый образец, способный производить 10000 операций в секунду. Одним из первых экспериментов с аппаратом стало написание шахматной программы, правда, шахматы были нестандартные - на доске 6*6 без слонов.
Через несколько лет этот компьютер ("MANIAC") сыграл с людьми: сильный шахматист одержал уверенную победу, а новичок проиграл за 23 хода.
В 1957 году на IBM704 (42 кГц, 7 Кбайт -память) был реализован тип В программы на полной доске, с участием всех фигур. Машина считала 4 полухода за 8 минут. Уровень игры - любительский[15].
В 1962 году Ньюэл, Саймон и Шоу открывают алгоритм, получивший название альфа-бета (alpha-beta), он давал результат не хуже, чем полный перебор, не исследуя все варианты. В нем не требовались никаких специальных шахматных знаний, и он мог быть применен для решения любой переборной задачи. Суть алгоритма в том, что в каждой строке игры, для белых и черных отслеживаются их максимальные результаты, и если в некоторой точке черные уже получили результат, сравнявшийся с максимумом белых, достигнутым до этого, то дальше передирать нет смысла. Когда перебор вернется в точку, где был достигнут максимум белых, результат, все равно, будет отвергнут.В основе всех современных шахматных программ лежит одна из усовершенствованных версий данного алгоритма[22].
Примерно до 1973 года все шахматные программы были типа В. Они главным образом основывались на генераторах правдоподобных перемещений, отсекая статической оценкой малоправдоподобные. С появлением более мощных процессоров программисты стали переключаться на тип А. Первыми были Teach и Chess4, это были программы грубой силы, как только они достигали глубины 5 полуходов средней стадии игры, они начинали побеждать в соревнованиях с программами типа В.
В 1975 году Роберт Хьят начинает разрабатывать CrayBlitz, который долгое время был самой быстрой шахматной программой и в период с 1983 по 1989 гг . - мировым чемпионам среди шахматных программ. Он искал примерно 40-50 тыс. позиций в секунду (в 1983 году), что для своего времени было большим достижением[17].
В 1977 году Томпсон и Кондон из лаборатории Bell создают первый специализированный шахматный комрьютер. Основная идея была в реализации некоторых частей шахматной программы (генератора ходов, функции оценки позиции, детектора шахов и пр.) на аппаратном уровне, что избавляло от программных задержек в каждой позиции не дожидаясь увеличения мощности процессоров. Лучшие компьютеры того времени могли исследовать до 5 тысяч позиций в секунду, а машина Кена Томпсона, которую назвали Belle, обрабатывала 180 тысяч строк в секунду. Belle мог продумывать позиции на 8-9 полуходов вперед, что ставило его на уровень мастера. Он побеждал на многих компьютерных шахматных турнирах. Но несмотря на то, что специализированное железо на порядок быстрее, чем обычная машина, программа CrayBlitz на сверхсовременной тогда машине все равно играла лучше[17].
В 90-х года Ричард Лэнг , пишущий исключительно на ассемблере, сделал очень сильную программу выборочного поиска Genius. До сих пор эта программа стабильно держит 5-6 место на мировых компьютерных шахматных чемпионатах. Так же в 90-ы годы стали сильно развиваться шахматные алгоритмы, появилась эвристика пустого хода (NullMove), выборочное отсечение пограничных ветвей дерева перебора[17].
Отдельно стоит рассмотреть самую известную шахматную программу, шахматный супер компьютер - Deep Blue. В 1987 году Deep Blue начиналась как студенческая разработка - интересно было группе способных студентов попробовать свои силы, да и тема для диплома отличная. Прогресс технологии позволил сделать первую же версию процессоров (названную ChipTest) очень быстрыми. Последовала следующая, усовершенствованная версия, названная Deep Thought. В этот момент группу заметил маркетинговый департамент фирмы IBM и обратился к ней с предложением, от которого невозможно было отказаться. Результатом стали Deep Blue и Deep Blue II. Таким образом, Deep Blue II - это результат более чем 10 лет работы очень способной группы, в которой были как программисты/железячники, так и сильные гроссмейстеры . Финансировалась вся работа фирмой IBM, таким образом у группы были ресурсы, которые и не снились академическим организациям. Deep Blue II сделана на основе мощного сервера RS/6000 фирмы IBM. В сервере имеется 31 обычных процессора; один объявлен главным, ему подчиняются 30 остальных. К каждому рабочему процессору подключено 16 специализированных шахматных процессора, таким образом всего имеется 480 шахматных процессоров. Весь комплекс обрабатывал более миллиарда позиций в секунду[21].
мая 1997 года Deep Blue II одержал победу над чемпионом мира по шахматам Гарри Каспаровым в матче из 6 партий. После матча с чемпионом, Deep Blue был разобран.
Как видно, начиная с самых первых, и заканчивая самыми современными программами, шахматные программы строились на основе перебора возможных ходов, но были и попытки построить более "интеллектуальные" алгоритмы, отличные от переборного. Многие известные шахматисты пытались разработать такие алгоритмы, но результаты не удовлетворяли требованиям. К примеру Ботвинник М.М., будучи чемпионом мира и автором многочисленных работ по теории шахмат, более 20 лет занимался созданием шахматной программы, но программа так никогда и не заиграла[5].
Все переборные алгоритмы для поиска наилучшего хода строият