Читать «Дилемма заключенного и доминантные стратегии. Теория игр» онлайн - страница 23
Хорди Деулофеу
Чтобы лучше понять суть этой стратегии, рассмотрим несколько примеров. Сначала мы рассмотрим три кучки с 1, 3 и 5 фишками (это игра 4, которую мы решили ранее). Затем мы перейдем к более привычной версии игры Ним под названием Мариенбад. В ней четыре кучки с 1, 3, 5 и 7 фишками.
В первом случае число фишек в кучках равно 1, 3 и 5.
1 в двоичной системе: 1
3 в двоичной системе: 11
5 в двоичной системе: 101
Сложим единицы в каждом столбце и увидим, что сумма цифр каждого столбца нечетная (справа налево: 3, 1 и 1). В этом случае существует выигрышная стратегия для первого игрока. Для этого ему нужно ходить так, чтобы суммы цифр во всех столбцах оставались четными. Единственный способ сделать это — забрать фишки из кучки, где их 5 (101), оставив 2 (10), то есть забрать 3 фишки из кучки с 5 фишками. Получим:
1 в двоичной системе: 1
3 в двоичной системе: 11
2 в двоичной системе: 10
Теперь сумма цифр в каждом столбце четная. Любой ход второго игрока сделает сумму цифр в одном из столбцов нечетной. После этого первый игрок сможет снова сделать все суммы цифр четными и так далее до финального положения. В финальном положении все цифры будут равны 0. Ноль — четное число, то есть суммы цифр во всех столбцах снова будут четными.
На столе четыре кучки фишек. В кучках лежат 1, 3, 5 и 7 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?
Аналогично предыдущему случаю получим:
1 в двоичной системе: 1
3 в двоичной системе: 11
5 в двоичной системе: 101
7 в двоичной системе: 111
Так как в начальной позиции суммы цифр в каждом столбце четные, первый игрок не может выиграть. Выигрышная стратегия существует для второго игрока. Любой ход первого игрока сделает сумму цифр хотя бы в одном столбце нечетной. Допустим, что первый игрок взял одну фишку из кучки с тремя фишками. Получим:
1 в двоичной системе: 1
2 в двоичной системе: 10
5 в двоичной системе: 101
7 в двоичной системе: 111
NIMROD
В начале 50-х годов XX века инженеры английской компании Ferranti создали первый компьютер, предназначенный только для игр. Он назывался NIMROD. Первые три буквы NIM означали игру, для которой он и был спроектирован. На панели компьютера находились светящиеся лампочки, которые представляли положение фишек в игре. Прототип компьютера был представлен на выставке «Фестиваль Британии» в 1951 году. Считается, что это послужило началом эпохи электронных игр.
