Рубрика «логические игры»

Привет!

Меня зовут Миша, и я студент. На факультативе по теории игр мы решаем различные интересные задачи, и я хотел бы поделиться с вами одной из таких.
Читать полностью »

Думаю, ни для кого не секрет, что "Дурак" (далее это слово будет написано с маленькой буквы и без кавычек) — это самая популярная карточная игра в России и странах бывшего СССР (хотя и почти неизвестная за его пределами). Несмотря на свое название и довольно несложные правила, выигрыш в ней все-таки зависит больше от мастерства игрока, чем от случайного расклада карт (в английской терминологии игры того и другого типов называются соответственно game of skill и game of chance. Так вот — дурак в большей степени game of skill).

Целью статьи является написание простого ИИ для игры. Под словом "простого" подразумевается следующее:

  • интуитивно понятный алгоритм принятия решений (то есть, как следствие, никакого машинного обучения, в котором этот алгоритм скрыт глубоко "под капотом");
  • отсутствие состояния (то есть, алгоритм руководствуется только данными на текущий момент времени, проще говоря, ничего не запоминает (например, не "считает" вышедшие из игры карты).

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

Математическая модель игры Доббль

Уровни сложности чтения

  • Я слишком молод, чтобы думать

    • Введение и правила игры
    • Как они это делают?
    • Матрица инцидентности для игры Доббль
    • Каких двух карточек не хватает в комплекте игры?
    • Почему в игре на 2 карточки меньше максимально возможного количества?
    • Благодарности

  • Сделай мне умно

    • Введение и правила игры
    • Как они это делают?
    • При чём тут карточки?
    • Проективные плоскости малых порядков
    • Матрица инцидентности для игры Доббль
    • Каких двух карточек не хватает в комплекте игры?
    • Почему в игре на 2 карточки меньше максимально возможного количества?
    • Благодарности

  • Кошмар

    • Введение и правила игры
    • Как они это делают?
    • Конечная геометрия для грудничков
    • При чём тут карточки?
    • Проективные плоскости малых порядков
    • Как построить проективную плоскость?
    • Матрица инцидентности для игры Доббль
    • Каких двух карточек не хватает в комплекте игры?
    • Почему в игре на 2 карточки меньше максимально возможного количества?
    • Благодарности

Введение и правила игры

Несколько лет назад я купил игру Доббль (Dobble, оригинальное название “Spot It!”). Это очень простая, быстрая и весёлая игра, которую я считаю одной из лучших настольных игр вообще.

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

ИИ и 2048. Часть 1: Метод Монте-Карло - 1

«2048» через несколько недель исполняется 5 лет, а значит, пора написать что-нибудь, посвящённое этой замечательной игре.

Особенно познавательна тема самостоятельной игры искусственного интеллекта в головоломку. Способы реализации есть самые разные и сегодня разберём относительно лёгкий из них. А именно — научим компьютерный разум собирать степени двойки с помощью метода Монте-Карло.Читать полностью »

При игре по стандартным правилам Гомоку для выигрыша черным требуется не более 35 ходов. В статье Вашему вниманию представлена полная выигрышная стратегия и соответствующий алгоритм игры.
Выигрышная стратегия Гомоку – 35 ходов - 1
Демонстрация полного решения – здесь – можно поиграть и найти самые длинные варианты. Программа всегда выигрывает и затрачивает на это не более 35 ходов. Исходные тексты приложения, само решение и примеры партий в конце статьи.
Читать полностью »

Стратегического покерного бота Libratus адаптировали для военных симуляторов - 1В 2017 году покерный бот Libratus попал в заголовки СМИ, когда обыграл четырёх профессионалов в безлимитный холдем на дистанции 120 000 рук. Теперь технологию адаптировали для военного применения.

Разработчики систем слабого ИИ часто сравнивают эффективность своих программ в игровом противостоянии против человека. В играх с полной информацией в любой момент игры все игроки имеют полную информацию о состоянии игры, то есть о позиции и всех возможных ходах любого из игроков. В отличие от таких детерминированных ситуаций, в играх с неполной информацией часть информации о состоянии игры скрыта от игрока — например, карты оппонента. Безлимитный холдем как раз одна из таких игр. Кроме закрытых карт оппонента, добавляется здесь элемент неопределённости за счёт произвольного размера каждой ставки. С учётом этого количество возможных исходов оценивается в 10161. Выработка оптимальной стратегии в условиях неопределённости с учётом тактики оппонента — именно то, что нужно военным.
Читать полностью »

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

Один гигантский шаг для машины, играющей в шахматы - 1

В начале декабря исследователи из компании DeepMind, занимающейся искусственным интеллектом и принадлежащей Alphabet Inc., родительской корпорации, также владеющей и Google, рассказали о происходящем на передних рубежах шахмат.

Годом ранее, 5 декабря 2017 года, команда поразила шахматный мир, объявив о своём алгоритме машинного обучения (МО) AlphaZero, который сумел овладеть не только обычными шахматами, но и японскими шахматами сёги и игрой го. Алгоритм начал работу без какого бы то ни было понятия об играх, кроме базовых правил. Затем он начал играть сам с собой несколько миллионов раз и учиться на своих ошибках. Всего за несколько часов алгоритм стал наилучшим игроком, как среди людей, так и компьютеров, из всех, что видел мир.
Читать полностью »

День первый. Нам подарили игру «Ticket to ride. Европа». Это моё первое знакомство с игрой данной серии, надо обязательно попробовать и заценить.

День пятый. Как-то надоело регулярно проигрывать, пора бы призвать на помощь математику и попробовать таким образом одержать заслуженную победу.

Ticket to Ride.Европа — скромные шаги в арифметику игры - 1

С помощью гугла, excel и python и чёртовой матери была проведена познавательная экскурсия в механики игры. Читать полностью »

image

Теория ходов

Математика апокалипсиса: теория игр и карибский ядерный кризис - 2«Мы сыграли в гляделки, и, по-моему, противник моргнул», — сказал государственный секретарь США Дин Раск на пике кубинского ракетного кризиса в октябре 1962 года. Он имел в виду сигналы, которые подавал Советский Союз, желая разрешить самую опасную ядерную конфронтацию между двумя сверхдержавами, которую многие аналитики интерпретировали как классический пример игры в ядерного «цыплёнка» (на русском аналог этой игры называется «ястребы и голуби»).

Игра в «цыплёнка» обычно используется для моделирования конфликтов, в которых каждый из игроков взял курс на столкновение. Игроками могут быть водители, приближающиеся друг к другу на узкой дороге, каждый из который имеет выбор — свернуть, чтобы избежать столкновения, или не сворачивать. В рассказе «Бунтарь без причины», который позже был переделан в фильм с участием Джеймса Дина, водителями были два подростка, но они ехали не друг на друга, а к обрыву. Цель игры была в том, чтобы не нажать на тормоза первым и не превратиться таким образом в «цыплёнка», и в то же время не свалиться с обрыва.

Хотя с виду карибский ракетный кризис похож на игру в «цыплёнка», на самом деле он плохо моделируется этой игрой. Другая игра более точно описывает действия лидеров США и Советского Союза, но даже для этой игры стандартная теория игр не полностью описывает доступные им варианты выбора.

С другой стороны, воспроизводит или предсказывает прошлое действий лидеров «теория ходов» (theory of moves), основанная на теории игр, но радикально меняющая стандартные правила игры. Что ещё более важно, эта теория проливает свет на динамику игры, основываясь на предположении, что игроки думают не только о непосредственных последствиях их действий, но и об их влиянии на игру в будущем.
Читать полностью »

Что можно сделать с компьютером на электромагнитных реле у которого нет никаких устройств ввода, а из устройств вывода — только дамп восьми регистров?

Поиграть в игры, конечно! Играли же древние люди на калькуляторах МК-61/52, которые лишь немногим нагляднее.

Как написать игру для компьютера, в котором нет устройств ввода и вывода - 1
Читать полностью »