Rogue

В МИРЕ НАУКИ 04/85 / А.К.ДЬЮДНИ / ПРОГРАММЫ-ЭКСПЕРТЫ СРАЖАЮТСЯ С ЧУДОВИЩАМИ В ПОДЗЕМЕЛЬЕ ОБРЕЧЕННЫХ И ОДЕРЖИВАЮТ ПОБЕДУ

ЕЖЕГОДНО тысячи людей "погибают" в Подземелье Обреченных, играя в "Бродягу" (Rogue) - одну из компьютерных игр нового поколения. На экране дисплея игрок видит карту подземелья и управляет действиями своего персонажа по имени Бродяга, участвующего в приключениях. Цель игры заключается в том, чтобы суметь пробраться вниз через 26 уровней подземелья, захватить амулет Йендора и благополучно вернуться на поверхность, по пути подбирая драгоценности и убивая чудовищ или спасаясь от них. Немногие играющие возвращаются "живыми", пройдя через все опасности этой подземной одиссеи, не говоря уже о том, чтобы добыть амулет.
Игра эта настолько захватывающая, что человек забывает о дисплее и клавиатуре. Вжившись в роль Бродяги, я приближался ко входу в подземелье с чувством тревожного возбуждения. Была ночь, и мрачные развалины старинных строений, около которых находился вход, наводили страх и сеяли недобрые предчувствия. Чтобы быть готовым к любым неожиданностям, я достал свою волшебную палицу, лук и колчан со стрелами, похищенные из сокровищницы дракона в далеких Темных Горах, надел доспехи, сделанные эльфами, взял провиант и, держа наизготове свое оружие, ступил в адскую темноту лестницы, ведущей в подземелье.
Спуск уже начал казаться мне бесконечным, когда я наткнулся на тяжелую дубовую дверь и осторожно отворил ее. Передо мною открылось первое помещение на верхнем уровне Подземелья Обреченных. Оно было тускло освещено свечами. Чувствуя опасность, я все же вышел на середину зала, чтобы лучше осмотреться. Внезапно пол подо мной провалился, и в течение секунд я испытывал головокружительное чувство падения, а затем больно ударился, приземлившись в другом помещении. Здесь темно, как в чернильнице, и, даже привыкнув к темноте, можно видеть лишь на расстоянии нескольких шагов. В зале послышался какой-то подозрительный шум. Похолодев от страха, поднимаюсь на ноги и тут же вижу перед собой низкорослое, облаченное в устрашающие доспехи существо, сжимающее в руке огромную булаву.
Когда это чудовище подняло оружие, чтобы нанести удар, я вышел из оцепенения, заправил в лук стрелу, натянул тетиву и выстрелил. Все это было сделано в одно мгновение. (К счастью, в институте, уже на последнем курсе, я занимался в секции стрельбы из лука.) Слышно было, как взвизгнула отпущенная тетива, затем - свист стремительно пронесшейся стрелы и удар, от которого гоблин (им оказалось напавшее на меня существо) с пронзительным криком повалился на пол, корчась в бессильной ярости. Осторожно отступаю, полный решимости найти лестницу, ведущую вверх, и уйти прочь из Подземелья Обреченных. Вспоминаю об уютном доме, о письменном столе с неоконченной рукописью очередной статьи для рубрики "Занимательный компьютер".
Медленно двигаясь в направлении, в котором, как мне казалось, находилась лестница, внезапно спотыкаюсь о груду камней. Под ногами вижу в темноте что-то блестящее. Золото! А не заглянуть ли еще в одну комнату, прежде чем выйти на поверхность?
"Бродяга" - это не только игра, полная острых ощущений. Она выходит за рамки обычных приключенческих игр. Во-первых, потому, что игровые декорации в ней порождаются самой программой и меняются от партии к партии. Во-вторых, программа дает игроку схему данного уровня уже исследованной им части подземелья (см. рисунок внизу). Детали обстановки изображаются на экране при помощи букв и знаков, имеющихся на клавиатуре. Например, дефис и вертикальная черта используются для обозначения стен, пробел и знак % соответствуют проходам и лестницам, плюс - это вход, а знак ^ - западня. Обстановка в помещении может быть видимой или невидимой в зависимости от того, освещено ли помещение. Когда Бродяга впервые попадает на какой-либо уровень подземелья, на экране нет никакой информации об этом уровне. Чтобы те или иные элементы окружающей обстановки появились на экране, Бродяга (представляемый на экране символом @) должен их "открыть". Для этого он начинает исследовать обстановку, натыкается на западни, обыскивает углы в различных помещениях и проходит по коридорам. Он может встретиться с буквой U, которая обозначает чудовище по имени Коричневый Громила.

	        --+------           ----------------------
	        *..@.......|       |......................|
	        ...U.......|       |....^.................|
	|...... ...........+#######+...        ...........|
	|..................|                          ....|
	|..................|                         ...
	 ----------------+-                          -+-
	                                              #
	                           ####################
	                           #
	                         --+-----
	                       |.........|
	                       |.........|
	                       |.........|
	                       |.......
	                           ....
	                           ----


	Level: 25  Gold: 7730   Hp: 25(77)  Str: 15(18)  Arm: 9  Exp: 13/30668


		25-й уровень Подземелья Обреченных

В нижней части экрана, под схемой игровой обстановки, изображенной символами клавиатуры, высвечиваются показатели, которые имеет Бродяга в данный момент. Бродяга находится на 25-м уровне подземелья, он набрал 7730 золотых монет, у него 77 очков здоровья (из которых осталось только 25; остальные сняты за полученные им самим ранения - штрафные очки), его сила соответствует 15-й степени (высшая степень равна 18), на нем доспехи 9-го класса, а его опыт, выраженный в очках, достигает 30668 - показатель, достаточный для того, чтобы присвоить ему очень высокий, 13-й разряд по опыту. Поскольку Бродяга находится уже на 25-м уровне подземелья, ему осталось спуститься лишь еще по одной лестнице, чтобы достичь самого нижнего уровня и попытаться захватить заветный амулет Йендора. Однако для этого Бродяге надо еще каким-то образом избавиться от Коричневого Громилы.
Пока мы говорили лишь о внешней стороне игры. Можно было бы написать целую книгу, содержащую правила игры и советы начинающим. В настоящее время единственным руководством для играющих может служить довольно сжатая статья на восьми страницах, выпущенная Калифорнийским университетом в Беркли. Написанный М.Тоем и К.Арнольдом "Путеводитель по Подземелью Обреченных" на самом деле предназначен для тех, кто пользуется операционной системой с разделением времени VAS-UNIX. Версию "Бродяги" для персонального компьютера фирмы IBM выпускает фирма A.I.Design. Создатели игры Той и Арнольд, очевидно, считают, что лучший способ научиться игре - это играть в нее. Тем не менее общее описание игры, наверное, было бы полезно. Из приведенного ниже анализа некоторых игровых ситуаций и структуры используемых программ читателю, возможно, станут понятнее и правила игры и возможности разнообразить ее.
На каждом уровне игровое пространство поделено на клетки. Бродяга всегда находится в какой-то одной клетке и исследует ее окрестности. Играющий управляет передвижениями своего персонажа по помещениям и проходам, набирая на клавиатуре буквы, такие, как h, j, k и l, соответствующие перемещению Бродяги на одну клетку в одном из четырех главных направлений. Существуют и другие команды управления движением, такие, как команда перемещения по диагонали или продолжительного перемещения в заданном направлении. Чтобы Бродяга поднимался или спускался по лестнице, игрок должен нажимать на клавиши со знаками < или >.
Когда в одной из соседних клеток Бродяга обнаруживает какой-нибудь предмет, он переходит в эту клетку и автоматически "подбирает" его. Если же играющий хочет попасть в клетку, где находится предмет, и не подбирать его, то перед тем, как задать соответствующую команду на перемещение, нужно нажать на клавишу m. Можно также заставить Бродягу заняться поиском западни, набрав на клавиатуре букву s. По этой команде он осмотрит все соседние клетки. Однако следует учесть, что вероятность обнаружения западни при таком поиске составляет только 20%, поэтому не нужно терять бдительности.
Время от времени Бродяга должен отдыхать (знак "точка") или есть (буква e), чтобы восстановить силы, растраченные в блужданиях по подземелью и в борьбе с чудовищами. Кроме ограниченного запаса еды в рюкзаке, у Бродяги нет больше ничего съестного, за исключением того, что он может найти на полу подземелья (правда, это не всегда съедобно).
Если найден какой-нибудь предмет, относящийся к доспехам, Бродяга может подобрать его (после чего предмет автоматически попадает в рюкзак) или надеть на себя (буква W). Доспехи, разумеется, дают Бродяге дополнительную защиту в бою, однако может оказаться, что на них лежит "заклятье". В этом случае попытка снять их (буква T) окажется бесполезной, пока не будет найден волшебный папирус, при помощи которого можно избавиться от заклятья. Когда Бродяга находит какое-нибудь волшебное кольцо, он может надеть его (буква P), а потом снять (буква R), если только на нем не окажется заклятий.
Иногда Бродяге приходится выбросить фляжку или парочку свитков (для этого надо набрать букву d, а затем букву, обозначающую выбрасываемый предмет), потому что рюкзак переполнен. (Когда рюкзак полный, Бродяга не может брать найденные доспехи.) Однако, прежде чем выбросить фляжку, Бродяга может выпить ее содержимое, которое ему неизвестно: некоторые напитки оказываются целебными, а другие позволяют Бродяге увидеть Невидимое Чудовище. Среди напитков есть и такие, которые могут вызвать потерю ориентации: если Бродяга выпьет такой напиток и ему будет дана команда переместиться, например, к северу, он пойдет в другом, случайном направлении. Точно так же, прежде чем избавиться от свитка, полезным может оказаться его прочесть (буква r): свиток может содержать формулу, которая поможет снять заклинание с доспехов.
Наиболее впечатляющий волшебный предмет, которым может располагать Бродяга, - это волшебная палочка. В зависимости от типа подобранной волшебной палочки Бродяга может тем или иным образом подействовать на чудовище (чтобы оказать это воздействие, на клавиатуре следует нажать клавишу с буквой z): переместить его в другое, произвольно выбранное место, стрелять в него огненными шарами или превратить его в другое чудовище. Палочкой этого последнего типа, называемой палочкой Полиморфа, лучше всего пользоваться против самого ужасного чудовища. Например, лучше превратить страшного Огненного Змея в летучую мышь, чем наоборот.
Когда Бродяга встречается с чудовищем, иногда его лучше не трогать. Чудовище может спать и не нападет, если его не беспокоить. Если же схватка кажется неизбежной, то нужно взмахнуть оружием (нажав клавишу с буквой w) и затем "сражаться насмерть" (буква f). Но это можно сделать, только подведя Бродягу вплотную к чудовищу. Исход схватки будет определяться вероятностно, в зависимости от таких факторов, как сила, которой обладает Бродяга на данный момент, его опыт и "класс" доспехов.

@ Бродяга	h ход на одну клетку к западу
-| стены помещений	j ход на одну клетку к югу
# проходы между помещениями	k ход на одну клетку к северу
. пол	l ход на одну клетку к востоку
% лестница	> спускаться по лестнице
^ западня	< подниматься по лестнице
) оружие	m не брать предмета
] доспехи	s искать западню
* золото	^ определить вид западни
! фляжка с напитком	е отдыхать/есть
? волшебный свиток	W/T надеть/снять доспехи
: еда	P/R надеть/снять кольцо
/ волшебная палочка	d выбросить предмет
= волшебное кольцо	q выпить напиток
A-Z буквы верхнего регистра обозначают обитателей подземелья	г прочесть свиток
	z махнуть волшебной палочкой
	t бросить что-нибудь
	w взмахнуть оружием
	f биться насмерть

Команды и их обозначения, принятые в игре "Бродяга"
Наибольших успехов среди играющих в "Бродягу" добилась компьютерная программа, разработанная четыре года назад. Она не уступает лучшим игрокам в охоте за амулетом и золотом и предоставляет нам заманчивую возможность проследить стратегию системы, демонстрирующей высший класс игры.
В одном из сеансов игры, проводившейся в 1984г. в Техасском университете в Остине, Бродяга, управляемый программой, расправился со всеми чудовищами, собрал значительное количество золота и вернулся с амулетом. Эта программа, называемая ROG-O-MATIC, руководила каждым шагом Бродяги, каждой паузой, каждым броском и ударом.
ROG-O-MATIC - творение выпускников факультета вычислительной техники Университета Карнеги-Меллона в Питтсбурге А.Эппеля, Л.Хэйли, Г.Джейкобсона и М.Молдина. Программа связывает встроенные источники знаний с экспертными системами для того, чтобы принимать решения в той или иной ситуации, которая может сложиться в подземелье.
Когда в "Бродягу" играет человек, команды, набираемые им на клавиатуре, переносятся в программу ROGUE операционной системой. Программа автоматически решает, с каким чудовищем должен встретиться Бродяга в следующий момент, какой должна быть обстановка на следующем уровне подземелья и т.д. Программа передает эти данные (опять-таки с помощью операционной системы) на экран, чтобы информировать игрока о текущей ситуации.
Заменив в игре человека, программа ROG-O-MATIC посылает свои собственные команды программе ROGUE, которая воспринимает их точно так же, как если бы они были набраны на клавиатуре. ROGUE понятия не имеет (если можно так выразиться), что с ней играет другая программа. Аналогичным образом информацию, отправляемую программой ROGUE на экран дисплея, перехватывает программа ROG-O-MATIC и по ней строит свою собственную карту Подземелья Обреченных.


Программа ROG-O-MATIC состоит из 12тыс. операторов языка программирования С. Она объемнее и сложнее программы ROGUE. Первоначально Эппель и Джейкобсон, приступив к разработке программы в 1981г., рассчитывали сделать ее простой. Однако вскоре, после того как к ним присоединился Молдин, исходная версия программы, играющей в "Бродягу", подверглась многочисленным и серьезным модификациям, и каждая ее новая версия все больше совершенствовала тактику и стратегию игры. К тому времени, как в работу по созданию программы включился Хэйли, четвертый член группы, авторы, наконец, осознали, что, по существу, они создали экспертную систему. Такие системы будут представлять собой основное звено в компьютерах пятого поколения, производство которых, как ожидают, должно начаться в конце 80-х годов. Экспертная система должна будет заменить профессиональные познания человека и его творческую деятельность в различных областях, от медицины до технического конструирования.
Использование программной архитектуры, присущей экспертным системам, облегчало создателям программы ROG-O-MATIC ее построение и модифицирование. В частности, запас необходимых знаний и игровые приемы, используемые Бродягой, они организовали в виде иерархической структуры, состоящей из различных подсистем (см. рисунок).


Экспертные подпрограммы (овалы) и источники знаний (прямоугольники), используемые программой ROG-O-MATIC
Например, подсистема-эксперт высокого уровня под названием Melee (рукопашная) управляет схваткой, когда Бродяга вступает в бой, а другой эксперт высокого уровня - Target (мишень, цель) направляет Бродягу, когда он преследует чудовищ. Оба этих эксперта прибегают к услугам эксперта более низкого уровня Battle (бой), который реализует тот или иной вид атаки или инициирует отступление, если этого требуют обстоятельства. Таким образом эксперт боя обращается иногда за помощью к эксперту Retreat (отступление), а тот в свою очередь неизменно черпает необходимые данные у "источника знаний" Pathс. Здесь действует специальный алгоритм, исследующий окрестности в поисках кратчайшего пути к указанной цели. Вообще существует немало алгоритмов для поиска кратчайшего пути, и в нашем частном случае нужен лишь самый быстрый; он почти все время используется, когда программа ROG-O-MATIC исследует Подземелье Обреченных. Знания об окружающей обстановке, используемые в источнике Pathc, поступают из другого источника - Termap (карта местности), представляющего собой, по существу, структуру данных, куда записываются все сведения о месте, полученные к данному моменту Бродягой в ходе его поисков на данном уровне подземелья. Наконец, информация, содержащаяся в источнике Termap, поступает в него из структуры данных нижнего уровня Sense (восприятие), хранящей все относящиеся к этому источнику выходные данные программы ROGUE.
Прежде чем перечислить функции, выполняемые остальными экспертами и источниками знаний, рассмотрим несколько подробнее, как действует уже упомянутый эксперт боя Battle. Когда начинается бой, эксперт рукопашной схватки Melee обращается к эксперту боя, чтобы тот решил, атаковать или отступать. Так как осторожность всегда сопутствует храбрости, эксперт боя сначала рассматривает, насколько желательным и возможным является отступление. Для этого нужно проверить, выполнены ли некоторые важные условия:

1. Бродяга не должен в данный момент находиться под воздействием напитка, нарушающего ориентацию (иначе он может побежать прямо на чудовище).
2. Попытка отступления будет бессмысленной, если чудовище уже захватило и держит Бродягу.
3. Следует учесть возможность поражения Бродяги в следующем "раунде" рукопашной схватки (в таком случае желательно попытаться избежать конфликта).
4. Эксперт по отступлению может найти путь (т.е. отступление возможно).

Если все четыре условия оказываются выполненными, программа передает руководство по отступлению Бродяги подсистеме, являющейся экспертом по отступлению. Если же необходимые условия для отступления не выполнены, эксперт боя начинает просматривать список возможных атакующих действий:

1. Если существует возможность гибели Бродяги в следующем раунде рукопашной, если чудовише находится поблизости и является видимым для Бродяги и если Бродяга располагает волшебной палочкой, совершающей перенесение предметов (телепортацию), то бродяга направляет палочку на чудовище.
2. Если существует возможность гибели Бродяги в следующем раунде рукопашной, если чудовище находится поблизости и если Бродяга располагает свитком телепортации, то он читает свиток, содержащий магическую формулу против заклинания.

Когда ни одна из этих последних ситуаций не соответствует действительности, то никакой альтернативы схватке с чудовищем нет и программа спокойно выводит Бродягу на бой. Может быть, он достаточно силен, чтобы выдержать по крайней мере один раунд рукопашной. А может быть, он будет убит.

	/*
	* If we can die in 1 turn and we are not at peak strength, we might want
	* to retreat. Don't try to run if we are confused or being held by
	* something. If we are on a door, wait until the monster is next to us
	* (that way we can shoot arrows at him, while he catches up). Don't run
	* away from Dragons!!! They'll just flame you from behind.
	*/
 	if ((die_ in(1) && Hp + Explev < Hpmax) &&
 		!confused && !beingheld && (!on(DOOR) || turns < 1) &&
		!streq(monster, "dragon") &&
		runaway ()) {
		display("Run away! Run away!"); return(1);
	} 
	/*
	* We can't run and there is a monster next to us who could kill
	* us in 1 turn. If we have a scroll of teleportation, read it.
	*/ 
	if (die_ in(1) && turns == 0 &&
		(obj = havenamed(scroll, "teleportation")) >= 0 && reads(obj))
		return (1);

Среди других экспертов, к услугам которых прибегает программа, отметим подсистему обследования Explore, которая решает, что нужно обследовать в следующий момент и какими перемещениями для этого воспользоваться. Есть еще эксперт по снарядам - Missile, управляющий стрельбой из лука, метанием камней, копий и т.д.; эксперт, решающий, какой предмет следует подобрать - Object; эксперт, выбирающий, какие доспехи следует носить - Armor; эксперт, пользующийся магией - Magic, и эксперт - Health, контролирующий состояние Бродяги, решающий, не наступило ли время поесть ему или отдохнуть. Objmap (карта предметов) - структура данных, хранящая информацию о местонахождении и истории всех предметов, найденных в подземелье до сих пор. Invent - перечень предметов, лежащих в рюкзаке Бродяги, a Intern - "устройство", распознающее внутреннее состояние Бродяги и оценивающее его готовность к дальнейшим испытаниям.
Не удивительно, что программа может играть в "Бродягу" очень быстро. Игра обычно завершается (независимо от исхода) за несколько минут машинного времени. До сегодняшнего дня только в Университете Карнеги-Меллона программа сыграла более 12тыс. партий. Как утверждают разработчики программы ROG-O-MATIC, ее искусство в настоящее время превосходит уровень подавляющего большинства первоклассных игроков-людей. Например, в ходе испытаний, проведенных в Университете Карнеги-Меллона в 1983г., средние показатели за три недели, в течение которых проводились игры, у программы оказались выше, чем у любого из 15 лучших игроков университета. ROG-O-MATIC не только превосходит большинство игроков-людей, но и демонстрирует поразительные различия в стиле игры. По словам Молдина, программа действует осмотрительно и без воображения. Она эффективно обследует подземелье, избегая лишних действий, что обычно присуще игрокам-людям. Стиль ведения боя, пожалуй, слишком методичен. Программа упускает некоторые возможности, относящиеся к арсеналу "головореза", в то время как люди часто пользуются ими. Однако в бою важную роль играет везение.
Рассмотрим, например, какова роль фактора удачи в исторической партии, сыгранной программой в Техасском университете в г.Остин в феврале прошлого года. Бродяга, преодолев невероятные опасности, подстерегавшие его на самых нижних уровнях Подземелья Обреченных, нашел амулет Йендора (конечно, под руководством ROG-O-MATIC) в одном из проходов 26-го уровня. Устремившись с этой добычей обратно, Бродяга на 22-м уровне встречается с одним из наиболее грозных чудовиш подземелья, драконом. Бродяга обнажил меч, но дракон опередил его, изрыгнув струю пламени. Однако огонь прошел мимо Бродяги, стоящего в дверном проеме, и, отразившись от стены, поразил самого дракона, нанеся ему тяжелые ожоги. Собрав последние силы, дракон бросился на Бродягу, и тот убил его ударом меча. Затем Бродяга продолжил свое путешествие наверх, расправляясь по пути с менее серьезными противниками. Когда он вышел из подземелья, у него был не только амулет, но и 6913 золотых монет и еше много всякой всячины.
Возможно, читатель, заинтригованный всеми этими описаниями, тоже захочет попробовать свои силы в игре. В качестве упражнения предлагаем ему задачу, составленную Молдином. Помимо того, что эта задача представляет собой неплохое введение в игру, она показывает, насколько трудно было встроить "интеллект" в программу ROG-O-MATIC.

	-------------------
	|.................|
	|..P.......,......|
	|............%.G..|
	|.............@...+
	-------------------

В помещении на 26-м уровне Подземелья Обреченных в настоящий момент находятся: Огненный Змей (Р), Грифон (G) и Бродяга (@). Амулет Йендора (,) лежит на дальней стороне лестницы (%) по отношению к Бродяге. Бродяга должен захватить амулет и убежать по лестнице, избежав стычек с чудовищами, поскольку он уже не способен вынести удары и ранения - у него осталось лишь одно очко. К счастью, Огненный Змей крепко спит, и Бродяге, который носит на пальце магическое кольцо, помогающее ему быть незамеченным, нужно лишь случайно не наступить на Змея, чтобы не разбудить его. Грифон, напротив, находится в бодрствующем состоянии, и, более того, он преследует Бродягу. Хотя Грифон при обычных обстоятельствах не стал бы беспокоить Огеннного Змея, сейчас все его помыслы направлены на то, чтобы оказаться в одной клетке с Бродягой, которого он может разорвать на куски своими страшными когтями. Очередной ход должен сделать Бродяга. Сделав этот ход, Бродяга может попасть в одну из восьми прилегающих клеток, в ту же, что и Грифон после своего хода. Действующий "напрямую" Грифон всегда выбирает кратчайший путь к своей жертве. Если Бродяга прорвется к лестнице, ни Грифон, ни Огненный Змей не причинят ему уже никакого вреда, потому что правила игры запрещают чудовищам преследовать жертву на другом уровне подземелья.

Недостающие иллюстрации взяты из статьи "ROG-O-MATIC: A Belligerent Expert System" ( www.robot-club.com/lti/pub/rgm84.htm ). Исходники лежат на www.roguelikedevelopment.org/archive/index.php .- G.