Статья по результатам работы от классического результата Аксельрода 1984 года до пары фишек, которые я защищал на конкурсах этой зимой.Теория игр иногда дает совершенно предсказуемые ответы, а иногда нетривиальные вопросы, которые, сильно прищурившись, может задать даже школьник, способный дать забавные и довольно доказательные картинки отношений между… да кем угодно! Это и мотивировало меня взять в качестве первой проектной работы математическую игру «Дилемма заключенных».
Читать полностью »
Рубрика «теория игр» - 6
«Расширенная дилемма заключенных» или «Почему нужно прощать»
2013-04-29 в 12:44, admin, рубрики: математика, теория игр, метки: математика, теория игрАбстракции в компьютерном покере
2013-03-29 в 12:33, admin, рубрики: искусственный интеллект, покер, теория игр, метки: искусственный интеллект, покер, теория игр
Компьютерный покер является весьма нетривиальной задачей в первую очередь из-за громадного количества игровых состояний, которое настолько велико, что мечтать о непосредственном решении этой игры не приходится. Единственным способом хоть как-то научить машину играть в покер является переход к абстракции — уменьшенной копии покера, в которой близкие в стратегическом смысле ситуации исходной игры объединены воедино. Именно вопросам абстракций в покере и посвящена данная заметка.
Читать полностью »
Око за око
2013-01-22 в 13:51, admin, рубрики: Песочница, Социальные сети и сообщества, социум, теория игр, метки: социум, теория игрВ известной проблеме теории игры «Проблема заключенного» предательство является единственным верным решением. Однако если также не давать двум сторонам договариваться друг с другом, но повторять ситуацию множество раз подряд, то такая стратегия поведения станет не самой выгодной. Выбор верной стратегии может помочь ответить на вопросы об эволюции человеческого социума, появление фактов сотрудничества в личных и деловых отношениях, соотношения моральных норм и собственных интересов.
В конце 1970-х годов Роберт Аксельрод (математик, политолог, ныне профессор Мичиганского университета) придумал эксперимент, заключающийся в моделировании поведения субъектов, поставленных перед многократно повторяющейся дилеммой заключенного (IPD или iterated prisoner’s dilemma).
Читать полностью »
Теория игр: Введение
2012-12-24 в 2:48, admin, рубрики: математика, теория игр, метки: математика, теория игр
Что это такое, и с чем его едят.
Теория игр — это раздел математической экономики, изучающий решение конфликтов между игроками и оптимальность их стратегий. Конфликт может относиться к разным областям человеческого интереса: чаще всего это экономика, социология, политология, реже биология, кибернетика и даже военное дело. Конфликтом является любая ситуация, в которой затронуты интересу двух и более участников, традиционно называемых игроками. Для каждого игрока существует определенный набор стратегий, которые он может применить. Пересекаясь, стратегии нескольких игроков создают определенную ситуацию, в которой каждый игрок получает определенный результат, называемый выигрышем, положительным или отрицательным. При выборе стратегии важно учитывать не только получение максимального профита для себя, но так же возможные шаги противника, и их влияние на ситуацию в целом.
Минимакс на примере игры в зайца и волков
2012-06-21 в 22:56, admin, рубрики: алгоритм, Алгоритмы, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, Программирование, теория игр, метки: алгоритм, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, теория игр Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.Читать полностью »
Биовычисления по сворачиванию. Снова простым языком о полученной модели сворачивания
2012-06-15 в 23:33, admin, рубрики: Алгоритмы, биоинформатика, кибернетика, сворачивание рнк, теория игр, Фолдинг белков, метки: кибернетика, сворачивание рнк, теория игр, Фолдинг белковЯ тут написал уже более 7 статей на тему одного своего подхода (набора алгоритмов и проблем) к задаче сворачивания РНК. Читающих становилось с каждой статьей все меньше, а кое кто признавался, что мозг выносило уже после второй статьи. Сравнительный успех первых двух статей, по сравнению с остальными — кажется заключается в простоте изложения и не углубления в детали. Хотя последние статьи давали возможность самим взять демо моей программы и прочувствовать проблематику — это видимо интересует меньше.
Поэтому я постараюсь тут изложить простым языком еще одну проблему, которая мешает решить эту задачу. И мне представляется, что это проблема связанна не только с выбранным мной подходом к решению, а она скорее общая для задачи.
В своем ПО RNAInSpace — я реализовал возможность «покрутить» спираль РНК вручную, чтобы стала понятна геометрия и ограничения такого вращения. Но так как по предыдущим статьям — это ПО не сильно заинтересовало, то тут очередную демо версию этого ПО я представлять не буду. А поговорим о том, что получается у меня.
История одного реинжиниринга или RNAInSpace v.1.3. Demo
2012-05-16 в 3:30, admin, рубрики: биоинформатика, кибернетика, Проектирование и рефакторинг, реинжиниринг, сворачивание рнк, теория игр, Фолдинг белков, метки: demo, кибернетика, реинжиниринг, сворачивание рнк, теория игр, Фолдинг белковТут недавно был такой пост Правила разработки сложных систем. История одного проекта, где автор описывает как он удачно «копался» в одном проекте, а потом все выкинул и переписал с нуля.
Я попробую рассказать обратную историю. Тут около месяца назад я не удачно попытался представить демо версию одной своей разработки (см. Часть №7. RNAInSpace — программное обеспечение для полуавтоматического конструирования РНК в пространстве).
Оказалось, что у скачивающих не работает один модуль, ответственный за показ графики. В двух словах проект RNAInSpace — это программное обеспечение для полуавтоматического конструирования РНК в пространстве. Обеспечивает 3D визуализацию структуры РНК, позволяет её изменять и с помощью связи с модулем RNAWorld позволяет автоматизировать некоторые этапы сворачивания РНК.
Чтобы войти в тему — я тут написал некоторое множество статей:
От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?, Ограничение оптимизирующих методов в играх с противником и без, Одна фундаментальная проблема, Введение в сворачивание многоспиральных РНК
Но эту статью можно обсуждать и не зная предметной области, кстати заодно проверим можно ли судить о качестве ПО не зная семантики предметной области (я утверждаю, что можно).
Так вот эта 3D визуализация (модуль RNAInSpaceDisplay) и не работала на некоторых компьютерах. Для реализации графики я использовал существующий проект VMD 1.8.7.
Ниже история о том как я адаптировал VMD 1.8.7 под свои нужды.
Часть №7. RNAInSpace — программное обеспечение для полуавтоматического конструирования РНК в пространстве
2012-03-30 в 13:34, admin, рубрики: биоинформатика, кибернетика, Программирование, разработка, сворачивание рнк, теория игр, Фолдинг белков, метки: demo, кибернетика, сворачивание рнк, теория игр, Фолдинг белковВ предыдущих частях От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?, Ограничение оптимизирующих методов в играх с противником и без, Одна фундаментальная проблема, Введение в сворачивание многоспиральных РНК я рассказал основы к предлагаемому мной кибернетико-геометрическому подходу для задачи сворачивания РНК. Повторю формулировку задачи:
Имеем произвольную, реально существующую, первичную последовательность до 100 нуклеотидов. Знаем все водородные связи которые нужно образовать. На выходе получаем файл .pdb, в котором третичная структура из указанной первичной последовательности и где образованы все требуемые водородные связи.
Здесь я расскажу о практике, чтобы каждый мог попробовать что это такое. Мной было разработано ПО для расчета того, о чем я рассказывал. Здесь я даю ссылку на демо версию. И объясняю, что вы сможете увидеть. Ведь лучше один раз увидеть, чем 100 раз услышать :)
Часть №6. Введение в сворачивание многоспиральных РНК
2012-03-29 в 13:23, admin, рубрики: Алгоритмы, биоинформатика, Биотехнологии, кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белков, метки: кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белковИтак, в прошлых частях мы разобрались как сравнительно просто сворачивать спирали РНК. Теперь нам предстоит понять, как вообще сворачивается РНК. То РНК, которые мы взяли в виде примера имеет три спирали. Две из них L1 и L2 можно свернуть независимо. А вот с третьей проблемы. Эта третья состоит из концов РНК, и при ее сворачивании начинаю двигать наши свернутые спирали L1 и L2. Во-первых, при этом они мешают друг другу, и следовательно и сворачиванию третьей спирали. Во-вторых, возможно образование около десятка разнообразных псевдосимметричных структур — спирали L1, L2 могут по разному располагаться по отношению к сворачиваемым концам РНК.
Здесь мы попробуем разобраться как эти проблемы решить.
Часть №5. Биовычисления по сворачиванию. Одна фундаментальная проблема
2012-03-25 в 3:58, admin, рубрики: Алгоритмы, биоинформатика, Биотехнологии, кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белков, метки: кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белковВ этой статье мы рассмотрим как свернуть одну спираль в РНК. Для понимания нужно прочитать все предыдущие части От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?, Ограничение оптимизирующих методов в играх с противником и без. Если ранее у нас все шло как по маслу, то здесь мы столкнемся с серьезной проблемой. Может кто-то подскажет как её решить.