Комментарии 30
Хороший обзор и с юмором.
+ Информация может быть не только ассиметричной, но и неполной, например, когда в настольной игре после очередного шага открывается следующая карта, вносящая новые данные или условия в игру...
+ Информация может быть не только ассиметричной, но и неполной, например, когда в настольной игре после очередного шага открывается следующая карта, вносящая новые данные или условия в игру.
А еще могут быть позиционные игры с неполной информацией. Например, преферанс, бридж. Когда все карты сданы на руки (т.е. создана какая-то позиция), но игрокам известны только карты своей руки (неполная информация о картах на руках соперников и партнеров).
Так что, даже в такой мелочи есть варианты.
Верно, эту часть я забыл
Ну, есть еще возможность всё исправить :)
А, вообще-то, в самом деле интересно и ненапряжно получилось. Обычно, популяризаторы ограничиваются рассмотрением матричных игр в чистых/смешанных стратегиях, совсем не упоминая про биматричные игры (мол, для них это уже слишком сложно). Тем более, не акцентируя внимание на повторяющихся играх (кстати, вся теория игра разработана именно для них, а про одиночные - только робкие упоминания).
Или, наоборот, рассматриваются какие-то узкоспецифические игры, но излишне подробно.
Во второй части можно как раз рассмотреть игры с полной/не полной информацией, игры с рациональным противником VS игры с природой. И смешанные игры - когда игроки действуют рационально, но в игру вмешивается безразличный Рок (случайность), подкидывая своих "черных лебедей".
А еще есть класс т.н. "игр с сгораемым накоплением". Правда, там больше математики, чем экономики. Суть их в том, что игрок выполняет серию рискованных действий. В случае удачи кэш увеличивается. В случае фиаско - сгорает и ход теряется. Игрок может прекратить серию и перевести кэш в несгораемый, либо рискнуть продолжить ее, рискуя всем кэшем. Вот эти игры никто толком не рассматривал. Только на уровне ликбеза.
В этой игре, очевидно, есть преимущество первого хода. Равновесие Нэша здесь - чтобы Боб согласился смотреть комедию. Но не все игры такие, и есть аспекты, которые могут сдвинуть равновесие. Например, если Боб достаточно дерзок (посмотрел Слово Пацана), чтобы заранее заявить, что он ни за что не будет смотреть комедию, тогда если Алиса рациональна, она выберет смотреть боевик (зная что Боб тогда присоединится).
Раннее заявление разве не является первым ходом?
Если вы хотите выглядеть умным и произвести впечатление на свою девушку — просто упомяните «игру с нулевой суммой» или «эволюционную стратегию», и ваши шансы отвести её домой сегодня вечером только что подскочили на 50%.
С оговоркой, что это еще работает для девушки
Однако оба они согласны смотреть документальные фильмы, хотя они им не так сильно нравятЬся.
Очепятка. (Не хочу показаться душным: хочу сделать хорошую статью чуть лучше)
Хороший разбор, спасибо!
Казалось бы, причём здесь сюрреалистичные числа.
Я за численное моделирование. Математический аппарат в простых случаях не нужен, ведь и так всё ясно, а в сложных случаях он показывает, что любое незначительное изменение легко переворачивает результат.
Численное моделирование (метод Монте-Карло) тоже не обладает достаточной эффективностью. И применяется, в основном, для исследования известных, наперед заданных параметров игры.
Если же нужен подбор этих параметров, то нужны другие методы. Например, для нахождения частот применения смешанных стратегий используют итерационный метод Робинсон-Брауна. Беда только, что он весьма медленно сходится. И применяется, опять-таки, для игр с полной информацией.
Если же надо делать то же самое для игр с неполной информацией, да еще не для жестко заданной позиции игрока, а для целого их класса (например, для различных мизерных рук в преферансе), то тут уже даже численные методы не помогают. Вернее, становятся ужасно громоздкими. Можно было бы использовать нейронные сети, но как совместить детерминированную задачу классификации выбора (одно из назначений ИНС) и вероятностную задачу нахождения смешанных стратегий в условиях участия Рока (природы, случая) - абсолютно не понимаю.
Создатели ИНС для игры в покер как-то решили эту проблему. Их программы умеют не только применять оптимальные чистые стратегии, но и блефовать с некоторой частотой (смешанные стратегии). Но как они обучили ИНС этому - загадка.
Обычно для игр с неполной информацией используют counterfactual regret minimization алгоритм. Для нейросетей придумывают эвристики для расчета мат. ожиданя, однако не видел статей о том что они сходятся к равновесию.Были какие-то попытки с reinforcement learning, выглядит более менее.
Почитал я про CFR-minimization ...
https://dspace.spbu.ru/bitstream/11701/40152/2/VKR_Tokareva.pdf
В принципе, это тоже алгоритм нахождения оптимальных смешанных стратегий, как и упомянутый мною итерационный метод Робинсон-Брауна. Только более эффективный и быстрее сходящийся.
Но как подружить любой из этих методов с нейросетью - вопрос остается открытым.
CFR позволит найти (рассчитать) оптимальные смешанные стратегии для конкретных заданных рук. А ИНС должна найти (пусть даже приближенно) эти оптимальные смешанные стратегии для любых рук, в т.ч. и для необсчитанных. Просто на основе опыта обучения игрой с самой собой.
Проблема CFR для того же покера в огромных рассчетах для первой улицы, и ограничение в 2 игрока. Если решать игру сначала, необсчитанных рук не будет. Кроме того алгоритм имеет свою погрешность, скорость сходимости итп.
Да на самом деле статьи с нейросетями несложно гуглятся по фразе " counterfactual regret minimization", например https://arxiv.org/pdf/1811.00164. Если добавить neural network, то еще 10 похожих найдете.
Если коротко, то из-за большого числа рассчетов, зачастую используют некие аппроксимации для замены вычислений мат. ожидания конкретной ветки или веток дерева принятия решений. В статьях предлагают заменить эти аппроксимации нейронными сетями, которые фактически обучают на решениях полученных CFR.
Не совсем понял что вы имели ввиду про конкретные заданные руки. Солвер считает всю игру с заданными условиями. Если например взять покер, то вы можете задать некоторые возможные варианты комбинаций двум игрокам и посчитать оптимальные смешанные стратегии с какого-то узла игры. Если считать с начала (очень долго и много ресурсов), то ничего задвать не нужно, солвер посчитает смешанные стратегии с начала игры. Примеры найти не очень сложно, например солвер для покера написанный на расте https://github.com/b-inary/wasm-postflop с гуи на васм (правда не с первой улицы).
Боюсь, что в покере я понимаю немногим больше, чем ничего. Мне ближе преферанс. Например, стратегии сноса и ловли на угадаечных мизерах.
Понимаю, что в данном случае понять будет трудно уже вам, но попытаюсь объяснить на пальцах.
Вот, допустим, у играющего мизер после прикупа до сноса такая рука:
♠: 7 8 9 10
♣: 7 8 9 10 J
♦: 8
♥: K A
Третья рука, торговли не было. Т.е. два других игрока в свою очередь заявок на игру не делали. Какие две карты отправить в снос, чтобы оставшуюся карту не "поймали"?
Интуитивно без расчетов понятно, что скидывать надо две червы. Т.к. вероятность получить взятку на бланковую бубновую восьмерку - крайне мала. А раз она не ловится в большинстве случаев, то "ловить" станут черву. А вот она ловится практически в 100%. Т.е. черву оставлять никак нельзя.
А теперь предположим, что в бубне не восьмерка, а десятка. Что сносить?
Теперь без расчетов не обойтись. И они показывают, что нужно применять смешанную стратегию примерно 50/50: в половине случаев нести две червы, а в половине - черву с бубной. Дело в том, что бланковая десятка "ловится" гораздо чаще. И если оставлять всегда её (а оппоненты про это знают), то чаще её и поймают.
А если применять смешанную стратегию, то оппоненты в половине случаев снос не угадают. А еще в ряде случаев десятка не может быть поймана, а мы ее и оставили. Т.е. профит от неизвестного сноса превысит профит от того, что десятка может не ловиться.
А если в бубне не восьмерка и не десятка, а девятка? А вот это уже сложно. Расчеты показывают, что тоже надо применять смешанную стратегию, но это не точно: Во-первых, преимущество смешанной стратегии в данном случае невелико. А, во-вторых, грубые расчеты не берут во внимание некоторые трудноучитываемые факторы: Не было торговли. А если и была, то прекратилась после нашей заявки "мизер". Слева сидит игрок осторожный, а справа - рисковый (или наоборот). У одного из них после нашей заявки задергалось ухо. И многое другое.
А если структура мастей другая - в черных мастях не 4:5 карт, а 3:6?
Т.е. абстрактные расчеты итерационными методами здесь ответа не дадут. Сложно и трудно всё учесть. А вот глубокое машинное обучение с имитацией игры против различных игроков - результат дать может.
Но оно должно не просто дать ответ, применять ли смешанные стратегии, но и их частоты. А вот на это ИНС, кажется, не способна.
Тут я набрел на статью по поводу ИНС Libratus, играющей в безлимитный холдем:
https://www.ijcai.org/proceedings/2017/0772.pdf
Оказывается, расчетом этих смешанных стратегий в ней тоже занималась не сама ИНС, а она только сводила воедино расчеты, выполняемые блоком Monte-Carlo CFR. Но как она это делала?
В этой игре, очевидно, есть преимущество первого хода. Равновесие Нэша здесь - чтобы Боб согласился смотреть комедию. Но не все игры такие, и есть аспекты, которые могут сдвинуть равновесие. Например, если Боб достаточно дерзок (посмотрел Слово Пацана), чтобы заранее заявить, что он ни за что не будет смотреть комедию, тогда если Алиса рациональна, она выберет смотреть боевик (зная что Боб тогда присоединится).
Может Алиса и рациональна, но будь она мудра, она бы выбрала комедийный боевик. И тогда в выигрыше были бы оба :) . Я к тому, что в реальности чистые версии всех этих задач практически никогда не встречаются. В той же дилемме заключенного нередко есть третий, который убьет стукача и оба заключенных это понимают. Именно поэтому (наверное) мы и не живем среди рациональных субьектов. Слишком сложно просчитать все.
Ну и конечно про эволюционную теорию игр и про доверие нельзя не упомянуть замечательный интерактивный сайт, который на примерах показывает критерии и выводы. Крайне рекомендую, меньше 30 минут на "прохождение":
https://notdotteam.github.io/trust/
Попробую сделать краткое резюмировать классификацию игр и кое-что добавить. (нашел свои старые записи - когда-то читал лекцию по теории игр школьникам в математическом лагере )))
Игры деляться на:
По наличию элемента случайности
Стратегические игры - в которых никогда не происходит случайных событий. Всё определяют только решения игроков. Благодаря отсутствию случайности, игры этого типа можно проанализировать и найти способ победить. В некоторых случаях можно полностью определить выигрышную стратегию, в других ввиду сложности игры это не удается, но можно показать, что подобная стратегия существует для одного из игроков.
Азартные игры - в которых присутствует элемент случайности (бросок кубика, поворот рулетки и т.п.) Но эти игры изучает не теория игр, а теория вероятности.
По порядку совершения ходов
Когда игроки ходят по очереди – игры с последовательными ходами
Когда игроки ходят одновременно – игры с параллельными ходами
По доступной игрокам информации
Когда перед совершением хода игроку известна вся инфоомация - игры с полной информацией
Когда перед совершением хода игроку НЕ известна вся инфоомация - игры с неполной информацией
По сумме выигрыша
Когда сумма выигрыша одного игрока в точности равна сумме проигрыша другого игрока – игры с нулевой суммой.
Когда сумма выигрыша\проигрыша обеих игроком не равна нулю – игры с ненулевой суммой. В этих играть могут быть ситуации когда оба игрока выигрывают или оба игрока проигрывают.
По возможности кооперации
Только соперничество игроков – НЕ кооперативные игры
Возможно сотрудничество игроков – кооперативные игры (два игрока в преферанс могут объединится против играющего или вистовать втемную). В кооперативных играх возникает проблема распределения совместного выигрыша между членами коалиции.
Если ходы определяются только решениями игроков, то можно проанализировав игру найти последовательность ходов, ведущую к выигрышу. Такая последовательность ходов называется выигрышной стратегией. Если в игре возможно ничья (как в шахматах) говорят о непроигышной стратегии.
Если выполняются условия:
1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.
2. Игроки совершают ходы поочередно.
3. В игре полностью отсутствует элемент неопределенности.
4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.
То всегда существует выигрышная стратегия для одного из игроков (хотя для сложных игр ее трудно рассчитать).
В 1930 году было доказано что для бесконечных игр не существует выигрышной стратегии ни для одного из игроков.
Спасибо, хорошее саммари
Чтобы игра считалась азартной, элемент случайности должен не просто существовать, а быть превалирующим. Т.е. его влияние должно сводить на "нет" всевозможные "выигрышные" стратегии.
Например, классический блэкджек со шлюхами с фиксированными ставками является азартной игрой. Потому что даже при оптимальном поведении играющего (т.н. "базовой стратегии") его выигрыш практически не отличается от нуля.
В то же время игра в нарды не является азартной, т.к. в ней элемент мастерства превалирует над случайностью. По крайней мере, в США суд так считает. У нас же, даже шахматы посчитают азартной игрой, если два пенсионера в парке сядут играть партию на деньги.
P.S. А как мы это забыли классификацию по сознательности противников?
Если противник действует осознанно и рационально, то это игра против рационального противника.
Если противник действует случайным образом, то это называется игрой с природой.
Но чаще бывает, когда часть противников действуют сознательно, но в игру вмешивается случайность. В таком случае даже вводят природу (Случай, Рок) как отдельного специфического игрока.
Или часть игроков действуют в ряде случаев не полностью рационально. Из-за отсутствия опыта или из-за авантюризма.
А есть какой-нибудь учебник или онлайн курс, который примерно на таком же уровне сложности с практическими примерами разбирает разные аспекты прикладной теории игр? Типа чтобы в свободное время почитать, например, в автобусе или при ожидании в очереди.
Достаточно много материалов, в которых много математики, продираться через которую нет ни желания, ни возможности
Выше скидывали https://notdotteam.github.io/trust/, действительно интересно
Поищите на YouTube видеолекции по ТИ Савватеева.
Я скачал даже все. Время от времени - просматриваю. Можно и в автобусе или в поликлинике с планшета смотреть.
Я не понял по поводу «Угадай 2/3 от среднего». Почему это должно быть 2/3 от максимального? Среднее это 50. Его 2/3 это примерно 26, что не так далеко от результата. Откуда же взялось 19 - угадывая случайные числа, людям свойственно самые большие на всякий случай не брать. Вот и всё.
"От среднего" имеется в виду не среднее от всех чисел от 0 до 100, а среднее, от названных всеми участниками.
Например, если четыре игрока назовут числа 0, 25, 50 и 75, то среднее будет 37,5. А 2/3 от среднего будет равно 25.
Таким образом, все захотят назвать 25. Но тогда 2/3 от среднего будет 16, (7) и выиграет тот, кто назовет не 25, а число поменьше.
Таким образом, называть нужно еше меньше ... и далее до нуля.
Раз уж статья с юмором, стоило бы упомянуть "Манчкин" и то что к нему никакие теории игр не применимы, поскольку вольная трактовка правил в затруднительных ситуациях -- часть самих правил и философии игры.
Теория игр за 15 минут