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. Тут как раз оптимальная стратегия для второго совпадает со стратегией первого. Но этот случай совершенно неинтересный и скучный
Здравствуйте, XopoSHiy, Вы писали:
XSH>ещё разик по-порядку.
XSH>Задача 1 (вспомогательная): У нас есть n игроков, которые играют с одинаковым, известным распределением вероятностей. XSH>Мы хотим придумать оптимального игрока который будет набирать максимум очков в такой компании. XSH>Решение: Согласно моим рассуждением, оптимальный игрок будет всегда играть в золотое число — самое выгодное число.
Причём здесь возникло противостояние: оптимальный игрок против всех остальных одинаковых игроков.
Ниже — попытка его снять...
XSH>Задача 2: У нас есть n игроков, которые играют с одинаковым распределением вероятностей S. XSH>Мы хотим найти такое распределение S, что стратегия оптимального игрока будет тоже совпадать с S.
XSH>Решение: Согласно п.1 распределение любого оптимального игрока будет выглядеть тривиально — вероятность 100% у золотого числа, и 0% — у остальных. Значит и распределение S у всех n игроков такое же (по условию).
Принципиальным условием выше было то, что остальные игроки "глупее" оптимального.
Иначе стратегия золотого числа не возникла бы никогда.
XSH>Сформулируем промежуточный факт: "если n>0 игроков играют c известным распределением S, и оптимальный против них игрок тоже играет с распределением S, то все они играют всегда в некоторое одно золотое число G".
XSH>Но при n>0 мы наберём вместе с ними по 0 баллов. Неужели оптимальная статегия такая плохая? XSH>Если золотое число G=1, а n=1, то очевидно мы нашли искомое распределение S — всегда играть в золотое число 1.
XSH>Если n>1, то оптимальная стратегия будет такая: называть максимально-возможное число — всё равно оно всегда будет выигрывать. То есть оптимальная стратегия отличается от той, по которой играют первые n игроков. А значит, что при n>1 просто не существует искомого распределения S. Ну не существует его! Хоть убей — любые предположения, что оно существует приводит к описанному мной противоречию и всё тут!
XSH>Остался случай n=1 и G>1. То есть когда помимо вашего игрока есть ещё ровно один игрок и он всё время говорит некоторое число G>1. Тогда, очевидно, оптимальная стретегия — это говорить всегда число (G-1). Так что и в этом случае распределение S первого игрока не совпадает с оптимальным растределением при игре с ним. Хоть убей не совпадает! И ничего тут не поделать
Давай покажу, что есть стратегия, более эффективная, чем золотое число.
Но сперва договоримся о цене. Пусть за выигрыш нам дают 1 очко, за ничью или проигрыш — 0.
Выберем два числа g1<g2 и будем выбирать первое из них с вероятностью p, второе — (1-p).
Вероятность выигрыша (когда все, кроме одного, ломанулись к одному числу) ненулевая — хоть и маленькая.
А уж оптимальна такая стратегия или нет — второй вопрос.
Факт тот, что золотое число — не оптимальная стратегия.
XSH>Основной вывод: эта игра принципиально отличается от "камень-ножницы-бумага". Тут просто не муществует стратегии, любое отклонение от которой ухудшает результат. Исключением является случай 2х игроков, где один всегда называет 1. Тут как раз оптимальная стратегия для второго совпадает со стратегией первого. Но этот случай совершенно неинтересный и скучный
Кстати, по ходу дела интересный момент нарисовался.
Есть несколько уровней рефлексии:
0) Золотое число: игрок всегда выбирает число, дающее максимальную вероятность выигрыша.
В случае полной симметрии игроков будут коллизии и ничья, в остальных случаях — неотрицательный баланс
1) Случайность первого порядка: игрок фиксирует наиболее удачное распределение вероятности и играет по нему.
Даже в случае полной симметрии будет неотрицательный баланс.
Посмотрим на мою стратегию "два золотых". При n>2 оказывается, что выигрышными являются два распределения: p=1/n и p=1-1/n.
По большому счёту, между ними нет предпочтений — но сработают они, если все игроки придерживаются одного и того же.
Отсюда
2) Случайность второго порядка: каждый игрок произвольно (по некоторому распределению) выбирает и фиксирует распределение вероятности и играет по нему.
Скажем, k игроков — играют с p=p1, остальные n-k — играют с p=p2. Можно найти оптимальные значения для p1,p2,k — так, что каждый игрок выбирает себе p1 с вероятностью k/n.
То есть, мы всё время исходим из симметрии — но раз за разом уточняем видение и улучшаем стратегию.
Наконец — для больших соревнований можно забить на гипотезы об уме противников. Среди них с некоторой (довольно высокой) вероятностью встретятся пофигисты (ставящие равномерно-случайно) и жадины (экспоненциально-убывающее распределение от меньших чисел к большим).
Распределение умника должно в первую очередь бороться против них, а между остальными умниками — надеяться на везение.
Здравствуйте, XopoSHiy, Вы писали:
XSH>Зафиксируем набор игроков. XSH>Пусть при этом все игроки работают по принципу распределения вероятности ходов. (т.е. они называют какое-то число случайно, в соответствии со своей функцией распределения вероятностей) Пусть характеристики всех соперников известны. XSH>Вопрос: как надо играть, чтобы набрать при этом максимальное количество очков?
XSH>Ответ: С помощью несложного анализа распределений, можно для каждого числа расчитать вероятность того, что оно выиграет в очередной игре. Так вот, выбрав самое вероятное выигрышное число и называя всё время только его, мы очевидно наберём максимум очков. Любая другая стратегия приведёт к тому, что мы наберём очков не больше, чем в первом случае.
XSH>То есть при сделанных предположениях оптимальная стретегия всегда выводит одно и то же число.
Пусть мы играем против двух игроков 1-ый из которых всегда выбирает "1", а 2-ой — "2".
В этом случае любой выбор приносит нам 0 очков, то есть оптимальной в указанном смысле стретегии не существует.
Единсвенное, что можно попытаться сделать — минимизировать выигрыш других игроков. Но тогда оптимальной будет смешанная стратегия "1" надо выбирать в два раза реже чем "2".
Здравствуйте, o.kostya, Вы писали:
К>>Но сперва договоримся о цене. К>>Пусть за выигрыш нам дают 1 очко, за ничью или проигрыш — 0.
OK>Вы еще первоначальную задачу решаете? Там за выиграш даеться столько очков, какое названо число...
Ой.
Ну и ладно Тогда мат.ожидание выигрыша будет M = g1*p*(1-p)^(n-1) + g2*(1-p)*p^(n-1).
Всё равно нечто, отличное от нуля
Здравствуйте, Трурль, Вы писали:
Т>Пусть мы играем против двух игроков 1-ый из которых всегда выбирает "1", а 2-ой — "2". Т>В этом случае любой выбор приносит нам 0 очков, то есть оптимальной в указанном смысле стретегии не существует. Т>Единсвенное, что можно попытаться сделать — минимизировать выигрыш других игроков. Но тогда оптимальной будет смешанная стратегия "1" надо выбирать в два раза реже чем "2".
Вообще, вопросы сговора — это очень интересная тема.
Например, как с футболом: поскольку "платы за вход" нет, то игроки могут сговориться против банка — максимизировать суммарный выигрыш и поделить между собой.
В этом случае стратегия проста до безобразия: один игрок загадывает наибольшее число, а остальные как попало, но с повторениями. И так N раз
Если плата за вход постоянная — то стратегия та же самая (из любой игры вычитается константа).
Если игра с нулевой суммой или отрицательной суммой — то сговор против банка невозможен, проще не играть.
Здравствуйте, XopoSHiy, Вы писали:
XSH>Не потрудитесь отослать свое решение. Чем больше игроков, тем интереснее будут результаты!
Интересное решение сделали организаторы во втором турнире. Они вместо последовательных 10к туров запустили 5 партий по 2к туров. Но!!! Они забыли исправить свой алгоритм и во всех турах кроме первого алгоритмы получали на вход данные победивших чисел первого тура !!!. Ярким примером данного служит алгоритм kirill, который ходит в победившее число или в 1, если ничья.
Данный момент дал возможность исследовать был ли в алгоритмах датчик случайных чисел Только 3 алгоритма таким обладали, а остальные 9 работали как часы, т.е. повторили в 2-5 партиях все свои ходы (все не проверял, но количество ходов во все числа у них делиться на 5)
Интересно выгладит статистика выиграшных чисел. Хоть 9 алгоритмов ходили в те же числа повторно, выигрывали те же числа в 70% случаев
Повторы по сравнению с первым туром (макс 2000)
5-й 1360
4-й 1364
3-й 1371
2-й 1372
Случайный алгоритм пробившийся выше всего — это albor tholus 3-е место. Его статистика совпадений по ходам
По сравнению с первым туром (макс 2000)
5-й 522
4-й 526
3-й 547
2-й 570
Интересна также статистика набора очков если сравнить сколько алгоритмы набрали за первую 1000 игр и за вторую:
Болдом выделены алгоритмы набравшие в первой 1000 игр почти все свои очки и что самое интересное они имеют в свое алгоритме элемент случайности. И вот тут возникает вопрос: а правильно ли был сделан переход от 10к партии к 5-ти партия по 2к игр?
Здравствуйте, o.kostya, Вы писали:
OK>Здравствуйте, XopoSHiy, Вы писали:
XSH>>Не потрудитесь отослать свое решение. Чем больше игроков, тем интереснее будут результаты!
OK>Интересное решение сделали организаторы во втором турнире. Они вместо последовательных 10к туров запустили 5 партий по 2к туров.
Слушай, раз уж ты неполенился потратить полчаса своего времени на написание этого поста, то может быть имеет смысл потратить чуть больше времени и оформить это в небольшую статью для eq.ur.ru, чтобы твои труды не потерялись в истории rsdn-а?
За одно получится мини-разбор очередного турнира. Если сделать его оценки по тем же метрикам, что и я в предыдущиё раз, то можно будет даже сравнить резальтаты
Я думаю основатели лаборатории Эквивалент будут очень рады такой инициативе
Забавно, что первые три места не поменялись за оставшиеся 4 круга. То есть как минимум баг организаторов никому не помешал, а значит можно считать результаты отражающими истиное положение дел Это особенно важно для меня любимого
Это, видимо, из-за поголовного отсутствия случайности. А это в свою очередь, отчасти, из-за хитрых правил игры, имхо.
Здравствуйте, XopoSHiy, Вы писали:
XSH>мдя? странно... посмотрим что будет в эту субботу.
у меня будет тот же алгоритм — в этот раз будет вторым с конца, если конечно набереться 10 программ
XSH>А откуда, кстати, информация о стратегии kirill? Догадка, сделанная глядя на лог, или информация от автора программы?
по логу, уж очень бросаеться в глаза
... << RSDN@Home 1.1.3 stable >>
Re[4]: 2000 vs 100000
От:
Аноним
Дата:
17.06.05 17:33
Оценка:
Здравствуйте, o.kostya, Вы писали:
XSH>>Я думаю основатели лаборатории Эквивалент будут очень рады такой инициативе
OK>Они даже не признают, что у них был баг. То уводят разговор в русло безопастности, то непонятности алгоритма ...
Признаем. Правда, недостаточно оперативно. Причем недостаточность оперативности — это тоже баг, И мы это тожн признаем.
Между прочим, мы не в состоянии читать все форумы, поэтому об этом обсуждении я узнал от Xoposhiy — спасибо ему. Это я к тому, что лучше все-таки общаться напрямую с нами (учитывая, правда, что мы, увы, не ежедневно читаем почту — такая уж у нас летом специфика).
А найти ошибку помогло именно Ваше описание ситуации. То которое Вы поместили здесь. А искать ошибки путем разбора чужих программ — дело действительно трудоемкое.
В любои случае большое спасибо. Турнир переигран, Новая таблица и новый лог — на сайте eq.ur.ru в разделе Игры, подраздел Архив турниров по игре жребий Крижановского.
Если и там что не так — будем по прежнему очень благодарны за анализ ситуации.
Здравствуйте, Аноним, Вы писали:
А> Турнир переигран, Новая таблица и новый лог — на сайте eq.ur.ru в разделе Игры, подраздел Архив турниров по игре жребий Крижановского.
Прикольно. Лидеры не сменились, но mckey из 8-го места первый тур уже сыграл третьим и таким остался до конца турнира.
OK>у меня будет тот же алгоритм — в этот раз будет вторым с конца, если конечно набереться 10 программ
Получилось Хотя начиная с 2-го и по 5-й тур уже и не верилось. Но в 5-м туре у кого-то произошел интересный сбой в алгоритме, который позволил мне занять законное 2-е место с конца и определило судьбу 2-5 места. На 2-е вышел mckey обогнав xoposhiy, а на 4-е genda обогнав julia. Когда bay набирал 0 очков, как и мой алгоритм, mckey и xoposhiy набирали практически поровну очков на протяжении 8000 игр, а вот когда bay и мой что-то зарабатывали, то mckey удалось вырваться вперед. Ща буду логи смотреть
Здравствуйте, o.kostya, Вы писали:
OK>Получилось Хотя начиная с 2-го и по 5-й тур уже и не верилось.
Поздравляю! Очень уж это нетривиально прогнозировать себе предпоследнее место. Это вам не последнее. И даже не первое
Забавно всё прошло. Первые 4 круга я был вторым, а на последнем, сильно отстав, стал 3-им. Со стороны это выглядело, как будто прога выдохлась. Истинная же причина — заниженная самооценка: на 2-ке тоже нормально очков зарабатывалось, поэтому моя прога на тройку и смотреть не стала. А ведь в предыдущих кругах почти сразу двойку откидывала... странно. Тоже жду не дождусь логов -- не выкладывают чего-то...
Здравствуйте, XopoSHiy, Вы писали:
XSH> Истинная же причина — заниженная самооценка: на 2-ке тоже нормально очков зарабатывалось, поэтому моя прога на тройку и смотреть не стала. А ведь в предыдущих кругах почти сразу двойку откидывала... странно.
А откуда у тебя инфа куда твоя прога ходила? У меня возникло подозрение, что меня bay глушил (или я его). Причем это наше взаимоглушение как-то очень влияло на кол-во набранных тобой и mckey балов, т.к. отрыв был 10 очек почти на протяжении 6000 игр.
В общем жду логов, а то все очень запутано
Здравствуйте, o.kostya, Вы писали:
OK>А откуда у тебя инфа куда твоя прога ходила?
Гм... Ну... её же я писал
Я примерно знаю как она ходить должна. Ну и во время турнира делимость зарабатываемых очков за последние 50 ходов анализировал.
Про логи. Похоже сейчас там находятся пары чисел (выигравшее_число, номер_игрока). (0, 0) означает, что никто не выиграл.
Написал организаторам вопрос на тему нового формата лога, жду ответа.
Здравствуйте, XopoSHiy, Вы писали: XSH>Забавно, что первые три места не поменялись за оставшиеся 4 круга. То есть как минимум баг организаторов никому не помешал, а значит можно считать результаты отражающими истиное положение дел Это особенно важно для меня любимого
Ну чтож поздравлям...
Встретимся в следующей игре...
Здравствуйте, o.kostya, Вы писали: OK>Выложили. Жаль что kirill своим предыдущим алгоритмом не участвовал, а то получилась бы интересная ситуация, а не борьба стояков...
Кстати Kirill это мой брательник младший...
Программирует неважно...
Я с его разрешения могу сказать что в первый раз алготим у него был простой как 2 копейки
если никто не выиграл или первый ход то Ход = Случайное число в нижней трети участников
иначе повторить ход выигрывшего...
А вот по поводу участия в июньском турнире он на организаторов обиделся... не приняли почему-то его программу...
хотя она была еще проще..
program Kirill_2;
{$APPTYPE CONSOLE}uses
SysUtils;
Type
arr = array [1..2000] 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 := Round(n/3 + Random(Round(n/3)));
Write(move);
end.
Здравствуйте, Mckey, Вы писали:
M>Здравствуйте, o.kostya, Вы писали: OK>>Выложили. Жаль что kirill своим предыдущим алгоритмом не участвовал, а то получилась бы интересная ситуация, а не борьба стояков... M>Кстати Kirill это мой брательник младший... M>Программирует неважно...
M>Я с его разрешения могу сказать что в первый раз алготим у него был простой как 2 копейки M>если никто не выиграл или первый ход то Ход = Случайное число в нижней трети участников M>иначе повторить ход выигрывшего...
M>А вот по поводу участия в июньском турнире он на организаторов обиделся... не приняли почему-то его программу... M>хотя она была еще проще..
К сожалению, эта программа в некоторых случаях выдает результат вне разрешенного диапазона. И, кстати, ее текст несколько отличается от того текста, который сейчас опубликовали Вы.
В таких случаях мы обычно отправляем программу на автору на доработку. Вообще-то у нас далеко не все участники — суперпрограммисты (и нас это радует!), так что такая процедура для нас — обычное дело. Но к сожалению письмо, которое мы отправили по тому адресу, которое он указал при регистрации, пришло с диагностикой "адрес не найден".
А допустить в турнир программу, нарушающую правила, мы не можем — это вызовет очевидное и справедливое недовольство со стороны других игроков.
Я рекомендую ему написать нам на адрес eq@mail.ur.ru, указав в письме регистрационное имя и пароль и сообщить нам правильный адрес для связи — тогда в будущем проблемы не возникнут.
А вообще-то я все время поражаюсь — при возникновении проблем пишут куда угодно (этот форум — отнюдь не единственное такое место), но только не к нам. Почему бы?
Здравствуйте, <Аноним>, Вы писали:
А>А вообще-то я все время поражаюсь — при возникновении проблем пишут куда угодно (этот форум — отнюдь не единственное такое место), но только не к нам. Почему бы?
Здравствуйте, XopoSHiy, Вы писали:
XSH>Здравствуйте, o.kostya, Вы писали:
XSH>>>Но учтите-с! Я намерен её выиграть OK>>выиграть у McKey или занять 1-е место?
XSH>1-ое место, очевидно
Здравствуйте, Аноним, Вы писали:
M>>А вот по поводу участия в июньском турнире он на организаторов обиделся... не приняли почему-то его программу... M>>хотя она была еще проще..
А>К сожалению, эта программа в некоторых случаях выдает результат вне разрешенного диапазона. И, кстати, ее текст несколько отличается от того текста, который сейчас опубликовали Вы.
А>В таких случаях мы обычно отправляем программу на автору на доработку. Вообще-то у нас далеко не все участники — суперпрограммисты (и нас это радует!), так что такая процедура для нас — обычное дело. Но к сожалению письмо, которое мы отправили по тому адресу, которое он указал при регистрации, пришло с диагностикой "адрес не найден".
А>А допустить в турнир программу, нарушающую правила, мы не можем — это вызовет очевидное и справедливое недовольство со стороны других игроков.
А>А вообще-то я все время поражаюсь — при возникновении проблем пишут куда угодно (этот форум — отнюдь не единственное такое место), но только не к нам. Почему бы?
А>Филимоненков Д.О. А>Лаборатория "Эквивалент"
Такссс... с братом разобрались...
отправил один раз программу... исправил... второй... исправил... отправить забыл...
Подзатыльник получил...
и за то что не отправил.. и за то что то что отправил не проверил на правильную работу.
Дааа... и на счет формума... Форума-то у вас и вправду нет... жаль...
Делай добро и бросай его в воду...
Re[14]: 2000 vs 100000
От:
Аноним
Дата:
27.06.05 14:02
Оценка:
Здравствуйте, Mckey, Вы писали:
M>Такссс... с братом разобрались...
Адрес-то его почтовый сообщите! На будущее. Письмом на eq@mail.ur.ru
В письме укажите логин, пароль, и адрес, который следует считать правильным
M>Дааа... и на счет формума... Форума-то у вас и вправду нет... жаль...
Может жаль, а может нет. Но все в наших руках... Пока у игроков все равно каникулы, а к осени посмотрим
Перекуём баги на фичи!
(все не проверял, но количество ходов во все числа у них делиться на 5)
Всего 2 столбика цыфр, где встречаються нули.
