Генератор для 3х зависимых дискретных величин.

[Sinclair]

Есть такая задача:

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

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

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

Так же, я набрел еще на одно решение: Генерировать ладьи любым способом, но каждый раз, когда ладья попадает на какую-то позицию, вычитать из данного элемента распределения некоторую величину, уменьшая, таким обрзом, вероятность попадания сюда в дальнейшем. Таким образом, "экранируемые" элементы распределения будут получать со временем бонус вероятности и выпадать, в соответствии с заданным распределением. Проблема в том, что у данного подхода отвратительные спектральные характеристики. То есть, при большом числе генераций ладьи достигнут заданного распределения, но при первых, например, 100 генерациях таким алгоритмом, распределение будет заведомо сдвинуто. А это тоже недопустимо.

Может быть кто-то сможет предложить иное решение, или объяснить, как допилить эти.

[ИСН]

Проведя эксперимент с открыванием коробки очень большое число раз, Вы можете just as well хранить тупо всю информацию об этом. В конце концов, $64^3$ - это меньше миллиона. И никто не гарантировал, что Ваше совместное распределение можно описать как-то проще, нежели задав его полностью. Приближая его независимым распределением, мы натыкаемся на проблему - как Вы и отметили - что оно очевидным образом не независимо. Хотите приблизить чем-то ещё, более подходящим, но простым?

[Sinclair]

ИСН в сообщении #671935 писал(а):

Проведя эксперимент с открыванием коробки очень большое число раз, Вы можете just as well хранить тупо всю информацию об этом. В конце концов, $64^3$ - это меньше миллиона. И никто не гарантировал, что Ваше совместное распределение можно описать как-то проще, нежели задав его полностью. Приближая его независимым распределением, мы натыкаемся на проблему - как Вы и отметили - что оно очевидным образом не независимо. Хотите приблизить чем-то ещё, более подходящим, но простым?

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

[ewert]

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

[Sinclair]

ewert в сообщении #671950 писал(а):

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

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

[ewert]

Sinclair в сообщении #671953 писал(а):

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

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

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

[ИСН]

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

[Sinclair]

ewert в сообщении #672088 писал(а):

Sinclair в сообщении #671953 писал(а):

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

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

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

ewert в сообщении #672088 писал(а):

Sinclair в сообщении #671953 писал(а):

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

Спасибо, я об этом еще не думал. Удивительно. Это простейшее решение не пришло мне в голову. Более того, я даже думал над ним, пока задача имела немного другой вид (там тоже были определенные сложности), но после ее изменения как то упустил из виду. Я сейчас начну думать в этом направлении. Впрочем, ту же проблему, что была раньше, можно упомянуть и сейчас - как распределить по трем позициям 3 ладьи? Это не так то просто. Ну или не было просто в том случае, который обдумывал я. Сейчас буду разбираться.

-- 15.01.2013, 23:38 --

ИСН в сообщении #672094 писал(а):

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

Жаль не знаком с темой. Выглядит и правда похоже.

[Евгений Машеров]

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

[TOTAL]

Sinclair в сообщении #671902 писал(а):

Так же, я набрел еще на одно решение: Генерировать ладьи любым способом, но каждый раз, когда ладья попадает на какую-то позицию, вычитать из данного элемента распределения некоторую величину, уменьшая, таким обрзом, вероятность попадания сюда в дальнейшем. Таким образом, "экранируемые" элементы распределения будут получать со временем бонус вероятности и выпадать, в соответствии с заданным распределением. Проблема в том, что у данного подхода отвратительные спектральные характеристики. То есть, при большом числе генераций ладьи достигнут заданного распределения, но при первых, например, 100 генерациях таким алгоритмом, распределение будет заведомо сдвинуто. А это тоже недопустимо.

На первые 100 генераций не обращайте внимания, считайте их разогревом двигателя перед стартом.

[Sinclair]

Так. Я подумал ночью над решением

ewert в сообщении #672088 писал(а):

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

и, в общем, к сожалению, я просто вчера тормозил. Это решение не удовлетворительное по той же причине, по которой неудовлетворительна последовательная генерация - частота отбраковки различных вариантов неравномерна. Просто в данном случае это учитывается сразу для 3х ладей.
Объясню проблему. Вот если у нас на одной линии (в рамках данного примера для упрощения представим, что ладьи бьют только по горизонтали, и их две) находятся клетки, совокупная вероятность нахождения в которых красной ладьи равна .3, и совокупная вероятность нахождения зеленой ладьи равна .3. С учетом отбракованых вариантов, вероятность нахождения ладей на этой линии изменится до .21 и .21 соответственно. То есть, будут отбракованы варианты, при которых ладьи одновременно выпадают на этой линии. Если же на другой линии совокупные вероятности нахождения красной и зеленой ладей равны .1 и .1 соответственно, то после отбраковки эти вероятности будут равны .09 и .09. Поскольку 0.21/0.09 не равно 0.3/0.1, мы видим, что вероятности меняются неравномерно. То есть, генерируются результаты с другим распределением.

Евгений Машеров в сообщении #672241 писал(а):

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

В этом случае просто итоговое распределение для красной, например, ладьи, будет усредненным распределением между тремя распределениями 1) "истинное распределение красной ладьи", 2) "распределение красной ладьи, прореженное одной ладьей", 3) "распределение красной ладьи, прореженное двумя ладьями". То есть, это тоже не будет точным.

-- 16.01.2013, 12:09 --

TOTAL в сообщении #672246 писал(а):

На первые 100 генераций не обращайте внимания, считайте их разогревом двигателя перед стартом.

Да, я склонялся к чему-то такому. Вычесть случайное колличество из каждого элемента перед началом генерации. Я подумаю еще над этим вариантом, сейчас пытаюсь с другой стороны зайти. Впрочем, тут есть те же проблемы, что в других вариантах:
Предположим, что у нас есть клетка, на которой красная и зеленая ладья находятся с вероятностью .5, а желтая - 0, при этом на остальных клетках строки и столбца все вероятности равны нулю. Понятно, что в данном случае на этом месте обязана стоять либо красная ладья, либо зеленая - иначе совокупная вероятность нахождения здесь будет меньше 1. Но пока ни при одном из методов генерации (включая этот) данная проблема не решена. То есть, чем ближе на каком то столбце/строке совокупная вероятность нахождения всех ладей к 1, тем больше отклоняются распределения.
Этот момент мне кажется самой серьезной из имеющихся проблем.

[TOTAL]

Sinclair в сообщении #672247 писал(а):

То есть, чем ближе на каком то столбце/строке совокупная вероятность нахождения всех ладей к 1, тем больше отклоняются распределения.

Отклоняются от требуемых. Поэтому надо расставлять ладьи не по требуемым вероятностям, а по вероятностям "с запасом". Эти новые вероятности найти из опыта путем многократных прогонов. Чем чаще отбраковывается какая-то клетка для ладьи, тем сильнее надо увеличить вероятсть попадания ладьи в эту клетку.

[Евгений Машеров]

А собственно? Есть ли проблема?
Имеется статистика по попаданию отдельных ладей в данные клетки. Она, очевидно, отражает только "небьющие" конфигурации. Генерируем случайное размещение с данными вероятностями. Получаем либо битие, либо небитие. В случае, если битие - генерация неудачна, сбрасывается и повторяется опыт вплоть до умпеха. В случае если небитие - сгенерировано расположение в точности с заданными вероятностями, "по построению". Может, и не надо мудрить?

[Sinclair]

TOTAL в сообщении #672255 писал(а):

Sinclair в сообщении #672247 писал(а):

То есть, чем ближе на каком то столбце/строке совокупная вероятность нахождения всех ладей к 1, тем больше отклоняются распределения.

Отклоняются от требуемых. Поэтому надо расставлять ладьи не по требуемым вероятностям, а по вероятностям "с запасом". Эти новые вероятности найти из опыта путем многократных прогонов. Чем чаще отбраковывается какая-то клетка для ладьи, тем сильнее надо увеличить вероятсть попадания ладьи в эту клетку.

Да, но этого недостаточно. Нужно еще и уменьшать вероятность остальных клеток. Вот это важно. В приведенном мною примере про совокупную вероятность 1 на одной клетке - можно сколько угодно увеличивать эту вероятность, но пока мы не занулим вероятности на остальных клетках - попадание в эту клетку не будет стопроцентным. Я пока не решил эту проблему. Рассматриваю варианты с заменой вероятности попадания на вероятность непопадания, и работы с ней. Вероятность непопадания можно просто обратить в 0, а точки со 100% вероятностью попадания можно просто вычеркивать из рассмотрения. В любом случае, похоже, вероятности будут модифицироваться после постановки каждой ладьи. Как - я пока думаю.
Проблема не такая простая, как казалось.

[TOTAL]

Sinclair в сообщении #672263 писал(а):

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

Про какую совокупную вероятность говорите, не вижу проблемы.