Начало истории компьютерных стратегий: эпоха шахмат, часть 1

Стратегии — один из давних и почтенных жанров компьютерных игр. Ценители жанра, вроде вашего покорного слуги, проводили в них тысячи и тысячи часов — и судя по объёмам дофамина, и эндорфинов, это время точно не было потрачено впустую. Ну и мозги это дело прокачивает неплохо, пожалуй.
Правда, ни одна самая глубокая и прошаренная стратегическая игра, увы, даже близко не подходит к уровню сложности и многогранности реальности. Стратегии как создают когнитивные искажения, порождая весьма ошибочные мнения о том, «как всё работает и как всех ногебать» в реальности — так и помогают понять хотя бы часть этой сложности. Об этом мы тоже поговорим, но чуть позже. А сейчас — к основам и истокам жанра, о том, как всё зарождалось в далёкую и ностальгическую эпоху классического киберпанка.

Вначале было обучение машин игре в шахматы

Первой стратегической игрой, играть в которую люди попытались научить машины, были, конечно, шахматы. Первая попытка ознаменовалась курьёзом очень в духе авантюрного и ироничного XVIII столетия, эпохи рацио и Просвещения — когда вся просвещённая публика обожала хитроумные устройства, а возможности шестерёнок и часовых механизмом казались неограниченными. В 1769 году знаменитый изобретатель Вольфганг фон Кемпелен представил в Вене невероятную разработку «Механический турок»: автоматизированное устройство для игры в шахматы. Манекен в человеческий рост, одетый по османской моде того времени, двигал рукой-манипулятором фигуры на шахматной доске, установленной на солидных габаритов коробке. Внутри коробки вращались загадочные шестерни, а механизм приходилось периодически подзаводить ключом. Устройство произвело фурор при дворе австрийской императрицы Марии-Терезии, а затем отправилось в долгий тур по всей Европе.

«Механический турок» фон Кемпелена

Как считается, автомат играл в шахматы даже с монаршьими особами, сумев победить в шахматы даже таких великих стратегов и тактиков, как Фридриха II Великого и Наполеона Бонапарта. Однако чуду техники было более чем прозаическое объяснение: внутри сидел скрытый системой зеркал вполне живой и очень толковый мастер игры, который с помощью воистину хитроумной механики фон Кемпелена видел ходы противника и двигал свои фигуры с помощью руки-манипулятора. Историки лишь гадают, кто именно играл за «пультом» — известно лишь с некоторой степенью вероятности, что в 1809 году Наполеона обыграл «турком» знаменитый шахматист Иоганн Баптист Альгайер. Никакого ИИ, само собой, в XVIII веке создать было нельзя. И всё же нельзя не отдать должное мастерству и изобретательности мастера Вольфганга.

Правда, до сих пор не совсем понятно, как именно игрок туда помещался: оригинал механизма не сохранился

Однако идея о том, чтобы научить машину играть в шахматы, снова овладела научно-инженерными умами, как только уровень развития техники позволил хотя бы попытаться это сделать. Уже в 1912 году испанский изобретатель Леонардо Торрес-и-Кеведо создал шахматную машину El Ajedrecista, «шахматист». Она работала на реле, играла только за белые фигуры и могла выигрывать простейший эндшпиль, когда у белого игрока на доске остались король и ладья, а у чёрных — только король. О ходах это порождение дизельпанка сигнализировало несколькими лампочками — фигуры двигал человек. А если игрок-человек нарушал правила игры, ходя фигурой короля не так, как ему полагается — машина возмущённо сигналила и при тройном нарушении прекращала игру.

Леонардо Торрес-и-Кеведо и его детище: в некотором смысле первая компьютерная игра

В 1920-м году сын Леонардо Гонсало усовершенствовал устройство: теперь фигуры двигала сама машина с помощью магнитов, а при победе она объявляла сопернику шах и мат через громкоговоритель.

Испанские El Ajedrecista I и II — первые игровые ИИ в истории

В 1951 году начиналась эпоха полноценных компьютеров — и об их обучении игре в шахматы уже одновременно думалиАлан Тьюринг и один из основоположников кибернетики — Норберт Винер. Впрочем, они были не первыми: Клод Шеннон ещё в 1950 году написал статью «Программирование компьютера для игры в шахматы», заложившую многие последующие успехи в этом направлении.

Передача эстафеты из рук в руки: Гонсало Торрес-и-Кеведо, сын Леонардо, демонстрирует усовершенствованный им шахматный автомат Норберту Винеру на Парижском кибернетическом конгрессе 1951 года

Уже в 1956-м году в ядерной лаборатории Лос Аламоса написали программу для MANIAC I по игре в упрощённые шахматы на доске 6х6 клеток без слонов и двойных ходов пешками — полноценную доску и полный набор ходов и правил один из первых фон-неймановских мейнфреймов ещё не тянул в принципе. Машина, конечно, тупила и тормозила, продула опытному шахматисту, но сумела-таки обыграть недавно научившуюся играть в шахматы сотрудницу лаборатории. Естественно, никакого графического отображения не было: компьютер выдавал только ходы, а фигуры на вполне материальной доске двигали сами люди.

Один из авторов программы Пол Штейн и создатель MANIAC I Николас Метрополис с «лос-аламосскими шахматами»

Уже в 1957 году американский компьютерщик из IBM и шахматист в одном лице Алекс Бернштейн при участии нескольких коллег написал первую в истории программу для полноценной игры в шахматы компьютером для IBM 704. Правда, программа едва помещалась в невеликой памяти машины — но зато ей требовалось для обдумывания хода всего лишь около восьми минут.

Шахматная программа Бернштейна выбирала наиболее вероятные плодотворные ходы и тщательно их исследовала, сравнивая один с другим по ряду параметров. Программа содержала большую базу данных, что позволяло ей обсчитывать возможные движения фигур по полям доски. Программа проверяла ситуацию и возможности в порядке убывания важности: для начала, не находится ли король под шахом? Если да, то нужно или съесть угрожающую ему фигуру, или вывести короля из-под удара. Если шаха не было, программа просчитывала: можно ли съесть вражескую фигуру, не находится ли своя фигура под возможным ударом, и что в данном случае было бы полезнее. Для её алгоритма спасти или взять ладью было важнее, чем спасти или взять пешку. Программа Бернштейна стала важным этапом в обучении машин стратегическим играм.

Алекс Бернштейн играет в шахматы со своей программой на IBM 704

Чем умнее и доступнее становились компьютеры, тем больше программистов разрабатывали шахматные программы для них — в том числе потому, что шахматы считались важной и полезной для интеллекта игрой, а крупные шахматные чемпионаты с битвами великих гроссмейстеров завладевали вниманием мировых СМИ и болельщиков лишь немногим меньше, чем футбольные или хоккейные матчи. Сделать программу, способную уверенно обыгрывать гроссмейстера, не удавалось до самых 90-х годов — но сделать это пытались многие, и далеко не только в США. Советские компьютерщики тоже обожали шахматы, разрабатывали программы для советских ЭВМ — и опирались при этом на сильнейшую советскую шахматную школу со множеством великих имён мирового уровня.

Советская ЭВМ М-20, для которой в середине 1960-х годов был написан алгоритм для игры в шахматы

Это нашло отражение и в творчестве Стругацких:

Фёдор же Симеонович Киврин забавлялся с машиной, как ребёнок с игрушкой. Он мог часами играть с ней в чет-нечет, обучил её японским шахматам, а чтобы было интереснее, вселил в машину чью-то бессмертную душу — впрочем, довольно жизнерадостную и работящую.

Масла в огонь мировой популярности шахмат подливала конкуренция советской и западных шахматных школ — и в 1966 году состоялся первый в мире советско-американский шахматный матч между компьютерными программами. Идея о нём возникла во время визита в СССР американского программиста Джона Маккарти, участвовавшего в разработке шахматного алгоритма Kotok-McCarthy 1962 года для IMB 7090 на основе программы Алекса Бернштейна. Американец из Стэнфорда встретился с Владимиром Арлазаровым из Института теоретической и экспериментальной физики — который, в свою очередь, вместе с Анатолием Усковым, Георгием Адельсоном-Вельским и другими коллегами в 1964 году сделали шахматный алгоритм для ЭВМ М-20.

Владимир Львович Арлазаров — ведущий советский разработчик игрового ИИ для шахмат

Арлазаров и Маккарти «забились» на матч своих программ и компьютеров буквально по переписке: ходы передавались между ИТЭФ и Стэнфордом по телеграфу. Алгоритмы были уже более-менее продвинутыми: по словам Маккарти, их детище играло на уровне «продвинутого новичка, сыгравшего около сотни партий», и на тот момент это была лучшая шахматная программа в США. IMB 7090 для обсчёта одного хода требовалось от 5 до 20 минут. Советская ЭВМ была гораздо более медлительной: ход она обсчитывала примерно за ночь. Но… зато советский алгоритм оказался более совершенным. И выиграл в четырёх партиях со счётом 3:1.

Джон Маккарти играет с компьютером в шахматы, 1966 год

Впрочем, игра 1966 года была самодеятельностью учёных поверх границ. В 1974 году состоялся уже официальный первый в мире чемпионат между компьютерными программами. За СССР выступала программа «Каисса», написанная Арлазаровым на ассемблере на основе своих наработок середины 60-х для британской ЭВМ ICL System 4/70 в Институте проблем управления АН СССР. Программа была крайне продвинутой, имела дебютную книгу на 10000 ходов, использовала новый алгоритм отсечения позиций и впервые использовала побитовое представление доски. «Каисса» умела производить анализ во время хода соперника, использовала эвристику нулевого хода и сложные алгоритмы для управления временем. И убедительно выиграла чемпионат у программ-конкурентов, принеся своим разработчикам золотую медаль. Впрочем, хорошим шахматистам-людям, даже крепким любителям, «Каисса» и другие компьютерные шахматисты 70-х всё же чаще проигрывали.

Фотографии и статистика первого чемпионата между игровыми ИИ

Однако успехи программ-шахматистов 70-х показали, что машины можно научить играть в игры стратегического и тактического характера — и далеко не только в шахматы. Уже в 70-е годы в США существовало немалое количество любимых гиками, военно-историческими и не только, настольных игр стратегического характера. Идея прикрутить к ним ИИ и сразиться с компьютером — особенно всё более доступным в виде ПК — буквально витала в воздухе. Самые первые игры в жанре компьютерной стратегии (к которым мы будем относить и тактические игры, которые в английской терминологии часто рассматриваются как отдельная категория) увидели свет в конце 70-х годов. С рассказа о них мы начнём нашу следующую часть.

Многие источники называют первой компьютерной стратегией Invasion 1972 года от Magnavox — но это мнение категорически ошибочно, о чём мы тоже поговорим

Ну а компьютерные шахматы продолжали бурно развиваться. В 1990-х они стали уверенно побеждать даже лучших шахматистов-людей, в том числе топовых гроссмейстеров. Ну а ныне люди даже не берутся всерьёз противостоять мощным шахматным алгоритмам: дело это по определению проигрышное.

А вот в более комплексных и сложных стратегиях у ИИ пока что это не слишком получается, несмотря на усилия разработчиков. И почему так — тоже попробуем разобраться дальше.

Оставайтесь с нами!

 

Источник