Тема: ai

AI, GAMEDEV, NARRATIVE

Копаясь в разных архивах, нашёл разного интересного:

Steering Behaviors For Autonomous Characters” — статья Крейга Рейнольдса, того, между прочим, самого, который в 86 году придумал боидов — известную модель для эмуляции поведения птичьих стай, впервые использованную в фильме “Batman Returns” для обсчёта движения летучих мышей. В данной же статье делается обзор базовых моделей движения NPC — преследования, уклонения, избегания, прибытия, преграждения, праздного шатания, группового поведения и т.п. — и способов их сочетания. Статья древняя, 99 года, но интересная.

Sims, BattleBots, Cellular Automata God and Go” — обширное интервью 2001 года с Уиллом Райтом, создателем Spore, SimCity, The Sims и прочих симсов. Обсуждаются интересные концепции программных и ментальных моделей мира, идея плавного перехода игрока от наблюдения через игру по правилам к соавторству, влияние современных медиа на нарратив в книгах, фильмах и играх и прочая метафизика.

Chatting Up Façade’s AI: 23 Ideas to Talk Your Game Into” — обзор AI-движка уникальной игры Facade от 2005 года (немного почитать про неё на русском можно тут), суть которой заключается в общении с двумя ссорящимися между собой NPC. Движок учитывает перемещения и речь персонажей и моделирует эмоциональное состояние, субъективные отношения, цели и, как следствие, поведение, речь и мимику героев. Несколько технических статей от авторов движка можно почитать тут: раз, два, три. Сейчас, кстати, они анонсировали новую игру Prom Week на улучшенном социальном движке, её промо можно посмотреть тут, а вот тут можно попроситься в закрытое бета-тестирование.

И, наконец, долгожданный солюшен к PacMan-у, пошаговое прохождение!

Tags: , , , | Make a comment

SOCIAL AI

Уже несколько лет я вяло подумываю в очередной раз переписать Мимика, на сей раз на питоне и с улучшенным NLP, и вывести в свет в социальные сети (скажем, в твиттер или одноклассничков), а то последнее время с ним никто не общается (напоминаю: он жив и доступен в jabber/gtalk/qip по адресу mimicq@jabber.ru). Кстати, если кто возжелает помочь в этом нелегком, но интересном деле — милости просим. А то мне одному лениво, да и времени вечно нет.

Ну, а тем временем, я собираю информацию об аналогичных проектах и сегодня решил поделиться с вами некоторыми находками:

Примером базового, классического варианта является Shrinkbot — порт Элизы под твиттер, интересующиеся могут почитать описание и скачать сырцы.

Далее, Joe McCarthy, преподаватель из Университета Вашингтона, Ботелл, организовал более масштабное действо. Он устроил соревнование между своими студентами — десять команд писали каждая своего бота под твиттер, а победителем считалась та команда, чей бот за 5 дней наберёт максимальное число фолловеров из заранее выбранного пула в 500 живых, не знающих об эксперименте пользователей. В обширном обзоре результатов описываются стратегии (в т.ч. достаточно сложные), использованные различными командами и приводятся результаты (число твитов, ретвитов, упоминаний, друзей) для каждого бота.

Идею этого соревнования Джой почерпнул из более серьезного конкурса, проходившего в рамках WebEcologyProject примерно год назад. Несмотря на то, что зарегистрировались всего 6 команд, а участвовали только три, условия соревнования были более обстоятельными: в течение 2 недель команды готовили код и аккаунты, а затем боты запускались на 2 недели более-менее самостоятельного функционирования. Баллы начислялись за ретвиты и фолловинг, снимались за жалобы на спам. Официальную летопись можно почитать здесь, весь результирующий код доступен тут (под MIT Open source license). Интересно, кроме того, почитать впечатления отдельных команд.

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

Еще один занятный проект — StrategyBot, основаная цель которого — мониторинг и ретвит интересных ссылок. На данный момент, как я понял, он автоматизирован только отчасти.

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

Tags: , , , , | Make a comment

CHICA

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

Вот, например, намедни ломали мы китайскую капчу.

Предвосхищая вопросы, сразу отмечу три факта:
- на всё про всё было потрачено 3 или 4 вечера, не считая разметки капч, которая занимала по 5 минут в день в течение 2-3 недель,
- нет, я не ломаю капчу на заказ и не планирую этим заниматься в будущем ;)
- целей никаких не преследовалось, это было for fun.

А дело было так:

Пришел ко мне как-то товарищ s0me0ne (с которым мы как-то раз делали 3d-ландшафты соли под микроскопом) и жалуется: я, говорит, постоянно что-то у наших заморских братьев с доставкой заказываю, всё время несколько заказов висят в процессинге. Ну и написал скрипт для мониторинга статусов заказов, делов то. Но с одной китайской службой промашка вышла — там, чтобы узнать статус, надо капчу решить. И непростую, а настолько суровую, что я даже глазами её не всегда разбираю:

Мне любопытно стало, и решил я её поломать.

О том и рассказ.

0. Дискляймер

Я, натурально, ненастоящий сварщик. Раньше капч я не ломал, да и в будущем не планирую. Некоторые навыки в ML и ImageProcessing, вообще говоря, у меня имеются, но скорее теоретический багаж, нежели жизненный опыт. Посему, я явно прошелся по нескольким классическим граблям, и результат вышел не слишком оптимальным, но зато вполне рабочим, чего мне в данном проекте вполне достаточно. В конце поста, однако, я постараюсь какие-то мысли в формате работы над ошибками написать, на тот случай, если кому-то понадобится.

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

1. Знакомство с ChiCa

После первого приступа естественного изумления удалось сформулировать следующие впечатления.

Плюсы:
- Число символов постоянно.
- Фоновый градиент фиксирован.
- Положение букв по вертикали более-менее стабильно.
- Шрифт один и тот же.
Минусы:
- Добавлен мелкий шум (вроде, не страшный)
- Букв в алфавите около сорока (английские буквы + цифры + символы доллара, собачки и т.п.)
- Положение букв по горизонтали колбасит страшно. В частности, нередки случаи когда буквы сильно перекрываются.
- Буквам рэндомно меняется кегль, болд, италик.

2. Базовая чистка

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


дальше картинки буду зумить

Имея такую радость, несложно её вычесть, дабы получить что-то вроде:

Ну и цвет нам совершенно не нужен больше. А кроме того, для дальнейших плясок нам пригодится две картинки — контрастная ч/б-версия и серая с полутонами (не важно, черным по белому, или наоборот):


По первой мы будем определять границы букв, а саму букву в конце будем угадывать по более информативной картинке с полутонами. Контраст, если что, я делал по на глаз подобранной константе в 160.

3. Вертикальная сегментация

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


я буду менять картинки периодически, чтобы не скучно было

Поскольку дырявых на просвет по горизонтали букв в нашем алфавите нет, то это надёжный способ выявить нужную нам область:

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

4. Горизонтальная сегментация

Тут начинаются песни и пляски с бубном, ибо китайцам всё равно, налезли буквы друг на друга, или нет; и даже в случаях, когда просвет между буквами имеется, он не обязательно строго вертикальный (т.к. буквы бывают написаны италиком), например:

Поэтому, пришлось вспомнить дедушку Брезенхэма и пробивать каждую вертикаль несколькими линиями под разными углами (я проверял 4 угла с шагом dx в 1 пиксель, исходя из максимального наклона италика). Опять-таки, считаем плотность, но на самом деле нам интересно только, нулевая она или нет. Ну и, конечно, плотность мы смотрим по вертикали уже только в пределах зоны, ограниченной желтыми линиями, т.е. там где буквы живут.

Получаем местами вполне неплохой себе результат:

Но бывают и упячки разного рода:



Визуальный анализ упячек позволил придумать следующий набор правил:
- одиночные (изолированные с обоих сторон) красные точки — убираем, т.к. это скорее-всего шум,
- скользящим окном в 5 точек ищем случаи вида Х0ХХ00, доставляем точку, преобразуя их в ХХХХ00
- и, симметрично, 00ХХ0Х в 00ХХХХ.

В результате выходит значительно лучше:


Если же всё-таки сегментов оказалось более 4, то сортируем их по размеру и берем 4 самых больших.
Что же, однако, делать, если сегментов оказалось меньше 4? Есть некоторые шансы, что сегменты у нас склеились или сразу, или в процессе работы предыдущей эвристики:

Этому горю несложно помочь, если внимательно рассмотреть возможные случаи:
- У нас на выходе 3 сегмента — значит, слиплись какие-то 2 буквы. Режем самый большой из имеющихся сегмент пополам.
- У нас на выходе 2 сегмента — если один из них сильно (более чем в 2 раза) второго, значит, считаем, что в него слиплись 3 буквы и пилим его на 3 части. Иначе — каждый из 2 сегментов пилим пополам.
- У нас на выходе 1 сегмент — значит, нам повезло, и все 4 буквы склеились в 1. Делим наш сегмент на 4 равные части, т.к. больше нам тут поделать нечего.

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

5. Обучающая выборка

По причине того, что каждая буква в данной капче имеет больше десятка различных возможных написаний (с учётом болда, италика и кегля) решено было стрелять из перспетрона. Благо у меня как раз осталась его реализация под Octave после прохождения стенфордского ML-курса. Но персептрону нужно обучаться, и тут пришлось поработать неграм (в лице меня и s0me0ne).

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

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

И тут… по всем законам жанра, в тот день, когда мы набрали 1000 сэмплов, КИТАЙЦЫ ПОМЕНЯЛИ КАПЧУ.

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

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

6. Персептрон

Дальше всё было несложно. Я порезал сэмплы описанным выше алгоритмом на “буквы”, снабдил их метками, которые мы расставили вручную, когда решали капчи, и выгрузил всю эту радость в Octave. Там я обучил стандартный персептрон с одним скрытым слоем — на входном слое было 195 нейронов (по числу пикселей в окне буквы 13х15). На скрытом я от балды поставил 30 нейронов, на выходном вышло 26, по числу распозноваемых букв. Обучение заняло минут 10.

Точность определения 1 символа на тестовой выборке получилась чуть больше 90% — т.е. если считать что точность определения 4 букв в капче независима (что не совсем правда, т.к. иногда гадит сегментация, а значит, портятся сразу несколько соседних букв), то вероятность корректного решения целой капчи вышла около 70%. На практике оценка подтвердилась.

Из обученного персептрона я выгрузил две матрицы параметров и зашил их в php-код. Кодить матричную арифметику с нуля самому было лень, PEAR я не люблю, в итоге я дернул пару полезных функций, кажется, отсюда. Собрал всё в кучку и наваял несложный единый скрипт. Работает он примерно так:

7. Мысли напоследок

Тут я хочу просто перечислить тонкие места и очевидные допущенные промашки:
* Начать сбор обучающей выборки можно было еще до того, как садиться за сегментацию — это хорошо распараллеливаемые процессы.
* После смены китайцами капчи нейросеть для распознавания символов в данном случае явно была оверкиллом. По идее, поиска по маске со словарём из двух масок (обычная и италик) на каждую букву должно было хватить. Просто я уже как-то настроился из персептрона пошмалять ;)
* По результатам кажется, что сегментация на символы, может быть гораздо более эффективно и универсально решена той же нейросетью. А так, это, конечно, заход солнца вручную получился :)
* Для того, чтобы не решать тысячи капч руками, по уму надо было подобрать шрифт (скажем, с помощью этого или этого сервисов), потом воспроизвести генератор и нагенерировать нужное количество сэмплов.

Вот такая история.

Tags: , , , , | 1 comment

PATHFINDING.js

Для тех, кто сейчас проходит стэнфордский онлайн курс ai-class, ну и просто для любопытствующих: наглядная демонстрация работы основных path-finding алгоритмов:

Tags: , , , , | Make a comment

GOOGLE AI CONTEST

Вчера узнал, что сейчас идет Google AI Contest.

В двух словах, задача состоит в написании логики бота, играющего в некоторый аналог игры Galcon — космической стратегии, основанной на разделении ресурсов. Прием ботов на конкурс идет до 27 ноября, а потом их будут стравливать и выявлять победителя. Языки доступны из списка C++, C#, Java, Python.

Было бы времени побольше, я бы, наверное, поучавствовал.

Вспоминаются стародавние времена, когда мы еще в школе рубились в RobotBattle, а потом на первом курсе с группой сотоварищей писали интерпретатор RedCode на придуманной нами модели тороидальной памяти (ToroWars).

Tags: , | Make a comment

VIRTUAL MUSIC

Минувшей осенью Дэвид Хоуп, американский ученый / композитор, занимающийся вопросами создания музыки искусственным интеллектом, анонсировал на начало 2010 года выход первого альбома классической музыки, полностью сочиненной его системой Emily Howell (Эми). До этого выходило несколько альбомов вроде “Virtual Bach”, “Virtual Mozart” и т.п., где система подражала стилю уже известных композиторов, теперь же ожидается полностью самостоятельный альбом.

С тех пор новостей о выходе альбома появлялось, но послушать старенькое интервью с Хоупом с вкраплениями сочиненной машиной музыки можно, например, тут. А уже вышедшие mp3 Эми можно бесплатно скачать и послушать с сайта Дэвида.

Tags: , , | Make a comment