Игра «Шаги» (Footsteps)

[arseniiv]

У неё такие правила:
Перед игроками шкала с $m = 7$ делениями, на среднем делении которой лежит камешек (ну или монета). Игроки одновременно называют свои ставки, которые могут быть от единицы до числа очков, которые у них есть (ставка сразу же вычитается из очков игрока). Если у кого-то больше, он двигает камень по шкале в свою сторону на деление. Ситуация повторяется, пока камень не достиг крайнего деления (тот игрок выигрывает) и у каждого не ноль очков. Потом, если у другого игрока остались очки, он на кажое очко двигает камень к себе, но их может не хватить, чтобы он додвигал его до конца. Перед первым ходом $S = 50$ очков у каждого.

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

(Вот отсюда я узнал про неё.)

-- Вс фев 20, 2011 23:19:27 --

Ах да, обозначения я ввёл, чтобы спросить, известно ли что-то о свойствах обобщённой игры $(m, \, S)$.

[ha]

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

[ИСН]

С вероятностной стратегией (а у тамошних ботов, действительно, она и есть) всё становится как-то сложно - слишком дофига вариантов действий...
...хотя всё равно величина обозримая. Или нет?

[arseniiv]

А какое число надо обозревать? (Интерес снова всплыл.) Вариантов сыграть в игру $(\_, S)$ не больше $A_{S,S}$; $A_{0,a} = A_{a,0} = 0$, остальные $A_{a,b}$ образуют тот же треугольник, что и A051597, т. е. $\left(A_{S,S}\right)_{S=1}^\infty$ — это A051924 $= \binom{2S}{S} - \binom{2S-2}{S-1} \sim \frac34\frac{2^{2S}}{\sqrt{\pi S}}$ (правильная асимптотика?). ($A_{S,S}$ — число вариантов у игры с бесконечной шкалой.) А осмысленная нижняя граница так просто не придумывается.

-- Вт дек 04, 2012 15:50:04 --

Так как эти стратегии находить?

[Sender]

Может, делений всё же $2m+1$? А то как-то несимметрично получается.

[arseniiv]

Да, пусть будет $m = 2m' + 1$, раз я забыл упомянуть про нечётность (хотя и написал «на среднем делении» ).

[nikvic]

Так как эти стратегии находить?
=====
Может быть, рекурсивным заполнением 3-мерного массива (позиция, 2 кошелька) с элементами-записями из цен и векторов стратегий?

[arseniiv]

А потом смотреть в массиве, как ходить? Но это же громоздко очень.

[nikvic]

arseniiv в сообщении #654243 писал(а):

А потом смотреть в массиве, как ходить? Но это же громоздко очень.

Зачем в массиве? Прям в Айпаде (если сумеете разлочить...) - Вам и "датчик случая" понадобится!

[arseniiv]

Не понял вас.

[nikvic]

arseniiv в сообщении #654302 писал(а):

Не понял вас.

Неясна цель исследования. А ссылка не открывается...

[arseniiv]

Да, Vying что-то пропали совсем, со всеми играми и конкурсами… Хотя описание этой игры под другим названием я кое-где встречал один раз. Но всё забыл — и где, и как называлась.

Цель исследования — хочу написать ИИ и радоваться.

[nikvic]

arseniiv в сообщении #654316 писал(а):

Да, Vying что-то пропали совсем, со всеми играми и конкурсами…

Цель исследования — хочу написать ИИ и радоваться.

Тогда нужно сосчитать точную стратегию - в качестве спарринг-партнёра

[arseniiv]

Ну вот, как их считают? Книжки никакой нет?

-- Ср дек 05, 2012 02:08:19 --

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

[nikvic]

arseniiv в сообщении #654331 писал(а):

Ну вот, как их считают? Книжки никакой нет?

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

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