如何对这种人工智能进行建模？

Question

当我玩this游戏时，我想知道控制侦探或罪犯的人工智能是如何工作的。

对于懒人来说，这个游戏的目标很简单：

• 这个棋盘游戏是一个无向图，有4种不同类型的边（对于同一对顶点也可以重叠），每种类型都需要特定种类的票证来移动
• 侦探们拥有一堆票证来在图中移动，每回合只能移动一次（从一个节点到另一个节点）。罪犯也可以进行相同的移动（加上3条专属路径），但是没有票证限制
• 通常情况下，侦探们无法看到罪犯，但是罪犯必须在5个特定回合内露面（然后再次隐藏）
• 如果侦探们在24步之前抓住了罪犯（其中一个侦探必须占据与罪犯相同的单元格），则他们获胜，否则罪犯获胜
• 罪犯必须在每个回合显示他使用的票证，但他还有1张黑票证，每个侦探（假设有5个）可用于验证此事
• 罪犯还有两张2x票证，允许他在同一回合内使用两张票证（因此进行两次移动）

我可以思考一个针对罪犯的人工智能，它只是一棵极小化极大树，试图选择最大化侦探寻找他所需步数的动作（这似乎是一个很好的指标），但我无法想出任何足够聪明的东西来帮助合作并尝试通过观察罪犯使用的车票猜测罪犯可能在哪里。

这只是为了好玩，但你有什么酷炫的想法可以设计出相当聪明的东西吗？

- Jack

---

http://sourceforge.net/projects/scotland-yard/ - Carl Norum

谢谢您提供的链接，我已经看了那个实现：正如评论所述，逃亡AI的问题在于它选择的是“最佳”移动方式，而不是更聪明的移动方式。这只是根据距离度量得出的最佳移动方式，它并没有考虑像回溯移动一样的技巧（也许是为了在侦探之间潜行而不仅仅是远离他们）。 - Jack

Answer 1

我喜欢这个游戏，我认为对于侦探，您需要建模罪犯在每个位置的概率。偶尔您会知道罪犯的确切位置，然后可以考虑他所采取的移动来确定他可能在哪些地方。

一旦您得到了这个结果，我不太确定如何优化侦探的移动。您可以将侦探移动以减少可能性的集合，有效地圈住罪犯。但我确定还需要一些更高层次的策略，涉及门票和避免用完门票。

- Chris Pitman

---

我也很喜欢它，虽然简单但非常有策略性。这就是为什么我会开始嘟囔如何有效地开发人工智能。也许遗传编程可以模拟不同的偏好倾向，使侦探们采取不同的方法，例如靠近小空间而不是尝试其他事情等。 - Jack

Answer 2

你询问的是如何建模，而不是如何高效地解决问题：

这可以很容易地建模为部分可观察马尔可夫决策过程（维基链接）。这适用于侦探和罪犯。POMDP是一个非常通用的模型。

- ziggystar

Answer 3

我想象一种蒙特卡罗实现可能是一个很好的选择，即模拟成千上万个组合，并选择大多数情况下以最佳结果结束的那个。由于罪犯必须在5回合内可见，分支因子应该保持在良好的控制范围内，尽管MC也被证明是高分支因子游戏中非常好的技术，例如围棋。

- tsiki

Answer 4

为了让侦探之间形成团队合作，您需要将他们建模为一个团队而不是个体。Minimax仍然是一种好方法，但（遗憾的是）您的分支因子将会飙升。

与其逐个检查所有侦探并为每个侦探选择最佳方案，不如计算出他们可能做出的每种移动排列。如果团队合作有助于这个游戏，那么Minimax将倾向于侦探们共同工作的排列。

我不确定是否实际可行，24步骤中5名侦探可能需要太多的工作量，但尝试一下也是很有趣的，这不就是重点吗？

- Daniel