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

[Padawan]

Ничего не понимаю. Давайте разберем пример какой-нибудь стратегии для $n=7$ что ли. Допустим первый игрок загадал 4. Опишите действия второго по какой-нибудь из стратегий.

[Euler7]

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

Ничего не понимаю. Давайте разберем пример какой-нибудь стратегии для $n=7$ что ли. Допустим первый игрок загадал 4. Опишите действия второго по какой-нибудь из стратегий.

Цитата:

Выбираем первую стратегию - {6, 5, 7, 4, 5, 6, 5}
Находим максимум в векторе-стратегии - это 7 на позиции 3. Значит выбираем 3.
Получаем ответ "больше", теперь стратегии с номерами с 1 до 3 включительно недоступны - {6, 5, 7, 4, 5, 6, 5}.
А в оставшейся части максимум 6 на позиции 6, значит 6 и выбираем.
Получаем ответ "меньше", теперь доступны только стратегии номер 4 и 5 - {6, 5, 7, 4, 5, 6, 5}.
В оставшейся части максимум (5) на пятой позиции, соответственно 5 и называем(из-за позиции).
Получаем ответ "меньше" - {6, 5, 7, 4, 5, 6, 5}.
Остаётся только стратегия 4, её и выбираем, выигрывая 4 очка.

Цитата:

Альтернатива - выбираем седьмую стратегию - {5, 4, 6, 5, 7, 5, 6}.
Находим максимум в векторе-стратегии - это 7 на позиции 5. Значит выбираем 5.
Получаем ответ "меньше", теперь стратегии с номерами с 5 до 7 включительно недоступны - {5, 4, 6, 5, 7, 5, 6}.
В оставшейся части максимум (6) на третьей позиции, соответственно называем 3.
Получаем ответ "больше", теперь доступна только стратегия 4 - {5, 4, 6, 5, 7, 5, 6}.
Выбираем стратегию 4 и получаем 5 очков.

[grizzly]

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

-- 15.03.2015, 21:15 --

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

[Padawan]

Euler7
Вы уверены, что у второго игрока существует всего 7 стратегий?

[svv]

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

Если, конечно, предполагать, что противник не дурак и тоже выбирает оптимальную стратегию.

Так в этом всё дело. Допустим, противнику точно известно, что я выбираю оптимальную стратегию, думая, что он не дурак и тоже выбирает оптимальную стратегию. Тогда он может эту мою оптимальность обратить мне во вред, придерживаясь некоторой определенной неоптимальной стратегии. Речь не об этой игре (фактически, не считая загадывания числа, здесь играет один игрок), а вообще.

Если же потребовать, чтобы я обеспечил себе некоторый гарантированный выигрыш, независимо от того, дурак противник или нет (о чем, собственно, и говорил Euler7), думаю, это приведёт к сильному снижению выигрыша. «Стратегия труса» не может быть эффективной.

[Padawan]

Как я понимаю, что такое стратегия второго игрока: Это граф-дерево, в первой вершине которого стоит число, которое игрок должен назвать в первый раз, и из каждой вершины выходит от одного до трех ребер, соответствующих возможным ответам первого игрока: "больше", "меньше", "угадал", эти ребра ведут в вершины, где стоит очередное число, которое должен назвать второй игрок. Теоретически такой граф может быть и бесконечным, но сразу можно отбрасывать бессмысленные ответы, которые уже не могут реализоваться.

svv в сообщении #990782 писал(а):

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

Не может. Для любой другой его стратегии, он получит меньший выигрыш, а Вы -- больший.

-- Вс мар 15, 2015 23:55:48 --

svv в сообщении #990782 писал(а):

«Стратегия труса» не может быть эффективной.

Ошибаетесь. Нельзя недооценивать противника. Это обычно приводит к печальным последствиям. Надо трезво оценивать его возможности.

-- Пн мар 16, 2015 00:00:42 --

Euler7
Вот, например, стратегию "тупо называть все числа подряд, начиная с 1, пока не угадаешь" Вы рассматривали?

[Euler7]

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

Вы уверены, что у второго игрока существует всего 7 стратегий?

У игрока 429 стратегий, а эти 7 составляют оптимальную стратегию(возможно она не единственная).

Padawan писал(а):

Вот, например, стратегию "тупо называть все числа подряд, начиная с 1, пока не угадаешь" Вы рассматривали?

нет, а зачем? Она же явно хуже. Я рассмотрел две стратегии за второго игрока - "интуитивную"(деление пополам) и "рекурсивную"(когда у игрока n стратегий, часть из которых - это игры с меньшим n). Но они обе оказались не оптимальны.

svv писал(а):

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

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

[Geen]

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

Но они обе оказались не оптимальны.

А как Вы это установили?

[Euler7]

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

А как Вы это установили?

Сравнил цену игры с той, что даёт оптимальная стратегия(на маленьких n).

[Geen]

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

Я рассмотрел две стратегии

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

Но они обе оказались не оптимальны.

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

Сравнил цену игры с той, что даёт оптимальная стратегия(на маленьких n).

Ничего не понял.
Сколько и каких стратегий Вы рассмотрели? Как устанавливали оптимальность?

[Euler7]

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

Ничего не понял.
Сколько и каких стратегий Вы рассмотрели? Как устанавливали оптимальность?

две, выше описал обе. Для n<14 посчитал оптимальные симплекс-методом, они приложены к первому сообщению и с ними сравнивал интуитивную(половинного деления) и рекурсивную стратегии и обе были хуже.

[Geen]

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

Нужно найти оптимальные стратегии

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

посчитал оптимальные симплекс-методом

Теперь совсем ничего не понимаю....

[Euler7]

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

Теперь совсем ничего не понимаю....

симплекс-методом можно посчитать, если стратегий миллион, но не $10^{56}$

[Padawan]

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

У игрока 429 стратегий

Опишите, как Вы их задаете?

[Euler7]

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

Опишите, как Вы их задаете?

Рекурсивно из более маленьких матриц, например для 4:

Если взглянуть на первую формулу для вычисления числа стратегий, то видно, что происходит просто рекурсивное суммирование длин этих матриц: $f(n)=\sum\limits_{k=0}^{n-1}f(k) f(n-k-1), f(0)=f(1)=1$