Алгоритм "забери номер в игре" - PullRequest
Новая
       48

Алгоритм "забери номер в игре"

7 голосов
/ 11 ноября 2011

Я изо всех сил пытаюсь найти какое-то решение, но понятия не имею об этом.

RobotA и RobotB, которые для начала выбирают перестановку из N чисел. RobotA выбирает первым, и они выбирают поочередно. Каждый ход только роботы могут выбрать любое оставшееся число из перестановки. Когда оставшиеся числа образуют возрастающую последовательность, игра заканчивается. Робот, который выбрал последний ход (после которого последовательность увеличивается) выигрывает игру.

Предполагая, что оба играют оптимально, кто победит?

Пример 1: 

 The original sequence is 1 7 3. 
 RobotA wins by picking 7, after which the sequence is increasing 1 3.

Пример 2: 

 The original sequence is 8 5 3 1 2.
 RobotB wins by selecting the 2, preventing any increasing sequence.

Есть какой-нибудь известный алгоритм для решения этой проблемы? Пожалуйста, дайте мне какие-либо советы или идеи о том, где посмотреть, было бы очень благодарно!

Ответы [ 4 ]

4 голосов
/ 12 ноября 2011

Учитывая последовательность 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, я полагаю, посвящен подобным играм.

3 голосов
/ 11 ноября 2011

Похоже на Минимакс проблему.

1 голос
/ 11 ноября 2011

Я думаю, что есть более быстрое решение для этой задачи. Я подумаю. Но я могу дать вам представление о решении со сложностью 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

Pick 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) </p>

0 голосов
/ 12 ноября 2011

Вот код Python для алгоритма Ветра Мудрости.Распечатывает победы для 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)
...