Комментарии 10
Sonnet написал сапёра немногим больше https://allchat.online/artifact/667ea2f3d772ce2ce96ed04f
предлагаю челендж: реализуйте алгоритм, решающий головоломку "Сапёр" с использованием метода Монте-Карло или другого метода, который показывает лучшие результаты по сравнению с текущим!
Людям далеким от математики было бы интересно увидеть это живьём. Я прочитал статью вики про метод Монте-Карло, но совсем ничего не понял :(
Вообще - Монте-Карло, это целая группа методов. Использовать их достаточно просто, например для рассчёта числа pi, или нахождения какого-нибудь интеграла. Но есть большое НО. Сам метод достаточно время затратный для расчетов и в целом - не всегда рациональный, поэтому нам в универе не всегда разрешали его использовать.
Самое простое объяснение - решение (точнее, оценка - о решении говорить не стОит), приблизительное, как правило, математических и иных задач путём генерации случайных чисел. Скажем, бессмысленный пример - нужно оценить площадь фигуры. Рисуем вокруг неё квадрат, заполняем этот квадрат случайными равномерно раскиданными по его площади точками, считаем точки, попавшие внутрь фигуры (как - это отдельный разговор, но фигура же должна быть как-то описана в рамках задачи), считаем площадь квадрата, умножаем на отношение числа точек внутри фигуры к общему числу (внутри квадрата). Проще, конечно, палетку использовать 🙂, но я указал, что пример бессмысленный. Задача посложнее (много текста):
У вас есть некий парк самолётов, на которых в случайные моменты времени, величина которых подчиняется некоему закону распределения, в каком-то условно-критическом месте возникает усталостная трещина, которая в процессе эксплуатации воздушных судов увеличивается, опять-таки, случайным образом, но в соответствии с некоторым законом роста таких трещин, и в какой-то момент достигает значения, при котором самолёт считается разрушенным. В парке этих самолётов проводятся периодические осмотры на предмет обнаружения этих трещин и, в случае обнаружения таковой, с последующим ремонтом конструкции, причём информация об обнаружении такого повреждения на одном самолёте приводит к внеплановом у осмотру всех самолётов в парке. Нужно оценить вероятность отказа (разрушения) в таком парке. Аналитическое решение такой задачи, скажем так, замысловато 🙂. Для оценки же такой модели можно воспользоваться компьютерным моделированием (пардон, тавтология случилась) процессов с использованием различных генераторов случайных чисел и прогоном модели с большим количеством генераций парка... Это и будет использованием метода Монте-Карло 🙂
Н-да...
если первый пример я понял, то про самолеты совсем не понял )
и как этот генератор случайных чисел прикручивается к Сапёру?
К Саперу? Ну надо же как-то мины по клеточкам расставить? Допустим, поле 30х30 - всего девятьсот клеточек. Нужно расставить, скажем, пятьдесят мин. Генератору случайных чисел можно задать границы, грубо говоря, от 1 до 900, и в цикле от 1 до 50 он выдаст пятьдесят "случайных" позиций (номеров клеток) из этого диапазона. Если вдруг случаются повторы, их можно отбросить. В кавычках - потому что на самом деле такой генератор вычисляет эти числа по специальным формулам, то есть, они не являются действительно случайными, но для компьютерного моделирования простых вещей это неважно.
Про самолёты я добавил просто, как сложный пример использования метода Монте-Карло - чтобы показать пример довольно серьезной математической задачи. Тридцать с лишним лет назад эта задача была темой кандидатской диссертации 🙂, а метод Монте-Карло применялся в качестве "опытовой" её части.
Я тут подумал, что не до конца ответил про прикручивание ГСЧ к Саперу в контексте предложения автора статьи использовать ММК (метод Монте-Карло) при решении игры. Видимо, речь идёт о том, чтобы в случае отсутствия расчётного решения, исследованного автором, добавить способ случайного выбора (с помощью генератора случайных чисел) среди не открытых ещё клеток (то есть игрок выбирает клетку из "невидимой" части поля наугад), делая так каждый раз, когда прямой расчет невозможен. В этом случае, очевидно, показанная автором кривая оценок вероятности успешных исходов будет иметь другой вид, особенно в области нулевых значений.
В свое время реализовывал перебор гипотез (это гораздо надежнее вероятностного подхода) с отметкой полей с минами и свободных от полей мин. Если одновременно могут существовать несколько гипотез, или превышено число переборов - считал и рисовал вероятности.
Публикации
Головоломка «Сапёр» на Python в 66 строк и ее решение вероятностным алгоритмом