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

[Утундрий]

Слишком часто здесь звучит "я не понимаю". Давайте-ка ещё раз пробежимся по условию. Итак, игрок у нас один, а оптимальность стратегии понимается в смысле минимизации числа попыток. Если стратегия вероятностная - в минимизации среднего числа попыток.

[Geen]

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

Рекурсивно из более маленьких матриц

Что означает эта матрица? Где там стратегии? Почему такая разница между 1 и 4 в этой матрице?

[atlakatl]

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

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

Игроков у нас два. Один загадывает число, другой его угадывает. Надо найти наилучшую стратегию второго игрока при активном противодействии первого. И да, критерий оптимальности - среднее число попыток.

[Euler7]

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

Что означает эта матрица? Где там стратегии? Почему такая разница между 1 и 4 в этой матрице?

Это матрица игры, как по столбцу восстановить стратегию второго игрока я описывал тут. Краткая инструкция по решению матричных игр есть тут.

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

Итак, игрок у нас один, а оптимальность стратегии понимается в смысле минимизации числа попыток.

Игрока у нас 2 - один загадывает, а другой отгадывает. Первый минимизирует средний выигрыш второго, а второй наоборот его максимизирует.
Оптимальная стратегия игрока — стратегия,которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш(или, что тоже, минимально возможный средний проигрыш).

[Geen]

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

как по столбцу восстановить стратегию второго игрока я описывал тут
.

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

Значит выбираем 3.
Получаем ответ "больше", теперь стратегии с номерами с 1 до 3 включительно недоступны

Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

[Euler7]

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

Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

да, их две. Вы для данной партии выбрали первую из них(которая описывается вектором {3, 4, 2, 3}, после ответа 2 на первом шаге будет {3, 4, 2, 3} и ответ 4 на втором).

[Geen]

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

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

Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

да, их две. Вы для данной партии выбрали первую из них(которая описывается вектором {3, 4, 2, 3}, после ответа 2 на первом шаге будет {3, 4, 2, 3} и ответ 4 на втором).

Понятно, спасибо.
Но тогда следующий вопрос. Зачем при $n=7$ Вам считать, что имеется 25 стратегий, начинающихся с вопроса 4?

[Euler7]

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

Но тогда следующий вопрос. Зачем при $n=7$ Вам считать, что имеется 25 стратегий, начинающихся с вопроса 4?

При ответе "больше" будет выбор из трёх чисел, т.е. 5 вариантов стратегий останется. Аналогично при ответе "меньше" 5 вариантов. И любой из ответов после "больше" можно сочетать с любым ответом после "меньше", значит всего 5*5. Это все возможные варианты развития событий.

[atlakatl]

Не понял, как ТС решил игру на трёх числах. Всё сложнее.
Игрок А загадывает число, игрок В угадывает. Составляем матрицу игры, элементами которой являются числа попыток.
Если В с первого раза угадал число, то число попыток $1$. Это диагональные элементы $a_{11}, a_{22}, a_{33}$.
Если В начал угадывание с числа $2$, а А загадал $1$ или $3$, то на следующем ходу решение будет найдено. Т.е. для элементов $a_{12}$ и $a_{32}$ число попыток равно $2$.
А вот если А загадал $1$, а В первым назвал $3$, или наоборот А загадал $3$, а В первым назвал $1$, то на втором ходе число можно не угадать. И для В опять нужна стратегия. Как её получить? - Ясно, что первым надо называть число, имеющее бо`льшую вероятность быть названным А. Но эту вероятность мы пока не знаем. Поэтому назову пока эти элементы $x, y, z, k$.
Имеем матрицу:

Что дальше?

[Euler7]

atlakatl
составляем платёжную матрицу:

строки - чистые стратегии первого игрока, столбцы - второго. Восстановление стратегий второго по столбцу объяснялось выше, для первого тривиально - номер строки и есть загаданное число. На пересечении стратегий стоит выигрыш второго игрока, он же проигрыш первого. Дальше решаем как и любую матричную игру. По этой ссылке можно воспользоваться онлайн-калькулятором игр. Кроме того случай n=3 разобран в книге Дрешер М. - Cтратегические игры Теория и приложения - 1964 со страницы 54.

[atlakatl]

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

случай n=3 разобран в книге Дрешер М. - Cтратегические игры Теория и приложения - 1964
со страницы 54.

Три страницы убористых вычислений. И это для простейшего - на первый взгляд - случая.

[Утундрий]

Книжку я сейчас посмотреть не могу. Но потыкав наугад склоняюсь к использованию треугольника Паскаля.

-- Пн мар 16, 2015 18:32:31 --

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

[Padawan]

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

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

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

[atlakatl]

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

Как такое задание соотносится c моим понимание стратегии:

По Дрешеру получается так:
Например, вектор $(4, 2, 6, 1, 3, 5, 7)$ означает: первым ходом называется $4$. Если следует ответ "много", то называется $2$, если "мало" - $6$. Дальше рассматривается выбор после второго ответа: $1$, если на предыдущее $2$ последовало "много", $3$ - если "мало", и т.д.

[Утундрий]

Глянул, платёж там выдаётся только первому игроку и это таки да - количество попыток второго. О платеже второму - ни слова. Поэтому я ещё раз внимательно спрашиваю, что это за сто очков за угадывание и вообще, огласите правила целиком, пжалста.