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

Теория игр — математическая дисциплина, рассматривающая моделирование действий игроков, которые имеют цель, заключающуюся в выбор оптимальных стратегий поведения в условиях конфликта. На Хабре эта тема уже освещалась, но сегодня мы поговорим о некоторых ее аспектах подробнее и рассмотрим примеры на Kotlin.
Читать полностью »

Вступление переводчика

Я вполглаза слежу за зреющим конфликтом в сообществе Linux. Материалов об этом везде публикуется довольно много, началось всё с этого, в текущем состоянии отражено, например, здесь, а за первоисточником можно обращаться сюда. Среди всего обилия информации меня заинтересовало письмо Эрика С. Рэймонда, которое он озаглавил иронично-пафосно: “On holy wars, and a plea for peace”. Это письмо отличается взвешенным тоном и интересно само по себе, а не только в контексте конфликта. Перевод следует.

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

«Дормамму, я пришел договориться»: алгоритм взаимовыгодной кооперации с человеком - 1

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

Большое спасибо всем участникам конкурса по программированию! Мы рады объявить окончательные результаты конкурса.

В конкурсе участвовали 186 решений. Мы провели между ними турнир в два раунда, как объявляли ранее. Поздравляем победителей:

  1. Asta — приз 3000 USD.
  2. Silent Bob — приз 2000 USD.
  3. Robert Speed — приз 1000 USD.

Специальный приз 400 USD получает участник под псевдонимом indutny за разработку альтернативной арены для онлайн-тестирования решений с большей пропускной способностью, чем у предоставленной нами. Спасибо!

Официальную таблицу результатов вы найдёте на GitHub.
Читать полностью »

Большое спасибо всем участникам конкурса по программированию! Приём решений ещё не закончен, но в полночь на 17 июля мы взяли тот набор решений, который был на тот момент, и провели между ними мини-турнир. В него попали 82 решения.

Но сначала — несколько объявлений.

Конкурс продлевается на неделю

Срок приёма решений продлевается до 27 июля 2018, 23:59:59 UTC. Также на неделю вперёд сдвигаются сроки, в которые будут объявлены результаты конкурса. Мы продлили конкурс для того, чтобы улучшить охват в сезон отпусков.
Читать полностью »

Компания Hola вновь объявляет конкурс по программированию! Победителей ожидают призы:

  1. Первое место: 3000 USD.
  2. Второе место: 2000 USD.
  3. Третье место: 1000 USD.
  4. Жюри может присудить по своему усмотрению специальный приз в 400 USD.
  5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя). За одного победителя такую награду может получить только один человек — тот, кто отправил ссылку первым.

Авторы интересных решений будут приглашены на собеседования.

Конкурс по программированию: Торговля - 1

Правила

Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.

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

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

Вместе порознь

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

Что общего у эффективного майнинга и теории игр - 1
Собственно, поэтому и возник Whalesburg

Фактически, сегодня весь сегмент занимается бесконечным самообманом, когда позиционирует пул как коллективный инструмент майнинга. Общности и взаимодействия лишь чуть больше, чем при добыче напрямую. Единственное, чем помогает пул — это увеличивает доходность за счет объединения мощностей с последующей «дележкой» добытого. При этом майнер сам решает, куда направить мощь своей фермы и что «копать». Подобный индивидуализм очень хорошо вписывается в парадигму современной рыночной культуры, но при этом, на длинной дистанции, снижает общую доходность майнинга. Выигрывают лишь сами владельцы пула и по-настоящему промышленные майнеры, когда как рядовому «копателю» остается лишь метаться между блокчейнами и до красных глаз мониторить курсы криптовалют.
Читать полностью »

image

Дисклеймер

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

Введение

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

Зачем нужны СППР:

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

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

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

Viva Las Vegas

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

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

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

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

image

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

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

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