Алгоритм игры «Собери число»

Дана последовательность w различных чисел, пусть N(w) будет длиной w, а L(w) будет длиной самой длинной возрастающей подпоследовательности в w. Например, если

w = 3 5 8 1 4

затем N(w) = 5 и L(w) = 3.

Игра заканчивается, когда L(w) = N(w) или, что то же самое, N(w) - L(w) = 0.

Возвращаясь к игре в обратном порядке, если на ходу RobotX N(w) - L(w) = 1, то оптимальная игра состоит в том, чтобы удалить уникальную букву не из самой длинной возрастающей подпоследовательности, тем самым выиграв игру.

Например, если w = 1 7 3, то N(w) = 3 и L(w) = 2 с самой длинной возрастающей подпоследовательностью 1 3. Удаление 7 приводит к увеличению последовательности, гарантируя, что игрок, удаливший 7, выиграет.

Возвращаясь к предыдущему примеру, w = 3 5 8 1 4, если удалить 1 или 4, то для полученной перестановки u мы получим N(u) - L(u) = 1, поэтому игрок, удаливший 1 или 4, обязательно проиграет компетентному противнику. Однако любая другая игра приводит к победе, поскольку заставляет следующего игрока перейти на проигрышную позицию. Здесь оптимальная игра состоит в том, чтобы убрать любой из 3, 5 или 8, после чего N(u) - L(u) = 2, но после следующего хода N(v) - L(v) = 1.

Дальнейший анализ в этом направлении должен привести к оптимальной стратегии для любого из игроков.

Ближайшая математическая игра, которую я знаю, — это игра монотонной последовательности. В игре монотонной последовательности два игрока поочередно выбирают элементы последовательности из некоторого фиксированного упорядоченного набора (например, 1,2,...,N). Игра заканчивается, когда результирующая последовательность содержит либо восходящую подпоследовательность длины A, либо убывающую подпоследовательность длины D. Эта игра берет свое начало с теоремы Эрдоса и Секереса, и хорошее изложение можно найти в МОНОТОННЫЕ ПОСЛЕДОВАТЕЛЬНЫЕ ИГРЫ и эту слайд-презентацию Брюса Сагана также является хорошим справочником.

Если вы хотите больше узнать о теории игр в целом или о такого рода играх в частности, то я настоятельно рекомендую «Выигрышные пути для ваших математических игр» Берлекэмпа, Конвея и Гая. Том 3, я полагаю, посвящен такого рода играм.

Похоже на проблему Minimax.

Я думаю, что есть более быстрое решение для этой задачи. Я подумаю. Но я могу дать вам идею решения со сложностью O(N! * N^2).

Во-первых, обратите внимание, что выбор числа из N-перестановки эквивалентен следующему:

1. Выберите число из N-перестановки. Пусть это был номер X.

2. Переназначить номера по правилу:

1 = 1

2 = 2

...

X-1 = X-1

X = Ничего, его нет.

X+1 = X

...

N = N - 1

И вы получите перестановку N-1 чисел.

Пример:

1 5 6 4 2 3

Выберите 2

1 5 6 4 3

Переназначить

1 4 5 3 2

Давайте использовать это как ход, вместо того, чтобы просто выбирать. Также легко видеть, что игры эквивалентны, игрок А выигрывает в этой игре для некоторой перестановки тогда и только тогда, когда он выигрывает в оригинале.

Дадим код всем перестановкам из N чисел, N-1 чисел, ... 2 чисел.

Определить F(x) -> {0; 1} (где x — код перестановки) — это функция, которая равна 1, когда текущий

игрок выигрывает, и 0, если текущий игрок терпит неудачу. Легко увидеть F(1 2 .. K-1 K) = 0.

F(x) = 1, если есть хотя бы ход, который переводит x в y, и F(y) = 0.

F(x) = 0, если для любого хода, переводящего x в y, F(y) = 1.

Таким образом, вы можете использовать рекурсию с запоминанием для вычисления:

Boolean F(X)
{
    Let K be length of permutation with code X.
    if you already compute F for argument X return previously calculated result;
    if X == 1 2 .. K return 0;
    Boolean result = 0;
    for i = 1 to K do
    {
         Y code of permutation get from X by picking number on position i.
         if (F(y) == 0)
         {
             result = 1;   
             break;
         }
    }
    Store result as F(X);
    return result;
}

Для каждого аргумента мы будем вычислять эту функцию только один раз. Есть 1! перестановки длины 1, 2! перестановки длины 2 .. N! перестановки длины N. Для длины перестановки K нам нужно выполнить операцию O (K) для вычисления. Таким образом, сложность будет O(1*1! + 2*2! + .. N*N!) =‹= O(N! * N^2) = O(N! * N^2)

Вот код Python для алгоритма Wisdom's Wind. Он выводит выигрыши для RobotA.

import itertools

def moves(p):
    if tuple(sorted(p)) == p:
        return
    for i in p:
        yield tuple(j - (j > i) for j in p if j != i)

winning = set()

for n in range(6):
    for p in itertools.permutations(range(n)):
        if not winning.issuperset(moves(p)):
            winning.add(p)

for p in sorted(winning, key=lambda q: (len(q), q)):
    print(p)