Третьего дня пришёл ко мне Паша Гертман с интересным набросом. Дескать, игре Жизнь, r-пентамино и глайдеру (планеру) то ли уже стукнуло 50 лет, то ли вот-вот исполнится. И как бы нам этот момент не прозевать. Разные источники дают противоречивую информацию, объявляя годом появления игры Жизнь, r-пентамино и глайдера то ли 1969, то ли 1970, в разных комбинациях, а авторство (точнее первооткрывательство) глайдера приписывается то Конвею, то Ричарду Гаю.

По кускам у меня собралась такая картина: Конвей сформулировал правила игры Жизнь в первой половине 1969 года в Кембридже, и первое время итерировал разные начальные паттерны вручную (на бумаге и на доске), но это оказалось делом сложным и занудным. Поэтому он договорился с кембриджским компьютерным центром, и ему на помощь пришли Стив Борн (автор первого юникс шелла, Bourne shell aka sh) и Майк Гай, которые как раз в тот момент работали там над языком ALGOL 68C. Они написали программу под PDP-7, облегчающую расчёт поколений Жизни, и стали вместе наблюдать за развитием разных комбинаций. На тот момент особенно их занимало r-пентамино, демонстрирующее хаотическую динамику в первые 1000+ поколений. Ближе к концу лета к экспериментам присоединился отец Майка, математик Ричард Гай, и именно он, согласно воспоминаниям Конвея, "в самом конце осени" 1969 года случайно заметил, что на 69 поколении развития r-пентамино в хаосе образуется комбинация, которая устойчиво двигается по полю с периодом 4 и скоростью c/4.

Почти год спустя, в октябре 1970 в журнале Scientific American вышла популяризаторская статья Мартина Гарднера об игре Жизнь, принесшая игре огромную популярность. Однако в ней не были указаны явные даты ("this month we consider Conway's latest brainchild"), а глайдер был назван "one of the most remarkable of Conway's discoveries". С тех пор в большинстве источников годом открытия игры Жизнь, r-пентамино и глайдера называется 1970, а открывателем глайдера часто объявляется сам Конвей.

В общем, разобравшись, мы с Пашей решили, что "Late in the fall of 1969" это прямо сегодня, и объявляем сегодняшний день Днём Глайдера (к тому же, юбилейным, пятидесятым!). И не верьте никому, когда через год все научпоп журналы будут справлять пятидесятилетие игры Жизнь, знайте, оно уже прошло ;)

А если вы заскучали, посмотрите мои старые трёхмерные визуализации поколений игры Жизнь, почитайте про глайдер на апериодичной мозаике Пенроуза или поиграйте со свёрткой поколений одномерных автоматов Вольфрама в кривые Пеано.

Внезапно, гистограмма частот разных линий мирового метро по цвету (hue) от Xan Gregg. Ссылки: пост с обсуждением на реддите, данные, предыдущий аналогичный проект.
А здесь можно посмотреть на 200+ логотипов метрополитенов мира, отсортированных по схожести.

Сегодня я узнал об удивительном мире "бесконечных кассет" -- это аудиокассеты специальной конструкции, позволяющие проигрывать одну и ту же плёнку по кругу без перемотки. Придуманы и запатентованы, если верить википедии, ещё в 1950гг, большой бум был в 1980гг в эпоху повсеместного появления автоответчиков. Короткие версии делаются за счёт создания лентопротяжных "лабиринтов", длинные имеют более хитроумную конструкцию. Производятся и продаются до сих пор, с диапазоном длительности от 10 секунд до десятков минут.

Старенький (2013 года) японский проект “Fencing Visualized” по наглядной визуализации рапирного боя. Это не realtime, и более того, судя по всему использовались специальные костюмы с датчиками для motion capture. Но всё равно, красиво, и скоро, благодаря всяким PoseNet, DensePose и BodyPix, будет возможным просто на основании видеопотока.

Громкость песен по жанрам, в формате raincloud диаграмм на данных из каггловского соревнования Spotify. Источник на реддите, в треде также поминают "войну громкости" и огромную базу данных динамических диапазонов по 140К альбомам.

До кучи: сэмплы всевозможных инструментов с разными параметрами от Philharmonia Orchestra и пара подборок странных космических звуков от NASA.

Я уже как-то писал о ежегодном конкурсе по автоматической генерации литературного текста, NaNoGenMo. В этом году случился интересный твист — Ник Монтфорт из MIT запустил конкурс-спинофф Nano-NaNoGenMo (NNNGM), с одним дополнительным правилом -- участники должны предъявить код не длиннее 256 байт.

В итоге, вместе с товарищем @s0me0ne, трушным Perl-нёрдом, мы собрали генератор текста на цепях Маркова в виде Perl-скрипта длиной 123 байта (всего 139 байтов вместе с shell-кодом). Детальный разбор этого безумия можно почитать здесь.

С другой стороны, если вам претит Perl, можете почитать древнюю байку о том, как двадцать лет назад мы оптимизировали один ассемблерный код вплоть до 4 байт. Или просто покидайте монетку через API.

Скучно регулярно рассказывать одно и то же, но и пропускать некоторые вещи не хочется, поэтому вот вам общий список не-новостей, про которые я так или иначе когда-то уже упоминал:
* Недавно прошла ежегодная рождественская лекция Дональда Кнута, а чуть пораньше — ежегодная лекция про берестяные грамоты, теперь в исполнении Алексея Гиппиуса (уже вторая без Зализняка).
* На NeurIPS сегодня проходит AI/ML Creativity Workshop (тот самый, на котором мы с Ваней пару лет назад презентовали наш альбом Neurona), чуть попозже организаторы обещали выложить галерею работ этого года.
* На Амазоне постепенно появляются книги в официальном соавторстве с GPT-2.
* Пару месяцев как выложили видео докладов со Strange Loop 2019 и Roguelike Celebration 2019.
* Прямо сейчас идёт ежегодный AdventOfCode, две ежедневные программистские головоломки до 25 декабря.
* Закочился еже-ноябрьский NaNoGenMo 2019, я про него вчера упоминал.

И, чтоб два раза не вставать, отмечу, что мне лично показалось на этом NaNoGenMo забавным или интересным:
* Bobey Dig — прочтение Моби Дика с заложенным носом (с помощью фонетической библиотеки Pincelate, настроенной на удаление назальных звуков, приглушения фрикативов и т.п.).
* Personalized Bibles — системная замена имён персонажей в тексте Библии на другие, например, на имена покемонов или на имена из книг о Гарри Поттере.
* A Most Portentous Dream Diary — автор собрал грамматику на Inform 7, которая генерирует дневник снов из сонника и 3700+ записей о снах, найденных в Project Gutenberg.
* Knowledge is power — текст из первых предложений разных статей википедии, собранный так, что каждое следующее "объясняет" предыдущее (последнее слово). Из комментариев — "I like this output a lot :) It feels like talking to one of my friends with ADHD."
* The Orange Erotic Bible — сетка GPT-2 долго читала эротику, а потом её попросили продолжать отдельные кусочки Библии.
* я и сам в этом году поучаствовал с моделькой Paranoid Transformer, которую делал к нашему с Ваней Ямщиковым новому набросу (сам наброс ещё не опубликован).
* Отдельно порадовал упомянутый мной вчера спин-офф от Ника Монтфорта, я про него (про Ника) как-нибудь отдельно напишу.

Меандрирование реки Укаяли в Перу в течение 30 лет. Нашёл в твиттере.

На тему вчерашнего поста @kborislav прислал мне замечательную цитату из "Жизни на Миссисипи" Марка Твена:

Еще замечательна Миссисипи своей склонностью делать громадные прыжки, прорезая узкие перешейки и этим способом выпрямляя и укорачивая свое русло. Не раз она сокращала свой путь на тридцать миль одним прыжком. Такие изменения русла имели любопытные последствия: многие приречные города бывали отброшены далеко вглубь, перед ними вырастали песчаные дюны и леса. Город Дельта раньше находился на три мили ниже Виксберга. Недавний поворот русла в корне изменил положение, и Дельта стоит теперь выше Виксберга на две мили.

Оба эти приречные города отодвинулись в глубь страны вследствие перемены русла. Такие перемены вносят путаницу в границы и законоподчиненность: сегодня, например, человек живет в штате Миссисипи, а ночью происходит перемена русла, и назавтра он видит, что сам он и земля его находятся на другом берегу реки, в границах и под властью законов штата Луизиана. Случись такое изменение в верховьях реки в старину, оно смогло бы перебросить раба из Миссури в Иллинойс и сделать его свободным.

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

Интересное от читателей:
- Кирилл Демура прислал ссылку на видео безумных людей, записывающих аналоговое аудио на трёхдюймовые дискеты.
- Макс Бекетов подбросил статью о сборке схем из логических вентилей на базе сапёра.
- Павел Лебедев поделился кикстартерным проектом чипированного волчка, который крутится без остановки часами.
- Булат Каримов прислал ссылку на пикабу-пост, где люди считают "индекс Гитлера" для разных статей русской Википедии.

Мирный ML на службе человечеству:
- Курсовая студента fast.ai, посвящённая автоматическому определению степени достроенности здания на снимках застройки в Занзибаре.
- Богатая тема -- чтение по губам нейросетью.
- Статья "Detecting Kissing Scenes in a Database of Hollywood Films".
- История спора символистов и коннекционистов в одной понятной картинке.
- Небольшой, но симпатичный датасет с национальными узорами — гжель, хохлома и т.п.

Уголок GPT:
- Миша Гранкин выложил в общий доступ русскую предобученную модель GPT-2.
- GPT-2 генерирует пошаговые инструкции для рисования, специальный скрипт превращает их в картинки в духе Сола Левитта.
- GPT-2 генерирует noscript-иконки и шрифты.

Весёлое безумие:
- RL-песочница для тренировки алгоритмов на сборке икейной мебели.
- Фонетический разбор и описание типичных звуков и междометий, издаваемых тинейджерами.
- Скрипт, транслирующий вебкамеру в фавиконку (немного напомнило мой старый проект).
- Тредик человека, прошедшего в этом году AdventOfCode на экселе.
- Музей смешных, глупых и откровенных названий сетей wi-fi со всего мира. Также: музеи автоматов с газировкой, канализационных люков и статуй Моаи в копьютерных играх.
- Нейросеть для генерации схемы вязания по фотографии (прицепом — мой древний пост про секту математического вязания).
- Усреднение флагов разных континентов, а также драфт флагов планет солнечной системы.

Всех с праздниками! ;)

Внезапно, прекрасный сайт thisfootdoesnotexist.com с услугой генерации фото ступней с помощью GAN.

Рубрика "уголок скучающего нерда": намедни поминали с товарищами древний проект CHDK, где нам пришлось отмаргивать прошивку фотоаппарата его же светодиодом. Потом, когда прошивка была получена, народ стал писать под фотоаппараты всякий дополнительный софт, из чего в итоге вырос не только CHDK, но и побочный проект MagicLantern. Из той истории для меня запомнилась пара находок, вроде замера выдержки с помощью дремеля и передачи дампа памяти через переменное энергопотребление (NOP vs MUL). Я же тогда более-менее ограничился тем, что запустил на фотоаппарате бегущую строку по ленте Мёбиуса в духе демосцены (снято на валенок) и отвлёкся на что-то другое.

И, к слову: недавно под руку попался проект по созданию народной opensource прошивки для паяльников TS100 (в числе улучшений отмечаются improved readability fonts). Что характерно, тут сами производители выложили свою прошивку в opensource, да зравствует конкуренция. Или, вот, скажем, проект по моддингу прошивки фонарика Convoy S2+. Меня тронуло, что он умеет отмаргивать свою температуру в градусах Цельсия.

Плотность туристов в залах первого этажа Лувра, восстановленная по гео-позициям снимков Инстаграмма. Для сравнения — карта этажа с основными экспонатами. Источник.

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

Контекст: AI Dungeon — это попытка сделать интерактивную текстовую игру на базе нейросети GPT-2. Про жанр текстовых игр я уже писал в этом канале. В целом, это похоже на настольные ADnD игры, в которых роль мастера выполняет компьютер.

История проекта: первую версию Nick Walton запустил весной 2019 года на базе малой версии GPT-2. Осенью, когда OpenAI опубликовала сетку полного размера (примерно в 12 раз больше), авторы переделали игру под неё и добавили всяких штук. В декабре с ними случился хабраэффект, к ним в одночасье пришло 70К игроков, условный игрок стоит им 1 бакс в месяц, а они студенты и у них лапки. Поэтому они теперь собирают денег на Патреоне, а файл с моделью раздают через торренты. Скачав модель, можно поиграть в игру на Colab-е. Вот тут родной пост от автора, а вот тут интервью с ним.

Чем это интересно: несмотря на мощный хайп, сетки вроде GPT-2, как и другие языковые модели довольно неудобны для unsupervised генерации текстов — они практически неуправляемы, и частенько сбиваются в бред или в повторение. Заранее предсказать, будет ли генерация выглядеть осмысленной или хотя бы грамматически корректной, обычно нельзя. Поэтому большая часть публикаций типа "нейросеть ХХХ написала УУУ" обычно является классическим cherry-picking-ом. Это не хорошо, и не плохо, это такой текущий state of the art, но именно по этой причине интересно анализировать попытки обвесить такую сетку костылями, делающими её поведение более контролируемым без ручной фильтрации и премодерации.

Я на выходных поковырял их исходный код и выписал несколько интересных моментов.
* в качестве базы используют GPT-2 1.5B parameter model на tensorflow
* написали scraper, который обходит всевозможные варианты в играх на chooseyourstory.com, и таким образом напарсили 30Мб
* на этих 30Мб тюнили модель с целью приучить её к стилистике таких текстовых игр, в репозитории можно заметить также следы попыток использования труда mturkers, а также упоминания данных с сабреддита writingprompts — вероятно, пытаются с их помощью поднять качество
* доучивали на DGX-1, это заняло около 16 часов
* для борьбы с повторениями использовали штраф 1.2 к вероятностям уже использованных слов, точно как это было сделано в Salesforce CTRL model — тут я бы отметил, что на моём опыте подход unlikelihood training работает получше
* запрещают модели генерировать плохие слова из явного списка
* для "удержания смысла" в качестве префикса подают не только команду, но и историю из последних 8 вопросов-ответов — это помогает "заземлить" модель от слишком резких поворотов
* при этом полученные от пользователя команды конвертируют из инфинитива и формы первого лица во второе лицо, таким образом, вход модели выглядит как слитный текст во втором лице -- это больше похоже на то, на чём она обучалась
* в качестве дополнительного префикса при генерации каждой реплики используют краткое статическое описание персонажа и инвентаря, эти описания просто написаны вручную в конфиге -- по идее это также способствует "стабилизации нарратива"
* эти же префиксы используют для реализации save / load
* победу и смерть персонажа пытаются определять просто поиском ключевых слов в ответе модели

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

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

AVERAGE ART: Я тут на праздниках взял датасет классической живописи с Kaggle-соревнования Painter by Numbers, отобрал из него 10К мужских и женских портретов, с разбивкой по стилям живописи. Затем использовал библиотеку Facer, о которой уже писал прошлым летом, чтобы построить средние лица по стилям, а также time-lapse средних лиц на портретах со средних веков по двадцатый. Детали можно почитать в посте на медиуме.

Нашёл что-то вроде курсача об оптимальной вероятностной стратегии игры в морской бой. Текст, график сравнения с другими стратегиями, оригинальный пост на реддите.