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

[Euler7]

Доброго времени суток. Нужно найти оптимальные стратегии обоих игроков в угадайке... Правила:
Первый игрок загадывает число от 1 до 100 включительно. Второй пытается это число угадать. Если угадывает - получает 100 очков от первого игрока, иначе отдаёт 1 очко первому игроку и получает подсказку - больше или меньше загаданное число названного.
Подобраться к решению не получилось... Выяснил, что топорно решить игру по матрице не выйдет. Поскольку число стратегий отгадывающего равно $f(n)=\sum\limits_{k=0}^{n-1}f(k) f(n-k-1)=\frac{(2 n)!}{n! (n+1)!}\to f(100)>10^{56}$
Не сложно рекурсивно составить матрицу игры, но игра не является рекурсивной, пытаясь свести игру с бОльшим диапазоном к играм с меньшим, приходим к варианту, когда загадывающий может менять загаданное число в оставшемся диапазоне.
Втупую нашёл решения для маленьких диапазонов(до 13 включительно), прикладываю их к сообщению:



здесь в первых двух ячейках первой строки содержится цена игры. Ниже в первом столбце стратегии первого игрока, а во втором частота их использования. Остальные столбцы - это стратегии второго игрока, а над ними частота их использования. Например: при загадывании числа от 1 до 5, четвёртый столбец матрицы говорит, что нужно с вероятностью 1/18 выбирать стратегию по которой начинаешь отгадывать с числа 2, если загаданное число меньше. то во второй раз выбирать 5, а если и там не угадал, то 4. Т.е. на пересечении выбранных чистых стратегий первого и второго игрока находится выигрыш второго игрока.

[ИСН]

Как соотносится то, что Вы делаете, с обычным тупым делением пополам?

[Euler7]

ИСН в сообщении #990339 писал(а):

Как соотносится то, что Вы делаете, с обычным тупым делением пополам?

никак, деление пополам позволяет гарантировать наилучший минимальный выигрыш, но в среднем даёт худший результат начиная с n=4(с=3, если первый игрок не использует оптимальную стратегию, а играет против половинного деления).

[atlakatl]

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

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

Это как? Загадал сначала, потом менять ни-ни. Или объясните, что Вы имели ввиду.

[Euler7]

atlakatl в сообщении #990348 писал(а):

Это как? Загадал сначала, потом менять ни-ни. Или объясните, что Вы имели ввиду.

это если пытаться не всю матрицу строить и просчитывать, а разбить на мелкие матрицы, из которых она состоит и подставить туда суммы игр для тех матриц. Это не даёт оптимальной стратегии для нашей игры, а даёт для игры, в которой первый игрок может менять число после каждого раунда в оставшемся диапазоне. Например:
интервал [1;10]. первый загадал 10. второй угадывает 5, первый отвечает "больше". остался диапазон [6;10], теперь первый игрок загадывает число из этого диапазона.

Эти две игры различны, легко в этом убедиться просто сравнив сумму такой игры с изначальной для конкретного n.

[atlakatl]

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

Эти две игры различны, легко в этом убедиться просто сравнив сумму такой игры с изначальной для конкретного n.

Так определитесь, какую игру Вы разбираете и предлагаете для обсуждения.

[Euler7]

atlakatl в сообщении #990354 писал(а):

Так определитесь, какую игру Вы разбираете и предлагаете для обсуждения.

Это предельно чётко написано:

Цитата:

Первый игрок загадывает число от 1 до 100 включительно. Второй пытается это число угадать. Если угадывает - получает 100 очков от первого игрока, иначе отдаёт 1 очко первому игроку и получает подсказку - больше или меньше загаданное число названного.

[atlakatl]

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

Это предельно чётко написано

Пошли на второй круг?
Просто, не "предельно чётко", скажите: может первый игрок поменять число в ходе угадывания или нет.

[ИСН]

Один студент © поселился в общаге, а потом как-то на каникулы поехал домой. Соседей, чтобы ключ от комнаты передать, дома не было, но он нашёлся: повесил ключ в комнате на гвоздик, куда они его обычно вешали, захлопнул дверь, снаружи оставил записку и радостный поехал домой. Приезжает, а соседи на него с кулаками:
- Где ключ, собака?
- Вы чё, ребята? Там же предельно чётко написано: "ключ где обычно".

[Euler7]

atlakatl в сообщении #990380 писал(а):

Просто, не "предельно чётко", скажите: может первый игрок поменять число в ходе угадывания или нет.

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

[atlakatl]

Euler7, не паясничайте. Никто Вам здесь ничего не должен.
Предлагаю для начала упростить задачу. Первый игрок загадывает числа среди $(1; 2; 3; 4)$.

[arseniiv]

Лучше от 1 до 10, может?

[ИСН]

Нет, не лучше. Давайте поймём на примере чисел до 4, какова оптимальная стратегия отгадывания и намного ли она лучше деления пополам.

-- менее минуты назад --

Лучше 7, оно пополам делится ловчее. И опять же, компромисс между 4 и 10. Да, точно, Euler7, расскажите. Вот первый загадал число от 1 до 7. Что делает второй?

[arseniiv]

ИСН в сообщении #990414 писал(а):

Лучше 7, оно пополам делится ловчее.

Думал, это, наоборот, плохо. Но посмотрим сначала, действительно.

[Euler7]

atlakatl в сообщении #990410 писал(а):

Euler7, не паясничайте. Никто Вам здесь ничего не должен.

Хорошо, вы правы, прошу прощения.

ИСН в сообщении #990414 писал(а):

расскажите. Вот первый загадал число от 1 до 7. Что делает второй?

пытается угадать это число:
первый - загадывает число 3
второй - 4
первый - меньше
второй - 2
первый - больше
второй - 3
игра окончена, второй игрок получает 5 очков за отгадку с третьего раза(максимум 7 - за отгадку с первого раза).

ИСН в сообщении #990414 писал(а):

Лучше 7, оно пополам делится ловчее. И опять же, компромисс между 4 и 10.

похоже при $n=2^n-1$ стратегия половинного деления не проигрывает, если первый игрок придерживается оптимальной стратегии.
Оптимальная стратегия загадывающего \left\{\frac{2}{9},\frac{1}{9},\frac{1}{9},\frac{1}{9},\frac{1}{9},\frac{1}{9},\frac{2}{9}\right\} - т.е. с вероятностью 2/9 загадать 1, с вероятностью 1/9 загадать 2 и т.д. Она получена построением матрицы игры и симплекс-методом в матпакете. Т.о. цена игры будет $\frac{49}9$, как и при оптимальных стратегиях с обеих сторон.
Однако оптимальной стратегией половинное деление считаться не может, поскольку если первый игрок отойдёт от своей стратегии и выберет стратегию \left\{\frac{1}{4},0,\frac{1}{4},0,\frac{1}{4},0,\frac{1}{4}\right\}, то средний выигрыш второго игрока упадёт до 5.