Автошахматы

[Doctor Boom]

Пусть игрокам А и Б надо расставить на столе в ряд 10 юнитов с характеристиками урон/здоровье $10/10, 9/9,...1/1$. После расстановки их ряды ставятся друг напротив друга, и дальше начинается последовательность ходов. Сначала самый левый юнит игрока А атакует случайного юнита игрока Б. Потом то же самое делает самый левый юнит игрока Б и так далее, пока хотя бы у одного из игроков не останется юнитов на столе, т.е. возможны игровые ситуации победа/ничья/поражение. Вопрос - как надо расставить юнитов каждому из игроков, чтобы обеспечить себе
1) Максимальное мат ожидание кол-ва очков (победа 1 очко, ничья 0, поражение -1)
2) Максимальное мат ожидание количества побед

[Dendr]

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

А вот с первым вопросом непонятки. Как ничья-то возникает?
Или правила атаки не полностью описаны?

[Doctor Boom]

Dendr в сообщении #1613238 писал(а):

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

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

Dendr в сообщении #1613238 писал(а):

А вот с первым вопросом непонятки. Как ничья-то возникает?
Или правила атаки не полностью описаны?

Пусть все фигуры ударяют в свои копии, тогда ничего не останется. Ничья

[Dendr]

Я и попросил уточнить правила атаки, потому что после прочтения условия у меня сложилась, очевидно, неправильная трактовка. Поэтому вопросы:

1. При атаке $\frac{A}{a} \rightarrow \frac{B}{b}$ результат будет $\frac{A}{a} ; \frac{B}{b-A}$, или $\frac{A}{a-B} ; \frac{B}{b-A}$?
$\ast$ здесь для наглядности в числитель я поместил "цену" фигуры, в знаменатель - ее текущее здоровье (в начале игры оно равно "цене", при опускании до нуля или ниже фигура выбывает)

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

[EUgeneUS]

Doctor Boom в сообщении #1613305 писал(а):

Пусть все фигуры ударяют в свои копии, тогда ничего не останется. Ничья

Рассмотрим ситуацию после последнего хода игры.
Кто-то должен остаться, ибо кто-то нанес удар на последнем ходе.
Так что либо одно из двух, либо я не понимаю:
1. Либо ничьи быть не может.
2. Либо процедура совершения хода в стартовом посте описана неверно.

-- 12.10.2023, 10:17 --

Doctor Boom в сообщении #1613305 писал(а):

Пусть все фигуры ударяют в свои копии, тогда ничего не останется. Ничья

Пусть самая мощная фигура ударяет в самую мощную. Фигура противника умерла и не может нанести удар в свою копию.

[Doctor Boom]

Dendr в сообщении #1613309 писал(а):

При атаке $\frac{A}{a} \rightarrow \frac{B}{b}$ результат будет $\frac{A}{a} ; \frac{B}{b-A}$, или $\frac{A}{a-B} ; \frac{B}{b-A}$?

Второе

Dendr в сообщении #1613309 писал(а):

здесь для наглядности в числитель я поместил "цену" фигуры

Назовем это уроном

Dendr в сообщении #1613309 писал(а):

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

Второе. А самая крайняя правая фигура передает ход самой левой фигуре

EUgeneUS в сообщении #1613310 писал(а):

Пусть самая мощная фигура ударяет в самую мощную. Фигура противника умерла и не может нанести удар в свою копию.

Тогда они обе погибнут, т.к. ударяющая фигура тоже бьется об ударяемую

[EUgeneUS]

Doctor Boom в сообщении #1613352 писал(а):

Тогда они обе погибнут, т.к. ударяющая фигура тоже бьется об ударяемую

Чего? Где это написано?
Написано так:

Doctor Boom в сообщении #1613116 писал(а):

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

[Doctor Boom]

EUgeneUS в сообщении #1613353 писал(а):

Чего? Где это написано?

Это не противоречит написанному. Просто это обычные правила автошахмат, как в hearthstone и др., наверное надо было этот нюанс указать

[EUgeneUS]

Doctor Boom
О чём и речь.
Правила полностью опишите.
Телепатия антинаучна, знаете ли, нельзя на неё рассчитывать.

[wrest]

Doctor Boom в сообщении #1613358 писал(а):

наверное надо было этот нюанс указать

Надо было все нюансы указать. В том числе, что значит "атакует случайного".

[Dendr]

С формализацией не складывается, попробовал составлять таблицы для случая $n=3$, хотя там 36 комбинаций первоначальных расстановок, так что рассмотрел очень немного... Для расстановки $(3-2-1, 3-2-1)$ вероятности результатов "победа А - ничья - победа Б" относятся как $\{10:21:5\}$. Если А переставляет фигуры, то шансы улучшаются для Б, и наоборот.

Можно предположить, что для больших $n$ эта логика тоже работает, так что расстановки $(10-9-8-7-6-5-4-3-2-1)$ и есть ответ на оба вопроса.

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

[EUgeneUS]

Dendr
Тут не складывается с описанием задачи.

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

[Null]

EUgeneUS в сообщении #1613452 писал(а):

откуда у Вас такие перекосы получились при симметричной расстановке....

1ым атакует 10ка игрока А.

[Dendr]

Ну, она выглядит симметричной. Но первый игрок гарантированно уничтожает фигуру соперника на первом ходу (если у него слева старшая), при этом шанс потерять при этом ходе свою у него $1\over{n}$, так еще она может сохраниться к моменту, когда начнется второй круг.

Давайте вообще проследим для $n=2$ (когда $n=1$, то партия одна и та же всегда, ничейная по определению):

Если А поставил первой "двойку", то неважно, какую расстановку выбрал Б (!).
С вероятностью $50%$ обе старшие фигуры взаимоуничтожатся, игрок Б ответным ходом атакует своей "единичкой" "единичку" игрока А, получаем ничью.
С такой же вероятностью $50%$ игрок Б теряет "единичку", но она отнимает очко здоровья у "двойки" А. Теперь ходит игрок Б, и у него единственная фигура - "двойка". Если она атакует "двойку" игрока А ($25%$ в глобальном счете), они взаимоуничтожатся, у игрока А останется единственная фигура в игре, и он победил. Если же она нападет на "единичку", то выбивает ее, потеряв здоровье, но это ничего не значит, поскольку следующим ходом "двойка" игрока А нападает на "двойку" Б, и получится ничья.
Таким образом, при расстановке $(2, 1)$, игрок А получает шанс на победу в одну четверть, а игрок Б не победит, как бы он не поставил свои фигуры.

Если же игрок А поставит первой "единичку", то он ее гарантированно потеряет при первом ходе. А если еще она атакует "двойку", которую игрок Б поставил первой в очереди, то эта "двойка" выбивает "двойку" у А, и с "единичкой" останется уже игрок Б - победитель.

Ну а если оба поставят $(1, 2)$ - то тут уже всегда ничья.

Итого: есть $4$ начальные расстановки. В двух из них с шансов $0.25$ побеждает А, в одной - Б. Так что, если фигуры расставлять случайным образом (то есть подбрасывая монетку), "котировки" равны $\{2:13:1\}$

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

P.S. Хочется замонтекарлить, но это надо прям серьезно браться.