Настольная игра

[sa233091]

Недавно задался такой задачей:
Пусть у нас есть игровое поле некоторой заданной длинны и кубик на гранях которого записаны некоторые известные нам числа. Игроку за ход может либо перебросить кубик, либо передвинуть свою фишку на число клеток, указанное на кубике. (изначально фишка стоит в начале поля и исходы подбрасывания кубика равновероятны) Игрок выигрывает, когда выходит ща пределы поля. Необходимо найти оптимальную стратегию для игрока.
Решить эту задачу я не смог, но интуитивно понимаю, что стратегия, скорее всего, будет сильно зависеть от размера поля. Например, если поле крайне велико, имеет смысл бросать кубик, пока не выпадет наибольшее число, а только потом двигаться. А если размер поля 2 и на кубике число 3, то нужно просто ходить. Другой вопрос: можно ли на определенном этапе игры рассматривать задачу отдельно от ранее произошедшего (то есть считать, что мы начали сначала, только размер поля меньше и на кубике может быть другое число)?

[arseniiv]

Оптимальность здесь — минимизация числа ходов? Кубик перед игрой уже подброшен?

Попробуйте сначала найти лучшую из таких стратегий: сначала подкидываем сколько-то раз кубик, потом только ходим до самого конца. Должно быть несложно, простой теорвер.

[sa233091]

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

Кубик перед игрой уже подброшен?

да

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

Оптимальность здесь — минимизация числа ходов?

Ну скорее оптимизация мат ожидания числа ходов

[arseniiv]

Да, матожидания, конечно.

[sa233091]

Ну например если на кубике стандартный набор чисел 1, 2, ..., 6 и поле из 100 клеток, то если перед каждым подбрасыванием считать, что оно последнее (то есть после него надо будет просто ходить), то тогда в случае подбрасывания мат ожидание будет 41 ход (без учета самого подбрасывания), а значит перебрасывать имеет смысл тогда, когда на кубике число меньше 3.
Но можно ли считать на каждом ходе, что он последний?

[Aritaborian]

sa233091 в сообщении #1236538 писал(а):

Ну например если на кубике стандартный набор чисел 1, 2, ..., 6 и поле из 100 клеток, то если перед каждым подбрасыванием считать, что оно последнее (то есть после него надо будет просто ходить), то тогда в случае подбрасывания мат ожидание будет 41 ход

А почему не 14? Почему?

[ET]

Aritaborian в сообщении #1236539 писал(а):

sa233091 в сообщении #1236538 писал(а):

Ну например если на кубике стандартный набор чисел 1, 2, ..., 6 и поле из 100 клеток, то если перед каждым подбрасыванием считать, что оно последнее (то есть после него надо будет просто ходить), то тогда в случае подбрасывания мат ожидание будет 41 ход

А почему не 14? Почему?

$1+\dfrac{\frac{100}1+\frac{100}2+\frac{100}3+\frac{100}4+\frac{100}5+\frac{100}6}6=41,8...$

[Aritaborian]

Спасибо, ET. Я неверно понял условия задачи.

[sa233091]

ET
Если я правильно понимаю, необходимо округлять частные от деления в большую сторону, ведь если на кубике 3, то необходимо сделать 34 хода

[grizzly]

ET в сообщении #1236542 писал(а):

$1+\dfrac{\frac{100}1+\frac{100}2+\frac{100}3+\frac{100}4+\frac{100}5+\frac{100}6}6=41,8...$

Я до сих пор не могу понять условие задачи. Какому вероятностному пространству соответствует этот расчёт МО? Выглядит так, как будто считается, что с вероятностью 1/6 потребуется 100 ходов, с той же вероятностью -- 50 и т.д. Тогда правила игры должны быть такими: подбросили кубик и должны сделать 100 одинаковых ходов. Но это звучит как-то странно. Просьба помочь.

[lel0lel]

ET в сообщении #1236542 писал(а):

$1+\dfrac{\frac{100}1+\frac{100}2+\frac{100}3+\frac{100}4+\frac{100}5+\frac{100}6}6=41,8...$

По-моему это неверно. Вы считаете как-будто доску можно пройти только одними единичками, двойками,..., шестерками. Приписывая этим событиям вероятности $1/6$. Пока набирал сообщение, об этом написал grizzly

Мат. ожидание числа очков при одном бросании равно $3.5$ (округлять его, конечно, не надо). Тогда потребуется бросаний $100/3.5$. Каждое, кроме первого, бросание требует два хода. Имеем $2(100/3.5-1)+1\approx 56$

[Someone]

Я тоже никак не врублюсь. Допустим, мы бросали кубик несколько раз и получили некоторую последовательность чисел. Что с ней делать? Учитывается только последнее число или все? Если только последнее, то сколько ходов можно с ним сделать — один или сколько хочешь?

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

[Geen]

А что именно оптимизируем?

[mihaild]

Странно, мне кажется, что задача интерпретируется однозначно.
У нас в каждый момент времени есть два числа: число на кубике и число оставшихся клеток. Мы можем сделать одно из двух действий: заменить число на кубике случайным, или уменьшить число оставшихся клеток на число на кубике. Мы побеждаем, когда число оставшихся клеток становится неположительным. Нужно минимизировать мат. ожидание числа действий.

Someone в сообщении #1236560 писал(а):

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

Такая стратегия вряд ли оптимальная - история предыдущих бросков не должна влиять на действия (по крайней мере на нее точно можно забить).

Выше подсчет для стратегии "кинуть один раз и дальше только идти".

[grizzly]

mihaild
Спасибо за пояснения. Правила однозначные, но действительно странные.

mihaild в сообщении #1236591 писал(а):

Такая стратегия вряд ли оптимальная

Почему? У меня по этой стратегии получилось мат.ожидание 23 (если учитывать начальный ход). Всяко лучше посчитанного выше. Да и странно было бы ожидать, что какая-то другая стратегия может быть лучше.