теория игр, угадывание числа

[Euler7]

Padawan в сообщении #991086 писал(а):

Euler7
Вы стратегии задаете в виде вектора из $n$ чисел. Как такое задание соотносится c моим понимание стратегии:

Взаимно-однозначно. Выше показано как выглядит игра по такому вектору-стратегии. Такой вектор выбран потому, что он также является столбцом в платёжной матрице.
Примеры конвертации:

Если хотите, то могу скинуть файл *.nb (wolfram mathematica) с функциями построения матриц, вычисления стратегий и т.п.

Утундрий писал(а):

Глянул, платёж там выдаётся только первому игроку и это таки да - количество попыток второго.

Та книга к этой задаче отношения не имеет. Там разбор очень похожей задачи, для тех кто не знает как это делается. Тут первый платит второму $n-t$ монет, где n - величина диапазона в котором загадывают, а t - число неудачных попыток угадать число.

Утундрий писал(а):

Кстати, а как здесь формируется платёж? Я считал очки передаваемыми монетками.

так и есть.

[Утундрий]

Тогда повторюсь. Далеко я не забирался, но для малых $n$ второй игрок в среднем обыгрывает первого на любой его чистой стратегии, расставляя веса на каждом вновь образующемся интервале в соответствии с биномиальным распределением.

[Euler7]

Утундрий в сообщении #991143 писал(а):

Тогда повторюсь. Далеко я не забирался, но для малых $n$ второй игрок в среднем обыгрывает первого на любой его чистой стратегии, расставляя веса на каждом вновь образующемся интервале в соответствии с биномиальным распределением.

Тут первый игрок при любом раскладе проигрывает, даже если второй будет действовать наихудшим образом. При биномиальном выборе с p=0.5 для n=3 получаем стратегию - с вероятностью 1/2 выбрать 2 на первом шаге, а любой из оставшихся четырёх сценариев с вероятностью 1/8. Если первый игрок будет при этом придерживаться оптимальной стратегии, то средний выигрыш второго составит 2.125, вместо 2.2 при оптимальной стратегии.

[Geen]

Euler7 в сообщении #991138 писал(а):

Если хотите, то могу скинуть файл *.nb (wolfram mathematica) с функциями построения матриц, вычисления стратегий и т.п.

Лучше задачу переформулировать - убрать $n$ из платежей и рассмотреть результат с точки зрения загадывающего. Тогда, скажем для $n=4$ полная матрица игры (при рациональных в первом приближении стратегиях отгадывающего) будет такая:

$$\begin{array}{c|cccccccccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 2 & 2 & 3 & 3 & 4 \\ 2 & 2 & 2 & 3 & 3 & 4 & 1 & 1 & 3 & 2 & 3 & 4 & 2 & 4 & 3 \\ 3 & 3 & 4 & 2 & 4 & 3 & 2 & 3 & 1 & 1 & 4 & 3 & 3 & 2 & 2 \\ 4 & 4 & 3 & 3 & 2 & 2 & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 \end{array}$$

КМК, так было бы понятней...

[Euler7]

Geen
не вижу разницы, нужно что-то новое с точки зрения алгоритма придумывать, а подстановка никак не приближает к решению.
Например, может можно доказать, что начиная с n=4, второму игроку никогда не стоит начинать угадывать с чисел 1 и n?

[Утундрий]

Euler7 в сообщении #991164 писал(а):

первый игрок при любом раскладе проигрывает

Ну и кому нужна такая игра?

[Euler7]

Утундрий в сообщении #991304 писал(а):

Ну и кому нужна такая игра?

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

[Утундрий]

Euler7 в сообщении #991308 писал(а):

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

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

P.S. Отвечать на это сообщение не надо.

[Geen]

Euler7 в сообщении #991206 писал(а):

Например, может можно доказать, что начиная с n=4, второму игроку никогда не стоит начинать угадывать с чисел 1 и n?

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

[Geen]

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

Кстати, для $n=4$ у Вас ошибка....

[Euler7]

Geen в сообщении #991728 писал(а):

Кстати, для $n=4$ у Вас ошибка....

Как так?! Это же катастрофа просто :) . Если ошибка при одном n, то скорее всего и при остальных, одним скриптом всё считалось...

[Geen]

Euler7 в сообщении #991750 писал(а):

Как так?!

Для 1 и 4 вероятности отличаются....

-- 18.03.2015, 01:01 --

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

[Euler7]

Geen в сообщении #991768 писал(а):

Для 1 и 4 вероятности отличаются....

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

Geen в сообщении #991768 писал(а):

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

К сожалению не могу отредактировать ранние сообщения. Рекламу вообще не видел, видимо adblock вырезал всю. Насколько я понял там просто подстановка $a_{ij}\to n-a_{ij}+1$. И, к сожалению тут нет спойлера, так что:
$\left(\begin{array}{ccccc} \frac{11}{5} & 2.2 & \frac{1}{5} & \frac{3}{5} & \frac{1}{5} \\ 1 & \frac{2}{5} & 1 & 2 & 2 \\ 2 & \frac{1}{5} & 3 & 1 & 3 \\ 3 & \frac{2}{5} & 2 & 2 & 1 \\\end{array}\right)$ ; $\left(\begin{array}{cccc} 3 & 3. & \frac{1}{2} & \frac{1}{2} \\ 1 & \frac{3}{7} & 2 & 2 \\ 2 & \frac{1}{7} & 1 & 3 \\ 3 & \frac{1}{7} & 3 & 1 \\ 4 & \frac{2}{7} & 2 & 2 \\\end{array}\right)$ ; $\left(\begin{array}{ccccccc} \frac{34}{9} & 3.778 & \frac{2}{9} & \frac{1}{18} & \frac{4}{9} & \frac{1}{18} & \frac{2}{9} \\ 1 & \frac{5}{18} & 2 & 2 & 2 & 2 & 3 \\ 2 & \frac{1}{6} & 1 & 1 & 3 & 3 & 2 \\ 3 & \frac{1}{9} & 3 & 4 & 1 & 4 & 3 \\ 4 & \frac{1}{6} & 2 & 3 & 3 & 1 & 1 \\ 5 & \frac{5}{18} & 3 & 2 & 2 & 2 & 2 \\\end{array}\right)$ ; $\left(\begin{array}{cccccccc} \frac{23}{5} & 4.6 & \frac{1}{10} & \frac{3}{10} & \frac{1}{10} & \frac{1}{10} & \frac{3}{10} & \frac{1}{10} \\ 1 & \frac{1}{4} & 2 & 2 & 2 & 2 & 3 & 3 \\ 2 & \frac{3}{20} & 1 & 3 & 3 & 3 & 2 & 2 \\ 3 & \frac{1}{10} & 4 & 1 & 1 & 4 & 3 & 3 \\ 4 & \frac{1}{10} & 3 & 3 & 4 & 1 & 1 & 4 \\ 5 & \frac{3}{20} & 2 & 2 & 3 & 3 & 3 & 1 \\ 6 & \frac{1}{4} & 3 & 3 & 2 & 2 & 2 & 2 \\\end{array}\right)$
$\left(\begin{array}{ccccccccc} \frac{49}{9} & 5.44 & \frac{19}{81} & \frac{1}{9} & \frac{2}{81} & \frac{8}{27} & \frac{2}{27} & \frac{11}{54} & \frac{1}{18} \\ 1 & \frac{2}{9} & 2 & 2 & 2 & 3 & 2 & 3 & 3 \\ 2 & \frac{1}{9} & 3 & 3 & 3 & 2 & 3 & 2 & 4 \\ 3 & \frac{1}{9} & 1 & 1 & 4 & 3 & 4 & 4 & 2 \\ 4 & \frac{1}{9} & 4 & 4 & 1 & 1 & 1 & 3 & 3 \\ 5 & \frac{1}{9} & 3 & 3 & 3 & 3 & 4 & 1 & 1 \\ 6 & \frac{1}{9} & 2 & 4 & 2 & 2 & 3 & 3 & 3 \\ 7 & \frac{2}{9} & 3 & 2 & 3 & 3 & 2 & 2 & 2 \\\end{array}\right)$ ; $\left(\begin{array}{cccccccccc} \frac{63}{10} & 6.3 & \frac{1}{7} & \frac{5}{14} & \frac{11}{70} & \frac{3}{70} & \frac{4}{35} & \frac{1}{14} & \frac{3}{28} & \frac{1}{140} \\ 1 & \frac{1}{5} & 2 & 3 & 2 & 3 & 3 & 3 & 3 & 3 \\ 2 & \frac{1}{10} & 3 & 2 & 4 & 2 & 4 & 2 & 2 & 4 \\ 3 & \frac{1}{10} & 1 & 3 & 3 & 3 & 2 & 3 & 4 & 2 \\ 4 & \frac{1}{10} & 4 & 1 & 4 & 4 & 3 & 4 & 3 & 3 \\ 5 & \frac{1}{10} & 3 & 4 & 1 & 1 & 1 & 1 & 4 & 4 \\ 6 & \frac{1}{10} & 2 & 3 & 3 & 3 & 3 & 4 & 1 & 1 \\ 7 & \frac{1}{10} & 4 & 2 & 2 & 2 & 4 & 3 & 3 & 3 \\ 8 & \frac{1}{5} & 3 & 3 & 3 & 3 & 2 & 2 & 2 & 2 \\\end{array}\right)$
$\left(\begin{array}{ccccccccccc} \frac{79}{11} & 7.18 & \frac{46}{1111} & \frac{267}{1111} & \frac{21}{202} & \frac{81}{2222} & \frac{201}{1111} & \frac{113}{6666} & \frac{1321}{6666} & \frac{40}{303} &\frac{166}{3333} \\ 1 & \frac{2}{11} & 2 & 3 & 2 & 2 & 3 & 3 & 3 & 3 & 3 \\ 2 & \frac{1}{11} & 3 & 2 & 4 & 4 & 2 & 2 & 4 & 2 & 4 \\ 3 & \frac{1}{11} & 1 & 3 & 3 & 3 & 3 & 4 & 2 & 4 & 2 \\ 4 & \frac{1}{11} & 4 & 1 & 1 & 4 & 4 & 3 & 4 & 3 & 4 \\ 5 & \frac{1}{11} & 3 & 3 & 4 & 1 & 1 & 4 & 3 & 4 & 3 \\ 6 & \frac{1}{11} & 4 & 4 & 3 & 3 & 4 & 1 & 1 & 1 & 4 \\ 7 & \frac{1}{11} & 2 & 2 & 4 & 2 & 3 & 3 & 3 & 4 & 1 \\ 8 & \frac{1}{11} & 4 & 4 & 2 & 4 & 2 & 2 & 2 & 3 & 3 \\ 9 & \frac{2}{11} & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 & 2 \\\end{array}\right)$ ; $\left(\begin{array}{cccccccccccc} \frac{97}{12} & 8.08 & \frac{1}{12} & \frac{67}{408} & \frac{5}{102} & \frac{35}{408} & \frac{2}{17} & \frac{4}{51} & \frac{3}{34} & \frac{5}{408} & \frac{1}{12} &\frac{97}{408} \\ 1 & \frac{1}{6} & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 2 & \frac{1}{12} & 4 & 2 & 4 & 2 & 2 & 2 & 4 & 2 & 2 & 4 \\ 3 & \frac{1}{12} & 3 & 3 & 2 & 3 & 4 & 4 & 2 & 4 & 4 & 2 \\ 4 & \frac{1}{12} & 1 & 1 & 3 & 4 & 3 & 3 & 4 & 3 & 3 & 4 \\ 5 & \frac{1}{12} & 4 & 4 & 1 & 1 & 1 & 4 & 3 & 4 & 4 & 3 \\ 6 & \frac{1}{12} & 3 & 3 & 3 & 4 & 4 & 1 & 1 & 1 & 1 & 4 \\ 7 & \frac{1}{12} & 4 & 4 & 4 & 3 & 3 & 3 & 3 & 4 & 4 & 1 \\ 8 & \frac{1}{12} & 2 & 2 & 2 & 4 & 4 & 2 & 4 & 3 & 3 & 3 \\ 9 & \frac{1}{12} & 4 & 4 & 4 & 2 & 2 & 4 & 2 & 2 & 4 & 2 \\ 10 & \frac{1}{6} & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 & 3 \\\end{array}\right)$

[mustitz]

Я бы вначале попытался разобраться решая задачи меньшей размерности. Например, $n=3$. Сколько стратегий у игрока, который задумывает число? Если решать в лоб, то три. Получаем матрицу типа

               1          2          3
=========================================
   2           2          1          2
1, 2, 3        1          2          3  
1, 3, 2        1          3          2
3, 1, 2        2          3          1
3, 2, 1        3          2          1

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

               1/3           2
=================================
    2           2            1
1/3 - 2         2            2
1/3 - 3/1      1.5           3

Тут очевидно, что стратегия 1/3 - 2 доминируется стратегией 2, так что ее можно вычеркнуть, получаем

               1/3           2
=================================
    2           2            1
1/3 - 3/1      1.5           3

-- 18.03.2015, 17:47 --

Утундрий в сообщении #991304 писал(а):

Euler7 в сообщении #991164 писал(а):

первый игрок при любом раскладе проигрывает

Ну и кому нужна такая игра?

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

[Geen]

Geen в сообщении #991728 писал(а):

Завтра проверю, тогда отпишусь.

Проверил. Существенная экономия есть, но пока мало для 100.... Ещё немного пооптимизирую...