Какое число показать?

[Shadow]

$q=1$ Боб ВСЕГДА заявляет, что спрятано бОльшее число: (У меня тут насчет программирования только Excel, так что VBA)

Const C = 0.689897949

Function AlceWin() As Single
Dim X1, X2, R As Single
X1 = Rnd
X2 = Rnd
If X1 > X2 Then 'Делаем X1 меньшее, X2 - большее
 R = X1
 X1 = X2
 X2 = R
End If

'Стратегия Боб работает только если оба числа больше C
If X1 > C Then AlceWin = -X2 Else AlceWin = X1
End Function 

Private Sub CommandButton1_Click()
Dim I As Long, N As Long, Rez As Double
N = 1000000
Randomize
Rez = 0
For I = 1 To N
 Rez = Rez + AlceWin
Next I
Label1.Caption = Rez / N
End Sub

Средний выигрыш Алисы в одной игре, прибл. $0.171$

-- 06.07.2025, 09:47 --

При $q=0$ (всегда говорит спрятано меньшее)

Если $x_1>c, x_2>c$ Алиса выигрывает $x_2$. В остальных случаях проигрывает $x_1$

Симетрично получилось...вы правы кажется.

-- 06.07.2025, 09:59 --

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

[EUgeneUS]

Нашлось простое решение в чистых стратегиях.

Алиса нумерует ГСЧ. И всегда прячет из ГСЧ-1 ($x$), а показывает из ГСЧ-2 ($y$).
В чистых стратегиях у Боба нет шансов выйти из нуля. Да и в смешанных тоже.

-- 06.07.2025, 11:02 --

Shadow в сообщении #1693411 писал(а):

Тоесть, не существует стратегия, при которой Алиса гарантированно выигрывает.

Нужно найти стратегию, в которой Алиса сводит проигрыш\выигрыш в ноль. При любой стратегии Боба.

Shadow в сообщении #1693411 писал(а):

А значит ей нужно тоже действовать совершенно случайно?

Не совсем совершенно случайно.

Впрочем, нашлось простое решение в чистых стратегиях. См. выше.

[wrest]

EUgeneUS в сообщении #1693413 писал(а):

Алиса нумерует ГСЧ. И всегда прячет из ГСЧ-1 ($x$), а показывает из ГСЧ-2 ($y$).

Поясните пож-ста, что значит нумерует ГСЧ?
Звучит так, что следующий выбор Алисы зависит от предыдущего ("игроки помнят историю"), а не только от выпавших чисел.

[EUgeneUS]

wrest в сообщении #1693414 писал(а):

Поясните пож-ста, что значит нумерует ГСЧ?

mihaild в сообщении #1693259 писал(а):

Алиса получает два независимых равномерно распределенных на $[0, 1]$ числа $x$ и $y$.

Это означает, что Алиса различает потоки, откуда идут $x$ и $y$, и прячет всегда $x$, а скрывает всегда $y$ (например).

Вообще говоря, подойдёт любая $f(x,y)$ (вероятность того, что Алиса покажет меньшее число, а спрячет бОльшее), такая что $f(y,x) = 1 - f(x,y)$.

Если у Алисы нет возможности различить $x$ и $y$. То она может действовать так:
1. получив пару чисел, пронумеровать их внутри пары. Это всегда можно.
2. подбрасывать честную монету, и в зависимости от исхода: прятать первое число, показывать второе, или наоборот.

[wrest]

EUgeneUS в сообщении #1693418 писал(а):

Это означает, что Алиса различает потоки, откуда идут $x$ и $y$, и прячет всегда $x$, а скрывает всегда $y$ (например).

Ну это как то странно... А это не то же самое что выбирает равновероятно какое из двух показать?

[mihaild]

EUgeneUS в сообщении #1693413 писал(а):

Алиса нумерует ГСЧ. И всегда прячет из ГСЧ-1 ($x$), а показывает из ГСЧ-2 ($y$).

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

[Shadow]

EUgeneUS в сообщении #1693418 писал(а):

Это означает, что Алиса различает потоки, откуда идут $x$ и $y$, и прячет всегда $x$, а скрывает всегда $y$ (например).

Правиьно вас понимаю что в коде:

x = Rnd
y = Rnd

Алиса показывает всегда $y$. Тогда если Боб всегда говорит "спрятано бОльшее" выигрывает в среднем $0.167$ на игру.

А если при $y>\dfrac{1}{\sqrt 2}$ говорит "спрятано меньшее", то выигрывает $0.304$

[wrest]

Начнём моделировать.

Используется pari/gp
Главная функция:

1. simulate_game(N, alice_strategy, bob_strategy) = { 
2.     my(total_payoff = 0, x, y, S, H, guess, is_correct, payoff,bob_win=0); 
3.  
4.     for (i = 1, N, 
5.         \\ 1. Алиса получает два случайных числа 
6.         x = random(2^32)/2^32; 
7.         y = random(2^32)/2^32; 
8.  
9.         \\ 2. Алиса делает свой ход 
10.         [S, H] = alice_strategy(x, y); 
11.  
12.         \\ 3. Боб делает свою догадку 
13.         guess = bob_strategy(S); 
14.  
15.         \\ 4. Проверяем, прав ли Боб 
16.         is_correct = ((guess == 1 && H > S) || (guess == -1 && H < S)); 
17.  
18.         \\ 5. Рассчитываем выигрыш Боба в этом раунде 
19.         if (is_correct, 
20.             payoff = H;bob_win++, 
21.             payoff = -H 
22.         ); 
23.  
24.         \\ 6. Добавляем к общей сумме 
25.         total_payoff += payoff; 
26.     ); 
27.  
28.     \\ Возвращаем средний выигрыш Боба за N игр 
29.     print("Bob guess rate = ",floor(1/2+100*bob_win/N)," percent."); 
30.     print("Bob average prize = ",total_payoff/N+0.0); 
31.     print("Best approximation = ",bestappr(total_payoff/N,60)); 
32.     return(total_payoff / N); 
33. }; 

Случайные числа берутся как целые с равномерным распределением из диапазона $[0,2^{32}-1]$
Этого должно быть достаточно для симуляции по крайней мере до $10^{10}$ раундов игры.
Все вычисления точные без округлений. Округление делается только при печати статистики.
Ну из-за этого есть некоторое смещение: Алиса может получать на вход одно из чисел равное нулю (с вероятностью $2^{-32}$), но никогда - равное единице.

Эта же функция одной строкой без пробелов, комментариев и кириллицы, для удобства копипаста в pari/gp:

(Оффтоп)

1. simulate_game(N,alice_strategy,bob_strategy)=my(total_payoff=0,x,y,S,H,guess,is_correct,payoff,bob_win=0);for(i=1,N,x=random(2^32)/2^32;y=random(2^32)/2^32;[S,H]=alice_strategy(x,y);guess=bob_strategy(S);is_correct=((guess==1&&H>S)||(guess==-1&&H<S));if(is_correct,payoff=H;bob_win++,payoff=-H);total_payoff+=payoff;);print("Bob guess rate = ",floor(1/2+100*bob_win/N)," percent.");print("Bob avegage prize = ",total_payoff/N+0.0);print("Best approximation = ",bestappr(total_payoff/N,60));return(total_payoff/N) 

Чтобы всё работалo, надо иметь ещё две функции.

1. Стратегия за Алису. Эта функция должна принимать на вход два числа, и отдавать на выход вектор из двух чисел. Первое - то что показывает, второе - скрывает.
Пример "Алиса выбирает равновероятно"
alice_strategy_random(x,y)=if(random(2),return([x,y]),return([y,x]))
Пример "Алиса всегда показывает меньшее"
alice_strategy_show_min(x,y)=return([min(x,y),max(x,y)]);
Пример " Алиса всегда показывает большее"
alice_strategy_show_max(x,y)=return([max(x,y),min(x,y)]);

2. Стратегия за Боба. Эта функция принимает на вход одно число (показанное) и возвращает 1 если Боб считает что показанное больше, и -1 если Боб считает, что показанное меньше.
Пример "Боб выбирает равновероятно"
bob_strategy_random(S)=if(random(2),return(1),return(-1));
Пример "Боб всегда говорит больше"
bob_strategy_say_max(S)=return(1);
Пример "Боб говорит меньше и если показанное ему число больше 1/2"
bob_strategy_half(S)=if(S>1/2,return(-1),return(1));

Как запускать.
Основная функция game_simulate(N,alice_strategy,bob_strategy,p) принимает три аргумента
N - количество игр
alice_strategy - имя функции реализующей стратегию за Алису, например alice_strategy_random
bob_strategy - имя функции стратегии за Боба например bob_strategy_random
В момент запуска основной функции, функции реализующие стратегии, понятное дело, должны быть уже записаны в интерпретатор pari/gp

Функция печатает статистику -- каков оказался процент угадываний и сколько в среднем выиграл Боб за одну игру.
Функция так же возвращает средний выигрыш Боба.

Запускаем вариант "Алиса выбирает равновероятно, Боб выбирает равновероятно":

? simulate_game(10^5, alice_strategy_random, bob_strategy_random);
Bob guess rate = 50 percent.
Bob avegage prize = 0.00016247203767998144030570983886718750000
Best approximation = 0
time = 357 ms.
?

Видим что выигрыш нулевой.

Запускаем вариант "Алиса выбирает равновероятно, Боб всегда говорит больше"

? simulate_game(10^5, alice_strategy_random, bob_strategy_say_max);
Bob guess rate = 50 percent.
Bob avegage prize = 0.16670685586136998608708381652832031250
Best approximation = 1/6
time = 350 ms.
?

Видим что Боб угадывает в половине случаев и его средний выигрыш 1/6

-- 06.07.2025, 13:22 --

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

[wrest]

Shadow в сообщении #1693398 писал(а):

И так я-Алиса. И я вам говорю свою стратегию:

Есть константа $c=\dfrac{1+\sqrt 6}{5}$

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

Вот и постройте вашу(Боба) стратегию, исходя из этой информации. Посмотрим что получится.

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

1. alice_strat_shadow(x,y)=my(c=(1+sqrt(6))/5);if(min(x,y)>c,return([min(x,y),max(x,y)]),return([max(x,y),min(x,y)])) 

Пишем стратегию за Боба "всегда говорит меньше"

1. bob_strat_say_min(S)=return(-1); 

Запускаем "Алиса вычисляет константу по Shadow и затем выбирает, Боб всегда говорит меньше"

? simulate_game(10^5, alice_strat_shadow, bob_strat_say_min);
Bob guess rate = 91 percent.
Bob avegage prize = 0.17221842876082984730601310729980468750
Best approximation = 5/29
time = 439 ms.
?

Боб угадал в 91% случаев и заработал чуть больше 1/6, Алиса в пролёте

[EUgeneUS]

mihaild в сообщении #1693430 писал(а):

Как правильно замечает wrest,

Да, по-простому не получилось

wrest
Просьба, Вы не могли бы посчитать такие стратегии:

I. Стратегия за Алису:
i. Если $y < x$ - показываем $x$, прячем $y$
ii. Если $x < y < \frac{1}{2}(x+1)$ - показываем $y$, прячем $x$
iii. Если $\frac{1}{2}(x+1) < y $ - показываем $x$, прячем $y$

И при такой стратегии Алисы, следующие стратегии Боба (разные запуски)

1. Всегда говорит "Показано большее"
2. Всегда говорит "Показано меньшее"
3. Если показано больше $0.25$, говорит "Показано большее", иначе говорит "показано меньшее"
4. Если показано больше $0.5$, говорит "Показано большее", иначе говорит "показано меньшее"
5. Если показано больше $0.75$, говорит "Показано большее", иначе говорит "показано меньшее"

Ожидаемый результат: в стретегиях Боба 1 и 2 - ноль, в других - не ноль.

II. Стратегия за Алису:

С вероятностью $1/3$ Алиса покажет меньшее число, а спрячет бОльшее.

И при такой стратегии Алисы, следующие стратегии Боба (разные запуски)

1. Всегда говорит "Показано большее"
2. Всегда говорит "Показано меньшее"
3. Если показано больше $0.25$, говорит "Показано большее", иначе говорит "показано меньшее"
4. Если показано больше $0.5$, говорит "Показано большее", иначе говорит "показано меньшее"
5. Если показано больше $0.75$, говорит "Показано большее", иначе говорит "показано меньшее"

Ожидаемый результат: в стратегиях Боба 1 и 2 - ноль, в других - а это будет интересно .

[wrest]

EUgeneUS в сообщении #1693447 писал(а):

I. Стратегия за Алису:

Давайте я разными постами сделаю. В этом посте -- функции.
Стратегии пишу точно как вы хотите, без приведения подобных и т.п.
i. Если $y < x$ - показываем $x$, прячем $y$
ii. Если $x < y < \frac{1}{2}(x+1)$ - показываем $y$, прячем $x$
iii. Если $\frac{1}{2}(x+1) < y $ - показываем $x$, прячем $y$

alice_strat_EUgeneUS(x,y)={
if(y<x,return([x,y]));
if(x<y && y<(x+1)/2,return([y,x]));
if((x+1)/2<y,return([x,y]));
error("Alice failed to make a choice with x=",x," y=",y);
}

И при такой стратегии Алисы, следующие стратегии Боба (разные запуски)

1. Всегда говорит "Показано большее"

bob_strat_say_max(S)=return(1);

2. Всегда говорит "Показано меньшее"

bob_strat_say_min(S)=return(-1);

3. Если показано больше $0.25$, говорит "Показано большее", иначе говорит "показано меньшее"

bob_strat_quarter(S)=if(S>1/4,return(1),return(-1));

4. Если показано больше $0.5$, говорит "Показано большее", иначе говорит "показано меньшее"

bob_strat_half(S)=if(S>1/2,return(1),return(-1));

5. Если показано больше $0.75$, говорит "Показано большее", иначе говорит "показано меньшее"

bob_strat_triquatro(S)=if(S>3/4,return(1),return(-1));

[EUgeneUS]

Промежуточный итог.

1. Задача решена в смешанных стратегиях, при условии, что Боб не анализирует показанное число.
Это сильно допущение. Возможно (но неточно), что найденная стратегия Алисы подойдет и для этого случая. Но это не доказано.

2. В чистых стратегиях. Решение не найдено, и не доказано, что его не существует.

Не густо

[wrest]

EUgeneUS в сообщении #1693447 писал(а):

С вероятностью $1/3$ Алиса покажет меньшее число, а спрячет бОльшее.

alice_strat_EUgeneUS_drittel(x,y)=if(random(3),return([min(x,y),max(x,y)]),return([max(x,y),min(x,y)]));

-- 06.07.2025, 18:16 --

Как запускать если нет pari/gp

Идём сюда: https://pari.math.u-bordeaux.fr/gpwasm.html
Копипастим основную функцию (как раз пригодится вариант в одну строку) и жмем кнопку evaluate with pari:

Жмём clear input и последовательно копипастим стратегии которые хотим проверять, после кажого копипаста нажимаем evaluate и clear input.
Затем собсно запуск. В окно ввода пишем например simulate_game(10^5, alice_strat_EUgeneUS, bob_strat_triquatro); жмём evaluate и получаем:


Забыл ещё пояснить про best approximation. Это наилучшее приближение несократимой дробью со знаменателем не большим 60. Почему 60? Ну потому что это суперизбыточное число

[EUgeneUS]

wrest
Спасибо!

[wrest]

Кажется тут ошибка для трети.
Для стратегии "С вероятностью 1/3 Алиса покажет меньшее число, а спрячет бОльшее." правильный текст такой

alice_strat_EUgeneUS_drittel(x,y)=if(!random(3),return([min(x,y),max(x,y)]),return([max(x,y),min(x,y)]));

Пояснение. random(3) равновероятно возвращает 0,1,2. Для pari/gp все что ббольше нуля - истина. Поэтому в старом тексте с вероятностью 1/3 Алиса показывала максимум, а не минимум.

-- 06.07.2025, 18:36 --

EUgeneUS
Напишите пож-ста удалось ли запускать в вебе -- надо ли чтобы я позапускал?