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

Старая книжечка «Программирование Игр и Головоломок» — наверное попадалась многим из нас. Изданная в 1985 в наши дни она смотрится архаично и сподвигнуть кого-то программировать приведённые в ней игры — затруднительно. А жаль 🙂

Попробуем немного освежить этот материал! Немного познакомимся с примерами из книжки — и поговорим о возможной реализации таких игр — в виде задач, HTML-страничек — либо в виде HTTP-сервера — так что любопытствующие смогут даже попробовать написать код и поиграть против онлайнового «злого гения» (ну это преувеличение).

История

Жак Арсак — профессор и преподаватель программирования из Франции, из времён когда компьютеры были большими а их возможности — очень скромными 🙂 Он оставил значительное наследие в виде десятка-другого книжек — но на русский переведена только одна, упомянутая выше. Кстати из её французского названия мы узнаем что casse-tete (кастет) — это головоломка.

Арсак ратует за обучение программированию через написание игр. Он жалуется: подростки обучаются программированию в школах и университетах — но не знают что программировать!

Удивительно — прошло 40 лет а ситуация в этом смысле не очень изменилась, не так ли? На курсах дети старательно переписывают какие-то таинственные инструкции, мамочки восторженно смотрят на (а то и показывают знакомым) нечто похожее на 3-мерную игру (или видео с роботом) и платят денежки. За пределами курсов креатив напрочь выветривается из головы ребёнка 🙂

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

Таким образом эта книжка не была пособием по компьютерной графике (как например «Секреты Программирования Игр» — Андре Ламот — из неё друзья старательно копировали код 3d лабиринта — культовая тогда и почти малополезная сейчас) и другим техническим средствам. Здесь же больше про идеи, логику, стратегии и т.п. — эти вещи не устаревают так быстро.

Проблема

Мне всегда хотелось «подсунуть» похожий материал, идеи — современным ученикам. Вопрос — как это сделать. Ниже я покажу примеры своих попыток, вкратце их можно сгруппировать так:

• игры, превращаемые в программистские задачи

• pastebin для создания простых игр

• игры, в которых нужно написать программу чтобы обыграть сервер

• игры, в которых нужно написать программу чтобы обыграть чужую программу

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

Вкратце о книге Ж.Арсака

Немного расскажу о примерах из книги на случай если вы её не читали. Не весь материал может показаться захватывающим. Например какое-то внимание уделено именно головоломкам — но программировать решение криптарифмов мне никогда не было очень интересно. Или Ханойские Башни — когда понял принцип — писать код для них не захочется.

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

Побег из рушащегося замка

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

O - - - - - - - - - - - - - - - X - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - X X - - - X X - - - - - - - - - - - - - - - - - - - - X - - - - - - - - - - - - - - - T

Тони и Жюли стартуют на мотоцикле из правого нижнего угла (буква T) — а выход из подземелья в левом верхнем (буква O) — на каждом шаге можно сдвинуться по горизонтали или вертикали на 1 позицию. После каждого хода происходит обрушение нескольких фрагментов потолка — они добавляют препятствия (буквы X) — а если падают на клетку где находятся в данный момент наши герои — игра заканчивается сразу.

Несколько других игр приводимых мсье Арсаком я упомяну ниже среди примеров — в отличие от эпопеи с Тони в них можно будет в том или ином виде поиграть:

• Ним

• Пешеходный переход

• Шадок и гиби

• Лиса и Гуси

А некоторые и не упомяну — потому что забыл — но они присутствуют на сайте (например так дело обстоит с Connect-Four). Резюмируя — я бы рекомендовал не полениться и скачать-полистать книжку. Несмотря на не слишком удачный (кажется) перевод и фрагменты которые могут оказаться устаревшими или не очень интересными лично вам — там всё-таки очень много занятных игровых идей.

Игры, превращённые в задачи

Лет 10 назад я стал сочинять собственный сайт с задачами (немного рассказывал уже — теперь опенсорсный) — и мне конечно хотелось кроме упражнений на поиск максимума или виды сортировок добавить и что-то вроде игр из книжки Арсака.

Одной из первых попыток был «Пешеходный Переход»: игрок стоит перед 8-полосной магистралью, по которой мчатся машины (на каждой следующей полосе всё быстрее). Игрок движется по вертикали — может вернуться на предыдущую полосу, шагнуть на следующую, или остаться на месте. Цель, конечно, оказаться на той стороне дороги. Выглядит это так:

Здесь игрок обозначен символом @ — видите, он уже прошёл половину дороги — но в данный момент если он шагнёт дальше, на 6-ю полосу или останется на 5-й — его раздавят приближающиеся машины (символы $) — единственный шанс остаться в живых — отступить на 4-ю полосу. На странице задачи вы можете поиграть в эту игру прямо сейчас в простенькой джаваскриптовой реализации. Клавиши Q, A, Z служат для движения по полосам. https://www.codeabbey.com/index/task_view/crossing-the-road

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

Задача не очень сложная, но воплотив её я почувствовал что это всё-таки «не то» — превращается в упражнение на «поиск в ширину» по позициям возникающим в игре.

К этому же классу относятся и «космические» игры на физическую симуляцию — например классическая «Мягкая Посадка» — в которую играли ещё на программируемых калькуляторах. На сайте она тоже есть (под названием Safe Landing).

Игры-челленджи

Следующая идея состояла в том чтобы сделать задачи, у которых результат не просто проверяется на правильность, а может быть хуже или лучше. Получалось что пользователи пишут программы пытаясь решить задачу лучше других. И тут неплохо подходили некоторые виды игр расчитанные на 1 участника, например «Цветные Кубики» — вы наверное знаете её — на квадратном поле усеянном разноцветными квадратами надо щёлкать и убирать смежные наборы одноцветных квадратиков стараясь набрать больше очков (за большие наборы бонус начисляется пропорционально квадрату количества).

Если поле достаточно большое, надежды на точное алгоритмическое решение по-видимому нет. Получается наверху таблицы окажется либо тот кто написал более остроумную логику — либо тот у кого больше времени обсчитывать входные данные (они всегда неизменны). Здесь на странице задачи тоже есть интерактивная реализация из которой можно понять принцип. https://www.codeabbey.com/index/task_view/color-cubes-advanced

К сожалению для такой реализации подходят только игры «для одного» (или те которые можно к ним свести). Поэтому я стал думать дальше.

Против вас играет HTTP-сервер

Хотелось воплотить полноценные игры для 2 игроков. Но изначальный принцип сайта был в том что задачи можно решать на любом языке. Как же я могу написать «второго игрока» которого можно подключить к программе на любом языке? И как проверять что они там наиграли?

Пусть код «второго игрока» будет жить на сервере, играть по HTTP а результат игры сообщать в зашифрованном виде. Программист заодно научится отправлять запросы на своём любимом языке! В этом духе были реализованы несколько известных и не очень классических игр: Ним, Лиса и Гуси, Шпионы (также «Охота на Лис»), Wumpus и другие. В качестве примера посмотрим на игру «Шадок и Гиби» — идея из той же книги Арсака.

На планете Шадоков испытания ракет продолжаются, постоянно кончаясь неудачами. Великий колдун сказал что не хватает транзисторов в системе безопасности. Транзисторы добывают на планете Гиби — они там растут вроде цветов. И вот в огород с транзисторами забрался Шадок с целью набрать 100 штук. Гиби очень умные благодаря своим шляпам — догадались в чем дело и решили позабавиться. Каждый раз когда Шадок идёт к какому-нибудь цветку с транзисторами — они бросаются туда же с целью сорвать транзисторы раньше него.

Эта немного бредовая история придумана автором по мотивам французского мультсериала про Шадоков — можете загуглить, хотя понять там что-нибудь сложно. Ну так вот игра — прямоугольное поле, цветы обозначены цифрами, показывающими сколько на них растёт транзисторов. Гиби обозначены буквами g а шадок буквой S, например:

- - 7 2 - - - - - - - - - - - - - - - - - - - - - - - g g - - 1 - - - - - g - - - - 8 - - - - - - - - - - - - - - - - - - - - - - - - 5 - - - - - 2 - - - - - - - - g 5 - - - - - 7 - - - - - - - - - - - - - - 1 - - 4 9 - - 7 - - - - - - - - - - - - - - - 4 - - - - 8 - - - - - 2 - - - - - - - - - - 5 - - 1 - - - - 6 g - - - - - - - - - g - - - - - - - - - - - - 2 - g - - 7 - - - - - - - - g - - S - - - - - 2 - - - - - g - g - - - - - - g - - - - - - - - g - - - - - - - - - - g - - - - - - - - - - 4 - - - - - - - - - - - - g - - - g - - - - - - - - - - - - - 7 g - - - - - - - - - - - - - - - - - - - - - - - - - 8 - - - - - - - - g g - - g - - - - - - - - - 5 - - g 4 8 - 9 - - - - g - - g - - - - - - - - - - - - - - - g - - - - - - - - - - 1 - - - - - g 6 - 5 4

Цель — собрать 100 транзисторов за 40 ходов или быстрее. Можно написать программу чтобы играть против сервера «в ручном режиме» для начала. Однако чтобы задачу нельзя было пройти таким образом установлено ограничение по времени — выиграть нужно за 60 секунд (с начала новой игры).

Эти игры с сервером имеют то неудобство что сначала надо научиться посылать HTTP-запросы — однако разобравшись с этим раз код можно переиспользовать в других играх. Из бонусов — по ходу того как программа «сражается» с сервером, можно визуализировать ход игры — и это может быть попросту увлекательно: например, я заметил что один из топовых пользователей перезапускает игру много раз подряд — и спросил что происходит — он пояснил:

My solution for #251 includes a coloured representation of the board after every move, and I quite enjoy seeing the spies (they are red, but that’s purely coincidental 🙂 appearing during the game.

Моё решение задачи 251 (Шпионы) содержит цветное отображение игрового поля после каждого хода — и мне очень нравится смотреть на то как постепенно обнаруживаются новые и новые шпионы (они отображены красным — но это чистое совпадение) — по ходу игры.

На страницах этих задач нет «интерактивчиков» как на предыдущих — поэтому для желающих просто пусть будет ссылка на их общий список — первым в нём идёт не столько игра сколько упражнение (Say 100) — чисто чтобы разобраться с отправкой запросов.

Игры против чужого кода

У игр с HTTP-сервером нашлось два недостатка:

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

• программист может видеть ход игры и для некоторых игр это позволит слишком легко догадаться о стратегии.

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

В то же время уже существовали задачи на Брейнфак и на Ассемблер-4004. Для них были написаны простые интерпретаторы на PHP и Python — при отправке задачи на сайт интерпретатор выполнял код и можно было проверить вывод.

Я решил попробовать этот же путь — изначально добавил интерпретатор Scheme — с ним появились например игры Hamurabi (экономический симулятор) и Maze Mapping Robot (нужно написать код для робота который проползёт весь лабиринт и распечатает его структуру). Прежде чем идти дальше, посмотрим на Hamurabi — это очень древняя компьютерная игра в которой вы царь (Хаммурапи) — и у вас есть три вида ресурсов: люди, земля и зерно. Зерно нужно чтобы засевать землю и кормить людей. Люди нужны чтобы землю обрабатывать — тогда вырастет больше зерна. За зерно можно купить землю и т.п.

Ваша задача — править 10 лет и постараться увеличить своё богатство и не уморить народ с голоду. На странице задачи опять же есть интерактивная реализация на которой можно потренироваться вручную: https://www.codeabbey.com/index/task_view/hamurabi

Естественно всё это упёрлось в то что Scheme хотя и по-своему интересный язык (упрощенная версия LISP) — но с непривычки писать на нём что-то масштабное сложновато. Решение для Hamurabi может содержать всего пару строк — но над механикой лабиринта для робота я сам возился дня три.

Поэтому следующими шагами этого эксперимента были внедрен BASIC (собственная реализация на PHP, немножко на стероидах, выложена на гитхаб) — на нём например предлагалось написать симулятор вывода космического корабля на околоземную орбиту. Но всё же и Basic это по нашим временам изврат, поэтому третьей попыткой стало внедрение Lua. Её я заодно скомпилировал в JavaScript что позволило запускать её и в браузерной странице — благодаря чему пользователь может до отправки протестировать свой код на подготовленном интерактивном виджете. В частности так сделана игра с отражением атаки пришельцев (о ней я вкратце упоминал в посте) — нужно написать код для «следящей системы» пушки стреляющей по кораблям инопланетян.

PasteBin для игр

На этом месте возникла идея не связанная с задачами. Раз у меня уже был интерпретатор Lua работающий с браузерным JavaScript — то можно воплотить возможность создавать собственные простенькие игры — с отрисовкой на canvas-е и простейшей реакцией на клики/тапы по экрану.

Конечно нужно чтобы пользователь мог сохранять и шарить свои «игры». Это несложно было сделать по аналогии с PasteBin или скорее JsFiddle.

Более того на основе такой штуки оказалось возможно написать что-то вроде серии небольших уроков.

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

Для желающих потрогать «руками» — вот демонстрашка («нулевой» из недописанной серии уроков-инструкций по этой фиче).

Конечно в эпоху Roblox и подобных штук не так просто будет кого-то удивить простыми играми на Canvas-е. Тем не менее её наверняка можно использовать в образовательном процессе и пр.

На вопрос почему Lua а не Python — в основном потому что Python гораздо больше и компактной реализации на JS я не нашёл (хотя Brython пробовал).

Игры друг против друга — Арена

Тем кто помнит Robot Battles или разнообразные Google AI Challenges наверное объяснять идею не нужно. В предыдущем разделе мы говорили о ситуации когда программист пишет код чтобы «переиграть» решение сделанное, например, автором сайта. Но ведь можно сделать так чтобы программисты состязались попарно друг против друга!

С некоторыми усилиями я предпринял попытку реализовать что-то подобное на своём сайте. Игра вновь найдена у Арсака — она очень простая:

Игроки по очереди бросают один кубик. Сумма очков за ход копится пока игрок не решит передать ход оппоненту (в этом случае сумма прибавляется к текущим очкам игрока) — или пока он не выкинет единицу (в этом случае сумма за ход сгорает).

Сайт позволяет «запускать» своё решение против решения другого игрока. Вот так выглядит текущая таблица результатов игр друг против друга:

Страница самой задачи (там тоже есть JS-реализация чтобы попробовать живьём) https://www.codeabbey.com/index/task_view/dice-black-jack

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

• в отличие от одноразовых мероприятий (вроде Google AI Challenge) хочется чтобы такое «соревнование» продолжалось постоянно, для чего нужно каждое новое решение заставлять периодически «сражаться» с остальными, пересчитывать таблицу результатов и ещё много о чем подумать (например, что происходит когда чьё-то решение перезагружают)

• всё это будет выглядеть значительно интереснее если добавить визуализацию — для этого надо например выгружать лог игры обратно в веб-интерфейс — в общих чертах понятно — но в деталях как обычно много тумана

Заключение

Хотя большинство из идей которые я описал выше не оказались слишком популярными (по крайней мере пока) — сама работа в этом направлении постепенно приносит новые идеи. В частности с появлением у сайта собственного sandbox-сервера (из-за того что сломался сторонний) появилась и возможность запускать пользовательский код на нескольких популярных языках.

Недавно эта фича была для эксперимента использована в задаче где нужно поставить мат королём и ладьёй — играя против скрипта пытающегося убежать одиноким королём.

Кстати с этой задачей я сам (в очередной раз) ощутил как интересно программировать логику игры. Дело в том что в подобных задачах написать код для каждой из двух сторон — неравноценная задача. Убегать одиноким королём проще. Поэтому создав задачу на сайте, я взялся вместе с другими пользователями её решать. Оказалось что у неё примерно 3 подхода:

• можно использовать алгоритм «El Ajedrecista» — который использовался ещё в первом электромеханическом автомате больше 100 лет назад (или похожий «геометрический» подход)

• можно строить эндшпильные таблицы (это похоже на динамическое программирование) — для каждой позиции мы определяем выигрышность и можем указать другие позиции из которых в неё попадаем

• наконец, можно попытаться приспособить обычный МиниМакс — алгоритм который и по ходу обычной шахматной (и подобных) игр используется — но проблема в том что в эндшпиле нужна большая глубина а разветвлённость дерева поиска огромна — в то же время возникают некоторые эвристические соображения которые позволяют значительно уменьшить объём поиска

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

В общем, возиться с программированием игр разнообразной сложности — это в любом возрасте и независимо от скиллов достаточно забавно и развлекательно. По возможности (если дочитали досюда) напишите в комментариях:

• какие игры вы писали (или хотели написать) когда учились программированию

• какие направления в обучении через программирование игр вам кажутся более важными (техническое — графика, звуки; логическое — алгоритмы и стратегии; идейное — придумывание геймплея и т.п.)