Рубрика «теория игр»

Эта статья имеет целью продолжить дискуссию начатую статьей «Больше, чем государство: Британская Ост-индская торговая компания» и является личным мнением автора.

Viva Las Vegas

Больше, чем государство: внешний долг США - 1

Для многих очевидно, что игра с казино убыточна. Исходя из установленных там правил и имея небольшое представление о теории вероятности, становится понятно, что при достаточно большом количестве попыток среднее значение выигрыша будет близко к математическому ожиданию выигрыша. Перевес казино в европейской рулетке (с одним «зеро») составляет 1 — 36/37 = 2,7%, что для игрока означает потерю в среднем 2,7% от ставки.

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

Дело не только в казино. Институциональный анализ развития экономических систем позволяет нам увидеть правила игры, которые создаются и изменяются людьми.Читать полностью »

image

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

В 1950-х математик Джон Нэш доказал, что в любом виде игры с конечным количеством игроков и конечным количеством вариантов (таком, как «камень-ножницы-бумага») всегда существует смешение стратегий, при которой ни один игрок не может показать результатов лучше изменением только собственной стратегии. Теория таких устойчивых наборов стратегий, которые называются "равновесиями Нэша", совершила революцию в области теории игр, изменила направление развития экономики и способы изучения и анализа всего — от политических договоров до сетевого трафика. А ещё она позволила Нэшу получить в 1994 году Нобелевскую премию.

Так как же выглядит равновесие Нэша в игре «камень-ножницы-бумага»? Давайте смоделируем ситуацию, в которой есть вы (Игрок A) и ваш противник (Игрок B), снова и снова играющие в игру. В каждом раунде победитель получает очко, проигравший теряет очко, а ничья засчитывается как ноль очков.
Читать полностью »

Разработка AI для пошаговой игры на Node.js (часть 1) - 1
Всем привет!
Прошло целых полтора года с момента написания моей первой статьи на Хабре. С тех пор проект FOTM претерпел ряд изменений. В начале пройдёмся вкратце по всем модернизациям, а затем перейдём к детальному разбору основной фичи — AI.Читать полностью »

Теория игр, мышиная возня и спущенная шина - 1

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

Стратегическая игра
«Игра» — слыша это слово, многим кажется, что речь идет о чем-то малозначительном и не масштабном в особенности по сравнению с мировой экономикой, бизнесом или военным делом. На самом деле стратегические игры включают в себя не только военную и бизнес стратегии, но и экономику, построение карьеры и отношений и многое другое. Почти все, что нас окружает, относится к стратегическим играм, а теория игр помогает во всем этом разобраться.
Но достаточно лирики, все уже поняли, что стратегические игры и теория игр — это самое важное, что может быть в жизни, а значит пора приступить к разбору примеров.
Читать полностью »

image
Юлмарт против инвесторов, конфликтов и долгов

Человек из Колпино, немного сгорбленный жизнью, в очках с толстыми линзами, обрамлёнными древнесоветской роговой оправой, с потёртым рюкзаком за плечами, вышел из метро на площади Ленина и поплёлся в сторону Кондратьевского проспекта. Из рюкзака выглядывал старый системный блок. Через пару километров странный человек остановился рядом со зданием № 15, на дверях которого висела бумажка с крупными буквами “Закрыто навсегда”. Он постоял пару секунд, что-то подумал, затем что-то негромко сказал. Вроде той фразы, которую он обронил на этом же месте 9 лет назад, став невольным эмоциональным вдохновителем команды Юлмарт. Это вполне может быть правдой.
Читать полностью »

Привет!

Свой первый пост я решил посвятить квантовой информатике и ее приложению к теории игр. Эта идея абсолютна не нова и своими корнями уходит в статью Жиля Брассарда 1999 года [1]. Квантовая механика сама по себе удивительная вещь, а возможность ее использования в играх вдвойне удивляет!

Играем с квантовой монеткой - 1

«Если квантовая механика вас не потрясла до глубины души, значит, вы ее еще не поняли.» (Нильс Бор)

Читать полностью »

В кладовой Манчестерского университета нашли утерянные письма Алана Тьюринга - 1Уникальная коллекция почтовых писем к Алану Тьюрингу и копии его писем найдены старом шкафчике в одном из служебных помещений Алана Тьюринга. Письма датируются от начала 1949 года и до самой трагической смерти великого математика в июне 1954 года. Судя по всему, более 60 лет никто не видел эти раритеты. Удивительно, что их обнаружили только сейчас.

В общей сложности найдено 148 документов, в том числе письмо из британской службы разведки GCHQ, рукописный сценарий радиопрограммы на BBC об Искусственном интеллекте, приглашения прочитать лекции от самых известных американских университетов, таких как Массачусетский технологический институт. Есть и письма на профессиональные темы, в том числе обсуждение теории комплексных чисел юного школьника и математика-вундеркинда Лионеля Марча из городка Хоув в графстве Восточный Суссекс. Копии некоторых писем Тьюринга тоже попали в архив: большинство из них напечатаны на печатной машинке. По мнению специалистов, письма под диктовку набирала секретарша Алана Тьюринга — мисс С. Дж. Вагстафф.

Многие письма относятся к главным сферам исследования Тьюринга: это Искусственный интеллект, вычислительная техника и математика.
Читать полностью »

ИИ: блеф, отъем денег у населения и победа над неопределенностью - 1

Прямо сейчас, пока вы читаете эти строки, в мире происходит удивительное событие — искусственный интеллект побеждает человека в очередной игре. Удивителен не сам факт превосходства машин, а то, что об этом мало пишут. Возможно, в связи с тем, что на этот раз машина состязается не в легендарную игру «го», не в DOOM, лапту или прятки, а в спортивный карточный покер.

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

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

Читать полностью »

Мы решили пофантазировать и заглянуть в будущее на 1 год, на 10 и на 69 лет вперед. Под катом вы найдете 17 прогнозов от женщин-исследователей из подразделения Microsoft Research на 2017 и на 2027 годы, а также поздравительную открытку, которая перенесёт вас в 2086 год.

17 прогнозов на 2017 год: исследователи корпорации Microsoft — о том, чего ожидать в 2017 году и через десять лет - 1
Читать полностью »