解决积木问题所需的算法

Question

考虑以下场景:

1. 我们有许多顺序构建 block (例如 12 个构建 block ，从 1 到 12 排序)，随机(但不一定均等)分布在多个构建器上(例如 3 build 者)。
2. builder 必须按顺序工作并从 4 号街区开始 build 隔离墙，双向；向下到第 1 block 或向上到第 12 block 。
3. 每个 builder 不知道其他 builder 可能拥有的区 block 编号，尽管他知道有多少。
4. builder 必须通过阻止其他人进行移动来尝试先完成任务。 如果可以的话，他们不应该通过并且必须放置障碍物。任何第一个完成所有区 block 的 builder 将获得最高奖励，然后是第二个，依此类推...

我们能否预测谁将获得第一名、第二名和最后一名？构建者是否应该遵循任何算法来首先完成他们的工作？

下面是问题的实际例子:
让我们说:

builder 1 has: b2 b5 b8 b9
builder 2 has: b1 b11
builder 3 has: b3 b4 b6 b7 b10 b12

builder 1和 builder 2必须等待 builder 3放置b4。
builder 3 将放置 b4，并将他的位置归还给 builder 1。

wall: b4

builder 1 将不得不放置 b5，因为他别无选择。

wall: b4 b5

builder 2 会跟进，但他不能放置他的积木，他将不得不等待 b2 或 b10。
Builder 3 现在有两个选项:b3 或 b6，他必须选择帮助他先完成的那个。

wall: b4 b5 b6

builder 1 无事可做，他将轮到 builder 2。
builder 2还在等待b2或b10的安装。
builder 3 必须放置 b7。

wall: b4 b5 b6 b7

builder 1 现在将放置 b8。

wall: b4 b5 b6 b7 b8

builder 2还在耐心等待中……
builder 3 被迫放下 b3，因为没有其他选择，他希望 builder 2 可以放置 b9... 但他的希望破灭了!

wall: b3 b4 b5 b6 b7 b8

builder 1 现在完全负责了，感觉很开心!但他很困惑!在思考之后，他决定 b2 可能允许他继续阻止更多的 block ，这反过来又增加了他的机会。

wall: b2 b3 b4 b5 b6 b7 b8

builder 2 说:终于!一些行动!并放置 b1。

wall: b1 b2 b3 b4 b5 b6 b7 b8

builder 3 失去了成为第一的希望!
builder 1 现在将安装他的最后一个区 block 并带着最大的奖励回家!

wall: b1 b2 b3 b4 b5 b6 b7 b8 b9

builder 2 将等待...
Builder 3 遗憾地放置了 b10
builder 2 放置 b11 并带着第二个奖励回家......

有解决此类问题的已知算法吗？

Answer 1

乍一看，球员的力量是他最高和最低盖帽所跨越的范围的函数。在您的示例游戏中，我们可以看到 Builder 1 完全支配 Builder 2。

Builder 1:            2 ----------- 9   
Builder 2:          1 ----------------- 11
Builder 3:              3 --------------- 12

Start position:           ^^

由于游戏从 b4 开始，所以最重要的棋子都在高端。例如，Builder 3 有 b3，它阻止了其他 2 个移动(b2 和 b1)；但是，这不是很决定性的。阻止 b2 和 b1 的 block b3 仅与阻止 b6 和 b7 的 b5 一样强大。

真正的力量在上图的右侧。这意味着具有上述初始起始范围的游戏通常会这样结束:Builder 1、Builder 2，然后是 Builder 3。

至于玩家策略，这里有一个公认的推测性指南:捕获你最强大的棋子，也就是那些能阻止其他玩家移动最多的棋子。在此策略中，您持有的每一 block 棋子都可以根据它阻止的其他移动次数分配一个分数。

例如，假设墙位于 b3-b4-b5，而您持有 b2、b6 和 b9。您可以玩 b2 或 b6。你如何评价你的作品？

b2 score = 1 (prevents b1)
b9 score = 3 (prevents b10, b11, b12)
b6 score = 2 (prevents b7, b8)

请注意，b6 不会因为阻止 b10 和更高版本而获得荣誉，因为 b9 正在做这项工作(Matthieu M. 也指出了这一点)。在这种情况下，您应该更愿意先玩 b2，因为它使您面临其他玩家完成游戏的风险最小。

其他答案提出了不想阻碍自己进步的有趣想法，建议先打b6。但我认为加速向 b9 的移动不会有任何好处。你想尽可能地延迟 b9，因为它是最能保证(从概率的角度)防止其他玩家完成的棋子。

更新:

我编写了一个 Perl 模拟来测试一些简单的玩家策略。我开始怀疑玩家策略是否无关紧要。我尝试了以下方法:(a)选择最高的方 block ； (b) 选择最低的方 block ； (c) 我推荐的策略是选择最安全的区 block (防止其他人移动最多的区 block )。我通过授予第一名 3 分、第二名 2 分和第三名 1 分来评估这些策略。这些策略中没有一个始终比随机选择表现更好(或更差)。

当然，可以设想玩家的选择会影响结果的场景。例如，如果 block 是这样分布的，玩家 3 将获得第一名或第二名。

b1  b2  b3  b4  b5  b6  b7  b8  b9  b10  b11  b12
2   1   3   1   3   2   2   2   2   2    2    2

然而，从概率的角度来看，这种结果变化可以简化为:玩家 3 将获胜，除非他选择了与仅剩一个方 block 的玩家相邻的方 block 。换句话说，准确的结果是掷硬币。

所以问题来了:谁能提供一个结果既不是命中注定也不是掷硬币的场景？我试了大约 15 分钟，然后就觉得无聊了。