?

Log in

No account? Create an account

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, а другой подходящий алгоритм — наоборот. ограничения на затраты инструкций (и памяти) будут вынуждать применять разные алгоритмы для с виду одинаковых условий.
(no subject) - the7ofdiamonds - Aug. 29th, 2010 04:00 pm (UTC) - Expand
(no subject) - 9000 - Aug. 29th, 2010 05:31 pm (UTC) - Expand
(no subject) - the7ofdiamonds - Aug. 29th, 2010 05:38 pm (UTC) - Expand
(no subject) - 9000 - Aug. 29th, 2010 06:31 pm (UTC) - Expand
(no subject) - the7ofdiamonds - Aug. 29th, 2010 08:17 pm (UTC) - Expand
(no subject) - 9000 - Aug. 29th, 2010 10:08 pm (UTC) - Expand
(no subject) - the7ofdiamonds - Aug. 30th, 2010 02:46 am (UTC) - Expand
(no subject) - 9000 - Aug. 29th, 2010 06:36 pm (UTC) - Expand
(no subject) - kostya_puhov - Sep. 17th, 2010 01:01 pm (UTC) - Expand
(no subject) - the7ofdiamonds - Aug. 29th, 2010 05:44 pm (UTC) - Expand
(no subject) - 9000 - Aug. 29th, 2010 06:34 pm (UTC) - Expand
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)
Поправка: не "до не давних пор", а "с недавних пор". У них случился ребрендинг. ;-)

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

(no subject) - 9000 - Aug. 29th, 2010 11:35 am (UTC) - Expand
gornik
Aug. 29th, 2010 11:07 am (UTC)
> Понятно и за что деньги брать: с рекрутеров за контакты игроков.

Десять баллов!
sab123
Aug. 29th, 2010 01:54 pm (UTC)
Рекрутерам (то есть, их клиентам) такое нафиг не надо. Ибо к настоящему программированию отношения не имеет.
9000
Aug. 29th, 2010 03:29 pm (UTC)
Конечно, это не строчка в резюме типа "написал банковский операционный день". Но некоторая корреляция с умением решать задачи и записывать их решения на языках программирования, мне кажется, есть.
(no subject) - sab123 - Aug. 30th, 2010 02:13 am (UTC) - Expand
(no subject) - 9000 - Aug. 30th, 2010 09:11 am (UTC) - Expand
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)
Спасибо, уважаемый. Не знал, попробую.
(no subject) - udpn - Oct. 14th, 2011 07:24 pm (UTC) - Expand
( 33 comments — Leave a comment )