1. Игра "Ферзя в угол"
Рассмотрим игру «Ферзя в угол» для двух игроков.
В левом верхнем углу доски размером n × m находится ферзь, который может двигаться только вправо-вниз.
Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз,
либо по горизонтали вправо, либо во диагонали вправо-вниз.
Игрок, который не может сделать ход — проигрывает, иными словами, выигрывает игрок, который поставит ферзя
в правый нижний угол.
Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока.
Эту задачу также можно решить при помощи динамического программирования. Будем заполнять доску знаками «+» и «--».
Знак «+» будет означать, что данная клетка является выигрышной для ходящего с неё игрока (то есть если ферзь
стоит в этой клетке, то игрок, который делает ход, может всегда выиграть), а знак «--» означает, что он проигрывает.
Клетки последней строки, последнего столбца и диагонали, ведущей из правого нижнего угла необходимо отметить, как «+»,
так как если ферзь стоит в этой клетке, то ходящий игрок может выиграть одним ходом:
+ ? ? ? ? +
? + ? ? ? +
? ? + ? ? +
? ? ? + ? +
? ? ? ? + +
+ + + + + -
Но в правом нижнем углу необходимо поставить знак «--» — если ферзь стоит в углу, то тот игрок, которых должен
делать ход, уже проиграл.
Теперь рассмотрим две клетки, из которых можно пойти только в те клетки, в которых записан знак «+».
В этих клетках нужно записать знак «--» — если ферзь стоит в этих клетках, то какой бы ход не сделал
ходящий игрок, ферзь окажется в клетке, в которой стоит знак «+», то есть выигрывает ходящий игрок.
Значит, тот, кто сейчас ходит — всегда проигрывает.
+ ? ? ? ? +
? + ? ? ? +
? ? + ? ? +
? ? ? + - +
? ? ? - + +
+ + + + + -
Но теперь в те клетки, из которых можно попасть в клетку, в которой стоит знак «-» за один ход, необходимо
записать знак «+» — если ферзь стоит в этой клетке, то игрок, который делает ход, может выиграть, если передвинет
ферзя в клетку, в которой стоит знак «--»:
+ + ? + + +
+ + + + + +
? + + + + +
+ + + + - +
+ + + - + +
+ + + + + -
Дальше таблица заполняется аналогично.
В клетке ставиться знак «+», если есть ход, который ведет в клетку, в которой стоит знак «--».
В клетке ставится знак «-», если все ходы из этой клетки ведут в клетки, в которых записан знак «+».
+ + - + + +
+ + + + + +
- + + + + +
+ + + + - +
+ + + - + +
+ + + + + -
Продолжая таким образом, можно определить выигрывающего игрока для любой начальной клетки.
Реализацию данного алгоритма оставим читателям.