Главная arrow книги arrow Копия Глава 6. Поиск в условиях противодействия arrow Современные игровые программы
Современные игровые программы

Успех программы Deep Blue укрепил и без того широко распространенное мнение, что прогресс в области ведения компьютерных игр достигается главным образом за счет все более мощного аппаратного обеспечения; к тому же распространение таких взглядов стимулировалось компанией IBM. Создатели программы Deep Blue, с другой стороны, утверждают, что важную роль сыграло также расширение поиска и применение продуманной функции оценки [216]. Более того, нам известно, что некоторые новейшие алгоритмические усовершенствования позволяют программам, работающим на стандартных персональных компьютерах, побеждать на каждом мировом чемпионате по компьютерным шахматам с 1992 года и часто наносить поражение противникам с массовой параллельной архитектурой, способным выполнять поиск в 1000 раз большего количества узлов в секунду. Для сокращения эффективного коэффициента ветвления меньше чем до 3 (по сравнению с фактическим коэффициентом ветвления, составляющим около 35) применяются всевозможные эвристики отсечения. Наиболее важной из них является эвристика с пустым ходом, в которой вырабатывается хороший нижний предел значения позиции с использованием поверхностного поиска, в котором противнику в начале игры разрешается сделать ход дважды. Этот нижний предел часто позволяет выполнять альфа-бета-отсечение без затрат на полный поиск в глубину. Является также важным метод отсечения ненужных ходов, который позволяет решить заранее, какие ходы вызовут альфа-бета-отсечение в узлах-преемниках.

Группа разработчиков Deep Blue отказалась воспользоваться шансом провести матч-реванш, предложенный Каспаровым. Вместо этого в одном из самых последних крупных соревнований в 2002 году против чемпиона мира Владимира Крамника выступила программа Fritz. Матч из восьми игр окончился ничьей. Условия этого матча были гораздо более благоприятными для человека, и в качестве аппаратного обеспечения использовался обычный персональный компьютер, а не суперкомпьютер. Тем не менее Крамник прокомментировал этот матч так: "Теперь очевидно, что эта самая лучшая программа и чемпион мира играют примерно на равных".

Шашки. Начиная с 1952 года Артур Самюэл из компании IBM в свое свободное время занимался разработкой программы игры в шашки, которая совершенствовала с помощью обучения свою собственную функцию оценки, играя сама с собой тысячи раз. Эта идея будет описана более подробно в главе 21. Программа Самюэла вначале играла на уровне новичка, но всего лишь через несколько дней игры с самой собой усовершенствовалась до такого уровня, что стала побеждать Самюэла (хотя он не был сильным игроком). В 1962 году эта программа победила Роберта Нили, чемпиона игры в шашки "вслепую", благодаря ошибке с его стороны. Многие в то время посчитали, что компьютеры уже играют в шашки лучше людей, но фактически этого еще не произошло. Тем не менее, если учесть то, что вычислительное оборудование, использовавшееся Самюэлом (компьютер IBM 704), имело 10 000 слов основной памяти, магнитную ленту для долговременного хранения и процессор с частотой 0,000001 ГГц, эта победа остается большим достижением.