玩这个游戏时，我一直在想，控制侦探或罪犯的AI应该如何运作。

简单来说，这个游戏的目标如下（面向懒人）：

• 游戏棋盘是一个无向图，有4种类型的边（对于同一对顶点，也可能存在重叠），每种类型都代表一种交通方式，需要特定类型的票。
• 侦探拥有一堆车票，可以在图上移动，每回合移动一次（即从一个节点到另一个节点）。 罪犯可以做同样的移动（加上3条独有路径），但票的数量没有限制。
• 罪犯通常对侦探是隐藏的，但他必须在5个特定回合中现身（然后再次隐藏）。
• 如果侦探能够在24步之前抓住他（其中一个必须占据罪犯的同一单元格），那么他们就赢了，否则罪犯获胜。
• 罪犯必须展示他每回合使用的车票，但他还有每位侦探1张的黑色车票（假设有5张），可以用来掩盖这一点。
• 罪犯还有两张2倍车票，允许他在同一回合中使用两张车票（从而进行两次移动）。

我可以有效地想到一个罪犯的AI，它只是一个minmax树，试图选择最大化侦探到达他所需步数的移动（这似乎是一个不错的指标），但我无法想到任何对侦探来说足够酷的东西，他们应该合作并通过查看罪犯使用的车票来尝试猜测罪犯可能在哪里。

这只是为了好玩，但你知道任何很棒的想法来实现一些非常聪明的东西吗？

回答：

你问的是如何建模，而不是如何有效地解决这个问题：

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