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



Имея параметры видимости наблюдателя (направление взгляда, расстояние видимости и угол поля зрения), нам нужно найти видимую для него область, т.е. определить область видимости (field of view, FoV). Если препятствия отсутствуют, это будет сектор круга, состоящий из двух граней (радиусов) и соединяющей их дуги (см. Рис. 1). Кроме того, имея заданную точку мира, мы должны быстро определить, видима ли она для наблюдателя, т.е. необходимо обрабатывать запросы линии взгляда (line of sight, LOS) для заданной точки. Обе эти операции можно выполнить достаточно эффективно для использования при рендеринге в реальном времени.

У современного человека слово «форекс» непременно ассоциируется с нелестными эпитетами, самый безобидный из которых — «казино». По смыслу именно «казино» лучше всего отражает суть предмета: игроки форекс делают ставки на рост или падение котировок финансовых инструментов, отдавая часть своих денег в виде комиссии за операции. Остальные негативные сравнения по большей части вызваны некомпетентностью и жадностью участников этого сегмента индустрии развлечений, которые становятся жертвами многочисленных паразитирующих на нём дельцов.

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



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

Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:

• реализован как обычное B-дерево, а мы знаем что
• страницы B-дерева имеют лучшую заполняемость, кроме того,
• Z-ключи сами по себе более компактны
• B-дерево имеет естественный порядок обхода, в отличие от R-дерева
• B-дерево быстрее строится
• B-дерево лучше сбалансировано
• B-дерево понятнее, не зависит от эвристики расщепления/слияния страниц
• B-дерево не деградирует при постоянных изменениях
• ...

Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.

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

Много ядер не бывает

Атомарные операции (atomics), например, Compare-and-Swap (CAS) или Fetch-and-Add (FAA) широко распространены в параллельном программировании.

Мульти- или многоядерные архитектуры установлены одинаково как в продуктах настольных и серверных компьютеров, так и в крупных центрах обработки данных и суперкомпьютерах. Примеры конструкций включают Intel Xeon Phi с 61 ядрами на чипе, который установлен в Tianhe-2, или AMD Bulldozer с 32 ядрами на узле, развернутых в Cray XE6. Кроме того, количество ядер на кристалле неуклонно растет и процессоры с сотнями ядер, по прогнозам, будут изготовлены в обозримом будущем. Общей чертой всех этих архитектур является растущая сложность подсистем памяти, характеризующаяся несколькими уровнями кэш-памяти с разными политиками включения, различными протоколами когерентности кэш-памяти, а также различными сетевыми топологиями на чипе, соединяющими ядра и кэш-память.

Практически все такие архитектуры обеспечивают атомарные операции, которые имеют многочисленные применения в параллельном коде. Многие из них (например, Test-and-Set) могут быть использованы для реализации блокировок и других механизмов синхронизации. Другие, например, Fetch-and-Add и Compare-and-Swap позволяют строить разные lock-free и wait-free алгоритмы и структуры данных, которые имеют более прочные гарантии прогресса, чем блокировки на основе кода. Несмотря на их важность и повсеместное употребление, выполнение атомарных операций полностью не проанализировано до сих пор. Например, по общему мнению, Compare-and-Swap идет медленнее, чем Fetch-and-Add. Тем не менее, это всего лишь показывает, что семантика Compare-and-Swap вводит понятие «wasted work», в результате – более низкая производительность некоторого кода.

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

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

Под катом много картинок, в том числе анимированных gif.

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

Вот первичный анонс о внедрении нового сборщика, датированный августом 2015-го:

В Go создаётся сборщик мусора (GC) не только для 2015 года, но и для 2025-го, и ещё дальше… Сборщик в Go 1.5 возвещает о наступлении будущего, в котором паузы на сборку больше не являются барьером для перехода на безопасный язык. Это будущее, в котором приложения без труда масштабируются вместе с оборудованием, и по мере роста мощности оборудования сборщик мусора больше не является сдерживающим фактором при создании более качественного, масштабируемого ПО. Go — хороший язык для использования как минимум в ближайший десяток лет.

Создатели утверждают, что они не просто решили проблему пауз на сборку мусора, а пошли куда дальше:

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

Более того, освободившись от бремени поддержки десятков настроек, разработчики могут сосредоточиться на улучшении runtime’а приложения.

Не сомневаюсь, что многие пользователи Go были просто счастливы получить новый подход к runtime’у в Go. Но у меня есть претензии к этим заявлениям: они выглядят как недостоверный маркетинговый булшит. А поскольку они раз за разом воспроизводятся в Сети, пришло время подробно с ними разобраться.

После не сильно долгих уговоров, меня убедили, что 30 место не так уж и плохо, и написать статью стоит. Я – участник с ником Stef, и занял в песочнице около 30 места.

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

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

Привет, Хабр! Меня зовут Дичковский Алексей, и я хочу вам рассказать о том, как я потратил полтора месяца своей жизни на написание бота для упрощённой версии DotA.

Ежегодно компания Mail.ru проводит онлайн-чемпионат по программированию игровых стратегий (Russian AI Cup 2016). Я принимал участие в данном соревновании в 2012 году (СodeTanks) и, совсем немного, в 2013 (СodeTroopers). В этом году, изрядно наевшись веб разработкой, я решил попробовать принять участие ещё раз. Я изначально не надеялся (но, конечно же, очень хотел) занять какое-либо призовое место и в целом для меня это был скорее тест, насколько я ещё могу реализовать нечто интересное. О том, что из этого получилось, можно прочитать под катом.

Итак, заканчивается 2016 год. Для нас он был очень активным. Было 6 выпусков нашего курса для аналитиков, 5 выпусков курса для менеджеров (Data-MBA). Мы запустили курс в Санкт-Петербурге и уже провели первый выпуск. В партнерстве мы также обучали студентов Высшей Школы Экономики и Российской Экономической Школы, проводили мастер-классы в Сколково, участвовали в десятках хакатонов по всей стране, консультировали ведущие компании касательно применения аналитики и монетизации данных. В этом году один из наших преподавателей стал первым в мире в рейтинге Kaggle.

Около десяти лет тому назад симметричная криптография, основанная на ГОСТ 28147-89, перестала удовлетворять потребностям аппаратных платформ по скоростным параметрам. Скорости криптопреобразований, обеспечиваемые алгоритмами реализованными на регистрах общего назначения процессоров, не успевали за скоростями обмена информацией в сетях и на дисковых накопителях.

С другой стороны (американской), появился AES-256, который показывал гораздо лучшие скоростные параметры при той же степени криптостойкости.

В этой ситуации 8 центр ФСБ начал работы над новым блочным шифром, который получил в последствии название «Кузнечик» от начальных букв фамилий авторов.

Изначально это была бесперспективная затея, поскольку повторялась логика шифра AES, но если тот был ускорен аппаратно в процессорах Интел и АМД, то у Кузнечика такого аппаратного ускорения на этих процессорах конечно быть не могло.

Так что Кузнечик, это классический пример выброшенных на ветер бюджетных денег и не малых…

Идиома ranges — крайне удачное развитие итераторов. Она позволяет писать высокопроизводительный код, не выделяющий память, где это не надо, находясь на предельно высоком уровне абстракции. Кроме того делает библиотеки гораздо более универсальными, а их интерфейсы гибкими. Под катом краткое описание и практические примеры использования идиомы, тесты производительности, а так же сравнение с популярными реализациями итераторов в C++ и C#.

Маршрутизация ортогональных соединений в редакторах диаграмм

В данной статье я покажу, как решить проблему маршрутизации соединений в редакторе диаграмм типа MS Visio. Здесь будет минимум теории и максимум практики. Если вам нужно быстро реализовать маршрутизацию соединений в двумерной сцене, и вы первый раз сталкиваетесь с подобной проблемой — то эта статья для вас.

Проблематика

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

Многие из вас работали с Microsoft Visio, и конечно же оценили, как красиво автоматически маршрутизируются стрелочки. Конечно, и Visio не всегда справляется, и для таких случаев есть возможность ручной подгонки. Но тем не менее, не рассматривая крайние ситуации — мне захотелось это повторить. Действительно, ведь там все этим проблемы достаточно неплохо решены.

В этом году исследователи из Google Brain опубликовали статью под названием Exploring the Limits of Language Modeling (Исследование границ языкового моделирования), в которой была описана языковая модель, позволившая значительно снизить перплексию (с примерно 50 до 30) на словаре One Billion Word Benchmark.

В этом посте мы расскажем про самый низкий уровень этой модели — представление символов.

Простенький алгоритм генерации идеальных лабиринтов в самом обычном двухмерном пространстве. Nuff said, остальное под катом.

Привет Хабр! Я решил продолжить серию статей про гипотезу Эйлера, написав несколько улучшенных версий программ для решения диофантова уравнения вида a⁵ + b⁵ + c⁵ + d⁵ = e⁵.


Как известно, для того, чтобы решить какую-либо сложную вычислительную задачу, нужно обратить внимание как минимум на следующие пункты:

1. Эффективный алгоритм
2. Быстрая реализация
3. Мощное железо
4. Распараллеливание

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

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