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

Метод Монте-Карло это алгоритм принятия решений, часто используемый в играх в качестве основы искусственного интеллекта. Сильное влияние он оказал на программы для игры в Го, хотя находит свое применение и в других играх, как настольных, так и обычных компьютерных (например Total War: Rome II). Так же, стоит отметить, что метод Монте-Карло используется в нашумевшей программе AlphaGo, победившей го-профессионала 9-го дана Ли Седоля в серии из 5 игр.

В данной статье хотелось бы рассказать про версию алгоритма Монте-Карло под названием Upper Confidence bound applied to Trees (UCT). Именно после публикации этого алгоритма в 2006-м году, программы для игры в Го сильно усилили свои позиции и достигли значительных успехов в игре против человека.

Будучи дилетантом в области разработки приложений, я испытал сложности с пониманием алгоритма работы обратной польской нотации, а если быть точнее — алгоритма подготовки стека. Делу так же мало помогли статьи в «интернетах».

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

Делу помогли две статьи. Одна из них на википедии, а вторая была написана замечательным пользователем хабра, GORKOFF, который объяснил все буквально «на пальцах».

Однако до конца я так и не понял тот важный вопрос: как же построить стек?

от пер. Исходный материал датируется 2001 годом, так что некоторые моменты могут показаться забавными. Так же все отсылки на «сегодня», «в настоящий момент» и т.п. относятся к тому периоду.
Изложение ведется от лица автора, как и в оригинале.
Все ссылки добавлены мною.

Изложение организовано в хронологическом порядке. Мы начнем с наших экспериментов, легших в основу создания Lua в 1993, и пройдемся через восемь лет обсуждений, решений, работы и развлечений.

Многопользовательская онлайн игра – передача пакетов и обмен сообщеями между клиентами и сером(client-server,p2p,tcp/upd, графы)
Представьте себе многопользовательсукую игру по типу lineage

Если вы уже наигрались с Go, устали от копипасты, ручного жонглирования типами и подумываете вернуться на какой-нибудь Python или, прости господи, PHP, то позвольте предложить вам попробовать язык D, где типизация хоть и тоже статическая, но она не путается под ногами и позволяет писать не менее выразительный код, чем на языках с динамической типизацией. А чтобы переход был не такой болезненный, вашему вниманию предлагается перевод Tour of the Go c эквивалентным кодом на D и краткими пояснениями.

Часть первая. Основы.

Глава 1. В поисках сокровищ

Иногда процесс разработки мобильной игры, можно сравнить с поиском сокровищ. Вы тяжело трудитесь, день за днем, месяц за месяцем, строите планы и на них базируются ваши ожидания. Мечтаете. Конечно. Вы много мечтаете, что однажды наступит тот самый день, когда ваши поиски закончатся и все ваши мечты сбудутся. Это могут быть деньги, слава или уважение от миллионов. Но мечты для романтиков, а в реальной жизни все продолжается. Поиски. Разработка.

Но, что будет, если вы делаете игру о поиске тех самых сокровищ? На это у нас пока еще нет ответа, но мы, хотябы попытались. Мы кое-что нашли. А сокровище это или нет, вопрос к тебе, дорогой читатель.



Если вы читаете эту статью, значит мы выжили после разработки третьей по счету мобильной игры и выпустили её в свет. За время разработки, я много раз открывал заветную иконку хабры, дабы увидеть очередной рассказ от разработчиков, которые делятся своим опытом и впечатлениями. К сожалению, многие разработчики упускают много тонкостей и нюансов, особенно, если это касается бюджета и продвижения их игры, а зря.

Недавно ZlodeiBaal опубликовал статью «Нейрореволюция в головах и сёлах», в которой привел обзор возможностей современных нейронных сетей. Самым интересным, на мой взгляд, является подход с использованием сверточных сетей для сегментации изображений, про этот подход и пойдет речь в статье.



Уже давно появилось желание изучить сверточные сети и узнать что-то новое, к тому же под рукой есть несколько последних Tesla K40 с 12Гб памяти, Tesla c2050, обычные видеокарты, Jetson TK1 и ноутбук с мобильной GT525M, интереснее всего конечно попробовать на TK1, так как его можно использовать практически везде, хоть на столб фонарный повесить. Самое первое с чего начал, это распознавание цифр, тут конечно удивить нечем, цифры уже давно неплохо распознаются сетями, но при этом постоянно возникает потребность в новых приложениях, которые должны что-то распознавать: номера домов, номера автомобилей, номера вагонов и т.д. Все бы хорошо, но задача распознавания цифр является лишь частью более общих задач.

В задачах искусственного интеллекта применяются различные модели представления знаний и методы вычислений — мягкие вычисления, генетические алгоритмы, нейросети, логические модели и другие подходы. Все эти методы основаны на символьных вычислениях и поэтому могут быть реализованы на основе языка PROLOG.
Здесь мы рассмотрим методы построения интеллектуальных систем на основе логического подхода, который наиболее близок природе логического программирования и часто применяется в экспертных системах.

В последнее время всё чаще и чаще слышишь мнение, что сейчас происходит технологическая революция. Бытует мнение, что мир стремительно меняется.



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

Я работаю в области связанной с анализом изображений. Это одна из областей которую новые идеи затронули сильнее всего. Одна из таких идей — свёрточные нейронные сети. Четыре года назад с их помощью впервые начали выигрывать конкурсы по обработке изображений. Победы не остались незамеченными. Нейронными сетями, до тех пор стоящими на вторых ролях, стали заниматься и пользоваться десятки тысяч последователей. В результате, полтора-два года назад начался бум, породивший множество идей, алгоритмов, статей.

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

Кто лишится в ближайшие лет десять работы, а у кого будут новые перспективные вакансии.

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

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

Продолжение цикла статей о физике в играх про Соника.

Примечание:

Обзор затрагивает все четыре части игры на Genesis/Mega Drive и Sonic CD.

Все написанное ниже относится к ситуации, когда Соник находится на плоской сухой поверхности, не имея специальных бонусов. Кривые, физика поведения в воде, бонусы Super Sonic и Speed Shoes будут рассмотрены в отдельных статьях. Под шагами в статье понимаются программные циклы, а не шаги персонажа.

От переводчика: этот пост — перевод одной из частей масштабного обзора физики (Sonic Physics Guide) в играх серии Sonic the Hedgehog для Sega Genesis/Mega Drive и Sonic CD. В следующих частях рассматриваются такие темы: бег, прыжки, вращение, потеря колец, поведение под водой, суперскорость, специальные возможности, камера, анимации и некоторые другие. Так как частей много (14 штук), в конце поста я добавил опрос. Стоит ли продолжать — решать вам.

Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.

Сначала этот текст был написан в виде комментария к теме победителя данного конкурса. Но в итоге объем текста стал таким большим, что было решено выделить его в отдельную тему. Так что предполагается, что читатель в курсе о конкурсе и прочёл тему победителя. Также можете почитать историю 30-го места.

Сразу дам ссылку на репозиторий с исходным кодом — помимо непосредственно исходников там же есть вся история коммитов. Например, интересным может показаться время, в которое был совершён коммит с комментарием «спать пора».

В целом, сложилось такое ощущение, что у большинства лидеров были примерно одинаковые основные идеи для итоговой стратегии:

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

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

Хочу рассказать о своем участии и победе в ежегодном соревновании по программированию ИИ «Russian AI Cup 2015» от Mail.Ru Group. Посмотреть подробные правила соревнования и записи игры желающие могут на сайте соревнования russianaicup.ru.



В этом году соревнование было организовано на совершенно новом уровне. Изменения произошли как в масштабности игрового мира, в котором действует ИИ, так и на сайте соревнования. Благодаря трехмерной визуализации, игры смотрелись гораздо увлекательнее. По зрелищности, на мой взгляд, соревнование значительно превзошло прошлогодний хоккей, и «солдатиков» 2013 года.

Участнику предлагалось написать ИИ для управления автомобилем в гонках на выживание. Как и в прошлом году, задача была «с физикой». Но на это раз исходники «физического движка» были открыты. Еще, в отличие от прошлого года, на этот раз все случайные явления в игровом мире были наглядны — случайная карта, случайно расставленные бонусы. Сразу было видно — когда удача на твоей стороне, а когда она от тебя отвернулась. В прошлогоднем хоккее, даже наблюдая за игрой значительно отличающихся по силе противников, было трудно понять произошел выигрыш благодаря случаю или мастерству. Думаю, это положительно сказалось на зрелищности соревнования.

Краткое описание правил

Цель — проехать 2 круга по замкнутой трассе быстрее всех. Точнее надо набрать больше всех очков, но приехать первым — это основной способ заработать очки. Еще очки дают за сбор бонусов по дороге и нанесение урона противникам. Трасса, как конструктор, собирается из квадратных «тайлов», это прямолинейные участки трассы, углы (поворот трассы на 90 градусов), или перекрестки (Т образные и обычные). Нужно ехать по ключевым точкам («тайлам») трассы в определенном порядке – иногда приходится делать петли, иногда вообще ехать назад. Еще у машинок есть возможность разливать за собой лужи мазута, стрелять друг в друга специальными снарядами (шины и шайбы), и использовать особый ускоритель «нитро». Заряды для всех этих приспособлений ограничены, и пополняются подбиранием случайно разбросанных по карте бонусов.

Расскажу, как устроен мой ИИ, и благодаря чему (как я думаю) удалось победить.

Введение

В этом году в Russian AI Cup надо было запрограммировать бота для управления машинкой (а в финале даже двумя!), и я решил впервые поучаствовать, так как тема показалась близкой и родной: фанат гонок, периодически езжу катать в картинг (хоть и без выдающихся результатов), вечера часто провожу, катаясь по виртуальным Гавайям в Test Drive Unlimited или Nurburgring в GTR Evolution.

Высокого места я в итоге не занял (30 место в финале, песочницу закончил на 48 месте), но небольшое время между вторым раундом и финалом был в топ-10 песочницы. Также, судя по форуму соревнования, набор костылей решений как у меня больше никто не использовал, так что если желаете узнать подробностей — добро пожаловать под кат. Наиболее интересная часть в посте, пожалуй, про поиск оптимальной траектории.

Поводом для написания статьи стала публикация исходного кода языка Swift — мне стало интересно поближе познакомиться с ним. В глаза сразу же бросилась схожесть синтаксиса с другим молодым языком программирования под названием Rust, к тому же за схожими синтаксическими конструкциями просматривалась и схожая область применения этих языков. Оба языка имеют сильную статическую типизацию с локальным выводом типов, оба компилируются напрямую в машинный код. И тот и другой языки впитали в себя многие приемы из мира функционального программирования. И Swift и Rust имеют средства для запуска кода, написанного на C, что позволяет без труда писать обертки над огромным количеством библиотек. Оба языка рассматриваются как замена существующим системным языкам типа C, C++, ObjectiveC. Так что же в них общего, а что различается?

Введение

«Повторение придаёт нелепости вид благоразумия.» – Норман Вайлдбергер

(в оригинале: "Repetition renders the ridiculous reasonable." – Norman Wildberger)

Этот документ является учебным пособием по сложным конструкциям языка Nim. Помните, что этот документ в чём-то устарел, а в руководстве есть гораздо больше актуальных примеров по сложным особенностям языка.