стратегия для определения положения 8 ладей

[Димаsick]

На шахматной доске расположены 8 ладей (других фигур нет) так, что ни одна не бьет другую (на каждой вертикали и на каждой горизонтали - по одной ладье), но расположение нам неизвестно. Можно задавать вопрос о занятости той или иной клетки. Наша цель - максимально сократить число возможных вариантов расположения, задав всего 10 вопросов. Символом А0 обозначим алгоритм, состоящий в проверке каждого столбца (клетка за клеткой) до обнаружения занятой клетки и последующим переходом к следующему столбцу. Как доказать, что в среднем (усредняя по всем возможным начальным расположениям ладей) А0 будет максимально сокращать число возможных вариантов расположения фигур на доске?

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

[ИСН]

Попадание в клетку, где ничего нет, сокращает неопределённость на одну клетку. А попадание туда, где ладья - сокращает сразу на очень много (целый столбец и строку). Значит, надо стараться попадать в ладьи. А как в них попадать, когда они неизвестно где? А по вероятностям же. В неизведанном столбце ладья может стоять на любой из 8 клеток. А в том, где одна клетка уже проверена и пуста - на любой из остальных 7. Где шансы выше? То-то.

[Димаsick]

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

Попадание в клетку, где ничего нет, сокращает неопределённость на одну клетку. А попадание туда, где ладья - сокращает сразу на очень много (целый столбец и строку). Значит, надо стараться попадать в ладьи. А как в них попадать, когда они неизвестно где? А по вероятностям же. В неизведанном столбце ладья может стоять на любой из 8 клеток. А в том, где одна клетка уже проверена и пуста - на любой из остальных 7. Где шансы выше? То-то.

Не так все просто, как может показаться на первый взгляд, ведь неудачные попытки сокращают число вариантов по-разному. То, что ближайший один ход лучше, чем другой, еще не значит, что набор "лучших" ходов в совокупности будет лучше, чем набор других ходов. Как показал перебор, есть стратегии, не хуже стратегии А0, при которых уже второй ход можно делать не в том же столбце (правда, для меньшей размерности доски).

[_Ivana]

Так приведите эти стратегии, если это не коммерческая тайна.

[Димаsick]

_Ivana в сообщении #771196 писал(а):

Так приведите эти стратегии, если это не коммерческая тайна.

Если доска 3*3 и дается всего три попытки для угадывания, то и стратегия А0, и та, когда после первой неудачной попытки меняем столбец, дают одинаковый результат.

[Otta]

Нет, во втором случае при неудачном раскладе понадобится 4 попытки.

[_Ivana]

Нет, если не делать глупых ходов, то гарантировано решается за 3 попытки. Более того, при доске 3 на 3 это получается одна и та же стратегия, с точностью до переворота строк/столбцов. Только доска 3 на 3 существенно упрощает задачу. Тогда уж рассмотрим стратегии на доске 2 на 2 или 1 на 1...

[Otta]

_Ivana в сообщении #771226 писал(а):

Нет, если не делать глупых ходов, то гарантировано решается за 3 попытки.

Мы об одном и том же говорим? ТС предложил менять столбец (строку), то есть как раз делать "глупые" ходы.

[_Ivana]

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

[Otta]

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

[Null]

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

[Димаsick]

_Ivana в сообщении #771231 писал(а):

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

Имелись в виду все возможные стратегии. То, что замена строк-столбцов не меняет суть, я понимаю, но для меня все еще не очевидно, почему А0 наилучшая. То, что ближайший один ход лучше, чем другой, еще не значит, что набор "лучших" ходов в совокупности будет лучше, чем набор других ходов. Хотя бы потому, что неоптимальные ходы отсекая часть вариантов, теоретически могут на следующих ходах давать (суммарно) лучшие результаты, чем последовательные оптимальные ходы. Если бы каждый оптимальный ход, скажем, отсекал ровно половину вариантов, то сомнений не было бы, что лучше никак нельзя, но ведь это же не так.

-- Вс окт 06, 2013 13:28:10 --

Null в сообщении #771310 писал(а):

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

Это понятно. Речь как раз о меньшем числе попыток и поиске такой стратегии, при которой можно отсечь как можно больше вариантов.

[Shadow]

Вообще-то, оптимальная стратегия - выбирать ячейку где вероятность максимальная. В начале 64 ячеек, для любой ячейки вероятность находения ладьи 1/8. Сумма вероятностей по горизонталям и вертикалям в начале и после каждого хода должна быть 1. Выбираем ячейку A1 - нет ладьи. Тогда $P_{A1}=0$, По верикали A и горизонатли 1 $P_{Ai}=P_{j1}=1/7$ В остальных ячеек вероятность перевычисляется $P_{ij}=6/49$ Естествено, надо выбирать ячейку, где вероятность 1/7.
Выбрали A2 - оказалась ладья. Как будут менятся вероятности?

Димаsick в сообщении #771123 писал(а):

до обнаружения занятой клетки и последующим переходом к следующему столбцу

Вот тут что-то не договорено. Равны ли будут вероятности для B1 и B8?

[ИСН]

Shadow в сообщении #771318 писал(а):

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

Скорее всего, так и есть, но ведь, строго говоря,

Димаsick в сообщении #771311 писал(а):

То, что ближайший один ход лучше, чем другой, еще не значит, что набор "лучших" ходов в совокупности будет лучше, чем набор других ходов.

[Shadow]

Согласен, строгости не хватает, но интуитивно понятно, что так и будет.

Shadow в сообщении #771318 писал(а):

Вот тут что-то не договорено. Равны ли будут вероятности для B1 и B8?

Будут равны.