Определить выигрышную стратегию для первого игрока

Question

подскажите, как можно ещё подойти к решению такой задачи.
Есть поле размером m×n, которое разделено на сектора размером 1×1.
В левом верхнем углу стоит фишка, которую игроки могут поочерёдно двигать либо на один сектор вниз, либо на один сектор вправо, либо на k секторов по диагонали. Ходить начинает первый.
Проигрывает игрок, который не может сделать ход, т.е. выиграет тот, кто первый поставит фишку в правый нижний угол.

Входные данные:
t - количество партий, в которые нужно сыграть, k - количество ходов по диагонали.(1≤ t ≤ 20; 1≤ k ≤10^9)
n, m - размер игрового поля. (1 ≤ n,m ≤ 10^9).

Выходные данные:
Вывести t-строк результатов игры. В случае, если первый игрок имеет выигрышную стратегию - выведите "+", иначе "-"(Без кавычек).

Как я рассуждал:
Замечу, что количество пройденных клеток, необходимое для победы одного из игроков, константно и равно n+m - 2 .
Во вторых, я обратил внимание на чётность суммы сторон.
Ситуация 1 : Если сумма сторон чётна - по умолчанию первый игрок проиграет, если и первый и второй не смогут использовать хождение по диагонали.
Ситуация 2 : Если сумма сторон нечётная - выигрывает первый игрок, опять же, если не будет ни у кого возможности ходить по диагонали. Другими словами, если k ≥ min(m,n). Если же у нас есть возможность хождения по диагонали, то каждый игрок может применить её в своих целях.

Например, в первой ситуации, если 1 игрок походит по диагонали, то он перетянет победу на себя. Иными словами, если максимальное количество шагов по диагонали (min(m,n) - 1) / k нечётное - у первого игрока есть шанс выиграть.

Во второй ситуации всё наоборот. Только если максимальное количество шагов по диагонали (min(m,n) - 1) / k чётное - у первого игрока есть шанс выиграть.

Мой код:

#include <iostream>

using namespace std;

int main()
{
    int times, k, size, min;
    cin >> times >> k;
    size = times * 2;
    int* arr = new int[size];
    for (int i = 0; i < size; i += 2)
    {
        cin >> arr[i] >> arr[i + 1];
    }

    for (int i = 0; i < size; i += 2)
    {
        arr[i] < arr[i + 1] ? min = arr[i] : min = arr[i + 1];
        if (!((arr[i] + arr[i + 1]) % 2))
        {
            if ((min - 1) / k % 2) cout << "+" << endl;
            else cout << "-" << endl;
        }
        else
        {
            if (k < min)
            {
                if (!((min - 1) / k % 2)) cout << "+" << endl;
                else cout << "-" << endl;
            }
            else cout << '+' << endl;
        }
    }
    return 0;
}

Буду рад любым советам!

Answer 1

Давайте сначала абстрагируемся от конкретной задачи и поговорим о теории игр.

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

Если хотя бы один переход из данного состояния ведет в проигрышное состояние, то данное состояние называем выигрышным. И наоборот, если все переходы из данного состояния ведут в выигрышные, то назовем данное проигрышным. Учитывая, что мы знаем, какие состояния являются конечными и результаты игры в них, то мы можем вычислить функцию "выигрышности" для всех состояний, включая начальное.

Заметим, что в данной игре состояния задаются только положениями фишки, размерами поля и константой K. (На самом деле, состояния однозначно задаются даже только размерами поля, так как при каждом переходе мы фактически начинаем новую игру в левом верхнем секторе какого-то меньшего прямоугольника, сменив текущего игрока). Тогда можно для каждого сектора зафиксированного игрового поля вычислить функцию "выигрышности" по ее определению.

a[n][m] = 0
a[y][x] = !(a[y][x + 1] & a[y + 1][x] & a[y + k][x + k])

Но в данной задаче вычисление этой функции для всех состояний игры является невозможным за разумное время, поэтому игру нужно "хакнуть". Для этого я предлагаю вам написать программу, которая вычислит функцию "выигрышности" для каких-то небольших конкретных полей. (Например n = 20, m = 20, k = 3). Тогда хорошо присмотревшись к полученной матрице, вы сможете увидеть простые закономерности, которые вам лично даже не нужно доказывать, чтобы решить задачу - это проблема составителей задачи.

На всякий случай приведу тут набросанный код на питоне и его вывод для вышеприведенных чисел:

def print_m(a):
    for i in a:
        print(' '.join([str(j) for j in i]))

n, m = 20, 20
k = 3

a = [['-'] * m for _ in range(n)]

for y in range(n - k, n):
    for x in range(m):
        a[y][x] = (m - x + n - y) & 1
for y in range(n):
    for x in range(m - k, m):
        a[y][x] = (m - x + n - y) & 1

for y in range(n - k - 1, -1, -1):
    for x in range(m - k - 1, -1, -1):
        if a[y][x + 1] == 0 or a[y + 1][x] == 0 or a[y + k][x + k] == 0:
            a[y][x] = 1
        else:
            a[y][x] = 0

print_m(a)

1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

Answer 2

Обозначим:

x, y - текущие координаты
i - номер игрока

Тогда

Если x<k || y<k, то просто проверяем чётность.
Иначе если x==k || y==k, то точка (x, y) выигрышная.

Иначе считаем следующее (все ходы возможны):

best
(
  (x+k, y+k, i^1)
  worst((x+k+1, y+k, i), (x+k+1, y+k-1, i))
  worst((x+k, y+k+1, i), (x+k-1, y+k+1, i))
)

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

PS: Попозже объясню, как я это при думал.

БЛОГ НА HUSL

Определить выигрышную стратегию для первого игрока

Ответы (2 шт):