2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Игра «Шаги» (Footsteps)
Сообщение20.02.2011, 19:33 
Заслуженный участник


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

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

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

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

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение20.02.2011, 21:55 


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение21.02.2011, 15:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 12:39 
Заслуженный участник


27/04/09
28128
А какое число надо обозревать? (Интерес снова всплыл.) Вариантов сыграть в игру $(\_, 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 --

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 13:01 


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 13:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 19:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 21:14 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 21:40 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #654243 писал(а):
А потом смотреть в массиве, как ходить? Но это же громоздко очень.

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 22:30 
Заслуженный участник


27/04/09
28128
Не понял вас.

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 22:33 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #654302 писал(а):
Не понял вас.

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 22:43 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 22:45 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #654316 писал(а):
Да, Vying что-то пропали совсем, со всеми играми и конкурсами…

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


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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 23:01 
Заслуженный участник


27/04/09
28128
Ну вот, как их считают? Книжки никакой нет?

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

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

 Профиль  
                  
 
 Re: Игра «Шаги» (Footsteps)
Сообщение04.12.2012, 23:19 
Заслуженный участник
Аватара пользователя


06/04/10
3152
arseniiv в сообщении #654331 писал(а):
Ну вот, как их считают? Книжки никакой нет?

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group