Игры с одновременным ходом
Автор статьи: Антонио Грамши, математик, биолог и изобретатель настольных игр
В позиционных играх двух лиц с полной информацией ходы противников чередуются, образуя правильную последовательность АВ АВ АВ...(А, В – ходы игроков А и В соответственно). При этом каждую пару АВ иногда трактуют как единый ход, состоящий из двух полуходов А и В.
В позиционных играх с одновременным ходом полуходы в каждом ходе совершаются не последовательно, а одновременно. Поэтому речь идет, строго говоря, об играх с неполной информацией. В данном случае неполнота информации обусловлена не процедурой, генерирующей случайность (тасование карт, подкидывание кубика и т. д.), а тайным выбором полухода в каждом ходе.
Последовательность ходов в играх с одновременным ходом удобно изображать следующим образом:
Одноходовые игры такого рода, так называемые прямоугольные, или матричные игры, являются основным предметом изучения в теории игр. Простейший пример – детская игра “камень, ножницы, бумага”. Некоторые многоходовые игры с одновременным ходом сводятся к последовательности матричных игр.
Игры с одновременным ходом лучше моделируют реальность, чем игры с последовательными ходами. Поэтому представляется весьма перспективной и интересной разработка интеллектуальных игр такого рода – как принципиально новых, так и созданных на основе традиционных игр (шашек, шахмат и др.). В этом очерке рассмотрим простейшую игру с одновременным ходом – хап.
Хап
В названии игры содержится шутливый намек на аналогичную игру с полной информацией ним (от нем. nimm – “бери”). Игра была впервые опубликована в мартовском номере журнала “Квант” за 2004 год под названием “Ним с одновременным ходом” и, судя по отзывам читателей, стала отличным подспорьем для предварительного знакомства детей младшего школьного возраста с элементами теории множеств.
1. Вариант игры с равноценными элементамиИграют двое. Имеется исходное конечное множество U некоторых объектов.
Первый ход состоит в том, что каждый игрок выбирает для себя некоторое подмножество объектов из U.
Если подмножества противников не пересекаются, они забирают выбранные объекты.
Если подмножества игроков пересекаются, то сравниваются их мощности (мощность конечного множества равна числу входящих в него элементов). Если у одного из игроков мощность выбранного подмножества меньше, он забирает выбранные объекты, при этом второй игрок не забирает ничего.
Если подмножества пересекаются, но они равномощны (имеют одинаковое число элементов), противники забирают выбранные объекты кроме тех, которые входят в пересечение. Если подмножества совпадают, игроки не забирают ничего.
Можно выбирать пустое подмножество, то есть пропускать ход.
В результате, после первого хода исходное множество U превращается во множество U’, мощность которого меньше или равна мощности U.
Второй ход делается аналогично, но в качестве исходного рассматривается уже множество U’. Точно так же делается третий ход и т. д.
Партия прекращается, когда в универсальном множестве остается не более двух объектов. Она также прекращается в случае повторного совпадения выбранных подмножеств, в частности, когда противники два раза подряд пропускают ход (то есть оба раза выбирают пустое множество). Более сложное условие прекращения партии состоит в циклическом повторении ходов (то есть, когда последовательность совпадений выбираемых подмножеств зацикливается). Впрочем, последний исход крайне маловероятен.
Объединение всех выбранных каждым игроком подмножеств будем называть его набором.
Выигрывает тот игрок, который набрал больше объектов из U, то есть чей набор имеет бóльшую мощность.
Иными словами, общий выигрыш достигается максимальным объединением минимальных множеств.
Узнайте, как мы учим детей думать на наших онлайн-кружках математики
