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

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

Чтобы лучше понять суть этой стратегии, рассмотрим несколько примеров. Сначала мы рассмотрим три кучки с 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

В начале 50-х годов XX века инженеры английской компании Ferranti создали первый компьютер, предназначенный только для игр. Он назывался NIMROD. Первые три буквы NIM означали игру, для которой он и был спроектирован. На панели компьютера находились светящиеся лампочки, которые представляли положение фишек в игре. Прототип компьютера был представлен на выставке «Фестиваль Британии» в 1951 году. Считается, что это послужило началом эпохи электронных игр.

Теперь второй игрок должен сделать такой ход, чтобы сумма цифр в правом столбце стала четной, а остальные не изменились, так как они уже четные. Значит, нужно взять одну фишку из любой кучки, кроме второй. В двоичной системе это означает, что нужно заменить 1 на 0 в правом столбце.

Хотя найти стратегию игры Ним было намного сложнее, чем для предыдущих игр, о которых мы рассказали, для всех этих игр справедлива одна общая идея. Нужно найти равновесную ситуацию, которая совпадает с конечным положением, и определить, какой из игроков всегда сможет сохранять подобную ситуацию, а какой — никогда. Так, в первой игре этой главы («Игра 1: выигрывает первый») равновесная ситуация такова: нужно оставить на столе число фишек, кратное 3. Во второй игре («Игра 2: выигрывает второй») нужно записать число, кратное 11, а в последней игре Ним нужно оставить в каждой кучке такое число фишек, чтобы при записи количества фишек в двоичной системе сумма цифр в столбцах всегда была четной.