интересное за неделю

1)

strangeraven 

как размножаются вампиры

http://strangeraven.livejournal.com/6167.html

2)

Andrey Gulin 

Running lock free

http://users.livejournal.com/_foreseer/34284.html

3)

shodan

Best tools noone uses: PREfast

http://blog.gamedeff.com/?p=164#more-164

4)

dDIMA

Рецепты отладки. Позор для математика.

http://blog.gamedeff.com/?p=168

Я, Робот

Третьего дня надыбал занятную flash-игрушку LightBot - впрочем, занятна она будет только программистам. Там надо запрограммировать роботца зажигать лампы в лабиринте. В наличии 7 команд-движений (типа "вперед", "зажечь", "направо"), 12 ячеек под основной метод программы и две подпрограммы по 8 команд каждая. Однако, возникла мысль написать программу, составляющую успешные программы для робота.

Для решения был избран метод перебора решений, известный как генетический алгоритм, ибо это хорошо.

Дальше - проще. Каждое решение (бот) это вектор ячеек размером 28 со значением 0-7 в каждой ячейке (0 - "пустая" команда). Изначально создаем кучу таких решений решительно случайным образом (хаха) - это будет поколение 0.

Если альфа ГА это случайность, то омега безусловно - фитнес-функция (ФФ). Грубо говоря, ФФ оценивает решение, что позволяет сравнивать их по критерию "лучше/хуже". ФФ вещь довольно тонкая.. например, первоначально я стал штрафовать за число ходов, сделанных программой - оказалось, что популяция программ стремительно вырождалась в "пустые" команды. Поэтому сейчас ФФ выглядит так: это штрафные баллы, начисляемые за 1) незаженные лампочки при останове бота, 2) расстояние до ближайшей негорящей лампы, 3) таймаут, 4) структурные повреждения (типа вызов функции 1 из функции 1). Соответственно, у хорошего бота маленький фитнес, у плохого бота - большой.

Так, об чем я? ..А. Значит у нас есть поколение 0, состоящее из случайных решений с большими фитнесами (да, большой не всегда хорошо). Наша задача - найти одного бота без штрафа за лампы и без штрафа за таймаут.

Следующее поколение получается так: 1) часть ботов (лучшие) отмечаются как избранные - они перейдут в следующее поколение без изменений 2) оставшиеся места занимают либо мутанты со случаными искажениями кода, либо полноценные потомки двух родительских программ из прошлого поколения. Да - половое размножение реализовано. Нет - тема сисек не раскрыта.

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

Всякие подробности:

программу можно взять тут - 44Kb, включая исходники под VC++ 7.1 (программа под win32, запускалась под XP32 исключительно).

ключики запуска:

botsearcher.exe [stage] [max_pop] [best_num] [rnd_seed]

stage - уровень (1..12, default 1),

max_pop - максимум решений в поколении (default 10),

best_num - столько лучших решений будет перенесено в следующее поколение  (default 2),

rnd_seed - seed для ГСЧ. если не указан, то будет разный каждый запуск.

пример: botsearcher.exe 10 100 10 0

внутри есть консолька с командами:

find - автоматом ищет решение с нулевыми штрафами за лампы и за таймаут,

find N - ищет решение с фитнесом <= N,

gen N - ищет до поколения N,

list - показывает текущее поколение,

map - показывает текущий этаж,

bulb N - показывает карту растояний для лампы N,

stage N - загружает этаж N,

bot N - показывает детали бота N, 

fit N - прогоняет "тест" для бота N (это больше для дебага).

информация о каждом боте выглядит примерно так:

bot 00) bulb: 0/1, fitness: 14 (b: 10+2, t: 0, st: 2)   **<>*__*J1_1 *<>*J^_^ J<2j_1>2 : 0

где:

bulb 0/1 - 0 ламп зажглось после отработки программы. всего ламп = 1.

fitness: 14 (b: 10+2, t: 0, st: 2) - фитнес = 14, при этом за лампы 10 штрафа, 2 за расстояние до ближайшей погашенной лампы, 0 за таймаут и 2 за внутренние проблемы.

легенда команд: _ - пусто, * - зажигание, <> - налево/направо, J - прыгать, ^ - вперед, 1/2 - вызов функций 1 и 2.

0 в самом конце это номер поколения откуда решение родом.

Уф.. известные баги:

1) не проверяю нигде валидность введеных параметров. 

2) настоящий LightBot почему-то "принимает" откровенно таймаутные программы, например для 11-го этажа:

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

По итогам - программа довольно шустро ищет решения для всех этажей. Затруднения возникают на 10-м и на 11-м этаже, там слишком много блекджека и шлюх для одного бедного робота.

Минивикторина: у кого какая скорость при запуске 1М поколений на 11-м этаже?

botsearcher.exe 11 10 2 0

gen 1000000

на тачке моего работодаде.. датля.. тьфу. короче на рабочей тачке 401 sec, 2494 g/sec

Слава Роботам!

интересное за неделю

1) 

Gaperton 

Микроэлектроника demystified

http://gaperton.livejournal.com/22825.html

2)

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

Как я был тренером футбольной команды

http://plakhov.livejournal.com/83309.html

интересное за прошлую неделю

1)
Knives - Антипаттерн №35: Динамическая память
http://kunaifusu.livejournal.com/303588.html

нехорошая квартира

Иногда обыденные предметы дают узнать себя с неожиданной стороны..

Вот запустим к примеру обычный виндовый калькулятор и введём 1,+,2,*,3,= в инженерном, а затем в обычном виде. В инженерном ответ будет 7, а в обычном 9 - еще одна демонстрация того факта, что не всякое подходящее специалисту подойдет рядовому пользователю. (Кстати, не показывайте этот прикол иностранным товарищам - были прецеденты..)

На днях совершенно случайно выявил гадскую натуру CRITICAL_SECTION. По своей наивности я считал, что всё что залочено "внутри" lock-unlock есть единица исполнения, и повторный lock приведет лишь к ожиданию соответствующего unlock'a - как бы ни так. Внутри одной нити повторные lock'и будут просто проскакивать, причем это явно описано в MSDN: "Once a thread owns a critical section, it can make additional calls to EnterCriticalSection or TryEnterCriticalSection without blocking its execution.".

немного быдлокода:
1) обертка для критических секций http://www.everfall.com/paste/id.php?e4oiqnj5qmve
2) самопальная "критическая секция" на основе event'ов - вот она умеет лочиться даже внутри одной нити. http://www.everfall.com/paste/id.php?p9qoygyxzoks

ICFPC'08

Большие мальчики три дня играли с машинками на Марсе, вот пара-тройка отчетов:

Dmitry Astapov
http://users.livejournal.com/_adept_/84592.html

EaE
http://habrahabr.ru/blog/icfpc/46589.html

sparpc
http://sharpc.livejournal.com/28176.html

Роман Янковский
http://kerkzone.net/2008/07/15/icfp-2008/


Чуть не забыл - Слава Роботам!