Динамическое программирование: шахматная доска

Question

Ладья начинается в левом верхнем углу стандартной шахматной доски 8 на 8. Два игрока по очереди перемещают ладью либо горизонтально вправо, либо вертикально вниз, как и многие квадраты, как им нравится. Стационарные ходы не допускаются, и игрок 1 идет первым. Победителем является игрок, который размещает ладью на правом нижнем углу. Скажите, кто выиграет и охарактеризует выигрышную стратегию.

У меня проблема с вышеуказанным выражением, и мне интересно узнать, как другие будут обращаться к проблеме. Я знаю, что есть способ рассчитать разные пути, которые может принять ладья. Я попытался сделать проблему вручную, и всегда казалось, что Игрок 2 всегда выигрывал, но я мог бы думать об этом слишком просто. Приближение к нему в стиле динамического программирования показалось хорошим выходом. Во всяком случае, у кого-нибудь есть идеи, алгоритмы или такие, которые подходят к этой проблеме!

Answer 1

H8 является коробкой победителя, так что все выше и слева от него находится проигравший коробок.

Все слева и справа от G7 (G8 и H7) - это проигравший бокс, так что это поле победителя.

G7 является полем победителя, поэтому все выше и слева от него является полем неудачника.

И так далее ...

Игрок один, который начинает игру есть только выбор, чтобы пойти в поле проигравшего так игрока два всегда побеждает.

Все, что нужно сделать двум игрокам, - это переходить в поле w каждый раз, когда наступает его очередь.

Answer 2

Второй игрок всегда выигрывает за шахматную доску любого размера. Доказательство индукции по размеру доски.

Случай n = 1 можно игнорировать, поэтому начните с n = 2; ясно, что игрок 2 выигрывает на плате 2x2.

Предположим, что игрок 2 всегда выигрывает на доске размером n или меньше. На доске размером n + 1 игрок 1 переходит в позицию в левом столбце или в верхней строке. Затем игрок 2 переместится в позицию по диагонали (это все, что вам нужно), которая является исходной позицией на доске размером n или меньше.

КЭД

Answer 3

выигрышная позиция обладает следующими свойствами:

• Всех терминальными позиции выигрышными. В этом случае позиция (8, 8) является выигрышной позицией
• Все позиции, которые могут достигать позиции цели в шаге, являются выигрышными позициями. I.e. все позиции в последней строке или столбце выигрышной позиции
• Если мы можем перейти к проигрышной позиции, то мы находимся в выигрышной позиции, так как следующий игрок не может выиграть игру
• Если мы только в состоянии перейти к тогда мы находимся в проигрышной позиции

С учетом этого мы можем создать алгоритм, который может сказать нам, является ли текущая позиция выигрышной или проигравшей. Использование таблицы (dpTable) для хранения ранее вычисленных результатов позволит избежать повторных вычислений.

boolean isWinning(int x, int y) { 
    if (dpTable[x][y] != null) 
     return dpTable[x][y]; 

    // From the last row or the last column we can always win the game 
    if (x == n || y == n) 
     return true; 

    for (int i = 1; x + i <= n; i++) { 
     // Moving right 
     if (x + i <= n && !isWinning(x+i, y) { 
      dpTable[x][y] = true; 
      return true; 
     } 

     // Moving down 
     if (y + i <= n && !isWinning(x, y+i) { 
      dpTable[x][y] = true; 
      return true; 
     } 
    } 

    dpTable[x][y] = false; 
    return false; 
} 

isWinning(x, y) функция возвращает true, когда, начиная с позиции (х, у), вы можете выиграть игру, играя оптимально и false, когда нет никакого способа для вас, чтобы начать с (х, у) и выиграть.

Answer 4

Я думаю, стоит отметить, что игра, описанная на самом деле, представляет собой игру Nim с двумя сваями по семи монет. Победитель игры Nim можно определить, побив количество монет в каждой куче. Они называют это Nim-sum и дают значение функции Sprague-Grundy. Позиция выигрывает всякий раз, когда Nim-sum положительна. Итак, учитывая вашу игру: 7^7 = 0, что является проигрышной позицией. Каждая диагональная позиция проигрывает, поскольку для любого x, x^x всегда 0.
Хорошо, что с помощью этой техники вы можете играть (и выигрывать) эту игру в трехмерном и сколь угодно большом пространстве, а также в 4- , 5-мерный и т. Д.