Google AI Challenge

Недавно из блога Плахова узнал про конкурс Google AI Challenge. Конкурс очень интересный, и битвы топ-ботов очень впечатляют (для примера: один, два и три). В результате меня так зацепила простота идеи и в то же время сложность алгоритмов, что я тоже решил попробовать свои силы.

Google AI Challenge – это конкурс, в котором соревнуются не люди, а запрограммированные боты. Правила очень просты и основаны на игре Galcon. Есть двухмерная карта с планетами, каждая из которых характеризуется двумя параметрами: количеством войск и их приростом за ход. Планеты могут быть нейтральными, а могут принадлежать одному из двух соперников. Количество войск на нейтральных планетах не увеличивается. За ход одна или несколько планет могут отправить несколько флотов с определенным количеством войск в направлении других планет. На карте учитываются расстояния между планетами, поэтому на то, чтобы долететь, каждому флоту требуется несколько ходов. При прибытии флота на нейтральную или вражескую планету происходит схватка, в которой побеждает тот, у кого больше войск. Таким образом, чтобы захватить планету, нужно отправить на нее флот или несколько флотов с количеством войск на 1 больше, чем у противника. В то же время не нужно забывать, что за время прибытия вашего флота на планету количество войск на ней может увеличиться как за счет прироста населения, так и за счет быстро переброшенных войск противника. Это если вкратце, на самом деле количество вариантов бесконечно велико и это-то и составляет прелесть конкурса.

Писать ботов можно почти на любом языке программирования, включая даже JavaScript и PHP. Стартовые наборы (стартовый бот + соперники) есть для Java, Python, C++ и C#. Для остальных языков придется писать стартового бота самому.

Немного о своем текущем опыте. На данный момент я засабмитил вторую версию бота. Первую – в четверг, вторую – сегодня (воскресенье).

Первую версию я писал три вечера и основной целью было добиться, чтобы он научился побеждать 5 тестовых ботов на 100 картах (доступны в стартовом наборе) в большинстве случаев. Если описывать алгоритм в общем, то бот умел делать оптимальные первые хода, захватывая нейтральные планеты, защищать свои планеты (только самозащита на данном этапе) и очень неоптимально атаковать противника. Такого простого алгоритма оказалось достаточно, чтобы побеждать тестовых ботов в 99-100 случаях из ста. И этого оказалось достаточно, чтобы будучи засабмиченным в контест мой бот попал в топ-800, болтаясь там между 600 и 800 местами. К слову, на данный момент соперников чуть меньше 4000.

Во второй версии я научил бота коллективной защите и пофиксил пару багов. Это то, чего ему очень не хватало в битвах с соперниками. Конечно, это не даст ему возможность попасть в топ-100, но, надеюсь, он поднимется на 100-200 мест вверх.

В планах написание более серьезной версии, в которой бот научится оценивать перспективы захвата различных планет и будет принимать более оптимальные решения в плане отправки войск. А также – реализация атаки через свои и нейтральные планеты, учет фронтовых планет и пара алгоритмов контратак. Если же у меня хватит свободного времени завернуть это все в анализ дерева возможных ходов для просмотра будущего на несколько десятков ходов вперед – с этим можно будет претендовать и на топ-100.

В соревновании очень своеобразное ранжирование. Моего первого бота судьба сходу свела с ботом из 4-й сотни и после победы он сразу попал в топ-300. Затем, правда, был долгий путь вниз, пока он не сбалансировался в районе 700-го места. Второй же бот попал на товарища с 3100-какого-то места и после победы поднялся всего лишь на 3000-ю позицию. Не возникает сомнений, что за пару дней схваток он поднимется выше как минимум до того же 700-го места, но все-таки процесс выбора первого боя немного странноват. Random, что ли?

Если я вас заинтересовал, то сообщаю главную информацию. Соревнование будет длится еще почти целый месяц (!), до 27 ноября, так что у вас есть все шансы попробовать.

Несколько полезных ссылок:

• Сайт контеста: http://ai-contest.com/
• Секция форума, посвященная стратегии: http://ai-contest.com/forum/viewforum.php?f=17
• Отличная программа для тестирования своего бота: http://ai-contest.com/forum/viewtopic.php?f=18&t=748

Ну, и прочитайте алгоритм, который предлагает Плахов и обсуждение различных стратегий на форумах. Я там не знаю названий половины алгоритмов. Shame on me, в общем.

Кстати, если вы решите использовать C#, то учтите, что на сервере Mono 1.2.6, а это значит, что вы можете использовать только C# 2.0. Организаторов уже давно просили поставить на сервер Mono 2.0 (поддержка C# 3.5), однако те злобно морозятся. Не хотят плодить конкурентов, наверно ;) Подробнее здесь.

Ну, и напоследок. Если есть вопросы – спрашивайте. Если решите поучаствовать, мой аккаунт – AlexMerle. До встречи в бою :)

Железный треугольник

В последнее время на собеседованиях сталкиваюсь с тем, что не все люди, претендующие на роль team/dev lead, знают про железный треугольник. Хочется немного осветить этот вопрос. Сразу скажу, что опытные PM’ы не найдут для себя ничего нового в этой заметке, она ориентирована на тех, кто еще только начинает изучать проектный менеджмент.

Итак, железный треугольник (iron triangle, project management triangle) – это абстракция, описывающая взаимодействие основных атрибутов или характеристик проекта: объема работ, сроков и ресурсов (команды, а следовательно и бюджета). Выглядит он обычно так:

 

Иногда в центр этого треугольника кладут еще Quality, отмечая таким образом четвертую вершину, которая взаимосвязана с этими тремя, но мы сейчас не будем усложнять картину.

Смысл этого треугольника в том, что ограничения на объем работ (scope), сроки (time/schedule) и бюджет (cost/budget) должны быть разумными, и любой менеджер проекта должен уметь ими управлять. В противном случае проект рискует стать провальным.

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

Как же бороться с железным треугольником? Так же, как и с deadlock’ами – стараться не создавать предпосылок для его появления :)

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

1. Клиент более важно иметь продукт готовым полностью (ограничен объем работы), и у есть бюджет лишь на определенную команду. В таком случае сроки выполнения работ выбираются нами (отталкиваясь от оценки, а также размера и качества команды) или вообще делаются варьируемыми, если это возможно. Здесь нужно понимать, что этот вариант возможен лишь когда у клиента ограничен месячный или квартальный бюджет, если не хватает бюджета на весь проект, то нужно искать уже пути удешевления производства: покупка или использование сторонних разработок, использование более “дешевой” рабочей силы (аутсорсинг), экономия на качестве. Варьирование сроков здесь никого не спасает.
2. Клиент хочет иметь продукт готовым полностью в указанные сроки. Единственный разумный (!) вариант здесь – увеличение команды. Не очень разумные варианты вроде сверхурочные работы тоже имеют право на жизнь, но их нужно использовать ОЧЕНЬ аккуратно. С увеличением команды тоже есть один нюанс: оно не всегда приводит к желаемому результату. Во-первых, новым людям нужно время на вливание в проект (если он уже идет). Во-вторых, не все задачи хорошо параллелятся – часто задача Б может быть сделана лишь только после завершения задачи А, поэтому добавлять людей для выполнения задачи Б нет смысла. В-третьих, большее количество людей в команде ведет к увеличению времени на их координацию и общение между собой, что увеличивает оценку объема работ и, следовательно, бюджет. То есть, опять же, клиент платит больше. Все это ведет к тому, о чем говорил еще дядюшка Брукс (перефразируя): 9 женщин не родят ребенка за 1 месяц.
3. Клиент хочет иметь продукт в указанные сроки, но у него нет бюджета на увеличение команды. В этом случае единственная наша возможность – это варьирование объема работы, т.е. приоритезация задач проекта и договор сделать лишь те, что мы успеем, с учетом приоритетов. Менее важные задачи рискуют оказаться за границами продукта к дате релиза.

Эта ситуация очень напоминает выбор спальника (да и кучи других товаров). Спальник имеет три основных атрибута для выбора, находящихся в обратной пропорциональности друг от друга: теплота, вес и стоимость. Если у вас ограничен бюджет на покупку, вы можете купить либо теплый спальник, либо легкий. Если же вы хотите и то, и другое – пожалуйста, но придется раскошелиться.

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

Прежде всего, не паниковать :) Не вы первые, не вы и последние – по разной статистике в IT около 20-25% заваленных проектов, и еще около 45-50% – вышедших за рамки запланированных бюджетов, сроков, либо выпущенных не полностью готовыми (не вся функциональность либо плохое качество).

А вот дальше нужно сесть и хорошо подумать, причем желательно вместе с вашим клиентом. Возможно, вы сможете найти компромисс и освободить одну из вершин, а даже если и нет – клиенту лучше быть в курсе происходящего как можно раньше, а не за неделю перед релизом, чтобы успеть подстелить соломку, где это возможно. Оптимизация процесса работы и коммуникаций, более строгий контроль за выполнением работ, строгий change requests management, оплаченные сверхурочные, дополнительная мотивация сотрудников премиальными – все это может помочь не потерять лицо в глазах клиентов и избежать штрафов за срывы сроков. Но все-таки наилучшая рекомендация для менеджера проекта – постоянно держать в голове этот самый треугольник и отталкиваться от него, дабы свести возможность срабатывания этого риска к минимуму. Ну, и не забывать управлять остальными рисками, конечно же :)

А как вы решаете эту проблему?

Слушаете ли вы подкасты?

Я иногда публикую списки интересных подкастов, уже 4 выпуска набралось, но судя по посещаемости на dev.net.ua и Google Analytics, а также комментариям – эта тема не пользуется большой популярностью. Исходя из того, что на выпуски уходит определенное время, хотелось бы узнать, насколько прослушивание подкастов популярно и стоит ли продолжать делать обзоры.

Я создал два опроса в правой панели: “Слушаете ли вы подкасты?” и “Интересны ли вам обзоры подкастов?”, благодаря которым хочу выяснить эти моменты и определиться с дальнейшими действиями.

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

PS. Добавил третий вопрос. Буду признателен, если ответите и на него.

Список интересных подкастов: выпуск #4

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

.NET 4.0:

• .NET Rocks #517. Jason Olson Digs into the CLR 4.0

Jason Olson проходит по некоторым новым фичам CLR, C# и BCL. Concurrent GC, side-by-side CLR versions, Memory-Map files, co-variants и contra-variants, Parallel Extensions, немного об обновлениях в языках программирования и новых языках. И да, они наконец-то выкинули CAS и заменили его на более простой механизм. Хотя кто его вообще использовал :)

• .NET Rocks #515. Stephen Walther On ASP.NET AJAX 4.0

Небольшой обзор изменений в ASP.NET AJAX 4.0. От UpdatePanel до полностью кастомных AJAX-запросов и JavaScript-контролов. jQuery теперь "часть" ASP.NET AJAX, переработанный AJAX Control Toolkit - тоже, более того, AJAX Control Toolkit теперь работает не только с WebForms и MVC, но даже с PHP или любым другим back-end'ом. ASP.NET AJAX поддерживает dual data-binding на клиенте, который работает по аналогии с дата контекстом EF или L2S, на сервере его поддерживает WCF Data Services, которые раньше назывались ADO.NET Data Services. На закуску немного о ScriptLoader, history API, Microsoft CDN, Microsoft AJAX Minifier, Sea Dragon и Deep Zoom.

• .NET Rocks #514. Julie Lerman on Entity Framework 4.0

Честно говоря, еще сам не слушал этот подкаст, но судя по транскрипту - довольно любопытно. Foreign Keys, POCO и поддержка DDD разработки и модульного тестирования, Lazy/Deferred Loading, поддержка N-Tier сценариев при помощи Self-tracking entities, T4 templates, Code Only (в общем, все то, о чем я уже когда-то писал), немного о WCF Data Services, а также история о том, как Julie помогала Oren Eini (Ayende) создавать EFProf.

• .NET Rocks #377. Ted Neward and Amanda Laucher on F#

Обсуждение возможностей первого функционального языка программирования, включенного в .NET 4.0. Немного о том, что такое функциональные языки вообще, зачем нужен функциональный язык в .NET и какую пользу он может принести обычным разработчикам, привыкшим к императивным языкам вроде C#, VB.NET, Java или С++, некоторый ликбез по терминологии функциональных языков. Много интересного контента и шуток благодаря Теду.

• Hanselminutes #197. The Dynamic Language Runtime, IronRuby and IronPython with Jimmy Schementi

Интервью с програм менеджером DLR team. Конечно же, обсуждение DLR, который релизится с .NET 4.0, и его двух основных языков: IronRuby и IronPython. Разговаривают об архитектуре DLR, истории развития, возможностях, отличиях Iron-версий языков Ruby и Python от своих оригиналов, IronRuby on Rails :)

Другое:

• Hanselminutes #186. .NET Debugging 101 with Tess Ferrandez

И снова непревзойденная Tess. О чем еще с ней можно поговорить, как не об отладке. Что такое Memory Dump, как его создавать и почему об этом важно знать, что такое Allocated и Committed memory, как пользоваться WinDbg и CDB для отладки "утечек памяти" в .NET и проблем с производительностью, а также некоторые улучшения с отладкой многопоточных приложений в VS2010 и в предыдущих версиях, о которых вы, возможно, не слышали.

• Hanselminutes #202. A different way to do ASP.NET WebForms with WebFormsMVP

Интервью с создателем WebFormsMVP - очень интересного MVP-движка для WebForms. Автор рассказывает, что такое MVC и MVP, зачем использовать паттерн MVP в WebForms приложениях, архитектуре движка, особенностях его использования и том, насколько полно он работает с остальной инфраструктурой ASP.NET. Надо будет обязательно попробовать его в боевом проекте - по идее, должен сберечь кучу времени и сил.

• SpBaltNet #5. SOLID, TDD и прочие показатели качества кода

Приятно, что в нашем уголке мира появляются хорошие подкасты :) В гостях у питерской группы ALT.NET подкаста Александр Бындю и Виталий Стахов. Разговор идет о вполне понятных вещах: принципах ООП (SOLID), TDD, практиках XP, полезных инструментах, развитии программиста и различных вариантах построения и развития команд. Прикольно, что Александр Бындю точно так же понимает разницу между Scrum и XP, как и я.

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

• SpBaltNet #7. Domain-Driven Design и CQRS

Обсуждение Domain-Driven Design и CQRS (Command and Query Responsibility Segregation pattern) с Мишей Чалым и frozen_space. Если про DDD многие хотя бы краем уха слышали, то что такое CQRS для меня для самого тайна :) Где помогает DDD и зачем он нужен, что такое CQRS, его преимущества и недостатки. В общем, самое острие программной инженерии - не пропустите! Подкаст только записали, завтра буду слушать сам.

И напоследок, как всегда, тема попроще :)

• Hanselminutes #194. Hello World: Computer Programming for Kids and Other Beginners

Скотт общается с Warren Sande и его 10-летним сыном об их опыте написания книги по обучению программированию для детей и других начинающих программистов. Вроде бы ничего особенного, но удивляет этот 10-летний малыш. Мало того, что он помогал отцу в написании книги и примеров для нее на Питоне, но он еще и рассуждает обо всем по-взрослому. Интересно, он просто настолько умен или изучение программирования действительно ускоряет развитие у детей?

Приятного прослушивания!

Слайдкаст по принципам проектирования

При помощи PowerPoint'а, пары программ по редактированию и конвертации звука и такой-то матери я наконец-то слепил свой первый слайдкаст и выложил его на Slideshare. Это слайдкаст с недавнего доклада по принципам проектирования и длится он аж три четверти часа, что сильно уменьшает его шансы быть прослушанным вами :). Вопросы-ответы в середине и конце пришлось выкинуть, т.к. вопросов не слышно - микрофон был только у меня.

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

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

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

Design Principles

View more presentations from AlexMerle.

Если вдруг слайдкаст не открывается из блога - вот прямая ссылка.

Принимаются любые пожелания по улучшению.

PS. И спасибо Вове Лещинскому за микрофон!

Доклад о принципах проектирования

Готовлю еще один доклад для харьковской Uneta по принципам проектирования.

Основные цели:

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

Доклад будет частично построен на заметке о качественном коде и проектировании. Частично, потому что этот материал пойдет лишь в начало доклада, а в основной его части я планирую все-таки рассказать про популярные на данный момент принципы проектирования (как общие, так и ООП): SoC, DRY, KISS, YAGNI, Low Coupling, High Cohesion, а также пятерку SOLID. Принципов много, и каждый из них, конечно, достоин отдельного небольшого доклада, поэтому придется рассматривать их достаточно поверхностно. Также очень хочется успеть дать какие-то взаимосвязи между ними, чтобы они лучше запоминались, и хотя бы пару примеров. Таким образом, доклад будет больше посвящен теории, а не практике.

Вторым докладчиком будет мой бывший одногруппник Денис Резник. Тема его доклада: “Защита данных в SQL Server 2008 при помощи Transparent Data Encryption”.

Встреча будет проходить в Харьковском национальном университете радиоэлектроники (ХНУРЭ), пр. Ленина 14, ауд. 329 (м. Научная), 5 марта 2010 в 18:25, то есть в эту пятницу вечером.

Если что-то изменится с местом, временем или форматом встречи – я сообщу дополнительно в комментариях.

Жду всех, кто захочет послушать и пообщаться на эту тему :)

Архитектура по Фаулеру

Пару дней назад наткнулся на статью Фаулера "Кому нужен архитектор?" ("Who Needs an Architect?"). Ей уже сто лет в обед, но я ее первый раз вижу.

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

"Whether something is part of the architecture is entirely based on whether the developers think it is important. People who build “enterprise applications” tend to think that persistence is crucial. When they start to draw their architecture, they start with three layers. They will mention “and we use Oracle for our database and have our own persistence layer to map objects onto it.” But a medical imaging application might include Oracle without it being considered part of the architecture. That is because most of the complication is in analyzing the images, not in storing them. Fetching and storing images is done by one little part of the application and most of the developers ignore it."

А вот еще кусочек:

"There is no theoretical reason that anything is hard to change about software. If you pick any one aspect of software then you can make it easy to change, but we don’t know how to make everything easy to change. Making something easy to change makes the overall system a little more complex, and making everything easy to change makes the entire system very complex. Complexity is what makes software hard to change. That, and duplication."

Это волшебно. Рекомендую почитать.

Если понравится, можно почитать еще пару интересных статей на тему архитектуры и проектирования:

Gaperton on Software Architecture - статья Gaperton о похожем с примерами и заодно с пояснениями, как согласуется архитектура с дизайном
The Difference between Marketecture and Tarchitecture - статья о компонентах архитектуры: Market-oriented и Technical-oriented
Is Design Dead? - статья об эволюционном проектировании, много разговоров на тему того, что ХР - это супер-пупер, но в целом есть что полезного почерпнуть

Что думаете?

PS. Поделитесь чем-нибудь интересным на эту тему.