Через что решать задачу про шахматную доску?

Question

[Юрий Янин]

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

UPD 1: не программным кодом. Интересует математическая/расчётная сторона. По какой схеме использования формул пойти?
Изначальная мысль в голове такая. Рассчитать количество всех возможных комбинаций расположения фигур. От них отнять те комбинации где парные фигуры одного цвета взаимозаменяют позиции друг друга. Далее отнять тоже самое но с пешками. Получаем общее число возможных комбинаций. Далее от этого числа отнимаем все вероятности при которых у ладьи на пути не встречаются фигуры. Соответственно со всеми видами комбинаций остальных фигур. После все отнимаем все вероятности, где путь ладье к королю преграждает другая фигура.
Как то так.
Но есть подозрение, что это слишком сложный путь и всё намного проще.

Comments

[Александр]

Да... что то много у нас программистов, а математиков нет )))
Пишу не в ответ, потому что решать до конца лень ))). Может рассуждения помогут.

1. 64 клетки на доске.
2. 32 клетки заняты фигурами
3. Тут туплю. Ладья бьёт по вертикали и горизонтали. 15 линий = 1-на или 2-е ладьи = 1 король. А нужно считать про 2-е ладьи?
4. И тут туплю. 8 клеток (по горизонтали или по вертикали) = 1 клетка для короля = 1 или 2 клетки для ладьи. А теперь проблема: какова вероятность что на линии не окажется кто то из 29-30 оставшихся фигур. Притом, там надо считать несколько вероятностей: расстояние между королем и ладьёй, от 6 до 1 клеток.

Не нужно думать о пешках и какого цвета. 2/15 *(1/30+2/30+3/30+4/30+5/30+6/30) = а вдруг это ответ )

[longclaps]

Александр, что-то тупишь)
Читай код, там чистая математика.

[Александр]

longclaps, Согласен с ТЕОРИЕЙ ВЕРОЯТНОСТЕЙ - у меня проблемы )))
Но что то мне подсказывает что число слишком большое получилось )))
Перебор это хорошо. Самому интересно стало просто вероятность с одним королем и ладьей.
1. Метод. По клеткам. 14/63. Это понятно. у короля 14 клеток на доске из оставшихся 63.
2. Но а если упростить задачу. По горизонтали и вертикали. 1/8+1/8. Что то не сходиться )))

[longclaps]

с ТЕОРИЕЙ ВЕРОЯТНОСТЕЙ - у меня проблемы
что то мне подсказывает что число слишком большое получилось

Проблемы подсказывают?

[Александр]

Ну ...подсказывает...
Не вижу в программе строчек вычисления вероятности что между королем и ладьей есть другая фигура или пешка.

[longclaps]

Александр, или несколько фигур или пешек. Оно там есть.

[Александр]

Юрий Янин
longclaps,
Кстати, повторяющиеся комбинации из-за наличии 8 пешек, 2 коней, 2 слонов. Надо учитывать? Ведь тогда комбинации повторяются.

[Александр]

В продолжении...
Забиваем на 64 клетки и рассматриваем горизонталь.
Тогда нам надо рассчитать только для 8 клеток что король под атакой.
Потом полученное число умножим на 16.

[longclaps]

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

Answer 1

[EVGENY T.]

Можно решить, смоделировав ситуацию.

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

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

3. Запускаете цикл, который запускает процедуру 1 и проверяет условие функцией 2. При увеличении количества итераций число = Да/Все будет стремиться к некоему числу, которое и будет ответом.

Comments

[Юрий Янин]

Апдейтнул тему. Нужно математически рассчитать.

Answer 2

[longclaps]

discount, p = [1., 1.], 1. - 29. / 61.
for dist in range(1, 7):
    discount.append(discount[-1] * p)
discount += discount[-2:-8:-1]

res, cnt = 0., 0
for king in range(64):
    for rook1 in range(64):
        for rook2 in range(64):
            if king == rook1 or king == rook2 or rook1 == rook2:
                continue
            cnt += 1
            kingx, kingy = divmod(king, 8)
            rook1x, rook1y = divmod(rook1, 8)
            rook2x, rook2y = divmod(rook2, 8)
            attac1hor = 1. if kingy == rook1y else 0.
            attac1ver = 1. if kingx == rook1x else 0.
            attac2hor = 1. if kingy == rook2y else 0.
            attac2ver = 1. if kingx == rook2x else 0.
            if kingx == rook1x == rook2x:
                if kingy < rook1y < rook2y or kingy > rook1y > rook2y:
                    attac2ver = 0.
                elif kingy < rook2y < rook1y or kingy > rook2y > rook1y:
                    attac1ver = 0.
            elif kingy == rook1y == rook2y:
                if kingx < rook1x < rook2x or kingx > rook1x > rook2x:
                    attac2hor = 0.
                elif kingx < rook2x < rook1x or kingx > rook2x > rook1x:
                    attac1hor = 0.
            attac1 = attac1hor * discount[kingx - rook1x] + attac1ver * discount[kingy - rook1y]
            attac2 = attac2hor * discount[kingx - rook2x] + attac2ver * discount[kingy - rook2y]
            res += attac1 + attac2 - attac1 * attac2
print(res / cnt * 2.)

итого 0.3756044599826443

Comments

[Юрий Янин]

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

[longclaps]

По какой схеме использования формул пойти?

Юрий Янин, схемы формул, хех.

[Юрий Янин]

longclaps, ну вы же поняли о чём я говорю) Не плохая игра слов вышла) Но о в коде, всё что далее с проверками, теряет математический смысл. Тут по сути эмпирические замеры программным методом (вот вам еще одна смешная фраза). Слабо представляю как подойти к этому моменту с точки зрения математики.

[longclaps]

Юрий Янин, это в вашей голове теряется математический смысл, а в моём коде ничего не теряется. Больше того, в нём намерено оставлены избыточные проверки и нет игры с симметриями - всё для того, чтобы дошло.
Но нет.

[Юрий Янин]

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

[Юрий Янин]

longclaps, Я пока только добился того, что мне vf=64*63*62*61*60*59*58*57*56*55*54*53*52*51*50*49*48*47*46*45*44*43*42*41*40*39*38*37*36*35*34*33 вот это нужно будет разделить на 4096 (исключение взаимозаменяемости фигур на клетках)

[longclaps]

Юрий Янин, зачем это вообще нужно? Для ответа на вопрос, атакует ли белая ладья черного короля, достаточно разделить фигуры на 3 группы:

• белые ладьи
  
• черный король
  
• прочие
  

И да, вы не знаете, как записывается факториал? Это же вроде проходят в 11 классе? Вы еще не проходили?

[Юрий Янин]

longclaps, я не могу понять, зачем вы ехидничаете? Я например не понимаю как я могу описать это факториалом. У меня всеже не вся группа натуральных чисел меньше 64. А лишь до 33. Я слабо уже помню школьную программу, а в жизни не приходилось использовать. Ну так, я сейчас вообще не использую маркировку фигур как таковую. У меня просто есть 32 чего-то на 64 ячейки. Вот я и пытаюсь это число вычислить. А дальше уже убрать взаимозаменяемость с учётом того, что это фигуры. Я не вижу того, что видите вы. Нужно для начала осознать это. Ход ваших мыслей по этому поводу мне не известен абсолютно. Свой ход решения я описал достаточно информативно чтобы его понять. А вы постоянно выдаёте что-то вроде "да как же вы не понимаете?" и всё. Я идею того почему разделить на группы нужно понимаю в принципе. Но только начальный этап. Как из "прочие" вычесть взаимозаменяемость тогда? Для описанной мной последовательности решения, это не подходит. А вашу я просто не вижу. Она же у вас в голове, а не у меня.

[longclaps]

Юрий Янин, математика - это про логику, и логики решения я, простите, в упор не вижу.
Попробуйте решить задачу попроще (вам всё равно этот этап не обойти, если уж хотите разобраться):
На доске 2 белые ладьи и черный король. Какова вероятность, что король под боем?
зы и перестаньте уже кичиться неграмотностью, вспомните факториал и разберитесь, как кратко записать вашу белиберду.

[Юрий Янин]

longclaps, ясно. Жаль, что вы умеете только язвить не в тему. Типичный житель форумов. Поищу помощь в другом месте.

[longclaps]

Юрий Янин, я, если чо, решил для вас задачу. Подите, поищите другое решение.

[Юрий Янин]

longclaps, ну вы у себя в голове то её решили. И упорно продолжаете доказывать что-то. Я в 3тий раз говорю, что решение которое вы у себя в голове видите, я увидеть не могу. Я не телепат. vf=64!/32! вот в вам запись в виде факториала. Что-то изменилось? Это превратилось в ответ? Нет. Мне нужна формула. Я её в упор не вижу. Зачем быть таким токсичным? Сложно просто по человечески объяснить?

[longclaps]

Юрий Янин, послушайте. Фигуры на доске взаимодействуют друг с другом. Как, по вашему, можно выразить это взаимодействие "в формуле"? Я знаю один способ: выписать все принципиально различные варианты и проанализировать их. Их не так много, как вам кажется, но и не так мало: порядка 32000.
Вы готовы их выписать и проанализировать? Или вы настаиваете на том, что их гораздо меньше?
Так вот: попробуйте решить ту задачу попроще, от неё до вашей - 1 шаг.

[Юрий Янин]

longclaps, задача по проще мной была решена легко. Я не понимаю как решить конкретно эту. Мне не нужны взаимодействия фигур вообще. Фигуры расставляются без учёта правил игры. На данный момент у меня есть vf=((64!)/(32!))/4096 общее количество вариантов расстановки фигур на поле без учёта их взаимозаменяемости. По моей, субъективной логике, мне осталось отнять от этого числа все варианты где на пути у ладьи(у четырёх скорее всего) вообще нет фигур и варианты где между ладьёй и королём есть другие фигуры (по идее тоже 4 варианта. 2 для одного короля. 2 для другого.). Тогда я и получу искомый мной ответ. Но я вот придумать как последние обратить в формулу не могу.

[longclaps]

Юрий Янин, ну вот и выложите здесь решение задачи попроще, мы его разберём и, если оно верно, двинемся дальше.

[Юрий Янин]

longclaps, там ошибка в том, что позиция короля изначально не учитывается вообще и я использовал числа самих вариантов. Поправка:
у нас есть 249984/2=124992 вариантов расстановок для 3 фигур. Из них бывают случаи где 26 клеток находятся под атакой ладьи и случаи где таких клеток 21 если ладьи находятся на одной линии, и при этом на этих клетках нет короля. По идее таких вариаций 64*(64-15)*34/2=53312 и 64*14*41/2=18368.
124992-53312-18368=53312
53312/124992=0.42652329749 это шанс того, что он не будет под атакой.
124992-53312=71680
71680/124992=0.5734767025 шанс того что будет.

[Юрий Янин]

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

[longclaps]

Юрий Янин, рассчеты понятны, но они

• неточны - вместо 21*64*14=18816 следует считать 20*64*14
• недостаточны
  

Нужно выяснить

1. не загораживает ли одна ладья другую, если все фигуры на одной линии
2. если ладья атакует - в скольки клетках она от короля
   

[Юрий Янин]

longclaps, с 1 согласен. И я там формулу изменил. Там вообще это число не применимо. И почему 20? у нас же занято 16 клеток одной ладьёй и вторая может находится на одной из этих клеток и засвечивать еще 7 при этом. 16+7=21. Но не суть.
Не понял зачем нам знать расстояние для короля. А вот про заграждения да.
Сейчас внесу корректировки.

[longclaps]

Юрий Янин, если ладьи на 1й линии - под боем 20 клеток.

[Юрий Янин]

longclaps, точно. Одна бьет 15, а не 16ть. Такой вопрос еще. По идее чтобы рассчитать все вариации где на пути одной ладьи нет других пешек, будет формула VL1=64*(49!/18!)/4096*4 . Я тут беру за основу расположение ладьи 64 варианта, умножаю на (49!/18!) это в моём понимании количество комбинаций всех остальных фигур, и всё это делю на 4096, это количество взаимозаменяемых вариантов, и умножаю на 4 так как у нас 4 ладьи. Тут всё верно? Меня конкретно смущает (49!/18!) точно ли нужно делить на именно на 18ть.

[longclaps]

Юрий Янин, нет, тут всё вздор.

достаточно разделить фигуры на 3 группы:

• белые ладьи
  
• черный король
  
• прочие
  

все прочие фигуры равноценны - любая (и любого цвета) может прикрыть короля от ладьи.

[Юрий Янин]

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

[longclaps]

Юрий Янин, хорошо, сейчас я объясню другой момент, а потом вернёмся к этому.
Пусть есть король и ладья, они на одной линии, вторая ладья где-то в уголке, не при делах, и остальные 29 фигур (все кроме второй ладьи).
Итого на 61 свободном поле 29 фигур.
Вероятность того, что произвольная клетка свободна - 32/61
Вероятность того, что между королём и ладьёй нет левых фигур - (32/61)^(сколько между ними клеток)

[Юрий Янин]

longclaps, Так. Я тут немного вижу, что по всей видимости я совсем всё усложняю по не понятной мне причине и путь на самом деле короче чем я пытаюсь выдумать.
((32/61)^6*(32/61)^5*(32/61)^4*(32/61)^3*(32/61)^2*(32/61)^1)*2=0.00000261368 по идее это шанс для одной ладьи на одной линии. Соответственно нам еще всё это нужно умножить на 64 варианта расположения этой одной ладьи 0.00000261368*64=0.00016727552. Но еще нужно прибавить шансы с второй ладьи без учёта пересекающихся клеток, а значит убрать просто перемножить на 62 варианта. Хотя сейчас вдруг дошло, что если ладья стоит не в углу, то варианты степеней то будут совсем другие...

[Юрий Янин]

longclaps, так. Вероятность, что одна ладья бьет короля в условиях если есть только они 14/63. Это понятно.
если ладьи две то 26/62. Я это понимаю. Но способ вычисления. Тоесть это что-то на уровне "потому что это так" для меня сейчас. Ну тоесть я понимаю, что причина в клетках. Но я же их блин просто посчитал чуть ли не пальцем.

[longclaps]

Юрий Янин, что это?

• вот король и ладья рядом, вероятность, что ладья бьёт == (32/61)^0 == 1
  
• вот король в одной клетке от ладьи, вероятность == (32/61)^1 == 32/61
  
• ....
  
• шесть клеток - максимум

[longclaps]

Юрий Янин, нет, так нельзя. Фигуры взаимодействуют (в смысле загораживают). До сих пор вы считали комбинации на чистом поле, та метода не работает.

[Юрий Янин]

longclaps, Ну вот это то я понял. Собственно:
(32/61)^0 == 1
(32/61)^1 == 32/61
(32/61)^2 == 1024/3721
(32/61)^3 == 32768/226981
(32/61)^4 == 1048576/13845841
(32/61)^5 == 33554432/844596301
(32/61)^6 == 1073741824/51520374361
Тут всё просто если ладья в углу. Но она ведь еще может находится по центру. Тогда у нас клеток максимальное расстояние меньше.

[longclaps]

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

[Юрий Янин]

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

[Юрий Янин]

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

[longclaps]

Юрий Янин, нет, взаимодействие ладей туда не запихнуть.
Руками считать нереально, и незачем. Точный ответ для обоих королей

5192299510604092080271901/13823849458141828712535768

[hint000]

Юрий Янин,

нужно обязательно подтянуть весь курс теории вероятности

Тут больше комбинаторики, чем теории вероятностей.