“选号游戏”的算法

Question

我正在努力寻找解决方案，但我对此一无所知。

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.

有任何已知的算法可以解决这个问题吗？请给我任何关于在哪里查看的提示或想法，我将非常感激！

Answer 1

给定一个由不同数字组成的序列 w，令 N(w) 为 w 的长度，令 L(w) code> 是 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，则对于生成的排列 < code>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 的降序子序列时，游戏结束。这个游戏起源于 Erdos 和 Szekeres 定理，可以在 单调序列游戏，以及这个幻灯片演示也是一个很好的参考。

如果您想了解更多有关博弈论的一般知识，或者特别是此类博弈的知识，那么我强烈推荐 Berlekamp、Conway 和 Guy 撰写的《数学游戏的获胜之道》。我相信，第三卷讨论了这类游戏。

Answer 2

看起来像一个 Minimax 问题。

Answer 3

我想这个任务有更快速的解决方案。我会想。
但我可以给你一个复杂度为 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

让我们使用这个作为移动，而不是仅仅选择。也很容易看出游戏是等价的，当且仅当玩家 A 在原始游戏中获胜时，玩家 A 在某些排列中获胜。

让我们为 N 个数字、N-1 个数字、...2 个数字的所有排列给出一个代码。

定义 F(x) -> {0; 1}（其中 x 是排列代码）是函数，当前

玩家获胜时为 1，如果当前玩家失败则为 0。很容易看出 F(1 2 .. K-1 K) = 0。

如果至少有一次移动将 x 转换为 y，并且 F(y) = 0，则

F(x) = 1。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)

Answer 4

这是 Wisdom 的 Wind 算法的 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)