Ним Витхоффа

  • Ним Витхоффа, или игра Витхоффа, — стратегическая математическая игра для двоих игроков с двумя кучками фишек. Игроки по очереди берут фишки из одной или обеих кучек; в последнем случае из обеих кучек берется поровну фишек. Выигрывает тот, кто забирает последнюю или последние фишки.

    Мартин Гарднер в книге «От мозаик Пенроуза к надежным шифрам» (глава 8) утверждает, что игра известна в Китае под названием 捡石子 цзянь-шидзы («взятие камней»). Голландский математик Виллем Витхофф опубликовал математический анализ игры в 1907 году.

Источник: Википедия

Связанные понятия

Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход.
Игры Блотто (Игры Полковника Блотто) представляют собой класс игр двух лиц с нулевой суммой, в которой задача игроков состоит в распределении ограниченных ресурсов по нескольким объектам (полям битв). В классической версии игры игрок, выставивший больше ресурсов на поле, выигрывает битву на этом поле, а суммарный выигрыш (цена игры) равен сумме выигранных битв.
Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.
В теории игр, игра в нормальной или стратегической форме (англ. normal form) состоит из трех элементов: множества игроков, множества чистых стратегий каждого игрока, множества платежных функций каждого игрока. Таким образом, игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора. Эта таблица называется платёжной матрицей (англ. payoff matrix).

Подробнее: Нормальная форма игры
Солитер — это настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita.
Варианты правил го — различные своды правил настольной игры го. Отличаются отдельными деталями, трактовкой некоторых редко встречающихся в реальных партиях позиций, правилами определения результата в спорных случаях и порядком подсчёта разности очков. Все используемые на практике варианты эквиваленты в абсолютном большинстве случаев, их различия проявляются только в редких ситуациях.
Реверси (другое название — оте́лло) — настольная игра для двух человек на доске 8 на 8 клеток.
Игра Гранди — это математическая игра на стратегию для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют одну кучу на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух и менее предметов и ни одна не может быть разделена на кучки разных размеров. В игру обычно играют как и в поддавки. Это означает, что последний игрок, который сможет сделать разрешенный ход, выигрывает.
Пешечная дуэль — это логическая игра на шахматной доске. В ней участвуют два игрока, у каждого перед началом игры по три (иногда более) пешки, расположенные друг против друга на противоположных крайних горизонталях. Первыми ходят белые. Каждый ход состоит из передвижения одной из пешек своего цвета. Первым ходом каждый из игроков может идти не далее, чем до середины доски, и на любое количество клеток во все последующие ходы. Пешки ходят вперёд либо назад. Задача каждого из игроков — оставить противника...
Сим — топологическая игра, заключающаяся в том, что два игрока по определённым правилам проводят линии на плоскости.
Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «Кто выиграет при правильной игре?»
Одновременной игрой (англ. simultaneous game) называют игру, в которой стратегии избираются участниками до того, как станут известны стратегии оппонентов. Одновременные игры противопоставлены последовательным, где ходы совершаются по очереди. Чаще всего одновременные игры предстают в нормальной форме.

Подробнее: Одновременная игра
Шахматы для троих — семейство вариантов шахмат, разработанных специально для игры втроем. Относятся к коалиционным играм. Существует множество вариаций шахмат для троих игроков. Как правило, в них используется нестандартная доска. Например, шестиугольная доска, доска с клетками — правильными треугольниками или трехсторонняя с четырёхугольными клетками, соединяющимися в центре доски особым образом.
То́чки — логическая настольная игра для двух человек, сочетающая позиционное стратегическое планирование с тактическим перебором вариантов. Ведётся на плоском игровом поле, расчерченном на клетки одинакового размера. Игроки поочерёдно ставят точки двух цветов в перекрестия линий. Цель — окружить точки соперника замыканием вокруг них непрерывной цепи своих точек.
Мус — является испанской карточной игрой, как утверждается, это самая популярная карточная игра в Испании. Это игра со взятками, с аспектом соперничества, происходящая из Наварры и страны Басков в Испании. Оттуда она распространилась по всей стране, где сейчас является самой популярной карточной игрой, порождая бесчисленные клубы Мус или Пеньяс и становясь основной игрой среди студентов колледжа. Она высоко ценится, рассматривается многими как одна из лучших игр в карты.
Рэ́ндзю (яп. 連珠) — настольная логическая игра для двух игроков, спортивный вариант крестиков-ноликов до пяти в ряд, сочетающая в себе, кроме спортивных элементов, также элементы искусства и философии. Возникла в Китае более четырёх тысяч лет назад, вариации были известны и цивилизации инков, и Древнему Риму. В начале нашей эры игра из Китая попала в Японию, где и получила наибольшее распространение. Принятый спортивный вариант, равно как и название, также родились в Японии. Старые вариации игры известны...
Некооперативная игра — термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.
Быки и коровы — логическая игра, в ходе которой за несколько попыток один из игроков должен определить, что задумал другой игрок. Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова. После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»). Роли участников игры не равнозначны — угадывающий должен анализировать...
Компьютерное го — направление искусственного интеллекта по созданию компьютерных программ, играющих в го.
«Абалон» (фр. Abalone) — настольная абстрактная стратегическая игра для двух игроков, придуманная французскими дизайнерами игр Мишелем Лале (Michel Lalet) и Лораном Леви (Laurent Lévi) в 1987 году под названием «Сумито». В игре используются шарики разных цветов (по 14 шаров каждого цвета) и шестиугольное игровое поле, содержащее 61 пункт. Целью игры является выталкивание шести шаров соперника за пределы поля. Существуют варианты правил для трёх-шести игроков.
Покер на костях — азартная игра в кости. В неё могут играть от двух человек и более, оптимальное число игроков — четыре. Для игры используют 5 кубиков с числовыми достоинствами от 1 до 6. В зависимости от игровой ситуации, выбрасываются от одного до пяти кубиков одновременно. За выполнение определённых комбинаций даются очки. Все комбинации и результаты их выполнения записываются в таблицу. Цель игры — набрать наибольшую сумму очков.
Го (яп. 碁; также кит. 围棋 вэйци, кор. 바둑 падук) — логическая настольная игра с глубоким стратегическим содержанием, возникшая в Древнем Китае, по разным оценкам, от 2 до 5 тысяч лет назад. До XIX века культивировалась исключительно в Восточной Азии, в XX веке распространилась по всему миру. По общему числу игроков — одна из самых распространённых настольных игр в мире. Входит в число пяти базовых дисциплин Всемирных интеллектуальных игр.
Элузис — индуктивная карточная игра, в которой один игрок загадывает правило раскладки карт, а другие, глядя на разложенные карты, должны его угадать. Элузис — одна из первых игр, моделирующих изучение законов природы и развивающих не только логическое, но и индуктивное мышление.
Компьютерные шахматы — популярный термин из области исследования искусственного интеллекта, означающий создание программного обеспечения и специальных компьютеров для игры в шахматы. Также термин «компьютерные шахматы» употребляется для обозначения игры против компьютерной шахматной программы, игры программ между собой.
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно...
Задача о соседях по комнате — математическая задача кооперативных игр (теории игр и комбинаторики) нахождения устойчивого (стабильного) соответствия, при котором никакая другая пара не предпочитала бы друг друга более чем в текущем распределении. Задача отличается от задачи о супружеских парах тем, что здесь нет разбиения на два пола: любой человек может проживать с любым другим (предполагается, что в общежитии студенты живут по два человека в комнате).
Равнове́сие Нэ́ша — концепция решения, одно из ключевых понятий теории игр. Так называется набор стратегий в игре для двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Джон Нэш доказал существование такого равновесия в смешанных стратегиях в любой конечной игре.
Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.
«Балда» — лингвистическая настольная игра для 2—4 игроков, в которой необходимо составлять слова с помощью букв, добавляемых определённым образом на квадратное игровое поле. В наиболее популярном варианте игры, который имеет множество компьютерных реализаций, слова составляются посредством переходов от буквы к букве под прямым углом. Правила варианта игры под названием «Королевский квадрат» допускают диагональные переходы.
Это статья об азартной игре. См. также Пасьянс Маджонг.Маджонг или мацзян (кит. трад. 麻將, упр. 麻将, пиньинь: májiàng, палл.: мацзян) — китайская азартная игра с использованием игральных костей для четырёх игроков (каждый играет за себя). Широко распространена в Китае, Японии и других странах Восточной и Юго-Восточной Азии. Игра ведётся костями, напоминающими костяшки домино, по правилам подобна покеру, требует от играющих таких качеств, как опыт, память и наблюдательность. В игре присутствует также...

Подробнее: Маджонг
Стохастическая игра (англ. stochastic game) в теории игр — повторяющаяся игра со случайными переходами состояний, разыгрываемая одним и более игроками.
Битва полов или семейный спор (англ. Battle of the sexes (BoS), альтернативное расшифровка аббревиатуры — англ. Bach or Stravinsky, «Бах или Стравинский») — одна из основополагающих некооперативных моделей в теории игр, которая предполагает участие двух игроков с разными предпочтениями.
Парадокс Монти Холла — одна из известных задач теории вероятностей, решение которой, на первый взгляд, противоречит здравому смыслу. Эта задача не является парадоксом в узком смысле этого слова, так как не содержит в себе противоречия, она называется парадоксом потому, что ее решение может показаться неожиданным. Более того, многим людям бывает сложно принять правильное решение даже после того, как его им рассказали.
Пентамино́ (от др.-греч. πέντα пять, и домино) — пятиклеточные полимино, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.
Парадо́кс Парро́ндо — парадокс в теории игр, который обычно характеризуют как комбинацию проигрышных стратегий, которая выигрывает. Парадокс назван в честь его создателя, Хуана Паррондо, испанского физика. Утверждение парадокса выглядит следующим образом...
См. также джетан из «Марсианских шахмат» Э. Р. Берроуза.Марсианские шахматы — абстрактная стратегическая игра, придуманная Эндрю Луни. Играется пирамидками Луни на шахматной доске. Количество игроков — от двух до шести. Чтобы играть количеством игроков, отличных от двух и четырех, нужно использовать неевклидову поверхность для получения доски необходимого размера.

Подробнее: Марсианские шахматы (игра)
Квантовая теория игр является расширением классической теории игр в квантовую область. Она отличается от классической теории тремя основными особенностями...
Эволюция (англ. Evolution: The Origin of Species) — настольная игра, основанная на теории Дарвина. Игра была создана кандидатом биологических наук Дмитрием Алексеевичем Кнорре в 2010 году, и входит в серию «Правильные игры» (www.rightgames.ru). В 2011 году вышла также на английском, французском и немецком языках. Игра была признана лучшей игрой 2010 года многими российскими игровыми порталами и стала известна также за пределами России.
Игра в кубики (игра в плитки, плиточки) была популярна среди детей всех возрастов во Владивостоке, а также в Cредней Азии в начале-середине 80-х годов XX века. Интерес к игре начал увядать приблизительно в 1986 году, когда стали осуществляться попытки получить коммерческую выгоду от продажи кубиков, что быстро привело к их девальвации.
Покер планирования (англ. Planning Poker, а также англ. Scrum poker) — техника оценки, основанная на достижении договорённости, главным образом используемая для оценки сложности предстоящей работы или относительного объёма решаемых задач при разработке программного обеспечения. Это разновидность метода Wideband Delphi.
База данных шахматных окончаний — компьютеризированная база данных, содержащая предварительно рассчитанный исчерпывающий анализ шахматных эндшпилей. В такой базе данных хранятся оценки (выигрыш, ничья, поражение) для каждой возможной позиции шахматного окончания как при ходе белых, так и при ходе чёрных. Некоторые распространённые базы данных также содержат количество ходов, необходимых для достижения теоретического результата (мат, переход в младший выигранный эндшпиль и т. п.) при наилучшей игре...
Коми — в игре го — компенсация, которую получает играющий белыми за право первого хода чёрных. Коми определяется в очках, которые по завершении партии добавляются к очкам, набранным игроком. Обычно размер коми нецелый — это сделано для исключения ничьих.
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
По́кер (англ. poker) — карточная игра, цель которой — выиграть ставки, собрав как можно более высокую покерную комбинацию, используя 4 (старый классический вариант), 2, или 5 карт, или вынудив всех соперников прекратить участвовать в игре. Игра идёт с полностью или частично закрытыми картами. Конкретные правила могут варьироваться в зависимости от разновидности покера. Обобщающими элементами всех разновидностей покера являются комбинации и наличие торговли в процессе игры.
Руле́тка — азартная игра ( слово рулетка (roulette) происходит от французского слова "ру" в переводе с французского означает "колесо, ролик , бегунок "). Рулетка впервые появилась во Франции. Она называлась "хока" и в ней было 40 пронумерованных гнёзд и три были помечены "зеро". Во времена короля Луи XIV, кардинал Мазарини, чтобы пополнить казну, повсеместно разрешил во Франции, открывать казино. После смерти Мазарини в 1661 году вышел Указ, гласивший что всякий кто осмелится открыть казино для игры...
Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет). Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянии.
Система Хатчинсона (англ. Hutchinson System) — это система определения перспективности любого набора карт, розданных игроку в покер (так называемой руки). Она была разработана для начинающих игроков с целью оказания помощи в принятии решения о разыгрывании руки.
В шахматах и других абстрактных стратегических играх в случае троекратного повторения позиции игрок может потребовать ничью. Повторные позиции не обязательно должны происходить в той же последовательности.

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

Подробнее: Кооперативная теория игр
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я