Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

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

Как только мы узнали выигрышную стратегию для любой игры типа Ним, возникает вопрос: можно ли создать игру подобного типа, для которой бы не существовало выигрышной стратегии в общем случае? Ответ на этот вопрос положительный и ведет нас к так называемым играм типа Нимбус. Эти варианты игры Ним имеют одно существенное отличие: если мы хотим взять больше одной фишки из определенного ряда (кучки), это можно сделать только тогда, когда фишки расположены рядом, то есть между ними нет промежутков, образованных после предыдущих ходов. Появляется правило, касающееся расположения фишек в рядах, что раньше не учитывалось. Это аналогично следующему: всякий раз, когда мы берем фишки из ряда, этот ряд разделяется на два. Это будет происходить всегда, если мы не будем снимать одну из крайних фишек. Поскольку образуются новые кучки, игра меняется так, что для нее уже нельзя использовать стратегию игры Ним.

Это позиционная система счисления, в которой любое число можно представить с помощью всего двух цифр: 0 и 1. Чтобы преобразовать двоичное число в десятичное, нужно заменить все единицы степенями двойки. Показатели этих степеней будут зависеть от позиции цифры: правый разряд соответствует 2 0, следующий — 2 1и так далее. Например, двоичное число 110101 в десятичной системе выглядит так: 1 • 2 0+ 0 • 2 1+ 1 • 2 2+ 0 • 2 3+ 1 • 2 4+ 1 • 2 5= 1 + 4 + 16 + 32 = 53.

Аналогично для записи десятичного числа в двоичном виде нужно разделить его на 2, полученный результат снова разделить на 2 и так далее до тех пор, пока результатом деления не будет 1. Последний результат деления будет первой цифрой справа. Все прочие остатки отделения, от последнего к первому, составят следующие разряды (остаток от деления на 2 может равняться только 0 или 1). Например, 39 в двоичной системе записывается как 100111, так как 39:2 дает 19 (и остаток 1), 19:2 дает 9 (остаток 1), 9:2 дает 4 (остаток 1), 4:2 дает 2 (остаток 0), 2:2 дает 1 (остаток 0). Мы выразили число в виде суммы степеней двойки.

Итак, 39 =1 + 2 + 4 + 32 = 1•2 0+1•2 1+1•2 2+0•2 3+0•2 4+1•2 5= 100111 по основанию 2. Хотя двоичная нотация появилась сравнительно недавно, свойство, на котором она основана («всякое число можно представить в виде суммы различных степеней двойки»), было известно и применялось еще в древности. Например, древние египтяне использовали для умножения такую систему. Один из сомножителей удваивался, второй делился на 2. Если число было нечетным, то на 2 делилось предыдущее число. Этот метод дает верный результат именно благодаря указанному свойству.

Страница бюллетеня Французской академии наук, посвященная двоичной системе счисления, разработанной Лейбницем в 1703 году.

Вращаем кубик. Это стратегическая игра для двух игроков. Первый игрок ставит кубик на стол выбранной стороной вверх. Второй игрок поворачивает кубик на четверть оборота так, что на верхней грани будет уже другое число очков, и прибавляет это число к первому. Затем каждый игрок по очереди вращает кубик на четверть оборота (так можно получить любое число, кроме тех, что расположены на верхней или нижней грани кубика) и прибавляет число очков на верхней грани к общей сумме. Тот, кто набирает в сумме 31, выигрывает.

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать?

Разрезаем прямоугольник. Это стратегическая игра для двух игроков. На листе бумаги в клетку нужно нарисовать прямоугольник размерами 17 × 15 клеток. Затем нужно пометить квадратик в нижнем правом углу. Каждый из игроков своим ходом делит прямоугольник на две части вертикальной или горизонтальной линией и удаляет ту часть прямоугольника, которая не содержит маленький отмеченный квадрат. Тот, кто не сможет разделить прямоугольник (то есть от прямоугольника останется только один отмеченный квадратик), проигрывает.