Автор статьи: Антонио Грамши, математик, биолог и изобретатель настольных игр
В позиционных играх двух лиц с полной информацией ходы противников чередуются, образуя правильную последовательность АВ АВ АВ...(А, В – ходы игроков А и В соответственно). При этом каждую пару АВ иногда трактуют как единый ход, состоящий из двух полуходов А и В.
В позиционных играх с одновременным ходом полуходы в каждом ходе совершаются не последовательно, а одновременно. Поэтому речь идет, строго говоря, об играх с неполной информацией. В данном случае неполнота информации обусловлена не процедурой, генерирующей случайность (тасование карт, подкидывание кубика и т. д.), а тайным выбором полухода в каждом ходе.
Последовательность ходов в играх с одновременным ходом удобно изображать следующим образом:
A A A ...
B B B …
Одноходовые игры такого рода, так называемые прямоугольные, или матричные игры, являются основным предметом изучения в теории игр. Простейший пример – детская игра “камень, ножницы, бумага”. Некоторые многоходовые игры с одновременным ходом сводятся к последовательности матричных игр.
Игры с одновременным ходом лучше моделируют реальность, чем игры с последовательными ходами. Поэтому представляется весьма перспективной и интересной разработка интеллектуальных игр такого рода – как принципиально новых, так и созданных на основе традиционных игр (шашек, шахмат и др.). В этом очерке рассмотрим простейшую игру с одновременным ходом – хап.
Хап
В названии игры содержится шутливый намек на аналогичную игру с полной информацией ним (от нем. nimm – “бери”). Игра была впервые опубликована в мартовском номере журнала “Квант” за 2004 год под названием “Ним с одновременным ходом” и, судя по отзывам читателей, стала отличным подспорьем для предварительного знакомства детей младшего школьного возраста с элементами теории множеств.
1. Вариант игры с равноценными элементами
Играют двое. Имеется исходное конечное множество U некоторых объектов.
Первый ход состоит в том, что каждый игрок выбирает для себя некоторое подмножество объектов из U.
Если подмножества противников не пересекаются, они забирают выбранные объекты.
Если подмножества игроков пересекаются, то сравниваются их мощности (мощность конечного множества равна числу входящих в него элементов). Если у одного из игроков мощность выбранного подмножества меньше, он забирает выбранные объекты, при этом второй игрок не забирает ничего.
Если подмножества пересекаются, но они равномощны (имеют одинаковое число элементов), противники забирают выбранные объекты кроме тех, которые входят в пересечение. Если подмножества совпадают, игроки не забирают ничего.
Можно выбирать пустое подмножество, то есть пропускать ход.
В результате, после первого хода исходное множество U превращается во множество U’, мощность которого меньше или равна мощности U.
Второй ход делается аналогично, но в качестве исходного рассматривается уже множество U’. Точно так же делается третий ход и т. д.
Партия прекращается, когда в универсальном множестве остается не более двух объектов. Она также прекращается в случае повторного совпадения выбранных подмножеств, в частности, когда противники два раза подряд пропускают ход (то есть оба раза выбирают пустое множество). Более сложное условие прекращения партии состоит в циклическом повторении ходов (то есть, когда последовательность совпадений выбираемых подмножеств зацикливается). Впрочем, последний исход крайне маловероятен.
Объединение всех выбранных каждым игроком подмножеств будем называть его набором.
Выигрывает тот игрок, который набрал больше объектов из U, то есть чей набор имеет бóльшую мощность.
Иными словами, общий выигрыш достигается максимальным объединением минимальных множеств.
Приведем пример партии.
Петя играет против Маши. Исходное множество объектов состоит из 15-ти разноцветных фигурок, изображенных на рис. 1.
Чтобы игроки не жульничали, им предлагается втайне друг от друга записывать ходы (множества выбираемых фигурок) на бумажке. Судья контролирует соответствие совершаемых ходов записанным.
Итак, игроки делают первый ход: Петя выбирает зеленый треугольник и четырехконечную звезду, а Маша – облачко, шестиугольник и левую стрелку (рис. 2).
Так как подмножества Пети и Маши не пересеклись, игроки забирают выбранные фигурки и кладут их в свои наборы (рис. 2).
Теперь от исходного множества осталось 10 фигурок (рис. 3).
Игроки делают второй ход. Петя жадничает и выбирает целых пять фигурок – сердечко, пятиконечную звезду, верхнюю стрелку, правую стрелку и кружочек. Маша выбирает 4 фигурки – молнию, пятиконечную звезду, верхнюю стрелку и квадратик (рис. 4).
Подмножества пересеклись. Мощность Машиного подмножества меньше: поэтому она забирает выбранные фигурки, а Петя не забирает ничего (рис.5).
От исходного множества осталось шесть фигурок (рис. 6).
Игроки делаю третий ход. Петя выбирает кружок и шестиконечную звезду, Маша – пятиугольник и шестиконечную звезду (рис. 7).
Так как выбранные подмножества равномощны, игроки забирают выбранные фигурки кроме шестиконечной звезды, входящей в оба подмножества (рис. 8).
Попутно отметим, что в последнем случае прорабатывается понятие разности множеств.
От исходного множества осталось четыре фигурки (рис. 9).
Игроки делают четвертый ход, причем выбирают одно и то же подмножество, состоящее из правой и нижней стрелки (рис. 10).
Так как подмножества одинаковы, противники не забирают ничего.
Игроки делаю пятый ход. Петя выбирает шестиконечную звезду, Маша – ее же и нижнюю стрелку (рис. 11).
Подмножества пересеклись. Так как мощность Петиного множества меньше, чем Машиного, он забирает выбранную фигурку объект, Маша не забирает ничего (рис. 12).
От исходного множества осталось три фигурки (рис. 13).
Игроки делают шестой ход. Петя выбирает правую стрелку, Маша – сердечко (рис. 14).
Так как подмножества не пересеклись, игроки забирают выбранные фигурки (рис. 15).
От исходного множества осталась лишь одна фигурка (рис. 16)
Партия закончена. Петя набрал 5 фигурок, Маша – 10. Маша выиграла.
Математический комментарий
Найдем оптимальные стратегии для игроков в хапе.
Во-первых, ясно, что игра распадается на следующие друг за другом независимые одноходовые подыгры со своими исходными множествами, мощность которых уменьшается от подыгры к подыгре.
Каждый полуход состоит из двух последовательных действий – выбора мощности подмножества и выбора объектов для него. Очевидно, что если мощность подмножества выбрана, то его элементы можно уже выбирать случайным образом (ведь все элементы универсального множества равнозначны, а при пересечении сравниваются только мощности).
Поэтому сосредоточим наш поиск стратегий на первом этапе, т. е. на выборе мощности подмножества.
Получить 10 полезных материалов для развития мышления ребенка в телеграм
🔔 Подпишитесь — расскажем, как превратить «не хочу» в «дай задачу посложнее».
Вам может быть интересна статья: