30 апреля на сайте http://eq.ur.ru/ пройдет турнир по игре Жребий Крижановского. Программы можно отсылать уже сейчас.
Правила игры "Жребий Крижановского"
Будем считать, что в игре участвует n игроков (n>2). Каждый игрок независимо от других называет натуральное число в диапазоне от 1 до n+1 включительно (при игре "вживую" игроки пишут числа на бумажках, а затем их оглашают). Затем среди названных чисел выбираются те, которые были названы только одним каким-либо игроком. Выигрывает игрок, написавший наименьшее из этих выбранных чисел, причем количество выигранных им очков равно написанному им числу. Если ни одно из названных чисел не оказалось уникальным, то объявляется ничья и очки никому не присуждаются.
Пример: играли 7 игроков и были названы числа: 5 1 1 3 1 2 2
В этом случае три очка выиграл четвертый игрок, так как его тройка меньше, чем пятерка, названная первым игроком, а все остальные числа (1 и 2) были названы больше, чем одним игроком.
Не потрудитесь отослать свое решение. Чем больше игроков, тем интереснее будут результаты!
Здравствуйте, XopoSHiy, Вы писали:
XSH>Не потрудитесь отослать свое решение. Чем больше игроков, тем интереснее будут результаты! Не потрудитесь или все-таки не поленитесь?
Don't crash the ambulance, whatever you do!
ICQ#327823673
In her dealings with man Destiny never closed her accounts. (c) Oscar Wilde
Раз тут форум этюдов, то спешу предложить парочку-троечку:
1. Разработать оптимальную стратегию, если известно, что остальные запостили "random(n+1) + 1", т.е. число вибирают случайно
2. Разработать оптимальную стратегию, если известно, что остальные запостили "random(m) + 1", т.е. число вибирают случайно из диапазона 1..m, m <= n+1
3. Мы хотим запостить стратегию "random(m2) + 1", а остальные уже запостили "random(m1) + 1". Какое m2 выбрать?
---
С уважением,
Лазарев Андрей
Re: Турнир по игре Жребий Крижановского
От:
Аноним
Дата:
21.04.05 06:55
Оценка:
Примерная схема программы для тех, кто использует C++
#include <iostream.h>
main()
{
int n; /* количество игроков */int m; /* номер текущего хода */int s; /* текущая сумма очков у программы */int winners[10000]; /* список чисел, выигрывавших в предыдущих турах */int i;
int move; /* ход программы */
cin >> n;
cin >> m;
cin >> s;
for (i=1; i<=m-1; i++)
cin >> winners[i];
/* Здесь должны размещаться операторы, приводящие к вычислению переменной move */
cout << move;
return 0;
}
Примерная схема программы для тех, кто использует Паскаль
Program kryzh;
Type
arr = array [1..10000] of integer;
Var
n : integer; { количество игроков }
m : integer; { номер текущего хода }
s : integer; { текущая сумма очков у программы }
winners : arr; { список чисел, выигрывавших в предыдущих турах }
i : integer;
move : integer; { ход программы }Begin
Read (n);
Read (m);
Read (s);
For i := 1 to m-1 do
Read(winners[i]);
{ Здесь должны размещаться операторы, приводящие к вычислению переменной move }
Write(move);
End.
Здравствуйте, XopoSHiy, Вы писали:
XSH>Привет всем!
XSH>30 апреля на сайте http://eq.ur.ru/ пройдет турнир по игре Жребий Крижановского. Программы можно отсылать уже сейчас.
XSH>
XSH>Правила игры "Жребий Крижановского"
XSH>Будем считать, что в игре участвует n игроков (n>2). Каждый игрок независимо от других называет натуральное число в диапазоне от 1 до n+1 включительно (при игре "вживую" игроки пишут числа на бумажках, а затем их оглашают). Затем среди названных чисел выбираются те, которые были названы только одним каким-либо игроком. Выигрывает игрок, написавший наименьшее из этих выбранных чисел, причем количество выигранных им очков равно написанному им числу. Если ни одно из названных чисел не оказалось уникальным, то объявляется ничья и очки никому не присуждаются.
XSH>Пример: играли 7 игроков и были названы числа: 5 1 1 31 2 2
XSH>В этом случае три очка выиграл четвертый игрок, так как его тройка меньше, чем пятерка, названная первым игроком, а все остальные числа (1 и 2) были названы больше, чем одним игроком.
XSH>Не потрудитесь отослать свое решение. Чем больше игроков, тем интереснее будут результаты!
Разработал оптимальную стратегию для двух игроков...
Честно говоря далось с большим трудом.
Получилось, что число 3 надо выбирать чаще всего.
Для трех без приближенных вычислений, пачки сигарет и пары бутылок пива не обойтись — оччень сложно.
Народ как по-вашему, сохранятся ли отношения вероятностей(для чисел 1,2,3) для оптимальной стратегии для 3?
То есть можно ли использовать индукцию?
Здравствуйте, tinytjan, Вы писали:
T>Разработал оптимальную стратегию для двух игроков... T>Честно говоря далось с большим трудом. T>Получилось, что число 3 надо выбирать чаще всего. T>Для трех без приближенных вычислений, пачки сигарет и пары бутылок пива не обойтись — оччень сложно.
T>Народ как по-вашему, сохранятся ли отношения вероятностей(для чисел 1,2,3) для оптимальной стратегии для 3? T>То есть можно ли использовать индукцию?
У меня предчувствие, что (раз получается что-то громозкое) потребуется привлечь марковские сети...
Представим себе самообучающуюся систему из N игроков. Ну или хотя бы из 3.
Известен вектор P[k] вероятности выбора противником числа k. Изначально вектор равномерно заполнен.
Далее, на очередной итерации я предполагаю, что противники делают выбор (1,1), (1,2), ..., (3,3) — и соответственно совершаю свой наилучший выбор.
* означает произвольный выбор, поскольку он в любом случае проигрышный. 1|2 — можно выбрать любое значение, оно будет выигрышным.
Предположим, что в этих случаях решение принимается равномерно-случайно.
Теперь строится сеть — рассчитываем вероятности нового выбора исходя из предыдущего вектора.
Здравствуйте, Кодт, Вы писали:
К>Как найти стационарное решение — затруднюсь сказать; теорвер не мой конёк. К>Как теперь перейти к более чем 3 игрокам... бум думать.
Я вижу у тя тоже не все просто.
Я рассуждал другим макаром:
Пусть есть оптимальная стратегия S(p1...pn+1).
Пусть все игроки пользуются этой стратегией.
Тогда можно составить целевую (n+1)- мерную функцию и пустить ее на максимум.
Так вот. Подумай пжалста:
Если есть стратегия S+(p1...pn+2),то сохранятся ли отношения между p1...pn+1?
Исходя из этого мне будет очень интересно узнать точное решение твоей системы для 3 игроков.
Здравствуйте, tinytjan, Вы писали:
T>Разработал оптимальную стратегию для двух игроков... T>Получилось, что число 3 надо выбирать чаще всего.
из чисел 1,2 и 3 применительно именно к двум игрокам число 3 является заведомо невыигрышным. ВСЕГДА! Если соперник выбрал 3, то это ничья, если 1 или 2, то соперник победил. Так что я бы сказал, что применительно к 2 игрокам, выигрышная стратегия это как раз выбирать 1. Либо ничья, либо гарантированый выигрыш.
Или я че-то в условиях не понял?
Затем среди названных чисел выбираются те, которые были названы только одним каким-либо игроком. Выигрывает игрок, написавший наименьшее из этих выбранных чисел, причем количество выигранных им очков равно написанному им числу.
Здравствуйте, Leshi, Вы писали:
L>из чисел 1,2 и 3 применительно именно к двум игрокам число 3 является заведомо невыигрышным. ВСЕГДА! Если соперник выбрал 3, то это ничья, если 1 или 2, то соперник победил. Так что я бы сказал, что применительно к 2 игрокам, выигрышная стратегия это как раз выбирать 1. Либо ничья, либо гарантированый выигрыш.
Мдя...
Натормозил -- неправильно сделал.
Буду думать дальше.
Здравствуйте, tinytjan, Вы писали:
T>Я вижу у тя тоже не все просто. T>Я рассуждал другим макаром: T>Пусть есть оптимальная стратегия S(p1...pn+1). T>Пусть все игроки пользуются этой стратегией. T>Тогда можно составить целевую (n+1)- мерную функцию и пустить ее на максимум.
T>Так вот. Подумай пжалста: T>Если есть стратегия S+(p1...pn+2),то сохранятся ли отношения между p1...pn+1?
T>Исходя из этого мне будет очень интересно узнать точное решение твоей системы для 3 игроков.
Фишка в том, что
1) Целевая функция не должна давать результат "туда не ходи, сюда ходи". Потому что иначе противник (зная мою ЦФ) обязательно сходит поперёк. Это распределение вероятности.
Скажем, для игры "камень-ножницы-бумага" ответом является равномерное распределение.
2) Я ищу стационарное решение, т.е. если у моих противников это распределение S, то оптимальным относительно него будет также S.
Здравствуйте, Кодт, Вы писали:
К>Фишка в том, что К>1) Целевая функция не должна давать результат "туда не ходи, сюда ходи". Потому что иначе противник (зная мою ЦФ) обязательно сходит поперёк. Это распределение вероятности. К>Скажем, для игры "камень-ножницы-бумага" ответом является равномерное распределение. К>2) Я ищу стационарное решение, т.е. если у моих противников это распределение S, то оптимальным относительно него будет также
угу. А теперь зайдём с другой стороны.
Зафиксируем набор игроков.
Пусть при этом все игроки работают по принципу распределения вероятности ходов. (т.е. они называют какое-то число случайно, в соответствии со своей функцией распределения вероятностей) Пусть характеристики всех соперников известны.
Вопрос: как надо играть, чтобы набрать при этом максимальное количество очков?
Ответ: С помощью несложного анализа распределений, можно для каждого числа расчитать вероятность того, что оно выиграет в очередной игре. Так вот, выбрав самое вероятное выигрышное число и называя всё время только его, мы очевидно наберём максимум очков. Любая другая стратегия приведёт к тому, что мы наберём очков не больше, чем в первом случае.
То есть при сделанных предположениях оптимальная стретегия всегда выводит одно и то же число.
Но, чтобы узнать какое именно число выводить, надо точно знать как устроены все соперники. А этой инфы обычно ни у кого нет.
Кроме того можно заметить, что даже оптимальная стратегия может не приводить к выигрышу. Рассмотрим пример:
1-ый игрок всегда говорит "1"
2-ой — всегда говорит "2"
все остальные всегда говорят числа большие 2.
В этом случае как бы вы ни ходили, вы не наберёте ни единого очка, а выиграет либо 1-ый, либо 2-ой.
Продолжая исследования:
Если вы играете оптимальной стратегией против n-1 игрока, и вдруг к вам подсаживают ещё одного какого-то игрока, то может случится так, что он играет всё время в то же число, что и вы. Тогда вы не наберёте ни одного очка.
А вот если бы вы играли в два самых выгодных числа случайно то в одно, то в другое (эта стратегия чуть хуже оптимальной), то вас не удалось бы "потопить" ни каким другим одним дополнительным игроком — максимум он бы отнял у вас половину ваших очков.
Дальше больше. Если играть в три самых выгодных числа, то одним дополнительным игроком у вас можно забрать максимум треть ваших очков, но ваша стратегия становится ещё чуть дальше от оптимальной
Ну и тд.
Короче, чем "шире" функция распределения вероятности ответов, тем программа стабильнее к добавлению новых игроков. А чем уже, тем она эфективнее, в том случае, если игроков не добавляется.
Под конец ещё раз замечу, что все эти рассуждения делаются на основе такого предположения, что все игроки устроены одинаково — они называют какое-то число случайно, в соответствии со своей функцией распределения вероятностей.
А так как в предлагаемом на http://eq.ur.ru турнире, программам-участницам известна история выигрышных чисел, то вероятно, игроки будут несколько более сложными, с динамически меняющимся поведением. Так что на самом деле все несколько сложнее и интереснее
Здравствуйте, Кодт, Вы писали:
К>2) Я ищу стационарное решение, т.е. если у моих противников это распределение S, то оптимальным относительно него будет также S.
Забыл добавить:
Ну и, в силу моего предыдущего поста, такого S не существует!
Здравствуйте, XopoSHiy, Вы писали:
К>>2) Я ищу стационарное решение, т.е. если у моих противников это распределение S, то оптимальным относительно него будет также S.
XSH>Забыл добавить: XSH>Ну и, в силу моего предыдущего поста, такого S не существует!
А вот это уже не так.
Представь себе игру камень-ножницы-бумага, в которой дают очки. За бумага-камень — по два очка, а за остальные — по одному.
Тогда загадывать бумагу выгоднее, чем ножницы. Но если упереться и загадывать только бумагу, то противник станет выигрывать, загадывая только ножницы.
Поэтому, сознательно внося элемент случайности в свои ходы, ты получаешь больше шансов.
Здравствуйте, XopoSHiy, Вы писали:
XSH>Ответ: С помощью несложного анализа распределений, можно для каждого числа расчитать вероятность того, что оно выиграет в очередной игре. Так вот, выбрав самое вероятное выигрышное число и называя всё время только его, мы очевидно наберём максимум очков. Любая другая стратегия приведёт к тому, что мы наберём очков не больше, чем в первом случае.
Не совсем, максимизировать нужно мат.ожидание выигрыша.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, XopoSHiy, Вы писали:
К>>>2) Я ищу стационарное решение, т.е. если у моих противников это распределение S, то оптимальным относительно него будет также S.
XSH>>Забыл добавить: XSH>>Ну и, в силу моего предыдущего поста, такого S не существует!
К>А вот это уже не так.
ошибку в моих рассуждениях в студию!
К>Представь себе игру камень-ножницы-бумага, в которой дают очки. За бумага-камень — по два очка, а за остальные — по одному. К>Тогда загадывать бумагу выгоднее, чем ножницы. Но если упереться и загадывать только бумагу, то противник станет выигрывать, загадывая только ножницы.
Аналогия неуместна. Камень-ножницы-бумага — это другая игра.
К>Поэтому, сознательно внося элемент случайности в свои ходы, ты получаешь больше шансов.
Это ты перефразировал мысль из моего предыдущего поста? Если так, то это надо делать аккуратнее:
'чем "шире" функция распределения вероятности ответов, тем программа стабильнее к добавлению новых игроков'
То есть в ситуации неопределённости, выгодно иметь маленько случайности.
Но если про твоих соперников всё известно (в точности описанная тобой ситуация: "...т.е. если у моих противников это распределение S..."), то выгодно всегда играть в "золотое" число
Здравствуйте, XopoSHiy, Вы писали:
XSH>Это ты перефразировал мысль из моего предыдущего поста? Если так, то это надо делать аккуратнее: XSH>'чем "шире" функция распределения вероятности ответов, тем программа стабильнее к добавлению новых игроков' XSH>То есть в ситуации неопределённости, выгодно иметь маленько случайности. XSH>Но если про твоих соперников всё известно (в точности описанная тобой ситуация: "...т.е. если у моих противников это распределение S..."), то выгодно всегда играть в "золотое" число
Невыгодно играть в золотое число. Потому что если найдётся ещё один такой же умник, как ты, то у вас двоих будет золотое число, и вы сольёте этот тур.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, XopoSHiy, Вы писали:
XSH>>Это ты перефразировал мысль из моего предыдущего поста? Если так, то это надо делать аккуратнее: XSH>>'чем "шире" функция распределения вероятности ответов, тем программа стабильнее к добавлению новых игроков' XSH>>То есть в ситуации неопределённости, выгодно иметь маленько случайности. XSH>>Но если про твоих соперников всё известно (в точности описанная тобой ситуация: "...т.е. если у моих противников это распределение S..."), то выгодно всегда играть в "золотое" число
К>Невыгодно играть в золотое число. Потому что если найдётся ещё один такой же умник, как ты, то у вас двоих будет золотое число, и вы сольёте этот тур.
Так.. если со второго раза не получается прочитать внимательно моё сообщение, советую насторожиться.
Прочитай ещё раз выделенное жирным!
Неоткуда умнику взяться!
Кроме того, можешь ещё раз перечитать мой первоначальный (длинный) пост. Там ты найдешь "свою" мысль про умника. Только в более подходящем контексте, нежели её применил ты.
Здравствуйте, XopoSHiy, Вы писали:
XSH>Неоткуда умнику взяться!
XSH>Кроме того, можешь ещё раз перечитать мой первоначальный (длинный) пост. Там ты найдешь "свою" мысль про умника. Только в более подходящем контексте, нежели её применил ты.
Разница в том, что ты исходишь из того, что противники не эквивалентны тебе (например, находятся в сговоре) — а я исхожу из полной симметрии.
Умник — это игрок, у которого стратегия такая же, как у меня. И если она детерминированная — то мы оба будем проигрывать раз за разом (заявляя одинаковые числа — ведь мы симметричны).
Для игрока выгоднее проиграть в некоторой доле случаев, нежели проиграть в 100%. Согласен?
Поэтому даже в дубовой ситуации (два игрока, два числа) есть смысл загадывать меньшее с вероятностью P и большее — (1-P). Тогда вероятность выигрыша равна W = P*(1-P) (я загадал меньшее, противник большее). Максимум при P=0.5, W=0.25.
Хотя тут тоже интересный момент: как оценивается ничья. Если, например, при ничье ставку забирает банк (и никаких джекпотов не предполагается) — то ничья это проигрыш. А если ставки возвращаются или идут в призовой фонд — то в золотые числа играть выгодно.
Здравствуйте, Кодт, Вы писали:
К>Хотя тут тоже интересный момент: как оценивается ничья. Если, например, при ничье ставку забирает банк (и никаких джекпотов не предполагается) — то ничья это проигрыш. А если ставки возвращаются или идут в призовой фонд — то в золотые числа играть выгодно.
Оффтопик:
В футболе за ничью дают 1 очко, а за победу — 3. Поэтому командам равной силы выгоднее сговориться и выиграть-проиграть (и заработать по 3 очка), чем дважды сыграть вничью (и заработать по 2).
Интересно, как на это смотрит ФИФА?
Здравствуйте, Кодт, Вы писали:
К>Разница в том, что ты исходишь из того, что противники не эквивалентны тебе (например, находятся в сговоре) — а я исхожу из полной симметрии.
К>Умник — это игрок, у которого стратегия такая же, как у меня. И если она детерминированная — то мы оба будем проигрывать раз за разом (заявляя одинаковые числа — ведь мы симметричны). К>Для игрока выгоднее проиграть в некоторой доле случаев, нежели проиграть в 100%. Согласен?
ещё разик по-порядку.
Задача 1 (вспомогательная): У нас есть n игроков, которые играют с одинаковым, известным распределением вероятностей.
Мы хотим придумать оптимального игрока который будет набирать максимум очков в такой компании.
Решение: Согласно моим рассуждением, оптимальный игрок будет всегда играть в золотое число — самое выгодное число.
Задача 2: У нас есть n игроков, которые играют с одинаковым распределением вероятностей S.
Мы хотим найти такое распределение S, что стратегия оптимального игрока будет тоже совпадать с S.
Решение: Согласно п.1 распределение любого оптимального игрока будет выглядеть тривиально — вероятность 100% у золотого числа, и 0% — у остальных. Значит и распределение S у всех n игроков такое же (по условию).
Сформулируем промежуточный факт: "если n>0 игроков играют c известным распределением S, и оптимальный против них игрок тоже играет с распределением S, то все они играют всегда в некоторое одно золотое число G".
Но при n>0 мы наберём вместе с ними по 0 баллов. Неужели оптимальная статегия такая плохая?
Если золотое число G=1, а n=1, то очевидно мы нашли искомое распределение S — всегда играть в золотое число 1.
Если n>1, то оптимальная стратегия будет такая: называть максимально-возможное число — всё равно оно всегда будет выигрывать. То есть оптимальная стратегия отличается от той, по которой играют первые n игроков. А значит, что при n>1 просто не существует искомого распределения S. Ну не существует его! Хоть убей — любые предположения, что оно существует приводит к описанному мной противоречию и всё тут!
Остался случай n=1 и G>1. То есть когда помимо вашего игрока есть ещё ровно один игрок и он всё время говорит некоторое число G>1. Тогда, очевидно, оптимальная стретегия — это говорить всегда число (G-1). Так что и в этом случае распределение S первого игрока не совпадает с оптимальным растределением при игре с ним. Хоть убей не совпадает! И ничего тут не поделать
Основной вывод: эта игра принципиально отличается от "камень-ножницы-бумага". Тут просто не муществует стратегии, любое отклонение от которой ухудшает результат. Исключением является случай 2х игроков, где один всегда называет 1. Тут как раз оптимальная стратегия для второго совпадает со стратегией первого. Но этот случай совершенно неинтересный и скучный
Перекуём баги на фичи!
