Eriright

Eriright

Сумасшедший математик из подпарижья. Пишу книги, двигаю науку, тискаю котика
Пикабушница
Дата рождения: 08 октября 1989
поставилa 4 плюса и 3 минуса
отредактировалa 0 постов
проголосовалa за 0 редактирований
Награды:
За неравнодушие к судьбе Пикабу
1418 рейтинг 112 подписчиков 6 подписок 39 постов 14 в горячем

Объединяю по-мелочи две волны

Объединяю по-мелочи две волны Математика, Волна постов, Работа, Селфи, Фото с работы, Пикабушники, Мобильная фотография

Это я на одной из работ, специалист по исследованию операций в RATP, это одна из двух крупнуйших компаний общественного транспорта во Франции. На этой работе я занимаюсь разными вида оптимизациями, но в большую сторону алгоритмическими :например, поисками кратчайших путей, типа как делают те же гуглокарты, но с добавлением всяких фич типа навигации по станции или с учетом предпочтений пользователей. Ну и разумеется приходится программировать, в прод в основном все идет на c++, но еще есть питон и раст.

А так по жизни я еще репетитор по математике внешкольного уровня (самое школьное, это программа IB, но обычно готовлю детей к национальным или международным олимпиадам по математике), писатель (книги по олимпиадной математике и научпоп немного), ну и иногда беру какие-то другие проекты, вроде руководства отделением математики в олимпиадных школах, методической работы, составления всяких олимпиад и т д.

Выгляжу сегодня как зомби, но понедельник день тяжелый )

Показать полностью 1

Мы тоже бунтуем ! Кусь !

Мы тоже бунтуем ! Кусь ! Кот, Бунт, Кусь, Абиссинская кошка, Лапки
Показать полностью 1

Лапки-Антистресс

Лапки-Антистресс Кот, Абиссинская кошка, Антистресс, Компьютер, Милота, Лапки
Показать полностью 1

Кажется, мой обеденный перерыв продлится…

Кажется, мой обеденный перерыв продлится… Абиссинская кошка, Кот, Компьютер, Мобильная фотография
Показать полностью 1

Кот-ревью

Кот-ревью Абиссинская кошка, Кот, Программирование, IT юмор, Длиннопост
Кот-ревью Абиссинская кошка, Кот, Программирование, IT юмор, Длиннопост
Показать полностью 2

Последовательные игры- продолжение

Продолжим вопрос о свидании Мата Хари и Мюнхаузена, начатый в предудущем посте из серии.

При внимательном рассмотрении становится ясным, что рассмотренная в игре угроза на самом деле угрозой не является. Ведь очевидно, что как только Мюнхаузен сделает свой выбор, возможными выигрышами Мата Хари могут быть либо 0, либо 1, так что пусть уж это будет 1.

Последовательные игры- продолжение Научпоп, Математика, Книги, Стратегия, Популяризация, Наука, Теория игр, Выбор


Проблема Мата Хари в том, что после того, как Мюнхаузен делает свой выбор, он ожидает рационального поступка от неё. Она могла бы себя связать обязательством съесть суши даже в том случае, если бы Мюнхаузен привёл её в кошерный ресторан, возможно, это могло бы улучшить её настроение.

Связать себя таким обязательством можно, например, позволив кому-нибудь другому сделать за себя. Мата Хари, например, могла бы нанять кузнеца и поручить ему заставить её есть суши в данном случае. Однако, с точки зрения Мюнхаузен, ситуация в этом случае решительно меняется.

Если он знает о договорённости Мата Хари с кузнецом, то он понимает, что если он приведёт Мата Хари не в японское кафе, его вечер будет безнадёжно испорчен. Поэтому для него разумнее пойти на поводу у девушки. В данном случае женский ультиматум помог повысить настроение Мата Хари.

Как вообще назвать равновесие, возникающее в данной игре?

Стратегии и равновесия в этом типе игр изучал барон Генрих фон Штакельберг (1905-1946), немецкий экономист. Конкуренция по Штакельбергу — это модель дуополии. Дуополия Штакельберга асимметрична, то есть две конкурирующие фирмы не обладают одинаковой властью. Мы говорим о фирме-лидере (или фирме-пилоте) и фирме-сателлите, ведомой фирме. Здесь пилот - барон Мюнхгаузен.

Равновесие в этой и ей подобных играх называется равновесием Штакельберга. В таких играх имеется лидер, игрок, который делает первый ход. Лидер может определить стратегии, определяющиеся равновесием Нэша, после каждого из своих ходов. Мы полагаем при вычислении данного равновесия, что ведомый рационален и выбирает стратегии согласно прогноза лидера.

Например, в рассмотренной игре, равновесием Штакельберга является шаурма из кошерного ресторана.

Показать полностью 1

Последовательные игры

До этого мы обсуждали только игры, в которых игроки совершают выбор одновременно. Но есть и другие варианты.

Мало того, такие варианты встречаются достаточно часто.

Рассмотрим следующую игру. Пусть барон Мюнхаузен и Мата Хари собрались на свидание в ресторане, в котором из соображений экономии разделят на двоих одно блюдо. В этой игре функцией полезности каждого игрока будет оценка удовольствия, которое он получил во время этой встречи (как удовольствие от общения с кем-то, так и от выбора ресторана или даже от выбора блюда).

Последовательные игры Математика, Книги, Выбор, Популяризация, Научпоп, Теория игр, Стратегия, Длиннопост

Для того, чтобы никто не обиделся, вначале Мюнхаузен выбирает одно из двух кафе, а потом Мата Хари выбирает одно из двух блюд в нём (блюда в кафе одинаковы, но готовят их по-разному).

Каждая пара исхода принесёт разные выигрыши, выигрышем в данной игре будет полученное удовольствие от поглощения пищи. Так как эти персонажи слишком различны, в своём выборе они руководствуются исключительно эгоистичными соображениями.

Попробуем описать данную игру в стратегической форме.

Последовательные игры Математика, Книги, Выбор, Популяризация, Научпоп, Теория игр, Стратегия, Длиннопост

Заметим, что когда игра представлена в указанной форме, то мы видим два равновесия по Нэшу (суши в японском кафе или шаурма в кошерном ресторане). На самом деле это не так. Проблема заключается в том, что игроки выбирают стратегии последовательно друг за другом, то есть, второй игрок уже знает, какую стратегию выбрал первый. Матрица платежей в привычной форме не даёт об этом представления.

Асимметричность данной игры лучше проявляется не в виде матрицы платежей, а в виде дерева выбора, экстенсивной форме. Решения в этой форме могут быть представлены этим деревом, каждый узел которого связан с игроком, который принимает решение. Каждый вариант представляет собой ветвь. Выигрыши всех игроков связаны с терминальными вершинами или листьями дерева.

Первым делом барон Мюнхаузен должен выбрать между японскими и кошерными ресторанами, а затем Мата Хари должна выбрать, что она возьмёт — суши или шаурму. Но Мата Хари, делая свой выбор, уже знает, в какой ресторан привёл её барон Мюнхаузен на свидание.

Последовательные игры Математика, Книги, Выбор, Популяризация, Научпоп, Теория игр, Стратегия, Длиннопост

Проведём анализ игры, рассмотрев ходы в обратном порядке. Если Мюнхаузен уже сделал свой первый ход и выбрал японское кафе, то, вне зависимости от хода Мата Хари, выигрыш будет составлять (1 ; 9). Если Мюнхаузен выбрал своим первым ходом кошерный ресторан, то ходы Мата Хари уже неравнозначны и для достижения наилучшего результата ей стоит выбрать шаурму, после чего выигрыш будет составлять  (2 ; 1).

Что же выбрать Мюнхгаузену? При выборе японского кафе, результатом игры будет (1 ; 9) и он получит выигрыш, равный 1. Если он выберет кошерный ресторан, то его выигрыш будет равен 2. Это и будет наиболее разумным для него выбором. Это значит, что равновесный выбор — шаурма из кошерного ресторана, что ведёт к выигрышу для Мюнхгаузена в 2 очка, а для Мата Хари –  в 1.

Второе из вроде как равновесий, которое было получено с помощью таблицы, точно не является равновесием, имеющим смысл в данной игре. Очевидно, что в случае выбора Мюнхгаузеном японского кафе, Мата Хари могла выбрать суши, но выбор данной столовой Мюнхаузеном был бы не самым умным поступком.

С точки зрения Мата Хари, свидание складывается не самым удачным образом – она могла бы получить выигрыш в 9 очков удовольствия, а получит всего-навсего 1. Что она может сделать в такой ситуации?

Например, она может угрожать Мюнхаузену, что они всё равно будут есть суши, даже если пойдут в кошерный ресторан. Если Мюнхаузен верит в женские угрозы, то это имеет смысл. В таком случае, японское кафе ему принесёт один балл удовольствия, тогда как суши из кошерного ресторана он вообще не захочет есть и получит 0 очков.

Но является ли эта угроза реальной?

Показать полностью 3

Полковник Блотто и китайские палочки


Аукцион китайских палочек (палочек для еды) происходит, когда в игру пускаются три китайские палочки, у этих аукционов очень специфические и очень строгие правила. У каждого игрока ровно одинаковая сумма. Есть только один раунд, и аукционы секретные, поэтому никто не знает, что предлагают другие. За этот единственный ход каждый из игроков обязан предложить ставку (возможно, нулевую) на каждую из трёх палочек (различимых). Каждый игрок хочет выиграть как минимум две палочки из трех. Действительно, есть только одной палочкой не очень-то и удобно!

Равновесия Нэша для аукциона китайских палочек всегда описываются смешанными стратегиями, но форма этих равновесий просто завораживает. Известное равновесие для трех палочек гласит, что одно из равновесий описывается стратегией, задаваемой равномерным распределением на поверхности тетраэдра в пространстве ставок на три палочки. Недавно было найдено другое равновесие (опять же для трех палочек), которое берет тот же тетраэдр и превращает его во фрактал в духе треугольника Серпинского. Равновесная стратегия в этом случае предполагает равномерное распределение ставок на поверхности этого фрактала.

Чем-то похожим на этот аукцион является игра «Полковник Блотто». Это тип игры с нулевой суммой для двух человек, в которой перед игроками стоит задача одновременно распределить ограниченные ресурсы между несколькими объектами (или полями сражений). В классической версии данной игры игрок, потративший больше всего ресурсов на какую-то битву, её выигрывает, а выигрыш игрока равен общему количеству выигранных полей боя.

Игра была предложена в 1921 году как пример игры, в которой «имеет значение психология игрока». Она изучалась после Второй мировой войны специалистами по исследованиям операций и стала классикой теории игр.

Название игры заимствовано у вымышленного полковника. Его задача — найти оптимальное распределение своих солдат на N полях сражений, зная, что:

  • на каждом поле боя побеждает та сторона, которая выделяет больше солдат, но

  • ни одна из сторон не знает, сколько солдат противоборствующая сторона отправит на каждое поле боя, и:

  • обе стороны стремятся максимизировать количество полей сражений, которые они рассчитывают выиграть.

Давайте представим себе игру, основанную как на китайском аукционе палочек, так и на игре «Полковник Блотто».


В игру «Голодный полковник» играют 2 игрока. Каждый из них может написать 3 числа, но не в порядке убывания. Сумма чисел должна быть 6. Выигрывает игрок, чьи 2 числовые позиции превышают 2 позиции противника.

У каждого игрока есть 3 варианта (игра симметричная) ходов, в том числе (2; 2; 2), (1; 2; 3) и (1; 1; 4). (1; 1; 4) против (1; 2; 3) приводит к ничье, (1; 2; 3) против (2; 2; 2) приводит к ничье, (2; 2; 2) выигрывает (1 ; 1; 4). Итак, (2; 2; 2) — оптимальная стратегия.


Рассмотрите другой вариант аналогичной игры для двух игроков и сыграйте в нее с друзьями:

  • Игровое поле представляет собой доску 3 на 3.

  • У каждого игрока есть армия из 100 маленьких Ктулху.

  • Перед ночным боем каждый игрок тайно размещает свои отряды на 9 клетках. На каждую клетку можно поставить любое целое число Ктулху от 0 до 100.

  • Утром начинается битва новую планету. На каждой из 9 клеток побеждает игрок, у которого больше всего Ктулху на этой клетке. За победу на каждом из 9 квадратов дается 1 очко. Если на какой-то клетке числа соперников были одинаковыми, то бой на этой клетке заканчивается вничью и оба игрока получают по 0,5 очка.

  • Битву выигрывает тот, кто выиграл больше всего полей. Если оба игрока получают по 4,5 очка, битва заканчивается вничью.

Полковник Блотто и китайские палочки Математика, Стратегия, Популяризация, Научпоп, Теория игр, Книги, Длиннопост

Эта игра (разумеется, немного в другой формулировке) проходила в качестве конкурса в 2019 году на сайте Михаила Павкухина. Наилучший результат получил игрок, разместивший Ктулхят согласно следующей таблице: :

Полковник Блотто и китайские палочки Математика, Стратегия, Популяризация, Научпоп, Теория игр, Книги, Длиннопост


Этот игрок обыграл 4121 соперника, проиграл 1011 и сыграл вничью с 216.

Показать полностью 2

Олени и буйволы

Робинзон Крузо и Пятница — охотники на зайчиков каменного века. Однажды вечером, когда они вместе выпивали, между ними завязался разговор о делах. Обменявшись мнениями, они поняли, что, объединив свои усилия, они могут замахнуться на гораздо более крупное животное, например, на оленя или буйвола. Тот, кто охотится в одиночку, не может рассчитывать на то, что сможет убить такого гиганта. Но если бы охотники объединились, каждый день охоты на оленя или буйвола давал бы в шесть раз больше мяса, чем день охоты только на зайчиков. Такое сотрудничество имеет большие преимущества: каждый охотник будет получать в три раза больше мяса от охоты на крупную дичь, чем от охоты на зайца.

Робинзон Крузо и Пятница договорились на следующий день поохотиться на крупную дичь, и каждый вернулся в свою пещеру. К сожалению, накануне они слишком много выпили и оба забыли, на какое животное они должны были охотиться, на оленя или буйвола. Охотничьи угодья для этих животных находятся в противоположных направлениях. Тогда не было сотовых телефонов, и все это было до того, как Робинзон Крузо и Пятница стали соседями. Поэтому они не могли просто вначале встретиться, а потом пойти охотиться. На следующее утро каждый должен был принять собственное решение.


Для того, чтобы решить, куда идти, обоим охотникам придется сыграть в игру с одновременными выбором их стратегий. Если обозначить количество мяса, которое каждый получает в день при охоте на зайчиков (выбранная единица), то доля каждого в случае удачной координации усилий по охоте на оленя или буйвола составит три единицы. Таким образом, платёжная матрица для этой игры выглядит следующим образом:

Олени и буйволы Математика, Книги, Популяризация, Научпоп, Теория игр, Джон Нэш


Эта игра сильно отличается от рассмотренной ранее дилеммы заключенного. Разберем самое главное отличие.

Лучший выбор для Робинзона Крузо зависит от того, что делает Пятница, и наоборот. Не существует оптимальной стратегии ни для одного из игроков, независимо от действий другого. В отличие от дилеммы заключенных, в этой игре нет доминирующей стратегии. Поэтому каждый игрок должен анализировать возможный выбор другого и с учетом этого искать свою оптимальную стратегию.

Робинзон Крузо размышляет подобным образом: «Если Пятница пойдет туда, где пасутся олени, то я получу большую долю добычи, если пойду туда, с другой стороны, я ничего не получу, если пойду на пастбище буйволов. Если Пятница отправится на землю бизонов, должно быть наоборот. Вместо того, чтобы пойти на риск и отправиться в одну из этих областей и обнаружить, что Пятница ушёл в другую, не лучше ли мне самому пойти и поохотиться на зайчиков, как я делал всегда, даже если это приносит мне меньше мяса? Другими словами, не должен ли я взять единицу лута наверняка, вместо того, чтобы рисковать получить три единицы или ничего? Это зависит от того, что, по моему мнению, собирается сделать Пятница, поэтому я должен поставить себя на его место и подумать о том, что он думает. Но он также задается вопросом, что я собираюсь делать, и пытается поставить себя на мое место! » Есть ли конец этим повторяющимся размышлениям о размышлениях?

Показать полностью 1

На один шаг вперёд?

Вспомним «Похищенное письмо» Эдгара По. Процитируем небольшой отрывок, как нельзя точно отражающий суть игр, подобных "игре в монетку" или "камень-ножницы-бумага".

Мне  знаком восьмилетний мальчуган, чья способность  верно  угадывать  в игре «чет и нечет» снискала ему всеобщее восхищение. Это очень простая игра: один  из  играющих  зажимает  в  кулаке  несколько камешков  и спрашивает  у другого,  четное  ли их  количество  он  держит  или нечетное.  Если  второй играющий угадает правильно,  то он выигрывает  камешек, если же неправильно, то  проигрывает камешек. Мальчик,  о котором я упомянул, обыграл всех  своих школьных  товарищей.  Разумеется,  он  строил  свои  догадки  на  каких-то принципах, и эти последние заключались лишь в том, что он внимательно следил за  своим  противником и правильно оценивал степень  его хитрости.

Например, его заведомо глупый противник поднимает кулак и опрашивает: «Чет или нечет?»

Наш школьник отвечает «нечет» и  проигрывает.. Однако  в следующей попытке он выигрывает,  потому что говорит себе: «Этот дурак взял в прошлый  раз четное количество камешков  и,  конечно, думает, что отлично схитрит,  если  теперь возьмет  нечетное  количество.  Поэтому я  опять скажу нечет!» Он  говорит «нечет!» и выигрывает.

С противником чуть поумнее он рассуждал бы так: «Этот мальчик  заметил, что я сейчас сказал «нечет», и теперь  он сначала  захочет

изменить  четное число камешков на  нечетное, но тут же спохватится, что это слишком просто, и оставит их количество прежним. Поэтому я скажу  «чет!». ». Он говорит  «чет!»  и  выигрывает.  Вот ход  логических  рассуждений маленького мальчика,  которого его товарищи окрестили «счастливчиком». Но,  в  сущности говоря, что это такое?

Всего  только, ответил  я,  уменье  полностью  отождествить  свой интеллект с интеллектом противника.

  Вот именно, сказал Дюпен.    А  когда я спросил у мальчика, каким способом он  достигает  столь  полного  отождествления, обеспечивающего  ему постоянный успех, он  ответил  следующее: «Когда  я  хочу  узнать, насколько умен,  или глуп,  или добр, или  зол  вот этот  мальчик иди о  чем он сейчас думает,  я стараюсь придать своему лицу точно  такое  же  выражение, которое вижу на  его  лице,  а потом жду,  чтобы узнать,  какие  мысли  или  чувства возникнут у меня в  соответствии  с этим выражением


Потому мальчик из данного рассказа настолько успешен, что он всегда может продумать цепочку «Он думает, что я думаю, что он думает, что....»  ровно на один шаг дальше, чем соперник.

Точно так же и в «камень-ножницы-бумага» нет равновесия Нэша: во всех этих вероятных исходах нет варианта, при котором оба участника были бы довольны своим выбором. Однако чемпионат мира и Всемирное общество ножниц-камень-бумаги (World Rock Paper Scissors Society) собирают игровую статистику. Очевидно, что в этой игре можно повысить свои шансы на победу, зная кое-что об обычном поведении людей.


По данным World RPS Society, камень — самый популярный бросок (37,8%). Бумагой играют 32,6%, ножницами — 29,6%. Итак, теперь вы знаете, что вам нужно выбрать «бумажный» ход. Однако, если вы играете с кем-то, кто тоже это знает, больше не берите бумагу, потому что это ожидаемо. Известен случай: в 2005 году два аукционных дома Sotheby's и Christie's соревновались за право выставить на торги очень крупный лот, в частности, коллекцию Пикассо и Ван Гога по стартовой цене в 20 миллионов долларов. Хозяин пригласил представителей двух домов поиграть в «камень-ножницы-бумагу». Sotheby's без колебаний выбрал бумагу. Победил дом Christie's. На самом деле его представители обратились к эксперту, 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым прочным, поэтому большинству людей хочется выбрать его. Но если мы не будем играть с совсем тупым новичком, то он не выберет камень, но будет ждать этого от нас, поэтому, он выберет бумагу. Мы подумаем на один шаг вперёд и выберем ножницы.»

Ящерица? Спок!

Новый вариант игры «камень-ножницы-бумага» популяризировал американский сериал «Теория большого взрыва», изначально созданный Сэмом Кассом и Карен Брайла. Это камень-ножницы-бумага-ящерица-Спок. Здесь действуют классические правила, к которым нужно добавить ящерицу, которая ест бумагу, отравляет Спока, раздавливается камнем и обезглавливается ножницами. Тем временем Спок испаряет камень, ломает ножницы и дискредитирует себя бумагой. Этот вариант, который увеличивает количество комбинаций с 3 до 10, должен уменьшить количество ничей между двумя игроками, которые знают друг друга.

На один шаг вперёд? Математика, Книги, Стратегия, Логика, Теория игр, Камень-ножницы-бумага, Популяризация, Научпоп, Длиннопост
На один шаг вперёд? Математика, Книги, Стратегия, Логика, Теория игр, Камень-ножницы-бумага, Популяризация, Научпоп, Длиннопост


Согласно теории вероятностей, в классическом варианте вероятность выигрыша, проигрыша и повторной игры одинакова и равна 1/3. В улучшенной версии ситуация меняется: вероятность выигрыша и проигрыша составляет по 0,4, а вероятность повторной игры — 0,2. Другими словами, если вы используете улучшенную версию инструмента разрешения споров, то в среднем количество неудачных раундов будет меньше. Тем не менее, между персонажами сериала этот вариант систематически приводит к ничье Спок vs. Спок.

Другой вариант, на этот раз французский, был популяризирован игрой Le Tout (изобретенной Tobiffleurs). Это камень-ножницы-бумага-галактика-клещ. Здесь мы используем классические правила, добавляя галактику, которая дематериализует камень, лист и ножницы, но которая взрывается из-за клеща. Последний может же быть убит камнем, листом или ножницами.

На один шаг вперёд? Математика, Книги, Стратегия, Логика, Теория игр, Камень-ножницы-бумага, Популяризация, Научпоп, Длиннопост


Давайте сравним этот режим игры с другими типами. Вариант «камень-ножницы-бумага-колодец» менее сложен, чем вариант «камень-ножницы-бумага-ящерица-Спок». Есть 4 знака для увеличения количества комбинаций. Это вариант, встречающийся во франкоязычных странах (Франция, Швейцария, Канада) и Германии.

Подробно о дополнительных условиях победы:

  • Ножницы падают в колодец,

  • Камень падает в колодец,

  • Бумага закрывает колодец.


В обычной игре каждый вариант не лучше и не хуже другого. В игре с колодцем, он, конечно же, лучше камня, так он, как и камень, проигрывает бумаге и выигрывает у ножниц, но при их встрече преимущество за колодцем. Таким образом, игрок не заинтересован в использовании камня, потому что, если он вместо этого покажет колодец, его шансы победить любого противника выше. Это означает, что ни один из игроков никогда не будет использовать камень и в игре снова есть три варианта с классическим балансом: колодец, ножницы, бумага. На языке теории игр можно сказать, что колодец доминирует над камнем.

В некоторых местностях и сообществах используются варианты до 9 различных фигур. В шутку на форумах и сайтах также обсуждались варианты до 101 фигуры. Неплохая тренировка памяти и гибкости пальцев, не правда ли?

Показать полностью 3
Отличная работа, все прочитано!