Последние записи в блоге

Полезные штуки: Random 20 Apr 2010 11:28

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

Задача: есть некоторая последовательность объектов. Возможно, неизвестной длины. Надо выбрать случайный элемент этой последовательности, так чтобы вероятность выбора любого конкретного была одинакова. Вариант "со звездочкой" — для каждого элемента последовательности задан вес, надо чтобы вероятность выбора элемента была пропорциональна весу.

Обычно это решается просто: элемент номер n, где n — случайное число от 0 до N, а N — длина последовательности. Ну, типа,

return sequence[random.Next(0, sequence.Count)];

Но для этого надо знать число элементов. И иметь доступ по индексу тоже неплохо бы. А если последовательность, как в нашем условии, этого не имеет? В терминах C# — это IEnumerable. Есть способ решения и в этом случае.

Работая с IEnumerable, все что мы можем — это перебирать элементы последовательно. Подойдем к вопросу так: пусть мы, перебирая последовательность, выбрали некий элемент Х из первых n. Теперь мы берем следующий элемент, номер n+1. C какой вероятностью мы выберем именно его? Если последовательность заканчивается на нем, ответ очевиден: $1/(n+1)$. Менее очевидно, что с той же вероятностью его надо выбирать и в остальных случаях! Попробуем посчитать вероятность для случая, когда длина последовательности n+2:

  • на шаге n+1 мы выберем наш элемент с вероятностью $1/(n+1)$
  • на шаге n+2 мы выберем _следующий_ элемент с вероятностью $1/(n+2)$; а предыдущий останется выбран с вероятностью $\frac{n+1}{n+2}$
  • в итоге, элемент с номером n+1 окажется выбранным с вероятностью $\frac{1}{n+1} \frac{n+1}{n+2} = \frac{1}{n+2}$ — что и требовалось!

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

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

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

    public static class RandomSelectExtension
    {
        public static T Random<T>(this IEnumerable<T> enumerable, Random rng)
        {
            int totalCount = 0; // число шагов
            T selected = default(T); // последний выбранный элемент
            foreach (var data in enumerable) // перебираем элементы
            {
                int r = rng.Next(totalCount+1); // случайное число от 0 до totalCount включительно 
                if (r >= totalCount) // с вероятностью 1/(totalCount+1)
                    selected = data; // выбираем текущий элемент
                totalCount++; // и следующий шаг
            }
 
            return selected;
        }
    }

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

Ну и наконец, к вопросу о задаче со звездочкой. Как быть, если веса элементов разные? Как оказалось, точно так же - только вместо номера шага надо брать вес элемента. То есть, если вес i-того элемента wi, то элемент номер n+1 выбирается с вероятностью $\frac{w_{n+1}}{\sum_{i=1}^{n}w_i}$. Доказывается это абсолютно так же, как и для случая равных весов — суммы опять сократятся. А реализуется, например, так:

    public static class RandomSelectExtension
    {
        public static T Random<T>(this IEnumerable<T> enumerable, Random rng, Func<T, int> weightFunc)
        {
            int totalCount = 0; // теперь это - суммарный вес всех предыдущих элементов
            T selected = default(T);
            foreach (var data in enumerable)
            {
                int r = rng.Next(totalCount + weightFunc(data)); // weightFunc вычисляет вес текущего элемента
                if (r >= totalCount)
                    selected = data;
                totalCount += weightFunc(data);
            }
 
            return selected;
        }
    }

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

return list.Random(m_Random, pd => pd.Count);

То есть, вес это поле класса, экземпляры которого лежат в списке.

Комментариев: 4. Последний 20 Apr 2010 13:19

Don't make me play 06 Apr 2010 08:48

Компьютерные игры с каждым годом все короче. Факт общеизвестный, и частый предмет жалоб. "В наше время игру надо было проходить месяц, а сейчас? Три часа!". Call of Duty 4, скажем, и впрямь проходится за 6 часов полностью… но вот жаловаться на это вряд ли стоит.

NEWpercentcomplete.png

Существует другой, тоже довольно известный факт. А именно: игры никто не проходит. Вот справа таблица с данными из XBox Live: доля игроков, прошедших данную игру. Даже самую популярную (на момент теста) игру прошли едва две трети игроков. Чуть менее популярные (и речь совсем не об аутсайдерах!) — и доля прошедших падает ниже 20%! А относительный середнячок Tomb Raider: Underworld прошли и вовсе чуть более пяти процентов игроков.

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

Я не специалист, но мне кажется что в любом другом жанре подобный уровень "потерь" считался бы катастрофой. Представьте себе фильм, с просмотра которого ушла половина зрителей — это же провал. Книгу, которую отложил на полдороге каждый второй читатель; музыкальный альбом который половина слушателей отправляет на полку после третьего трека. А в играх это, между прочим, оглушительный успех и суперхит.

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

Я не хочу сказать, что все игры должны быть одноразовыми. Речь идет прежде всего о длительности одной игровой сессии, имеющей начало и логическое завершение. Грубо говоря, одном уровне — но уровне полностью самодостаточном, не требующем проходить следующий и следующий и следующий, чтоб узнать, "женится он на ней или нет". Прекрасный пример — Civilization: Revolution. Игра завершается часа за два-три — полной победой или полным же поражением.1 Чтобы играть дальше, надо опять начать с начала. Если вспомнить о фильмах, такую игру можно сравнить с сериалом: в нем может быть тысячи серий, но смотреть их можно по одной, более-менее независимо.

А пример, который собсвенно сподвигнул меня на написание этого поста — Desktop Dungeons. Казалось бы, roguelike игры всегда отличались именно что немеряным временем прохождения (собственно, родоначальник был и вовсе непроходим в принципе). Особо упертые тратили на них по 18 лет! Но как оказалось, и этот жанр только улучшился от укорачивания. Одно прохождение Desktop Dungeons занимает 10-20 минут от начала до конца; требует, как и положено в roguelike, большой осторожности и постоянных мысленных расчетов; и содежит приблизительно стопицот мильенов разных стратегий. В DD можно играть часами, но при этом это очень короткая игра.

Ну и напоследок: предельный случай. Игра "Евангелие за 10 секунд". Она гениальна, между прочим.

Комментариев: 6. Последний 08 Apr 2010 11:56

Про копирайт 16 Mar 2010 10:54

Пришла тут в голову очередная мысль на тему копирайта и прочего пиратства. Я, если кто не в курсе, большой противник этого дела, борец с борьбой и т.п. Так вот, вопрос — почему, собственно?

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

И мне кажется, что я знаю, откуда оно берется. Дело в том, что когда я честно покупаю какую-нибудь "интеллектуальную собственность", я фактически плачу за её копию. Сторонники копирайта утверждают, что мои деньги — это награда создателю за его работу; вообще говоря это правда, но: работа уже проделана. Объект "интеллектуальной собственности" уже существует, независимо от того, куплю я его или нет. Значит, я не оплачиваю его создание: я оплачиваю услугу по копированию. То что с этой платы живет создатель, это уже эффект второго уровня (и вообще говоря не всегда верно).

Так вот, внимание вопрос: сколько стоит услуга по копированию информации? Правильный ответ, понятное дело — нисколько. Спасибо, я и сам могу все что мне надо скопировать1.

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

Ситуация выходит довольно дурацкая. Представьте себе, что к вам пришла прелестная маленькая девочка, и предлагает заплатить ей 50 баксов. Из этих 50, 5 баксов получат создатели новой классной игры Shooter III: Modern Shooting, а 45 достанутся девочке. А вы получите личную копию игры на диске. Странное предложение, правда? Забудем пока о том, что копия на диске требует всяких странных действий и подключения к интернету для игры; забудем даже о том, что при таком подходе сама девочка, походу, неприлично разбогатеет (я в общем-то ничего не имею против неприлично богатых прелестных маленьких девочек). Вероятно, найдутся люди, которые готовы поддержать разработчиков Shooter III и таким образом — особенно если других не предлагается. Но мне он все-таки представляется запутанным и не слишком эффективным2.

В таком разрезе понятно, почему я против копирайта. Запрет на копирование — это способ искусственно раздуть стоимость услуги. Если копирование запрещено всем, кроме некоторых избранных, эти избранные, конечно, заработают немаленькие деньги. Но пахнут эти деньги не очень-то: на ум сразу приходит другая индустрия, которая зарабатывает бешеные деньги на искусстввенных ограничениях. Наркоторговля.

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

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

Впрочем, есть как минимум один, уже навязший в зубах, пример. Сервис Steam не предлагает мне услуги по копированию игры. Он предлагает услугу по хранению. И вот это я уже не могу повторить бесплатно своими силами; поэтому я покупаю игры на стиме, и более нигде. Думаю, что Steam — далеко не единственный вариант услуги, за которую действительно стоит платить. И если я придумаю другую — вот тут-то и будем самое время организовать стартап (-8

Комментариев: 9. Последний 19 Mar 2010 13:49

Адронный коллайдер 11 Mar 2010 19:54

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

Запуск Большого Адронного Коллайдера привел к катастрофическим последствиям. Образующиеся Черные Дыры растут и поглощают все частицы, неосторожно оказавшиеся рядом. Смертельная угроза нависла над микромиром.

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

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

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

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

Пфф, уфф, с этим кустом пора завязывать…

Комментариев: 2. Последний 16 Mar 2010 12:53

Жаворонок-мутант 04 Mar 2010 19:00

Люблю я ставить над собой дурацкие эксперименты. Вот две недели назад я очередной раз увидел сылку на Стива Павлину - о том как просыпаться рано. Несмотря на то, что тут же нашлась и статья про то, что совы круче, метод "превращения в жаворонка" я применил на практике.

Отчет:

Я сразу замахнулся на серьезную цель и поставил будильник на семь утра. Хотел на восемь, но привычка не переводить часы на зимнее время таки сыграла злую шутку. Просыпаться в семь оказалось прикольно. Встаешь, а все еще спят. Можно спокойно позаниматься всякой ерундой: почитать френдленту, поиграть в Borderlands и даже поработать. Учитывая, что днем я работаю под вопли двухлетнего ребенка, раннее утро представилось особо приятным временем. Опять же, забавно привести ведущего программиста в состояние обалдения. Цитирую:

Vinder 12:36:12|
8:43!!!!!!!!!!! мне плохо стало от одного вида такого сабмита

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

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

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

Резюме:

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

PS А будете себя хорошо вести, я как-нибудь напишу про более жосткий эксперимент с многофазным сном.

Комментариев: 0. Последний

Конь-цепт 26 Feb 2010 14:07

Наконец дописал текст, который явился тиап как катализатором создания этого блога. Концепт тактической онлайн-игры, spiritual sequel для UFO: Enemy Unknown.

Концепт конечно довольно сырой, но для "просто идеи" по-моему неплох. Возможно, я его буду даже развивать — идеи приветствуются, во всяком случае. На реализацию моими силами рассчитывать вряд ли можно (-8

Сам концепт в вики.

Комментариев: 0. Последний

Немного хоумрулов 20 Feb 2010 06:13

Немного предыстории: уже около трех лет я вожу мега-кампейн по Вархаммеру. А именно, The Enemy Within переадаптированную под WFRP 2nd edition. В партии есть эльфийский маг (а как же!), он же главный манчкин; игрок любит почитать всякие разные дополнения и потом доставать меня просьбами всяческих ништяков.

Поскольку мастер я добрый (иногда), на просьбу о фамильяре я в общем откликнулся. Но правила по фамильярам из Realms of Sorcery меня не устроили, меня вообще мало что устраивает в вархаммерской магии. Поэтому я придумал свои.

Маг так обалдел, что возможностью создать фамильяра так и не воспользовался. Так что, чтоб оно не пропало - выкладываю правила здесь, вдруг кому пригодится.

Статья в вики.

Правила никак не тестировались, и балансировались только интуитивно (без таблицы в экселе на сто листов как положено). Use at your own risk, ага.

Комментариев: 0. Последний

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License