?

Log in

Previous Entry | Next Entry

вавилонский лабиринт

Проект игры для программистов: по карте-лабиринту двигается робот, нужно написать программу, помогающую ему попасть в отмеченную точку карты. Традиционно имеется выбор датчиков и эффекторов, ограничения на объём программы, данных и времени.

Но язык программирования на каждом уровне другой. То подобие бейсика, где надо нумеровать строки, то микро-лисп, где есть только списки, то язык без изменяемых структур данных, то с опорой на взаимодействие асинхронных процессов, то, наоборот, на continuations, то на текстовых подстановках, то на самомодификации программы, то на ленивых вычислениях, то микроскопический prolog, то мини-sql, то нано-smalltalk, где надо сначала структуры управления самому определить, разные ассемблеры, etc. Поскольку конкретный лабиринт можно упростить, язык даже не обязан быть полным по Тьюрингу. Важно, чтобы его было просто реализовать, хотя бы и наивно, поэтому "настоящий C++" исключён, а "настоящий Forth" — нет.

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

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

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

Разумеется, должен быть и сайт с текстами программ, соревнованиями и рейтингами, как разных языков в одном лабиринте, так разных программ на одном языке. Можно одновременно выпускать в лабиринт одиночных роботов-соперников или их команды. Выкладывать ролики прохождений и вести "прямой репортаж". Следует позаботиться о красоте анимации :)

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


Понятно и за что деньги брать: с рекрутеров за контакты игроков.

Tags:

Comments

( 33 comments — Leave a comment )
aruslan
Aug. 29th, 2010 02:09 am (UTC)
Думаю, роботы должны уметь делиться, распределяя доступные внутренние и коммуникационные ресурсы соответственно используемому языку.
Задачи типа убить Минотавра в лабиринте vs найти Джоконду в музее vs поместить врагов в сад расходящихся тропок.

Тогда можно будет точно с рекрутеров денег за контакты брать.
9000
Aug. 29th, 2010 11:43 am (UTC)
Ну, это очень высокий уровень. Для начала надо уровней 20-30-50 попроще. Сравним с Project Euler.

Кстати, кооперация или война, PvE или PvP, тоже должны появляться на старших уровнях. Тот же pacman, притом задачи чтобы бывали за обе стороны.
(Deleted comment)
9000
Aug. 29th, 2010 10:10 am (UTC)
Re: Borges 2.0
Sounds logical. But commerce wise, it seems more profitable to bring the idea to some initial implementation and sell the startup than to sell the bare idea.
kouzdra
Aug. 29th, 2010 08:36 am (UTC)
Нечто подобное было в 2004 на ICFP
9000
Aug. 29th, 2010 11:45 am (UTC)
В точности.
Но можно обобщить и (для снижения порога) добавить множество более простых задач.
the7ofdiamonds
Aug. 29th, 2010 08:40 am (UTC)
недостаток идеи в том, что хотя язык может быть всё время разный, но алгоритмы-то одинаковые. это получится развлекуха для кодеров и поэтому быстро наскучит. вот если б придумать что-нибудь такое для алгоритмистов..
9000
Aug. 29th, 2010 10:23 am (UTC)
у всего есть свои ограничения %)
но если некий алгоритм записывается на каком-то языке в 2 строчки, то на другом — в 20, а другой подходящий алгоритм — наоборот. ограничения на затраты инструкций (и памяти) будут вынуждать применять разные алгоритмы для с виду одинаковых условий.
the7ofdiamonds
Aug. 29th, 2010 04:00 pm (UTC)
по сути алгоритмы одинаковые все будут (максимум парочка разных для каждой задачи), отличаться будут только реализации. да и скучно все время одну и ту же задачу решать.
9000
Aug. 29th, 2010 05:31 pm (UTC)
ну что вы.
рассмотрим тривиальный лабиринт и разные условия:
* неограниченный запас топлива, запас памяти на весь лабиринт, зрение на 1 клетку вперёд (тривиальный обход с построением карты).
* сильно ограниченный запас топлива, видение карты в радиусе 0.1 диаметра лабиринта (на тупой обход не хватит, надо строить карту по фрагментам).
* маленький топливный бак, заправки разбросаны по лабиринту.
* ограниченная память, в которую весь лабиринт не влезет даже как битмэп.
* скользкий пол: в таких клетках нельзя затормозить или повернуть, начав движение.
* инерция: разгон требует топлива, контролируемое торможение рекуперирует часть топлива, столкновение нет. поворот на большой скорости невозможен.
* гравитация: лабиринт расположен вертикально, как в платформере, можно прыгать и падать, с ограничением высоты или без.
* окна: непроницаемые стены, через которые виден лабиринт за ними.
* зеркала: непроницаемы, но датчики зрения видят "сквозь них" мнимое изображение лабиринта "за спиной".
* рентген: по "цвету" стен можно определить, сколько других стен за ними.
* двери: клетки с односторонним движением, заранее различимые или нет.
* знаки: искомое место не помечено прямо, надо расшифровывать знаки на стенах/полу.
* дорогостоящее (по времени или топливу) зрение вдаль, бесплатное зрение в соседнюю клетку.
* темнота: дельнее зрение работает только вблизи "источников света", в иных местах работает "осязание" на одну клетку вперёд.
* бесконечный, процедурно генерируемый лабиринт; известно, что цель не далее указанного расстояния от стартовой точки.
* реал-тайм: за время перемещения вдоль клетки может исполниться ограниченное число инструкций (осмысленно для инерции и командных режимов).

Это навскидку вариации почти только лабиринтов (их можно комбинировать), и ни слова о характере предлагаемых языков.
the7ofdiamonds
Aug. 29th, 2010 05:38 pm (UTC)
алгоритм все равно будет один, и каждый программист через нек. время напишет универсальный код, который надо будет всего лишь адаптировать под разные языки - и смысл потеряется.

ограниченная память - это фигня, если на пиксел тратить один бит то картинка влезет куда угодно. ну и так далее.
9000
Aug. 29th, 2010 06:31 pm (UTC)
что сказать. вы попробуйте :)

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

кстати, можно же и лабиринты делать не только из клеток, а из произвольных полигонов.
the7ofdiamonds
Aug. 29th, 2010 08:17 pm (UTC)
ну дык жатую картинку хранить канешна. чтобы толщина коридора один пиксел. впрочем это все мелочи.

есть и другой недостаток у идеи - реализация упомянутых мелочей и борьба с меняющимся языком займет большую часть времени. в реальной жизни обычно одни люди пишут низкоуровневый глубоко оптимизированный код, а другие придумывают всякие умные алгоритмы, потому что так эффективнее.
9000
Aug. 29th, 2010 10:08 pm (UTC)
как бы это сказать. это всё же замышляется как игра, как вещь со значительным компонентом развлечения. это ж не за деньги люди будут писать, а потому что по кайфу поиграться с языком и прочими условиями.

ну, не знаю, как люди, хорошо играющие в Starcraft, имеют большой объём внимания и стратегическое мышление, или там умелые главы кланов в EVE умеют и в реальной жизни проектами рулить, так и тут я надеюсь на некоторую корреляцию. но не более.
the7ofdiamonds
Aug. 30th, 2010 02:46 am (UTC)
не, это я к тому что например мне интереснее придумывать алгоритмы, чем оптимизировать существующие
9000
Aug. 29th, 2010 06:36 pm (UTC)
а вообще, конечно, суровый хардкор начнётся, когда будут конкурирующие роботы разных игроков на одной карте. а уж если дать им оружие... %))
kostya_puhov
Sep. 17th, 2010 01:01 pm (UTC)
А странно, если подобных соревнований (с лучеметами и ножиками:)) не проводится на базе существующих игрушек - тех, где популярны соревнования между игроками-командами.
Хотя я ни о чем подобном не слышал.

В конце концов, в логических играх соревнования алгоритмов процветают.

Естественно было бы, если бы издатели нанимали победителей, хотя бы когда "AI" компютерных противников труден для написания, но существенно влияет на интересность игры для людей.
-----
А в описанном случае хардкор, с элементами психологии программистов и всякими интересностями, вроде существования "равновесия Нэша", более экзотических равновесий, кооперации и т.д.
И заранее ничего не будет понятно.

the7ofdiamonds
Aug. 29th, 2010 05:44 pm (UTC)
впрочем, вот моё описание похожей идеи - http://www.liveinternet.ru/users/691626/post129596497/
9000
Aug. 29th, 2010 06:34 pm (UTC)
про магию отлично! уловлена самая сути программистской работы :)
slobin
Aug. 29th, 2010 08:51 am (UTC)
Самое сложное — видимо, конструктор языков и трансляторов и какая-то разумно универсальная виртуальная машина для исполнения этих программ.

Насколько я в курсе, самый отработанный конструктор языков и трансляторов (именно для целей обучения) -- это PLT Scheme (до недавних пор Racket Scheme). У них там в комплекте долгое время была игрушечная Ява (сейчас убрали во внешний модуль) и до сих пор есть игрушечный Алгол-60. Разумеется, речь не идёт ни об эффективности, ни о взаимодействии с "обычным" внешним миром, но нам этого и не нужно. Собственно, у одного из авторов курс языков программирования так и построен: "чтобы понять, как эта фича работает, надо её самому реализовать".

... zo banzu na terbri la'e vo'a ...

slobin
Aug. 29th, 2010 08:52 am (UTC)
Поправка: не "до не давних пор", а "с недавних пор". У них случился ребрендинг. ;-)

... Тупанье в темноте ...

9000
Aug. 29th, 2010 11:35 am (UTC)
О, отлично. Но, не исключено, придётся иметь 2 или даже 3 backend-а для разных по характеру языков.
gornik
Aug. 29th, 2010 11:07 am (UTC)
> Понятно и за что деньги брать: с рекрутеров за контакты игроков.

Десять баллов!
sab123
Aug. 29th, 2010 01:54 pm (UTC)
Рекрутерам (то есть, их клиентам) такое нафиг не надо. Ибо к настоящему программированию отношения не имеет.
9000
Aug. 29th, 2010 03:29 pm (UTC)
Конечно, это не строчка в резюме типа "написал банковский операционный день". Но некоторая корреляция с умением решать задачи и записывать их решения на языках программирования, мне кажется, есть.
sab123
Aug. 30th, 2010 02:13 am (UTC)
Знание десятка языков на уровне написать "hello world" никому не нужно. Мало в каком проекте используется больше трех языков.
9000
Aug. 30th, 2010 09:11 am (UTC)
Обойти лабиринт, особенно в несколько извращённой форме — это немного сложнее "hello, world". А умение разобраться в странно выглядящей проблеме и решить её не совсем знакомыми инструментами [бывало мне] нужно в куче проектов.

И вообще, это на 90% игра же :)
shigin
Oct. 2nd, 2010 01:23 pm (UTC)
Мне кажется, что куда интереснее была бы игра, в которой надо построить лабиринт. Лабиринт, по которому робот дойдет до цели. Описание робота на каждом новом уровне дается на новом языке программирования. Плюс какие-нибудь константы, которые изменяются с каждым новом запуском.
9000
Oct. 2nd, 2010 01:43 pm (UTC)
Отличный вариант, спасибо.
however
Jan. 10th, 2011 03:08 am (UTC)
Я в прошлом году нашла вот такое: http://www.kongregate.com/games/Coolio_Niato/light-bot
taraslive
Apr. 28th, 2011 12:05 am (UTC)
Проглядел текст. Интересная идея. Вообще сделать игрушку, чтобы на неё притягивались нужные люди однозначно рабочая идея.
Я в Галакси с кучей клевого народа перезнакомился.

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

udpn
Oct. 14th, 2011 06:13 pm (UTC)
Уважаемый, уже есть SpaceChem.

Уже можете вынести себе мозг тем эээ... языком программирования, который в нём есть. Если пройдёте целиком, дайте пятьзнать.
9000
Oct. 14th, 2011 07:05 pm (UTC)
Спасибо, уважаемый. Не знал, попробую.
udpn
Oct. 14th, 2011 07:24 pm (UTC)
Если влом платить за игру, которая вам может не понравиться (хотя просто обязана), вот здесь http://rutracker.org/forum/viewtopic.php?t=3758549 последняя версия, там теперь есть русский язык от создателей.
( 33 comments — Leave a comment )