Текст книги "Программирование игр и головоломок"

Автор книги: Жак Арсак

сообщить о нарушении

Текущая страница: 1 (всего у книги 16 страниц)

Жак Арсак
Программирование игр и головоломок

Предисловие

«Играйте с компьютером, это захватывает…»

«Нет ничего увлекательнее создания собственных компьютерных игр»…

Это – два привлекательных лозунга, взятые из рекламы микрокомпьютеров. Поэтому самое существенное – это создавать игру.

КТО САМ ПРОГРАММИРУЕТ СВОИ КОМПЬЮТЕРНЫЕ ИГРЫ, НАСЛАЖДАЕТСЯ ДВАЖДЫ[1]1
  Я здесь совершаю плагиат по отношению к поговорке жителей плоскогорья Высоких Вивар, которая звучит так: кто сам пилит свои дрова, согревается дважды.


[Закрыть]

Я уже проводил небольшое расследование в SICOB в 1984 году. Во многих торговых предприятиях я представлялся как отец, который хочет подарить своему сыну микрокомпьютер. Мне объяснили, что именно нужно купить и во сколько это мне обойдется. Затем я спрашивал об играх. И вот что, приблизительно, там происходило.

«—Так он сможет со всем этим играть?

– Да нет же, месье. Чтобы он мог играть с компьютером, он должен покупать кассеты с играми.

– Кассеты с играми? Я думал, что компьютер… А сколько стоит кассета?»

Продавец называет мне цену, которую вы, должно быть, знаете. Я отвечаю:

«– И сколько игр на кассете?

– Одна, месье.

– Но тогда двадцать игр стоят дороже самой машины! А я слышал от сведущих людей, что на компьютере интереснее всего создавать игры самому.

– Для этого, месье, нужно уметь программировать.

– Но по телевизору твердят, что это очень просто. Мой сын, должно быть, может научиться?

– Да, месье. У нас есть кассета с Бейсиком.

– Кассета с Бейсиком! Бейсик – это и есть программирование?

– Нет, месье. Чтобы уметь программировать, нужна еще вот эта кассета с языком ассемблера…»

Я удалялся, исполненный отвращения, жалкий истец отцов семейств! В другом торговом заведении я отважился утверждать, что я слышал от сведущих людей, что некоторые журналы публикуют совершенно готовые игровые программы.

«– Да, это так. Но эти игры плохо сделаны. Они не являются профессиональной работой, как наши кассеты, где вывод изображения на экран тщательно отработан. Кроме того, очень неприятно набирать тексты этих игр на клавиатуре. Так что все это не очень серьезно, что бы об этом ни говорили…»

На этот раз я поверил, что мне говорят правду. Опубликованные таким образом игры весьма посредственны по качеству. Я не поленился внимательно прочесть некоторые из них (см., например, головоломку 28). Чаще всего они плохо составлены и так плохо прокомментированы, как будто автор хочет помешать читателю понять их. Стратегия этих игр иногда более чем примитивна: я видел игру ТИК—ТАК—ТОК, где компьютер случайным образом выбирал свой игровой ход… Это издевательство над читателями!

Во всем этом совершенно отсутствует творчество. Реклама трубит: «Создавать – это увлекательно!». Но на практике все делается так, как будто подростки неспособны что-либо создавать. И им не помогают начать делать что-нибудь творческое.

Чтобы восполнить этот пробел, я и написал эту книгу. Многие подростки обучены программированию – в лицее (причем не только в таких лицеях, которые официально предоставляют обучение со специализацией по информатике, устраивая курсы по программированию), в клубах и на каникулах – с родителями, с друзьями, по книгам… Но вот что программировать на компьютере? Игры? Какие? Примеры, публикуемые в журналах и книгах, непонятны. Как они могут хоть на что-то вдохновить? А если и посмотреть вокруг, что можно найти? Шахматы, Отелло, вошек? Это слишком трудно…

Поэтому я собрал здесь описания некоторых игр, которые есть в продаже, чаще всего на Бейсике, для которых не нужны графические возможности компьютера. Я сам все эти игры реализовал на микрокомпьютере, имеющем только алфавитно-цифровой черно-белый экран и не имеющем ни светового пера, ни мыши, ни планшета. Трудность программирования обозначается звездочками «*». Начинайте с игр без звездочек. К остальным вы перейдете позже. Каждая игра допускает многочисленные вариации, которые вы легко изобретете.

Для того чтобы менее мужественные читатели могли избежать искушения сразу же читать все подробности изготовления программ, в первой части книги условие игры обычно излагается вместе с некоторыми указаниями. Если этих указаний вам недостаточно, иначе говоря, если после размышления и возможных обсуждений с товарищами вы не видите, как тронуться с места, вас выведет из затруднений «первая помощь». Если же вы опять упретесь в какую-нибудь трудность, то третья часть книги должна позволить вам достичь цели. Смелее вперед: СОЗДАВАЙТЕ.

Игры привлекательны не только для молодых людей от 14 до ? (а до скольких?). Я знаю многих взрослых, любящих играть (и сам люблю). У меня много коллег, для которых программирование и есть игра – как для меня. Я написал эту книгу для всех молодых людей от 14 до 77 лет, которые любят играть с компьютером или которые любили бы это делать, если бы средство для этого им было предоставлено.

Серьезные журналы публикуют математические развлечения для «порядочных людей». Продаются книги с логическими головоломками. Продаются обзоры стратегий. Применение компьютеров полностью обновило весь этот круг вопросов. Всем тем, кто интересуется головоломками, я предлагаю здесь новую форму головоломок: задача, решение которой нужно найти на компьютере, – это настоящая головоломка. Они бывают трех основных типов:

некоторые головоломки интересно программировать (например, зашифрованные операции, господин S и господин P, пентамино…);

некоторые задачи имеют очень простой вид, но доведение решения до программы является настоящей головоломкой (например, переставить две части вектора, найти наибольший белый прямоугольник в решетке кроссворда). Это – совершенно новый тип задач, тесно связанный с компьютером;

наконец, последний тип – настолько трудный, что я уменьшил набор его примеров, выбрав их из поистине неисчислимого множества, – связан с тем, что я говорил в начале. Вам дана программа (в нашей книге – написанная настолько хорошо, насколько это возможно), но без комментариев. Скажите, что она делает.

Трудность головоломки обозначается вопросительными знаками. Есть головоломки с довольно простыми решениями, но деликатным программированием: «?***», и есть ужасные головоломки с легким программированием: «???». Выбирайте!

Эта книга будет полезна и всем тем, кто занимается подготовкой подростков по информатике: преподавателям лицеев и колледжей, руководителям клубов или каникулярных занятий.

Я не привожу никаких решений, за исключением нескольких настолько классических случаев, что их решение исследовано всюду, или задач, решение которых является образцом, который часто встречается и который нужно знать. Изучите сначала их.

Первый раздел – немного особенный. Каковы бы ни были ваши склонности – начните с него; он даст вам инструмент, необходимый для почти всех игр и немалого числа головоломок (формирование ситуаций случайным образом).

Если вы уже перелистали книгу, то вы, может быть, заметили в ней и кое-что, похожее на математику, Признаюсь! Несколько головоломок в ней – арифметические, и их решение требует вычислений. В большей части эта книга доступна и людям, не имеющим никакой специальной математической подготовки, даже тем, кому вся эта математика внушает страх и отвращение.

Я сказал все. Теперь – вам ИГРАТЬ, вам СОЗДАВАТЬ…

Обозначения

Вот конструкции, используемые в программах этой книги.

Оператор присваивания. В нем используется знак «:=»

i := i + 1

Вот его аналоги на других языках:

Бейсик: LET I = I + 1

LSE: I ← I + 1

Паскаль: I := I + 1

Условный оператор имеет вид

ЕСЛИ условие ТО последовательность операторов

КОНЕЦ_ЕСЛИ

При работе условного оператора вначале проверяется условие. Если оно имеет значение ИСТИНА, то выполняется последовательность операторов, заключенная между ТО и КОНЕЦ_ЕСЛИ. КОНЕЦ_ЕСЛИ играет роль закрывающей скобки, избавляющей от применения разделителей DEBUT FIN, как на LSE, или BEGIN END, как в языке Паскаль. При работе оператора

ЕСЛИ условие ТО последовательность операторов

  ИНАЧЕ последовательность операторов

КОНЕЦ_ЕСЛИ

вначале проверяется условие. Если оно имеет значение ИСТИНА, то выполняется последовательность операторов, заключенная между ТО и ИНАЧЕ, а если условие имеет значение ЛОЖЬ, то выполняется то, что содержится между ИНАЧЕ и КОНЕЦ_ЕСЛИ. Снова, как и выше, нет нужды в DEBUT FIN.

Цикл

ПОКА условие ВЫПОЛНЯТЬ

  последовательность операторов

ВЕРНУТЬСЯ

выполняет последовательность операторов, заключенную между скобками ВЫПОЛНЯТЬ – ВЕРНУТЬСЯ, пока условие справедливо. Он эквивалентен циклу LSE

FAIRE номер строки ПОКА условие

  последовательность операторов

n замыкающая строка

или циклу на языке Паскаль

WHILE условие DO

  BEGIN последовательность операторов END

Цикл

ВЫПОЛНЯТЬ

  последовательность операторов, содержащая слово КОНЧЕНО

ВЕРНУТЬСЯ

работает так:

Последовательность инструкций, заключенная между скобками операторов ВЫПОЛНЯТЬ – ВЕРНУТЬСЯ, повторяется неограниченно. Слово КОНЧЕНО означает, что цель цикла достигнута, повторяемая работа закончена. На этом цикл останавливается и программа продолжается со следующего за циклом оператора В английских книгах и статьях вместо КОНЧЕНО обычно пишут EXIT: выйти из цикла (также сделано и в языке Ада). Но EXIT вызывает идею действия: выхода. Я предпочитаю ему слово КОНЧЕНО, которое лучше отражает идею не действия, а ситуации: я достиг цели цикла, с ним все кончено.,..

Простых эквивалентов этого цикла на Бейсике, LSE или Паскале нет. Можно применить операторы ALLER EN или GO ТО для симуляции такого цикла.

– На Бейсике можно использовать дополнительную переменную Z:

FOR Z = 1 ТО 0 заменяет ВЫПОЛНЯТЬ

LET Z = 0 заменяет КОНЧЕНО

NEXT Z заменяет ВЕРНУТЬСЯ

Кроме того, нужно перепрыгнуть в цикле все, что стоит после слова КОНЧЕНО, т. е. после оператора LET Z = 0. Так как это можно сделать с помощью GO ТО, то я считаю предпочтительным использовать таким образом GO ТО для циклов. Если ваш язык не структурирован, то красивых циклов вы никогда не получите…

– На языке Паскаль используйте булеву переменную z, которой до начала цикла присвоено значение TRUE, и тогда цикл примет вид

WHILE z DO BEGIN END

Слово КОНЧЕНО придется заменить оператором z := FALSE, включенным в конструкцию так, чтобы сделать этот оператор последним выполняемым оператором цикла. Если структура языка нехороша…

Цикл

ДЛЯ i := exp 1 ШАГ exp 2 ДО exp 3 ВЫПОЛНЯТЬ…

ВЕРНУТЬСЯ

повторяет последовательность операторов, заключенную между ВЫПОЛНЯТЬ и ВЕРНУТЬСЯ, придавая i значения из арифметической прогрессии с разностью exp 2 (постоянная величина в данном цикле), начиная с exp 1 и останавливаясь на exp 3, Если шар равен 1, то фрагмент ШАГ 1 можно опустить.

Часть I. Условия задач

1. Случайные числа

Генерация случайного числа

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

Некоторые языки содержат функцию, значение которой есть непредсказуемое число в данном интервале. Если ваш компьютер использует LSE, достаточно набрать на клавиатуре

? ALE(0)

чтобы получить в ответ непредсказуемое число между 0 и 1, которое может рассматриваться как полученное случайным образом.

На языке Бейсик команда RND(0) дает тот же эффект при условии, что предварительно выполнена инструкция RANDOM. Но Бейсик – это скорее общее имя для целого класса языков, чем обозначение совершенно определенного стандартизованного языка, не меняющегося от одной машины к другой. Так что сверьтесь с описанием к вашему компьютеру…

Если используемый вами язык допускает описанные выше или аналогичные возможности, то получить случайное число в интервале (0, 1) – это никакая не головоломка, это тривиально.

Но если в языке такой возможности нет,_; то это больше чем головоломка, это невозможно. Предположим, что мы сделали программу, производящую такое число. Эта программа не может иметь исходных данных, иначе это не она вытаскивает, случайное число, а именно вы при введении данных… Если же у нее нет данных, то она действует, исходя из констант. Но тогда нет переменных элементов, и последовательные запуски программы дают совпадающие результаты. Как же вы получите с помощью такой программы случайное число?[2]2
  Строго говоря, эти рассуждения применимы к любой программе, написанной на любом языке, если только эта программа не использует никакой внешней информации в качестве исходных данных. В качестве такой внешней информации удобнее всего использовать что-нибудь связанное с временем: число изменений напряжения в сети с момента последнего включения вашего компьютера или число секунд с момента его покупки, если ваш компьютер снабжен внутренними энергозависимыми часами (на литиевой батарейке), и т. п. Обычно, на каком бы языке вы ни работали, у вас есть возможность прочесть показания внутренних часов компьютера (посмотрите в документации, как работать с таймером). – Примеч. ред.


[Закрыть]

Поэтому если ваш компьютер не допускает функции, дающей стохастическое число, я вижу только одно решение[3]3
  См. предыдущую сноску. – Примеч. ред.


[Закрыть]: введите сами случайное число в ваш компьютер. Как это сделать? Вот предложение. Вы берете колоду из 52 карт, перетасовываете. Затем вы делите колоду на верхнюю и нижнюю части и берете из нижней части три верхние карты. Небольшая и очень простая программа читает три целых числа x, y, z. В качестве значений этих целых чисел вы задаете численные значения трех выбранных карт, считая туза за 1, валета – за 11, даму – за 12, короля – за 13. Компьютер вычисляет значение

(((x − 1)/13 + у − 1)/13 + z − 1)/13.

Например, если вы достанете, как только что случилось со мной, семерку бубен, десятку червей и еще шестерку бубен, то

x =7 y= 10 z = 6

и компьютер получит 0.440601.

Эго значение не является воистину непредсказуемым. Как только вы достанете карты, вы уже сможете понять порядок величины результата. С другой стороны, таким способом вы не сможете получить более 13³ = 2197 различных чисел. Но этого на самом деле достаточно для приложений, которые мы рассматриваем в этой книге. А если вы и в самом деле хотите получить что-либо непредсказуемое, прочтите следующий раздел.

Непредсказуемые числовые последовательности

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

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

Может случиться, что используемый вами язык предоставляет эту возможность непосредственно в виде одной из конструкций языка.

Так, на LSE команда ALE(x) дает число, лежащее в интервале (0, 1), значение которого зависит от x, но непредвиденным образом и, кроме того, не специфицированным в языке: значение будет различным на разных машинах. Если вы трижды зададите один и тот же вопрос

? ALE (0.1)

вы каждый раз получите один и тот же ответ, но между ALE(0.1) и ALE(0.2) нет простого соотношения.

На Бейсике функция RND играет ту же самую роль. Она порождает непредсказуемую последовательность, значения которой зависят только от начального числа – оно одно и то же для данного компьютера. Инструкция RANDOM дает случайное число и ставит его начальным элементом последовательности, что позволяет порождать различные последовательности.

Может быть, интересно посмотреть, как можно строить подобные последовательности. Вот метод, предложенный А. Энгелем [ENG]. Если x – число между 0 и 1, то следующий за x элемент последовательности есть

дробная часть ((x + 3.14159)⁸)

Конечно, восьмая степень вычисляется тремя последовательными возведениями в квадрат! Она дает число между 9488 (для x = 0) и 86564. Очень небольшое изменение x вызывает сильное изменение (x + π)⁸, и, в частности, оно может перейти через ближайшее целое, так что новое значение (дробная часть результата) может оказаться меньше предыдущей.

Возьмем, например, x = 0.52000; тогда

(x + 3.14159)⁸ = 32311.5437

так что за 0.5200 следует 0.5437.

Но для x = 0.52005 имеем

(x + 3.14159)⁸ = 32315.0736

и за 0.52005 следует 0.0736.

Так как мы берем дробную часть, то полученное число, разумеется, лежит между 0 и 1.

Упражнение 1. Поведение последовательности.

Речь идет о том, чтобы увидеть, как ведут себя числовые последовательности, порожденные таким образом. Для этого вычислим большое число членов последовательности, порожденной своим первым элементом. Поместим каждый из этих членов в один из 50 интервалов длины 0.02, составляющих интервал от 0 до 1. Выведем число членов последовательности, попавших в каждый из этих интервалов. Если числа из последовательности равномерно распределены в интервале (0, 1), мы должны будем обнаружить, что их количество в разных интервалах имеет ощутимую тенденцию к постоянству.

Составьте программу для проверки зтого утверждения. Начальное значение может, например, вводиться в начале каждого вычисления.

Упражнение 2. Поиск других последовательностей.

Число π, использованное при вычислении наших последовательностей, не обладает никаким специальным свойством, и можно спросить себя, действительно ли выбор этого числа является наилучшим возможным. Числа (x + π)⁸ довольно велики, а берем мы от них только дробную часть. При этом мы отбрасываем значащие цифры целой части, и – поскольку вычисления на компьютере проводятся с фиксированным количеством значащих цифр – на дробную часть остается относительно небольшое количество цифр. Предположим, что числа представляются с помощью 24 двоичных цифр. Нужно 14 двоичных цифр, чтобы записать 9488, так как

2¹³ = 8192 < 9488 < 2¹⁴ = 16384

и 17 цифр, чтобы записать 86564, так что остается лишь от 7 до 10 двоичных цифр на дробную часть.

Используя (x + a)⁸ вместо (x + π)⁸ с меньшим значением a, можно ожидать сохранения большего количества значащих цифр для дробной части. Но нельзя взять a слишком близко к 1, так как тогда распределение чисел в интервале (0, 1) окажется плохим. Можете ли вы объяснить, почему?

Например, почему нельзя взять a = ⁸√2?

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

– постоянной а,

– начального значения последовательности.

На своем микрокомпьютере я выяснил, что а = 1.226 дает достаточно хорошие результаты. Но это наблюдение может меняться от машины к машине, так как все это очень чувствительно к способу, которым осуществляются умножения; в последней двоичной цифре результата умножения есть неопределенность, существенно влияющая на рассматриваемый процесс.

Азартные игры

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

Упражнение 3. «Орел» или «решка».

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

– она спрашивает вас, что вы загадали, «орла» или «решку», и читает ваш ответ;

– она порождает случайное число и затем сообщает вам, выиграли вы или проиграли.

Единственная трудность; генератор случайных чисел дает вам, быть может, число, содержащееся между 0 и 1 (это так в случае функции ALE языка LSE и для генератора из разд. 1.2. Имеются противоречивые сведения о языке Бейсик, возможности которого существенно меняются от машины к машине). Следовательно, нужно перейти от вещественного числа в интервале 0 : 1 к чему-либо принимающему не более двух значений, например 0 и 1. Вы сопоставляете по своему усмотрению «орла» одному из них, а «решку» – другому.

Если генератор случайных чисел действует не лучшим образом, то игра может оказаться нечестной, и одна из возможностей – «орел» или «решка» – может выпадать чаще, чем другая.

Сделайте программу, реализующую большое число испытаний, и подсчитайте число выпаданий орла.

Упражнение 4. Игральные кости.

Вместо игры в «орла» или «решку» заставьте компьютер играть в кости. Напишите программу, симулирующую большое число выбрасываний двух костей, и подсчитайте, сколько раз будет выпадать каждая комбинация от 2 до 12. Знаете ли вы, сколько раз должна выпасть каждая из них, если генератор случайных чисел идеален, а число бросаний действительно велико?

Перед вами – та же задача, что и в предыдущем упражнении: перейти от некоторого числа в интервале (0, 1) к целому числу от 1 до 6 включительно. Но если вы знаете, как сделать это для 2, то вы сможете сделать и для 6…

Игра 1. Фальшивые кости.

Ну да, такое еще бывает; есть еще такие люди, которые мошенничают и используют поддельные кости. Нужно быть в состоянии заметить это и,– как в любом хорошем вестерне, устроить грандиозную драку с мошенником.

Здесь мошенником пусть будет компьютер. Он играет одной-единственной костью и бросает ее столько раз, сколько вы требуете. Он дает вам число выпаданий единицы, двойки, …, шестерки. Вы сообщаете ему, верите ли вы, что кости поддельные, и если да, то какая грань выпадает чаще других. Компьютер отвечает вам, выиграли вы или проиграли, и случайным образом оценивает ваш выигрыш. Совершенно ясно, что если вы потребуете 40000 бросаний, то у вас будет больше шансов обнаружить истину, чем если вы потребуете 20 бросаний…

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

Вспомогательная задача: выбрать функцию оценки для выигрыша.

? Игра 2. Стратегия для одной игры в кости.

Ж.-К. Бейиф [BAI] предложил игру в кости с двумя игроками. Каждый игрок в свою очередь хода бросает кость столько раз, сколько хочет. Если он не выбрасывает единицу, то он записывает за этот ход сумму выпавших за бросания этого хода очков. Если же он выбрасывает единицу, то он не записывает ничего (и его ход кончается с выбрасыванием единицы). Выигравшим считается тот, кто первым наберет (или превысит) 100 очков.

Составьте программу, которая позволит человеку играть против компьютера. Эта программа реализует бросание кости. На своем ходе она честна и не мошенничает. На вашем ходе она бросает кость и сообщает^ что выпало, а вы требуете следующего бросания, если вы хотите играть дальше.

Задача о стратегии ясна. Вы можете, например, бросать кость ровно один раз. У вас хорошие шансы увеличить свою сумму, но на небольшое число очков (от 2 до 6). Если вы делаете несколько бросаний, вы увеличиваете шанс получить большую сумму, но вы увеличиваете и риск выбросить единицу. Стратегия играющего против компьютера – это его проблема, и программа компьютера во всех этих рассмотрениях не участвует. Она играет по команде человека, он говорит, хочет ли он продолжать – под его личную ответственность.

Напротив, программа должна быть снабжена стратегией для управления игрой компьютера. Возможностей много. Выбирать следует вам.

Программирование этой .игры представляет двоякий интерес;

– нужно придумать стратегию для компьютера;

– у вас есть возможность экспериментировать. Если компьютер снабжен некоторой стратегией, то вы можете играть против него с другой стратегией и посмотреть, кто выигрывает…

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