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

[ИСН]

Эге. Так. А Вы какую стратегию ищете? Которая оптимальна против которой?

[Euler7]

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

Эге. Так. А Вы какую стратегию ищете? Которая оптимальна против которой?

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

[svv]

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

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

А не может быть так, что эта стратегия, которую Вы называете оптимальной, в реальности малоэффективна? Что пытаясь гарантировать наибольший минимальный выигрыш при любой стратегии противника, мы делаем этот выигрыш очень малым (если не отрицательным)?

[ИСН]

А, я понял. "В среднем" она и есть малоэффективна. Её задача не в том, чтобы много выиграть в среднем. Не это оптимизируется.

[svv]

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

[Euler7]

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

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

А не может быть так, что эта стратегия, которую Вы называете оптимальной, в реальности малоэффективна? Что пытаясь гарантировать наибольший минимальный выигрыш при любой стратегии противника, мы делаем этот выигрыш очень малым (если не отрицательным)?

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

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

А, я понял. "В среднем" она и есть малоэффективна. Её задача не в том, чтобы много выиграть в среднем. Не это оптимизируется.

именно это...

[ИСН]

Да нет. Вы же сами только что сказали, что оптимизируется worst-case выигрыш, а не "средний", что бы это ни значило. (Возможно, последнее понятие здесь вообще нельзя никак пристойно определить - что такое средняя стратегия? - ну да неважно.)

[Euler7]

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

Да нет. Вы же сами только что сказали, что оптимизируется worst-case выигрыш, а не "средний", что бы это ни значило.

не, я таких слов не знаю, так что не мог это написать :) .
например тут именно такое определение:

Цитата:

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

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

[ИСН]

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

не, я таких слов не знаю, так что не мог это написать :) .

Ну да, буквально таких слов не было. Тем не менее, по смыслу Вы написали именно это.

[Padawan]

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

А не может быть так, что эта стратегия, которую Вы называете оптимальной, в реальности малоэффективна?

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

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

[Euler7]

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

Опишите, как Вы понимаете, что из себя представляют чистые стратегии второго игрока (который угадывает)?

К первому сообщению приложены картинки с решениями для n<14. Там стратегия второго игрока - это вектор(столбец) из n элементов, где под номером 1 находится выигрыш второго игрока, если первый загадал 1, под номером 2 выигрыш, если первый загадал 2 и т.д.

[Padawan]

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

-- Вс мар 15, 2015 21:07:38 --

То есть чистая стратегия второго игрока -- это некоторый набор правил, который говорит, в такой-то ситуации называй такое-то число.

[Euler7]

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

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

-- Вс мар 15, 2015 21:07:38 --

То есть чистая стратегия второго игрока -- это некоторый набор правил, который говорит, в такой-то ситуации называй такое-то число.

Для примера возьмём наименьшее нетривиальное n=3. Ещё раз картинка оптимальных стратегий:

Стратегии второго игрока идут начиная с третьего столбца.
первая стратегия {3, 1, 2} - её нужно использовать с вероятностью 2/5.
{3, 1, 2} значит, что начинаем отгадывать с числа 1, если не угадали выбираем 3, а потом 2. Т.е. алгоритм такой - на первом шаге ищем максимальное число в векторе, который описывает стратегию, его позиция в векторе - это число, которое мы называем. Если не угадали, то на следующем шаге повторяем эту операцию на оставшейся части вектора-стратегии.

[Padawan]

Что значит, "если не угадали". Не угадали бывает двух видов -- первый игрок сказал "больше" или "меньше". В зависимости от этого, называем следующее число. А по-Вашему получается, как он не ответит, все равно.

[Euler7]

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

Что значит, "если не угадали". Не угадали бывает двух видов -- первый игрок сказал "больше" или "меньше". В зависимости от этого, называем следующее число. А по-Вашему получается, как он не ответит, все равно.

нет же, если отвечает "меньше", то часть вектора с номерами "больше или равно" отпадает, ищем только в той части, что осталась. Поэтому в векторе-стратегии всегда ровно одно число n, не более двух n-1, не более четырёх n-2 и т.д.