Читать «Дилемма заключенного и доминантные стратегии. Теория игр» онлайн - страница 22
Хорди Деулофеу
Все подобные игры, в которых используется только одна группа фишек, можно считать упрощенными вариантами игры Ним, о которой мы поговорим далее.
Сложная стратегия: игра Ним
Все игры, о которых мы говорили до этого, можно обобщить еще больше: будем считать, что фишки лежат не в одной кучке, а в нескольких. Число кучек произвольное и конечное. В начале игры Ним фишки на столе лежат в нескольких кучках. Число фишек в кучках может отличаться. По правилам на каждому ходу игрок может брать минимум одну и максимум все фишки из выбранной кучки. Выигрывает тот, кто берет последнюю фишку. Также можно поменять правила и считать проигравшим того, кто должен взять последнюю фишку.
В начале игры на столе три кучки, состоящие из 1, 3 и 5 фишек. На каждом ходу игрок берет любое число фишек из выбранной кучки (минимум одну фишку, максимум все). Выигрывает тот, кто забирает последнюю фишку. Для какого игрока существует выигрышная стратегия?
Анализ игры позволяет увидеть, что такая стратегия существует для первого игрока, но из всех возможных начальных ходов только один гарантирует победу. Если читатель попрактикуется в этой игре, то увидит, что ни одному из игроков не выгодно делать следующие ходы:
1. Оставлять на столе две кучки с одинаковым числом фишек.
2. Забирать все фишки из одной кучки.
Если игрок А выполняет ход 1, игрок Б забирает все фишки из третьей кучки и выигрывает, симметрично повторяя ходы соперника. Если игрок А забирает из одной кучки гг фишек, игрок Б забирает столько же фишек из другой, и, когда А заберет все фишки из одной кучки, игрок Б заберет все фишки из другой и выиграет. Аналогично если игрок А совершит ход 2, то Б заберет нужное число фишек из той кучки, в которой их осталось больше. На столе останутся две одинаковые кучки, и игрок Б снова одержит победу, действуя как в предыдущем случае. Поэтому победу одерживает тот, кто заставит противника совершить один из двух «запрещенных» ходов. В рассматриваемом случае, если первый игрок берет 3 фишки из кучки, в которой 5 фишек, на столе останутся три кучки с 1, 2 и 3 фишками. Первый игрок выигрывает, так как его соперник будет вынужден или взять все фишки из одной кучки, или уравнять число фишек в двух кучках (оставив в них по 1 или по 2 фишки).
Очевидно, что это слишком частный случай и его сложно обобщить на произвольное число кучек и даже для трех кучек, но с большим числом фишек. Несмотря на это, математические методы позволяют найти выигрышную стратегию общего вида, применимую для любого количества кучек и фишек в каждой из них. Для этого нужно записать число фишек в каждой кучке в двоичной системе так, чтобы единицы были записаны под единицами. Каждым ходом четность как минимум в одном из столбцов будет меняться, так как после каждого хода будет изменяться только одно из чисел в одном или нескольких столбцах. Как минимум одна из цифр изменится с 1 на 0 или наоборот. Если в начальном расположении фишек сумма всех цифр каждого столбца четна, существует выигрышная стратегия для второго игрока: он должен ходить так, чтобы после хода сумма цифр во всех столбцах была четной. Первый игрок не может сделать такой ход. Если же хотя бы в одном столбце сумма цифр нечетна, то выигрышная стратегия существует для первого игрока: первым ходом он сможет сделать сумму цифр во всех столбцах четной и довести игру до победы.
