Игра разума

Логические задачи

Игра разума

Сообщение Юляша » 16 дек 2013, 11:53

Билл и Джо играют в следующую игру.

У Билла имеются карточки с нечетными числами от 1 до 9. У Джо - карточки с четными числами из того же диапазона. Каждый игрок выбирает одну карточку и кладет ее на стол закрытой. После этого карточки открываются. Если открытые числа отличаются ровно на 1, банк забирает Билл, если разность другая, то деньги переходят к Джо.

Билл перед каждой партией кладет в банк 12 доллариев. Сколько доллариев должен класть Джо, чтобы игра была честной? Каких стратегий следует придерживаться обоим?
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Игра разума

Сообщение Dendr » 16 дек 2013, 20:54

Для начала допустим, что и Билл, и Джо - слепые (о выигрыше им сообщает арбитр).
Билл с равной вероятностью кладет одну из своих 5 карточек, Джо - тоже с равной, одну из 4.
Всего 20 исходов, выигрышные при этом для Билла: 1-2, 3-2, 3-4, 5-4, 5-6, 7-6, 7-8, 9-8. Всего - 8. То есть Билл выигрывает с вероятностью 40%.
Тогда, если ставка Джо равна Х, то Билл должен "возвращать свое", т.е. выигрывать (12+X)*0.4=12; значит Х=18.

А стратегии...
Карточки Джо можно разбить на пары: 2-4 и 6-8. Значит, одна из пары карт 3 или 7 всегда выигрывает.

Пусть Билл ждет, когда Джо положит свою карту, потом подкидывает тайно монету, и если орел, кладет карточку 3, если решка - то 7.
Тогда, с вероятностью 50% он выиграет. Следовательно, Джо должен класть в банк те же 12 д. И стратегии у него просто нет: тащи карту наугад и все тут.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Юляша » 17 дек 2013, 10:50

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

Правда, у меня в условии оказалась ошибочка). Если числа различаются на единицу выигрывать должен не Билл, а Джо.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Игра разума

Сообщение Dendr » 17 дек 2013, 21:55

Юляша писал(а):Если числа различаются на единицу выигрывать должен не Билл, а Джо.

Но это уже совсем другая задача...
В частности, если это слепые игроки, то Джо должен ставить 8д.

А зрячие - должны отбирать карты более хитрым образом.
С ходу получается, что Билл будет равнопроизвольно выкладывать карты на стол 1, 5 и 9, а Джо - 2 и 8. Про ставки уже сложнее, попробую анализом, что ли?

Во-первых, можно считать, что задача строго симметрична, то есть вероятность выкладывания карты Х равна вероятности 10-Х.
И пусть Джо выкладывает карты с вероятностями (1/2-P) - 2 или 8, P - 4 или 6. (max P=1/2)

Билл же, соответственно, 1 или 9 - Q, 3 или 7 - R, 5 - (1-2Q-2R) (max Q = max R = max (Q+R) = 1/2)

Вероятность возникновения пар:
1-2 (9-8) (1/2-P)Q
3-2 (7-8) (1/2-P)R
3-4 (7-6) PR
5-4 (5-6) P(1-2Q-2R)

Общая сумма равна: (1-2P)(Q+R)+P(1-2Q-R)=P+Q+R-4PQ-3PR - это вероятность выигрыша Джо. Соответственно, Джо хочет эту величину увеличить, подбирая P, а Билл - уменьшить, подбирая Q и R.
P(1-4Q-3R) - вот часть, на которую влияет Джо. Если Билл уже выбрал Q и R, то в зависимости от знака скобки, Джо берет P=1/2 или 0.

Итак, если (1-4Q-3R)>0, то Джо берет P=1/2, тогда вероятность его победы равна 1/2-2Q-1/2R - и это меньше 1/2 (!)
Если же (...)<=0, то P=0, вероятность равна Q+R. И если Билл карту "5" не собирается выкладывать, то она точно равна 1.2

То есть Биллу желательно увеличивать Q и R, пока они не "почти" превратят скобку в равенство:
1=4Q+3R
Сумма 2Q+R/2=(1-2R)/2 максимальна, если R - минимально. Поэтому R=Q, R "почти" равно 1/3. Пусть, для простоты вычислений, Q=0.3

То есть Билл:
с вероятностью 0.3 кладет 1,
с вероятностью 0.4 - 5,
с вероятностью 0.3 - 9.

А Джо - кидает все ту же монетку и кладет либо 4, либо 6 по результатам. Как видно, теперь он выигрывает с вероятностью 0.4, что устраивает Билла.

Это и дает нам тактику Билла - класть (подбросив трехстороннюю монету) 1, 5 или 9. А Джо может играть как ему заблагорассудится, все равно выигрывает только в 1 случае из трех. Поэтому он ставит 6 д.
Как-то так вышло.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Илаис » 17 дек 2013, 22:40

Если Биллу и нужно кидать монету, то не трехстороннюю, а пятистороннюю, где на 2х сторонах написано 1, на 2х - 9 и на одной 5, это чтобы Джо не расслаблялся и не ставил только 4 и 6, (просто если Джо будет ставить только 4 и 6, то Билл спокойно может кидать все время 1 и 9, и не париться - забить полностью на 5).
Поэтому, Джо должен кидать не только 4 и 6, более того, я бы на его месте как раз чаще кидала бы 2 и 8 - именно потому, что если Билл кидает 1 и 9 , то 4,6 - гарантированный проигрыш для Джо в любой ситуации ,а 2 и 8 - дает 50% шанс угадать. Если же Билл начнет кидать и 5ку, то шанс для 2, и 8 падает, но не до нуля - а в зависимости от того, как часто Билл эту пятерку будет кидать.
В общем, им обоим нужно следить за стратегией партнера, и противник начинает избегать какой-либо монеты - воспользоваться этим.
В этом отношении Джо уязвимей - поэтому ему нужно кидать не только 2 и 8 (часто), но и 4/6 (реже), чтобы Билл его не поймал 5кой. Чаще/реже лень высчитывать )
Ну и конечно, Биллу тут совсем не нужно кидать 3 и 7 - просто дарить лишние шансы для Джо.
Аватара пользователя
Илаис
Графоман со стажем
Графоман со стажем
 
Сообщения: 936
Зарегистрирован: 02 мар 2006, 19:52

Re: Игра разума

Сообщение Юляша » 18 дек 2013, 08:46

Вообще, оптимальная стратегия в такого рода играх подразумевает, что противник не может улучшить свой результат, даже предполагая/зная, какую именно стратегию вы используете.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Игра разума

Сообщение Dendr » 18 дек 2013, 22:33

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

А вот тут появляется парадокс, который я и попытался выразить в формулах, но, похоже, засыпался.

То есть, каждый из игроков может воспользоваться одной из набора стратегий. Ну и тогда составляем умозрительную таблицу (умозрительную, потому что в общем случае это континуум), в которой для каждого случая проставляем вероятность победы, допустим, Билла. А дальше - по минимаксу. Формально-то. Но по идее должен быть более простой путь.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Dendr » 18 дек 2013, 22:35

Если за "стратегию" принять "равновероятное выкладывание карт из некого подмножества карт игрока", то у Билла стратегий будет 31, а у Джо - 15. Это реально убойная таблица...
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Юляша » 19 дек 2013, 08:43

Dendr писал(а):То есть, каждый из игроков может воспользоваться одной из набора стратегий.


Смешанная стратегия ("я кину 233-гранный кубик и в зависимости от результата выберу то или иное") - это тоже допустимая стратегия))). Так что матрицу надо совсем другую рисовать (подсказка: надо нарисовать матрицу 5х4, а потом посмотреть, не слишком ли она велика).
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Игра разума

Сообщение Dendr » 21 дек 2013, 14:12

Я покладистый. Могу и нарисовать...
Ходы Джо - горизонталь, Билла - вертикаль. Буквы - кто выиграл при открытии данной пары карт.
=-2-4-6-8
1-Д-Б-Б-Б
3-Д-Д-Б-Б
5-Б-Д-Д-Б
7-Б-Б-Д-Д
9-Б-Б-Б-Д

Ну, что видно? А в принципе, ничего нового:
* когда Джо выкладывает свою карту произвольно, то Биллу выгоднее открыть 1 или 9, чтобы иметь шанс на победу 75%.
* когда Билл выкладывает свою карту произвольно, Джо может ходить любой картой, шанс так и так будет 40%.

Но допустим, что Билл пользуется своей выгодой - мы убираем строки 3-5-7
=-2-4-6-8
1-Д-Б-Б-Б
9-Б-Б-Б-Д

Теперь Джо ни за что не станет кидать 4 или 6: нулевой шанс никому не нужен. Убираем столбцы 4 и 6.
=-2-8
1-Д-Б
9-Б-Д

Ну и выходит довольно нелепая стратегия у обоих: Билл кидает 1 или 9, Джо - 2 или 8. То есть мы пришли к задаче о подбрасывании монеты. Или, если хотите, двух монеток, и победитель определяется XOR'ом.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Dendr » 21 дек 2013, 14:14

Интересно, что если Билл передумает менять стратегию от базовой, а Джо - поменяет, то получится вот что:
=-2-8
1-Д-Б
3-Д-Б
5-Б-Б
7-Б-Д
9-Б-Д

Конечно, Биллу тут же захочется кидать только пятерку... Тогда Джо передумает тоже и начнет кидать 4 или 6.

В общем, камень-ножницы-бумага - стратегии нет, есть только паттерн.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Юляша » 23 дек 2013, 08:40

Рекомендуется в матрице 5х4 для начала сравнить первую и вторую строки, а затем продолжить в том же духе с прочими строками и столбцами...
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

Re: Игра разума

Сообщение Dendr » 23 дек 2013, 23:03

Ну... так-то изначально понятно, что при прочих равных карта 1 для Билла, как минимум, не хуже карты 3. Поэтому тройку и семерку он может спокойно отложить.

=-2-4-6-8
1-Д-Б-Б-Б
5-Б-Д-Д-Б
9-Б-Б-Б-Д

Билл отложил 3 и 7, и его средний шанс на победу возрос с 60% до 66,67%. Если он уберет еще одну карту, то шанс упадет до 50%, поэтому он так не поступит. А Джо волен выбирать любую тактику, и ничего в этой точке не изменит.

Парадокс, но Билл не может отложить в сторону пятерку (хотя средний шанс и подрастет до 75%): ведь тогда у Джо появится стратегия улучшения своих шансов.
Если же Джо решит отказаться от какой-то из карт, то он рискует тем, что Билл его раскусит и отложит в сторону несколько своих, увеличивая себе шансы на победу.

И, похоже, это и есть ответ: Билл подбрасывает 3-стороннюю монету (реально, игральный кубик, беря значение min(X, 7-X), пользуясь программистско-игровым сленгом, 1d3=(1d6 mod 3)), после чего выкладывает одну из карт 1-5-9, а Джо - 4-стороннюю (реально - дважды обычную: 1d4=2d2).
Для честной игры Джо должен ставить в два раза меньше, чем Билл.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

Re: Игра разума

Сообщение Юляша » 26 дек 2013, 11:25

Ответ близкий к правильному, но увы. Если Джо будет применять указанную стратегию, то Билл будет выкладывать только 5 и побеждать в 50% случаев))).

Вообще, довольно неожиданно для меня было обнаружить у завсегдатаев форума "дырку" в теории игр, но буду знать, если что, какие задачки сложные))).
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3115
Зарегистрирован: 15 янв 2009, 12:32

След.

Вернуться в Задачки



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2