[16.06.1999, 18:58:50]
Игорь Касьянский,
<grundik@netvision.net.il>
E2 - E4, ENTER
 Немного личного опыта
Это случилось лет двенадцать - тринадцать назад. Наш умница-тренер принес на Классификационный турнир по шахматам Дома пионеров Тимирязевского района города Москвы чудо-машину. Чудо-машина походила на карманные магнитные шахматы, но с дисплеем, на котором высвечивались ходы виртуального (в те годы никто из нас кроме, может быть, умницы-тренера, не знал этого слова) шахматиста, упрятанного в утробу аппарата. Это действительно походило на чудо: в ответ на ваше "Е2-Е4" чудо-машина, как полагается, немного пошумев, выдавала: "Е7-Е5". Сама. Умница-тренер радовался как ребенок. Мы, его питомцы, по-взрослому раздували щеки и тянули гласные: "Прогресс". Тот факт, что машина бесконечно долго думала над каждым ходом и играла откровенно слабо, никого не смущал. Под предлогом того, что нам не хватает еще одного игрока (откровенная ложь), тренер поместил машину в турнирную таблицу. Его расчет оказался точным - интерес к соревнованию повысился невероятно. Каждый рвался помериться силами с чудесной коробочкой.
Испытания выдерживал не каждый. Ослабленный утомительным ожиданием следующего хода невидимого противника, я наделал кучу глупостей и с трудом свел свою партию с чудо-машиной на ничью.
С тех пор прошло много лет. Я стал КМС-ом, забросил шахматы, уехал в другую страну, получил профессию, поменял профессию... Но по сей день, привычно загружая шахматную программку с диска, я испытываю почтительный ужас перед этой технологической загадкой, которую мне, простому смертному, так и не удается постичь.
История шахматных компьютеров
Создать механические шахматные автоматы люди пытались еще в средние века. Но возможности механической логики чересчур ограничены, а количество вариантов в любой шахматной партии слишком велико, так что все эти попытки ни разу не привели к успеху. Лишь с появлением компьютеров человечеству был дан еще один шанс. В 1950 году Клод Шэннон, основатель теории информации, предложил в качестве объекта для компьютерного анализа шахматы.
Шэннон утверждал: "Научное исследование проблемы игры в шахматы позволит развить методы построения систем искусственного интеллекта". Программисты и математики с энтузиазмом взялись за дело. В 1956 году в Массачусетском Технологическом Институте (США) был создан первый шахматный компьютер с характерным названием "MANIAC". Игра была смоделирована на доске 6x6, в ней отсутствовали слоны, а пешки могли ходить из начальной позиции лишь на одну клетку. Такие "издержки" объяснялись слабыми возможностями существовавших тогда машин. (Один из самых современных и наиболее дорогостоящих компьютеров того времени IBM 704 располагал 4K оперативной памяти и мог разместить на своем диске 16000 чисел).
Однако процесс пошел. В 1974 году в Стокгольме состоялся первый мировой чемпионат по шахматам среди компьютеров. Интересная деталь: чемпионат выиграла советская машина "Каисса". Впрочем, это был крупный, но, пожалуй, единственный успех российских создателей компьютеров.
На сегодняшний день бесспорным лидером в мире игровых машин является шахматный суперкомпьютер фирмы IBM "Deep Blue". Именно с ним в мае 1997 года в Нью-Йорке сразился чемпион мира среди людей Гарри Каспаров.
О сути проблемы
Для того чтобы написать компьютерную шахматную программу, необходимо было создать и запрограммировать соответствующий алгоритм. Но тут выяснилось, что никто не знает, как человек играет в шахматы. То есть, правила игры знают почти все, цель игры - поставить мат - знают даже те, кто не знает правил, но как описать эти правила и, тем более, цель игры "математически"? С чего начать?
Начинать при разработке первых шахматных программ приходилось с самого простого: с математического определения сравнительной ценности фигур. Уже на этом, самом первом этапе программисты столкнулись с поистине нечеловеческими трудностями. Пешка - самая слабая из фигур - принималась за единицу, конь был равен трем пешкам и т. д.. Но как быть с проходной пешкой? Или с пешкой, которая при определенных условиях может ей стать? Или с укрепленной пешкой в центре поля? Иногда вокруг нее происходят многоходовые, крайне драматические баталии с разменами и даже жертвами значительно более ценных фигур. Составлялись тысячи таблиц-вариантов перемещения фигур, их сравнительной ценности в зависимости от их взаимодействия с другими фигурами и позиции на доске. Таблицы разрастались, уточнялись, переделывались.
Машину так же, как человека, учили играть в шахматы с конца. В эндшпиле и фигур поменьше, и позиции изучены получше. К тому же на полновесные партии у маломощных компьютеров просто не хватало памяти. В эндшпилях машина преуспела, но в целом в шахматы она играла бездарно. Не атаковала позиционно, не придумывала комбинаций, а охотилась за фигурами в соответствии со своей шкалой ценности. Это была уже игра. Но игра скучная. Казалось, что машина никогда "не поймет" стратегии шахматной партии.
На первый взгляд, шахматы - очень простая для анализа игра, и кажется, что запрограммировать алгоритм действий в этой игре нетрудно. Однако основная сложность на пути создания такого алгоритма заключается в наличии большого числа вариантов дальнейшего развития событий, которое с каждым ходом катастрофически быстро растет. Например, после первого хода игроку надо проанализировать 400 различных позиций, после второго - 20000, и уже через несколько ходов эта цифра будет астрономической.
Человек может выбрать победную комбинацию интуитивно, причем иногда довольно быстро, даже не рассматривая заведомо ведущих к проигрышу вариантов. Как и почему это происходит, неясно пока даже крупнейшим специалистам по изучению человеческого интеллекта, и тем более непонятно, сможет ли когда-нибудь искусственный разум действовать как человеческий? Решение этой задачи еще весьма далеко от завершения. Поэтому почти все шахматные программы, созданные к сегодняшнему дню, построены на основе распространенного принципа решения компьютерных задач: последовательного перебора возможных вариантов.
Шахматные программы становились все более сложными. К основным критериям, таким как сравнительная ценность фигур, добавлялись новые - например, мобильность (количество полей, куда можно передвинуть фигуры), развитие фигур, оценка пешечной структуры, защита короля и т. д.
Наконец, более-менее современную форму шахматные программы обрели с разработкой алгоритма поиска по шахматному дереву. Как строится это дерево, легко представить, если вспомнить сложное ветвление вариантов в шахматной партии. Каждый вариант развития событий на доске является ветвью этого программного дерева. Первый алгоритм такого типа, который использовался в ранних шахматных программах, известен под названием минимакс (minimax). Этот алгоритм перебирает все варианты на заданную глубину, находит лучшую позицию на последнем уровне дерева и пытается найти приемлемый путь ее достижения путем оценки позиций на каждом уровне дерева. Оптимальное решение заключается в максимуме выгоды для себя и минимуме потерь со стороны противника. Отсюда и название алгоритма.
Уже с шестидесятых годов в написании шахматных программ стали применять так называемый альфа-бета алгоритм, разновидность минимакс-алгоритма. В отличие от минимакса, эта система позволяла упростить обход дерева путем отсечения бесперспективных ветвей-вариантов. В 1979 году был разработан принципиально отличающийся от альфа-бета алгоритм SSS*, который строил дерево таким образом, что программа сначала обходила наиболее обещающие узлы. Однако SSS* алгоритм требует огромных вычислительных ресурсов, поэтому в большинстве случаев создатели шахматных компьютерных программ отдают предпочтение альфа-бета алгоритму.
В наши дни в Альбертском университете (Канада) ведутся разработки продолжателя SSS* MTD(f) алгоритма. И как знать, может быть, в ближайшем будущем он станет ведущим при создании новейших шахматных программ.
Компьютерные шахматы - больше, чем шахматы
Таким образом, можно утверждать, что компьютерные шахматы оказали определенное влияние на развитие информатики. В процессе разработки шахматных программ создано несколько новых алгоритмов, главным образом в области теории графов. Эти алгоритмы находят применение практически в каждой программе (списки, сортировка, рекурсия). Без них не обходится ни один компьютер, так как они обеспечивают эффективное функционирование операционной системы (теория очередей) и управление памятью (в процессе написания шахматной программы усовершенствован известный уже в течение 30 лет алгоритм сортировки случайных данных hash-transposition). Подтверждается известное положение - все новое рождается, как правило, на стыке различных дисциплин.
И тем не менее, кто кого?
Однако человек, которому всегда было свойственно очеловечивать машины, не может и не хочет останавливаться на достигнутом. Человек не забывает, что шахматы - это еще и игра, человек бросает машине вызов. Раньше играть с компьютером было легко и приятно. Человек расслабленно обыгрывал глупую программку, что, впрочем, не мешало ему восхищаться фантастическим развитием техники и технологий. Сегодня ситуация изменилась.
Гарри Каспаров однажды сказал, что он будет последним чемпионом мира по шахматам - человеком, следующим будет компьютер. К прогнозам мастера с таким высоким уровнем интеллекта следует отнестись весьма и весьма внимательно.
Противоборства компьютера и лучших шахматистов мира уже имеют свою историю. В 1988 году недавние выпускники американского университета Carnegie-Mellon разработали суперкомпьютер Deep Thought. Программа была написана на языке программирования ANSI C под операционную систему AIX. Два процессора этого компьютера могли проанализировать 750000 позиций за одну секунду. Такой скорости было вполне достаточно, чтобы Deep Thought стал первым компьютером, чей шахматный рейтинг соответствовал рейтингу гроссмейстера (2450). Программисты бросили вызов чемпиону мира. Однако в октябре 1989 года экспериментальная шестипроцессорная версия Deep Thought проиграла Гарри Каспарову в демонстрационном матче из двух партий. Человеческий интеллект оказался сильнее.
Тем не менее, в августе 1993 Deep Thought выиграл у Юдит Полгара, самого молодого, по тем временам, гроссмейстера.
3 мая 1997 г. в Нью-Йорке начался матч-реванш по шахматам между Гарри Каспаровым и IBM-овским монстром Deep Blue. Суперкомпьютер RISC System/6000 SР2 - Deep Blue был, по сути дела, усовершенствованной версией Deep Thought. Кстати, компьютеры такого типа используются не только в шахматах, но и для разработки лекарственных препаратов методами молекулярной динамики, в дизайне автомобилей, при разработке нефтяных месторождений, а также в тех случаях, когда требуется интеллектуальный анализ больших массивов различных данных.
При игре в шахматы эта система решает задачу путем перебора различных вариантов и специальными шахматными чипами, что позволяет ей рассматривать до 100 миллиардов позиций за три минуты. В памяти этого компьютера хранились все шахматные партии нашего столетия, а также миллиарды возможных шахматных окончаний.
Матч между этой машиной и Гарри Каспаровым был интересен еще и тем, что оба участника - чемпионы мира в своих "весовых категориях", и перед началом матча обе стороны сделали заявление о победе. Нынешний турнир стал матчем-реваншем (в феврале 1996г. Deep Blue потерпел поражение от Каспарова со счетом 2:4), и в этот раз компьютер наказал прошлогоднего обидчика (3,5:2,5 очка), выиграв для команды разработчиков $700000, Каспаров же довольствовался $400000.
Обескураженный проигрышем суперкомпьютеру, Гарри Каспаров заявил, что Deep Blue перестал быть машиной и заиграл по-человечески. Однако когда обрадованные успехом создатели Deep Blue стали рассказывать о структуре своего детища, выяснились удивительные вещи: оказывается, в него не заложено никакого принципиально нового подхода к математической реализации шахматной партии. Создатели этой машины по-американски прямолинейно объединили для решения одной задачи 256 процессоров, чем обеспечили достаточно быстрый перебор вариантов. И все. Другими словами, игра "Дип Блю" основана на тех же компьютерных принципах, что и 5-10 лет назад, и Deep Blue точно так же не понимает шахматной стратегии, как и его предшественники. Точнее сказать, он "понимает" ее не лучше своих предшественников.
Ну и каков прогноз?
Так кто кого "положит на лопатки", человек компьютер, или наоборот? У каждого, как всегда, есть своя точка зрения на этот счет. Эксперты тоже не грешат единодушием. Одни считают, что с увеличением быстродействия электронных систем и появлением более совершенных алгоритмов человеку будет все труднее конкурировать с машиной, которая к тому же в состоянии хранить информацию обо всех шахматных новинках. Их оппоненты утверждают, что люди не уступят пальму первенства компьютерам, прежде всего потому, что все программы для машины пишутся человеком. Весьма вероятно, что через несколько лет мы станем свидетелями компромисса между этими крайними точками зрения. Профессиональные шахматисты и программы достигнут столь высокого уровня, что игра перестанет быть захватывающим зрелищем, так как заранее будет известен оптимальный ход.
И, наконец, о софте
Теперь спустимся с небес на землю, от титанов к простым смертным. Что делать любителю, который из-за недостатка времени, средств или сил не в состоянии найти себе партнера для игры в шахматы? Конечно, сгрузить программку на свой компьютер. Но какую?
Ни Deep Thought, ни Deep Blue рядовому любителю не потянуть. Не хватит ни средств, ни компьютерных ресурсов, ни профессиональных шахматных навыков. Однако существуют программы и попроще. Например, "обучалки" типа K-Chess или "500 Партий Бобби Фишера". Они могут продемонстрировать вам и самые азы - движения фигур и варианты эндшпилей и сыграть с вами на соответствующем вам уровне. "500 Партий Бобби Фишера" может повторить каждую из 500 партий великого шахматиста и потренировать в самостоятельной игре, сыграв в стиле выбранной вами для примера партии.
Но самое широкое распространение получила игра "CHESSMASTER". Кроме уже привычных для всех возможностей сохранения и записи игры или ее отдельных частей (например, шахматной нотации) с помощью пункта GAME главного меню (там же находится и клавиша выхода из игры), пользователю предоставляются очень широкие дополнительные возможности.
MENTOR поможет вам освоить правила игры, познакомит с основными ее хитростями. Там вы можете найти подсказку очередного хода и его объяснения, можно включить режим, при котором отмечаются фигуры, стоящие под боем. Вы можете попросить компьютер найти похожую позицию и показать, как она развивалась. Или вообще потребовать от компьютера найти матовую комбинацию в заданное вами число ходов.
Зайдите в меню WINDOWS. Здесь вы сможете установить часы, сможете включить функцию Think lines, которая покажет на экране, как программа анализирует позицию, и наблюдать за "размышлениями" компьютера. Даже в ходе игры вы можете менять вид и стиль доски, перекрашивать и поворачивать ее, заменять традиционные шахматные фигуры на китайские, или на динозавров, или на морскую живность. Для этого вам необходимо открыть LOOK > FEEL главного меню.
Выбор виртуального соперника в "CHESSMASTER" - это отдельный аттракцион. Вам предлагается помериться силами почти что со всеми чемпионами мира: с Алехиным, Ботвинником, Капабланкой, Смысловым, Ласкером и т. д.. Для этого загляните в Setup Detailes в PLAY главного меню. Вы можете также поменять характер партнера, определить стиль его игры, его представление о ценности фигур и стратегию. Например, можно создать очень осторожного противника, изменив параметры в "Безопасности короля" и "Предложение ничьей" (PLAY-Setup a Personality-Рozitional или -Style). Можно создать отчаянно храброго игрока, манипулируя движками "Пренебрежение угрозой" и "Материальные потери", находящимися там же. Таким образом, вы сможете создать двух непохожих друг на друга по стилю игры и "темпераменту" компьютерных соперников и наблюдать за их игрой в качестве болельщика и эксперта.
Вместо эпилога
Глупый компьютерный анекдот:
Один мужик говорит другому:
- А ты знаешь, что компьютеры между собой могут играть в шахматы?
- Ух, здорово, куплю себе компьютеры, поставлю играть, а сам в кино пойду.
Материал любезно предоставлен израильской компьютерной газетой Interface
|
