Pull to refresh

Учёные доказали превосходство расы терранов в StarCraft 2

Game development *


Двое исследователей из института астрономии при Эдинбургском университете опубликовали результаты статистического моделирования StarCraft 2 в секторе Копрулу, с учётом лучших экономических и военных стратегий для каждой расы.
Читать дальше →
Total votes 155: ↑132 and ↓23 +109
Views 159K
Comments 95

Быстрая генерация массивов случайных чисел для задач имитационного моделирования, статистического оценивания и создания повторной выборки

High performance *Concurrent computing *
Tutorial
Имитационное моделирование с использованием методов Монте-Карло в наше время используется практически во всех областях операционной деятельности, где требуется многократное принятие решений по итогам анализа поступающих из внешнего мира данных. При этом важную роль начинает играть качество, производительность и доступность генераторов случайных чисел, использующихся для придания абстрактному методу черт реальной задачи, решаемой специалистом. Как я недавно выяснил, этот вопрос начинает играть решающее значение при переходе к параллельному программированию… Вы тоже столкнулись с этой проблемой, и хотите знать, как в Windows можно быстро получить массивы случайных чисел с нужным распределением?
Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Views 15K
Comments 2

Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?

Game development *Algorithms *

Реми Кулом (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото Ёды

В 1994 году компьютер обыграл чемпиона мира по шашкам, в 1997 году — по шахматам. Сегодня компьютеры превосходят людей абсолютно во всех популярных играх с полной информацией, кроме одной — го.

У классической игры с 2500-летней историей очень простые правила, но компьютерные программы даже близко не могут подобраться к победе над лучшими гроссмейстерами, пишет Wired.
Читать дальше →
Total votes 199: ↑175 and ↓24 +151
Views 157K
Comments 232

Метод Монте-Карло и его точность

Mathematics *
Tutorial
Под метдом Монте-Карло понимается численный метод решения
математических задач при помощи моделирования случайных величин. Представление об истории метода и простейшие примеры его применения можно найти в Википедии.

В самом методе нет ничего сложного. Именно эта простота объясняет популярность данного метода.

Метод имеет две основных особенности. Первая — простая структура вычислительного алгоритма. Вторая — ошибка вычислений, как правило, пропорциональна
\sqrt{D\zeta/N}, где D\zeta — некоторая постоянная, а N — число испытаний. Ясно, что добиться высокой точности на таком пути невозможно. Поэтому обычно говорят, что метод Монте-Карло особенно эффективен при решении тех задач, в которых результат нужен с небольшой точностью.

Однако одну и ту же задачу можно решать различными вариантами метода Монте-Карло, которым отвечают различные значения D\zeta. Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее значение D\zeta.

Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Views 199K
Comments 9

Поиск по дереву методом Монте-Карло и крестики-нолики

Programming *Algorithms *
Sandbox

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


Читать дальше →
Total votes 20: ↑19 and ↓1 +18
Views 15K
Comments 2

Я смоделировал цену биткойна за весь 2018 год. Вы не поверите в результат (прим. перевод. и будете правы)

Cloud4Y corporate blog Mathematics *Research and forecasts in IT *Studying in IT Reading room
Translation
Дисклеймер: статья написана из любопытства и интереса, является личным мнением автора и не предназначена для принятия решений о инвестициях. Для этих целей примите личные меры должной осмотрительности, не совершайте глупостей и не вкладывайте денег больше, чем можете себе позволить потерять.

Дисклеймер 2: нет никаких гарантий, что доходы в будущем будут похожи на доходы в прошлом, а предыдущий рост не указывает на будущий. Я понимаю. Я уже говорил, что это из чистого любопытства? Не относитесь к этому как к строгой науке, для этих целей я бы опубликовал научную статью, а не публикацию в блоге с гифами и мемами. Take it easy:)

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



Это будет всего лишь 5-минутное приключение.

Я делаю простую симуляцию методом Монте-Карло по ежедневным приростам долларовой цены биткойна, чтобы попытаться узнать, какова будет его самая вероятная цена к концу 2018 года. Вы можете найти весь код, используемый мной для этого, на GitHub.
Читать дальше →
Total votes 42: ↑29 and ↓13 +16
Views 109K
Comments 74

Простой способ построения изотропных псевдослучайных рядов точек синего шума

Algorithms *Mathematics *
Translation
В данной статье я описываю простой способ создания ряда точек, основанных на псевдослучайном ряде с низким расхождением, демонстрирующем улучшенные изотропные свойства синего шума. Он обеспечивает высокую скорость схождения с минимальными артефактами алиасинга.


Рисунок 1. Первые 100, 200, 500, 1000, 2000 и 5000 точек выборки из предлагаемого прогрессивного нестохастического ряда точек (уравнение 11), демонстрирующие почти изотропные характеристики синего шума с быстрой сходимостью QMC и сниженным количеством артефактов. Ряд основан на новой простой псевдослучайной последовательности с низким расхождением $R_2$.

Введение


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


Рисунок 2. Сравнение регулярной решётки (слева) с тремя разными псевдослучайными функциями (посередине) и простым случайным распределением (справа). Заметьте, что псевдослучайные распределения выглядят менее регулярными, чем решётка, но имеют не так много скоплений и разрежений точек, как случайное распределение.
Читать дальше →
Total votes 19: ↑19 and ↓0 +19
Views 2.5K
Comments 1

Разработка ИИ на примере игры Dicey Dungeons

Game development *Algorithms *Artificial Intelligence
Translation

Примерно в течение месяца я решал одну из самых сложных технических проблем моей новой игры Dicey Dungeons — совершенствол ИИ для финального релиза игры. Это была довольно интересная работа, и многое в ней стало для меня новым, поэтому я решил немного о ней написать.

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

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

Ну, давайте начнём с объяснения задачи!
Total votes 26: ↑25 and ↓1 +24
Views 11K
Comments 1

Мюонный катализ с точки зрения квантовой химии. Часть II: электронная vs. мюонная химическая связь

Entertaining tasks Energy and batteries Nanotechnologies Physics Chemistry
Многабукафф о том, что квантовая химия думает о принципе работы мюонного катализа: как именно мюон понижает температуру требуемой плазмы. В двух частях (первую часть можно прочитать тут).

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

Но те, кто хочет посмотреть на формулки, графики, и узреть концептуальную суть квантовой химии в применении к наипростейшим (квази)молекулам, welcome под кат.

Читать дальше →
Total votes 22: ↑22 and ↓0 +22
Views 6.3K
Comments 6

Применение интегрирования Монте-Карло в рендеринге

Working with 3D-graphics *Algorithms *Mathematics *
Translation
Все мы изучали в курсе математики численные методы. Это такие методы, как интегрирование, интерполяция, ряды и так далее. Существует два вида числовых методов: детерминированные и рандомизированные.

Типичный детерминированный метод интегрирования функции $f$ в интервале $[a, b]$ выглядит так: мы берём $n + 1$ равномерно расположенных в интервале точек $t_0 = a, t_1 = a + \frac{b - a }{n}, \ldots, t_n - b$, вычисляем $f$ в средней точке $\frac{t_i + t_{i + 1}}{2}$ каждого из интервалов, определяемых этими точками, суммируем результаты и умножаем на ширину каждого интервала $\frac{b -a}{b}$. Для достаточно непрерывных функций $f$ при увеличении $n$ результат будет сходиться к верному значению.

Читать дальше →
Total votes 17: ↑15 and ↓2 +13
Views 3.9K
Comments 1

Цепи Маркова для процедурной генерации зданий

Game development *
Translation
image

Примечание: полный исходный код этого проекта можно найти [здесь]. Так как он является частью более масштабного проекта, я рекомендую смотреть коммит на момент выпуска этой статьи, или файл /source/helpers/arraymath.h, а также /source/world/blueprint.cpp.

В этой статье я хочу подробно рассказать о принципах использования цепей Маркова и статистики для процедурной генерации 3D-зданий и других систем.

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

Этот метод является обобщённым способом процедурной генерации систем, удовлетворяющих определённым требованиям, поэтому я рекомендую дочитать хотя бы до конца первого раздела, чтобы вы могли понять, сможет ли эта методика быть полезной в вашем случае, потому что ниже я объясняю необходимые требования.
Total votes 30: ↑30 and ↓0 +30
Views 11K
Comments 5

Теория вероятностей для физически точного рендеринга

Working with 3D-graphics *Mathematics *
Translation
image

Введение


В рендеринге часто используется вычисление многомерных определённых интегралов: например, для определения видимости пространственных источников освещения (area light), светимости, доходящей до области пикселя, светимости, поступающей за период времени и облучения, поступающего через полусферу точки поверхности. Вычисление этих интегралов обычно выполняется при помощи интегрирования Монте-Карло, в котором интеграл заменяется ожиданием стохастического эксперимента.

В этой статье я подробно расскажу о базовом процессе интегрирования Монте-Карло, а также о нескольких техниках, позволяющих снизить дисперсию методики. Это будет сделано с практической точки зрения — предполагается, что читатель не сильно знаком с теорией вероятностей, но всё равно хочет разрабатывать эффективные и корректные алгоритмы рендеринга.
Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Views 6.4K
Comments 10

Моделирование двумерной модели Изинга на языке C++ (с применением графического пакета OpenGL)

C++ *Data visualization *Physics
Sandbox

Модель Изинга


Модель Изинга была введена для понимания природы ферромагнетизма и повлияла на изучение фазовых переходов и критических явлений. Ферромагнетизм описывает появление самопроизвольной намагниченности у ферромагнетиков ниже определенной температуры — точки Кюри. В точке Кюри (узкой области температур) происходит упорядочение, в данном случае, выстраивание магнитных моментов, которое влечет фазовый переход, то есть свойства вещества меняются скачком.
Читать дальше →
Total votes 10: ↑10 and ↓0 +10
Views 6.9K
Comments 6

Часть 2. Dракоши. Комбинаторика мира Dракош

Mathematics *Matlab *Artificial Intelligence
В этой части я расскажу как рассчитывал вероятности обнаружения агентов в ячейках в зависимости от плотности заселения пространства Dракошами. А также о том, как можно наблюдать что Dракоши становятся более сознательными жильцами своей вселенной.

Кто такие Dракоши смотрите в первой части.

image
Читать дальше →
Total votes 3: ↑3 and ↓0 +3
Views 1.7K
Comments 0

Бернулли против Байдена

Нерепетитор.ру corporate blog Entertaining tasks Mathematics *Statistics in IT
Tutorial

В последнее время появляется все больше и больше аналитических обзоров результатов выборов, которые рассматривают их с точки зрения законов статистики и направлены, как правило, на изучение необычных явлений, сигнализирующих о возможных фальсификациях (см. "Гаусс против Чурова" и т.п. публикации). Думается, только что завершившиеся выборы президента США (подсчет голосов еще продолжается, причем беспрецедентно длительное время) дадут дополнительный толчок "электоральной математике". В этой статье при помощи классической схемы Бернулли и метода Монте-Карло я попробую оценить вероятность события, которое произошло на наших глазах: как при подсчете нескольких последних процентов голосов результаты голосования на президентских выборах в штате Джорджия "перевернулись", и вместо полпроцентного преимущества Трампа выборы, судя по всему, выигрывает Байден.

Читать далее
Total votes 59: ↑28 and ↓31 -3
Views 16K
Comments 358

А ваш фильтр Калмана правильно работает?

Auriga corporate blog Algorithms *Mathematics *Popular science

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

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

В это же время фильтр Калмана применяется в системах с особыми требованиями по функциональной безопасности, отказ или неисправность которых может привести к человеческим потерям, как это имеет место для автопилотируемых устройств. Таким образом, валидация результатов работы фильтра Калмана – это один из первых вопросов, который должен стоять перед инженером при разработке ПО для подобных систем.

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

Читать далее
Total votes 24: ↑23 and ↓1 +22
Views 7.8K
Comments 8

10 лучших алгоритмов 20 века

Timeweb Cloud corporate blog Algorithms *Mathematics *History of IT Popular science
Translation
Прим. Эта статья была опубликована в майском номере 2000 года журнала SIAM. На рубеже веков появилась «мода» на подведение итогов уходящего столетия. И алгоритмы этой участи не избежали. В этой статье авторы делают обзор 10 лучших алгоритмов 20 века. Возможно, вам будет интересно узнать, какие алгоритмы, по мнению авторов списка, внесли наибольший вклад в развитие науки.

Algos — греческое слово, означающее боль. Algor — латинское слово, означающее холод. Но ни то, ни другое не является корнем слова «алгоритм», которое происходит от имени Аль-Хорезми – арабского ученого девятого века – чья книга «al-jabr wa’l muqabalah» (Китаб аль-джебр ва-ль-мукабала) переросла современные учебники по алгебре для средней школы. Аль-Хорезми подчеркивал важность методических процедур для решения задач. Будь он сегодня здесь, то, несомненно, был бы впечатлен вершинами математического метода, названного в его честь.

Часть из лучших алгоритмов компьютерной эры были освещены в январско-февральском выпуске 2000 года журнала Computing in Science & Engineering — совместном издании Американского института физики и Компьютерного общества IEEE. Приглашенные редакторы Jack Dongarra (Джек Донгарра) из Университета Теннесси и Francis Sullivan (Фрэнсис Салливан) из Института оборонного анализа составили список из 10 алгоритмов, который они назвали «Top Ten Algorithms of the Century».

«Мы попытались собрать 10 алгоритмов, оказавших наибольшее влияние на развитие и практику науки и техники в 20 веке», — пишут Донгарра и Салливан. По признанию авторов, как и в любом рейтинге, их выборы неизбежно будут спорными. Когда дело доходит до выбора лучшего алгоритма, кажется, что он и вовсе не существует.

Итак, вот список 10 лучших алгоритмов в хронологическом порядке. (Все даты и имена стоит воспринимать как аппроксимацию первого порядка. Большинство алгоритмов формируются в течение времени при участии многих ученых).
Читать дальше →
Total votes 48: ↑47 and ↓1 +46
Views 36K
Comments 44