python - 逻辑游戏 : maximising (or minimising) the chances for two agents to meet

Question

Note: this question is tagged both language-agnostic and python as my primary concern is finding out the algorithm to implement the solution to the problem, but information on how to implement it efficiently (=executing fast!) in python are a plus.

游戏规则:

• 假设有两个团队，其中一个是A 代理 (An)，另一个是B 代理 (Bn)。
• 在游戏空间中有一定数量的可用插槽(Sn)可以被占用。
• 在每个回合中，每个代理都会获得他/她可以占用的一个插槽子集。
• 一个代理一次只能占据一个位置，但是每个位置可以由两个不同的代理占用，前提是他们来自不同的团队。

问题:

我正在尝试找到一种高效方法来计算A 代理的最佳可能移动，其中“最佳可能移动”是指最大化或最小化占用团队 B 占用的相同位置的机会。 B 队的行动是事先不知道的。

示例场景:

这个场景故意是微不足道的。它只是为了说明游戏机制。

A1 can occupy S1, S2
A2 can occupy S2, S3
B1 can occupy S1, S2

在这种情况下，解决方案很明显:A1 → S1 和 A2 → S2 是保证满足 B1 的选项 [as B1无法避免占用S1或S2]，而A2→S3和A1→随机(S1, S2) 是能够最大程度避免 B1 的机会。

现实生活场景:

在现实场景中，插槽可能有数百个，每个团队中的代理人可能有几十个。到目前为止，我尝试的天真实现的困难在于，我基本上考虑了团队 B 的每组可能的 Action ，并为 A 。因此，我的计算时间呈指数增长。

不过，我不确定这是一个只能通过“蛮力”解决的问题。即使是这种情况，我也想知道:

1. 如果最佳蛮力解决方案必然呈指数增长(时间方向)。
2. 如果有一种方法可以计算出局部最优的非最优解。

谢谢!

Answer 1

两个团队的成员和插槽定义了一个三方图 A-S-B，边由可能的移动给出。由插槽和仅一个团队的成员组成的二分图很有趣；将这些 A-S 称为团队 A 成员的图形，将这些称为 S-B 用于团队 B 成员。您可以使用 S-B 图为槽位赋值，然后使用 S-A 图选择能够最大化或最小化 A 队值(value)的 Action 。

An appropriate choice for the value of a slot is the likelihood of finding a member of team B in that slot.因此，团队 A 的一组移动的值是插槽值的总和，即，将找到团队 B 成员的预期插槽数。请注意，团队成员的移动不是独立的，因此两个阶段都存在一些挑战。

给定槽的值，为 A 队选择移动成为一个标准问题:assignment problem .这与 missingno 的答案中建议的最大二分匹配有关，但需要考虑插槽的值；可以给边缘赋予等于边缘入射的槽的值的权重，最大加权二分匹配等同于分配问题。使用标准算法来解决(或近似)这部分问题。

那么我们如何给槽赋值呢？我建议只为 B 队的成员生成随机移动，计算插槽被占用的频率，然后将计数除以您考虑的样本移动数。从这个问题中并不清楚生成一组随机 Action 有多难；假设每个团队成员都可以选择留在原地，只需按随机顺序为每个成员随机选择移动即可轻松完成。

两个阶段的一个简化因素是，有一种简单的方法可以将问题分解为独立的子问题。二分图的连接组件显示哪些团队成员可以以干扰其他人的方式移动，例如，如果团队成员在棋盘的不同部分分成两组，则可以独立对待这些组。这适用于两个阶段，即使用 S-B 图对槽进行概率评估，并优化 A-S 图中的分配。当然，如果任何组件足够小，您总是可以枚举可能性并精确地解决子问题。