Здравствуйте, 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 круга. То есть как минимум баг организаторов никому не помешал, а значит можно считать результаты отражающими истиное положение дел Это особенно важно для меня любимого
Ну чтож поздравлям...
Встретимся в следующей игре...
Перекуём баги на фичи!
(все не проверял, но количество ходов во все числа у них делиться на 5)
Всего 2 столбика цыфр, где встречаються нули.
