Не кинокритик

02:51 pm - Кто здесь?

"The time has come," the Walrus said,
"To talk of many things:
Of shoes--and ships--and sealing-wax--
Of cabbages--and kings--
And why the sea is boiling hot--
And whether pigs have wings."

Меня зовут Андрей Плахов. Я программист, делаю компьютерные и видеоигры; если кому-то вдруг интересно, подробнее здесь. Но пишу далеко не только об этом.

Чтобы было удобнее читать, большая часть записей снабжена тэгами.

06:17 pm - Танчики-машинки

Для pet-project'а про AI мне нужен визуализатор, обладающий следующими особенностями:
- 3D про танчик(и) или "машинки"
- с видом сверху, a la RTS или по крайней мере допускающий такое положение камеры
- с готовой моделькой хотя бы одного "танчика" или "машинки", можно даже в каком-нибудь кривом промежуточном формате - менять их я не буду
- с source кодами, доступными под разумной лицензией (BSD, Microsoft Permissive, LGPL, GPL тоже можно)
- относительно приятно выглядящий и сколько-нибудь прилично написанный
- на С++

Для примера: если бы не последний пункт, то XNA simple animation demo вполне подходило бы.

Кто подскажет? Я могу, конечно, написать и сам, но очень не хочется тратить на это время; ну а моделлер из меня вообще никакой. Если авторы называют это indie-движком и хотят оплату до $100, то меня и такое тоже устроило бы (но Torque все же не предлагать).

Буду очень благодарен подсказчикам.

01:55 pm - Mindpixel

2⁷⁰ байт обозначается милым словом "зебибайт".

07:58 pm - И последнее на сегодня

Теряю веру в Microsoft.
ReSharper в единственном sample, поставляемом сразу вместе с XNA (Space War Demo) показывает десятки warning'ов, даже если не считать за таковые ненужные using'и в шапке (и то правда, кто их там считает). Unused private fields, unused local variables, протухшие docstrings, ненужное многословие и тд и тп

Главное, что служит для меня оправданием существованию Java/C# - как раз то, что они позволяют создавать тулзы уровня ReSharper; ну и зачем, если их даже в самом MS не используют?

А вот кстати. В современных IDE есть такая удобная вещь, как умный autocomplete (если у кого работают знакомые в компании Metrowerks/Freescale, пожалуйста, сообщите им об этом). В момент, когда он выбирает подсказку, то, с чем он работает - это ведь не код; это текст, похожий на код, но он некорректен даже с точки зрения лексера, не говоря уж о возможности сделать из него AST. Но autocomplete все-таки понимает, о чем речь, и предлагает свои варианты, почти всегда правильно. Как он это делает? Это просто набор кастомных хаков, language или даже IDE-specific, или за этим все-таки стоит какая-то теория?

06:12 pm - И еще про производительность

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

У ММО есть возможность не тормозить, даже если N большое персонажей одновременно соберутся в одном месте. Нужно перестать передавать часть "неинтересных" апдейтов. Не исключено, что игроку неважно, видит он на городской площади толпу из 50 человек, или из 500 - и можно получить десятикратную экономию и трафика и производительности сервера; фактически, убрать все "эн-квадраты". Но невозможно применить эту технику, если делать это не с самого начала проекта, а в момент, когда код уже написан, идет бета-тестирование, и пришел баг "в окрестностях рынка в базарный день игра тормозит".

Чтобы находить такие решения, нужно до того, как пишется основной код, посчитать, чего именно следует бояться. Взять все цифры, которые можно узнать у дизайнеров уже сейчас (те, что нельзя - взять из WoW или из БК, кому что больше нравится), и поперемножать (крайне желательно при этом следить за размерностью результата). Каковы линейные размеры мира? Как далеко видит персонаж? С какой скоростью он бегает? Сколько человек в онлайне надо держать на одном сервере? Сколько раз в час игрок переходит в другую зону? Заходит в магазин? И зачем?

Это же относится к вопросам "а выдержит ли БД такую нагрузку" (какую "такую"? сколько чтений и апдейтов в секунду надо выдерживать? что у вас будет нагружать БД? я пару лет назад посчитал это для четырежды закрытого проекта™, тогда в списке сильнее всего была заметна процедура получения ХР; мне не известен способ до выхода проекта узнать примерную нагрузку, не запустив хотя бы Excel).

У Баткина pathfinding "не ходил на север", но это шутка; у нас он всерьез может ответить спрашивающему путь "ты подожди пока, я на этом фрейме уже достаточно поработал, не надо нам лагов". Текст выше должен пояснить, зачем такое понадобилось, в какой момент и как мы это придумали.

Ну а вообще можно, конечно, и std::vector не использовать - а то, как учат патриархи, компилятор не поймет. Только все это потом. Если приходится торговаться, покупая яхту с вертолетной площадкой, то яхта не нужна. А может быть, не нужна вертолетная площадка.

05:37 pm - Оптимизация, профилирование и производительность

На форуме "Оптимизация, профилирование и производительность", я хотел рассказать вот о чем.

( Как сделать так, чтобы игра не тормозила )

Да, я забыл похвастаться - Robocalypse стал лучшей игрой КРИ-2008 для портативных платформ. Для меня, orvind'а и Шера это уже вторая "лучшая портативная" (предыдущая была для телефонов, ММО и на Java, вот ведь кидает-то нас).

11:26 am - Scott Aaronson on Platonic Heaven

Ссылка в основном для timur0, kosilova и прочих людей, интересующихся основаниями математики.

Floating in Platonic Heaven

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

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

07:37 pm - Про индейцев

Про североамериканских индейцев.

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

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

Во времена, когда в Америке появились белые люди, цивилизация индейцев уже находилась в состоянии упадка. За пятьсот лет до этого они строили города, население которых достигало 50 000 человек (для того времени немало даже по европейским меркам) и возводили усыпальницы размером с египетские пирамиды (правда, по гораздо более простой технологии - насыпные, из земли или адобов). Существовали сверхсложные культы мертвых, всяческие ритуалы, общественные институты, развитая культура. Еще до прихода европейцев все это почему-то исчезло.

Не выдержав столкновений с белыми, больше половины племен погибло (их вырезали, или они вымерли от эпидемий, или тихо спились). Cейчас их где-то 250. Тем не менее, сейчас индейцев в Америке живет не меньше, чем тогда - миллион с лишним.

Из множества племен только у одного появилась письменность - у чероки. Ее разработал вождь Секвойя только в XIX веке (говорить "изобрел" неправильно: Джордж "Секвойя" Гесс к тому времени уже успел поучиться в миссионерской школе и, видимо, знал латиницу).

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

11:29 am - Когда у вас депрессия...

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

10:58 am - Все ли вы знаете о себе и о своих коллегах?

Синдром Аспергера.

А. Шень: "Профессия математика (и родственные) — способ социальной адаптации для людей с нестандартной психикой".

На ту же тему вспоминаются "сфокусированные" из "Глубины в небе" В. Винджа, и строчка из недавно прочтенной книжки: "...Родители детей-аутистов часто характеризуются как высокоинтеллектуальные, эмоционально холодные люди".

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

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

07:19 pm - Нужен ли AI в играх?

Нужен ли AI в играх?
Во многих не нужен совсем (например, в Match-3 попкорне). В подавляющем большинстве остальных какой-то нужен. Но умным он должен быть ровно настолько, чтобы не натыкаться на стенки и не падать самопроизвольно в пропасть (впрочем, фанаты серии Might and Magic легко прощали любимому сериалу и это). Почти никогда не имеет смысла учить AI действовать разнообразно и нетривиально. Исключением могут являться, разве что, классические стратегические жанры – TBS и RTS – да и то с оговорками. Так принято считать.

Меня такое положение дел несколько расстраивает. Я попробую для примера описать некоторые игровые возможности, реализация которых без полноценного AI невозможна – то есть, за счет него игра приобретает какие-то ударные отличительные черты, заметные даже самому казуальному игроку. На самом деле их наверняка можно придумать куда больше, особенно если рассуждать, как я, в рамках утопии.
( Фантазии )
О каждой из этих возможностей применения AI в играх я уже некоторое время размышлял и достаточно хорошо представляю себе, как это можно было бы сделать. К сожалению, когда мне доведется поработать над подобным проектом, и доведется ли вообще, я не знаю. Во-первых, мало в какой компании сложившиеся процессы позволят плясать от подобных features (особенно если инициатива будет исходить от программистов). Во-вторых, конкретно в той студии, где я работаю, в ближайшее время ничего похожего не планируется. Даже не знаю, быть может, вам что-то пригодится.

01:02 pm - Запоздалое, про КРИ

Слово "дзэн" пишется именно так, писать его через букву "е" не стоит.

С интересом почитал несколько отзывов о КРИ, напишу тоже что-нибудь. Поздно, конечно, но у меня есть два оправдания – 1) я был в отпуске и 2) я ленивый.

10:54 am - Правда ли это?

The stereotypes of New York City invariably portray New Yorkers as rude, obnoxious people. Usually, the ones that they're portraying as rude aren't the guys in suits; it's always the minorities or the working class. But in a year of this commute, I've never seen one of those stereotypical New Yorkers being the least bit rude. <...> If you're walking out of the subway with a stack of papers, and drop them, New Yorkers are the people who'll help you catch all of your papers, and then tell you what an idiot you are for dropping them. That's NY.

(из off-topic записи в блоге о хорошей и плохой математике)

04:39 pm - Просто дневник

За 10 дней отпуска побывал в Египте, на Украине, и вернулся в столицу нашей Родины.

( Египет, Украина )
( Москва )

12:47 pm - Открытое письмо в институт им. В. В. Виноградова

Мы требуем официально признать jr, lf и ytn словами русского языка!

Экономический эффект применения данной меры, выражающийся в снижении потерь времени при общении офисных сотрудников, трудно переоценить.

01:47 pm - Во мгле

В ex-USSR одна за другой исчезают небольшие игроделательные компании

http://www.dtf.ru/news/read.php?id=50723
http://www.dtf.ru/news/read.php?id=50679
И, судя по информации из закрытых источников (ой, случайный каламбур), это еще далеко не все. Самые шокирующие закрытия впереди (если о них вообще объявят, конечно, а не замаскируют под видом череды продаж-покупок и реорганизаций).

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

06:30 pm - Биологам - Leslie Valiant, Evolvability

Похоже, Лесли Валиант - великий ученый, хоть и неизвестный широкому кругу людей.

Я не так давно формулировал здесь вопрос об эволюции с точки зрения теории алгоритмической сложности. Оказывается, он тоже задался этим вопросом, но, в отличие от меня, сильно продвинулся в том, чтобы на него ответить. Его выводы изложены в этой статье 2007 года.

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

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

- чтобы ответить на вопрос, насколько вероятно появление тех или иных конструкций в ходе эволюции, не имеет смысла изучать конкретные механизмы изменчивости: результат от них не зависит

- появление конкретных типов структур в ходе эволюции имеет очень предсказуемую "вероятность", которая поддается строгим оценкам. Слово "вероятность" взято в кавычки, т.к. она имеет всего два варианта поведения: или асимптотически стремится к нулю, или к единице

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

У Лесли еще много отличных статей на стыке биологии и теории вычислительной сложности. Например, интерпретация двух нейробиологических фактов с точки зрения computational complexity (до Валианта, как я понял, для них не существовало внятных объяснений). Мне очень нравится такой подход. Если однажды я все-таки решу уйти в монастырь заняться наукой, я хотел бы заниматься чем-то подобным.

05:09 pm - !!!

Google groups отчего-то не прислали мне в почту оповещение об этом ответе, а я его так ждал!

Your result would be very interesting, resolving an open problem

Хорошо подымает настроение, несмотря на температуру. Обидно только, что больше 2 месяцев потерял - ответили мне аж 24го января, оказывается. Надо теперь где-то взять в этой кутерьме время на написание статьи. Когда напечатают, можно будет считать доказанным предположение, что в XXI веке информационные сервисы позволяют двигать вперед науку, не являясь формально научным работником, и не участвуя в жизни российской "научной мафии".

01:58 pm - Кое-что неизменное

    И Щеголев пошел рассуждать о политике. Как многим бесплатным болтунам, ему казалось, что вычитанные им из газет сообщения болтунов платных складываются у него в стройную схему, следуя которой логический и трезвый ум (его ум, в данном случае) без труда может объяснить и предвидеть множество мировых событий. Названия стран и имена их главных представителей обращались у него вроде как в ярлыки на более или менее полных, но по существу одинаковых сосудах, содержание которых он переливал так и этак. Франция того-то боялась и потому никогда бы не допустила. Англия того-то добивалась. Этот политический деятель жаждал сближения, а тот увеличить свой престиж. Кто-то замышлял и кто-то к чему-то стремился. Словом -- мир создаваемый им, получался каким-то собранием ограниченных, безъюморных, безликих, отвлеченных драчунов, и чем больше он находил в их взаимных действиях ума, хитрости, предусмотрительности, тем становился этот мир глупее, пошлее и проще. Совсем страшно бывало, когда он попадал на другого такого же любителя политических прогнозов. Был, например, полковник Касаткин, приходивший иногда к обеду, и тогда сшибалась щеголевская Англия не с другой щеголевской страной, а с Англией касаткинской, такой же несуществующей, так что в каком-то смысле войны международные превращались в межусобные, хотя воюющие стороны находились в разных планах, никак не могущих соприкоснуться.

    Владимир Набоков, "Дар"
    (это написано в середине тридцатых годов)

11:08 am - Computational Complexity

Этот пост расчитан в основном на людей, ищущих определенные ключевые слова в technorati, Yandex ППБ и подобных сервисах. Среди прочего мне интересно, сколько существует таких людей, так что если вы нашли этот пост именно таким образом - оставьте, пожалуйста, здесь комментарий, даже если тема вас не особенно заинтересовала.

1. После этой записи мне подумалось, что сложность по Колмогорову-Чаитину не только невычислима, но и не очень интересна: строки, вычисляемые экспоненциально долго, странно считать простыми, даже если это делается очень короткой программой. Что если к длине вычисляющей строку программы добавить число шагов до ее останова? Получим определение сложности, которая тривиально вычислима. Правда, вычисление нельзя произвести быстрее, чем экспоненциально долго (относительно измеряемой сложности строки), и я могу это доказать (шутка, конечно). Хорошо, а что если взять в качестве меры сложности (2^{длина программы}+число шагов до ее останова)? Тогда ее можно вычислять за квадратичное относительно сложности строки время. Правда, сама сложность при этом может оказываться очень большой даже для относительно коротких строк. Интересно, что в этом случае язык, на котором пишется программа, имеет значение (в отличие от сложности по Колмогорову-Чаитину). Языки становится можно делить на "мощные" и "маломощные", а также на пригодные и непригодные для данного типа задач, как это и делают практикующие программисты, в отличие от computer scientists. Я думаю, это вовсе не случайное совпадение.

Насколько такое определение сложности для чего-то годится на практике? Насколько оно изучено?

2. Я не понимаю, откуда в интернете такое количество липовых статей на тему P=NP. Да, я сам изобрел примерно сто алгоритмов решения 3-SAT за полиномиальное время, и еще столько же для PARITY-SAT, когда узнал о теореме Валианта-Вазирани. Но я все-таки первым делом писал реализацию на компьютере, и в 99% случаев понимал, в чем изъян, даже не запустив программу. А в оставшемся проценте программа, как и следовало ожидать, работала неверно, что помогало найти хитро замаскированную ошибку. В интернете присутствует даже вариант для крутых: RP = NP. Ну как может человек, умеющий пользоваться TeX'ом, знающий, кто такие поля характеристики 3, и чем permanent отличается от determinant'а, не написать немного кода, чтобы проверить свое открытие, потенциально переворачивающее мир?

3. По поводу теоремы Валианта-Вазирани. Я в какой-то момент придумал, как свести задачу PARITY-SAT к узкому частному случаю, и очень этим гордился, пока не осознал две вещи: узкий частный случай что-то тоже никак не поддается, и к тому же эта редукция может быть проведена очень простым, почти очевидным образом, так что наверняка уже известна. Частный случай вот какой: выражение представляет собой конъюнкцию clause'ов длины 2 (как у 2-SAT), и к тому же не содержит литералов с отрицанием. Можно это переформулировать как задачу "установить четность суммарного числа INDSETS в графе, независимо от их размера". При этом граф можно сделать bipartite, можно sparse, можно даже и то и другое. Решить задачу за полиномиальное время это не помогает. Вопрос такой: в интернетах (Google'ом, на citeseer и тп) упоминаний об этой редукции я не нашел, на sci.math и comp.theory по этому поводу никто не отвечает (впрочем, эти рассылки, кажется, довольно-таки мусорные). Summoned reader (скажем, belonesox), не могли бы Вы дать мне ссылку на эту тему, или подтвердить, что эта редукция ранее не была известна (что было бы довольно странно)?