2

几年前，研究人员宣布他们已经完成了一个针对跳棋的蛮力综合解决方案。

我对另一个应该有更少状态的类似游戏很感兴趣，但是在任何合理的时间范围内运行完整的求解器仍然是不切实际的。我仍然想尝试一下，因为即使是部分解决方案也可以提供有价值的信息。

从概念上讲，我希望拥有一个包含每个已知位置以及后续位置的游戏状态数据库。一个或多个客户端可以从数据库中获取未探索的状态，计算可能的移动，并将新状态插入到数据库中。一旦找到一个残局状态，所有导致它的状态都可以用极小极大信息更新以构建决策树。如果做出明智的决定来选择可能的分支进行探索，我可以为最重要的分支构建信息，然后随着时间的推移逐渐构建完成。

忽略这个想法的优点或可行性，实现这样一个数据库的最佳方法是什么？我在 sql server 中制作了一个快速原型，该原型存储了每个状态的字符串表示形式。它有效，但我的求解器客户端运行非常缓慢，因为它一次输出一个状态并计算所有移动。我觉得我需要在内存中做更大的块，但是搜索空间肯定太大了，无法一次将它们全部存储在内存中。

有没有更适合这种工作的数据库系统？我将进行许多插入、大量读取（以检查状态（或等效状态）是否已经存在）以及很少的更新。

另外，我怎样才能并行化它，以便许多客户可以解决不同的分支而不会重复太多工作。我正在考虑类似于检查分配，生成几百万个状态并将其提交回以集成到主数据库中的程序。我只是不确定这样的事情是否会很好地工作，或者是否有以前的工作方法来做这种事情。

4

3 回答 3

2

毫无疑问，您需要某种任务队列服务，例如RabbitMQ - 可能与数据库结合使用，该数据库可以在您计算后存储数据。或者，您可以使用像 Amazon 的SQS这样的托管服务。客户端将从队列中消费一个项目，生成后继者，并将它们排入队列，以及将它刚刚消费的项目的结果添加到队列中。如果状态是最终状态，它可以通过查询数据库将评分信息传播到父元素。

需要记住的两个警告：

  1. 当您探索树时，队列中的项目数量可能会呈指数增长，每个工作项目都会导致更多的工作项目入队。准备好排长队。
  2. 根据您的游戏，可能有多个路径可以通向同一个游戏状态。您需要检查并消除重复项，并且您的数据库需要进行结构化，以便它是一个图（可能带有循环！），而不是一棵树。
于 2011-05-29T00:22:14.857 回答
2

为了解决游戏，您真正需要了解数据库中每个状态的信息是它的博弈论价值，即轮到该移动的玩家是否获胜，或失败或强制平局。您需要两个位来对每个状态的信息进行编码。

然后，您会为要为其构建最终游戏数据库的那组游戏状态找到尽可能紧凑的编码；假设您的编码需要 20 位。那么在你的硬盘上有一个 2 21位的数组就足够了，即 2 13字节。当你分析一个终局位置时，你首先检查数据库中是否已经设置了相应的值；如果不是，则计算其所有后继节点，递归计算其博弈值，然后使用 min/max 计算原始节点的博弈值并存储在数据库中。（注意：如果您将赢/输/平局数据存储在两位中，则剩下一位模式表示“未知”；例如 00 = 未知，11 = 平局，10 = 玩家移动获胜，01 = 玩家到移动失败）。

例如，考虑井字游戏。有九个方格；每个都可以是空的，“X”或“O”。这种简单的分析为每个状态提供 3 9 = 2 14.26 = 15 位，因此您将拥有一个 2 16位的数组。

于 2011-05-29T20:55:40.090 回答
1

我首先想到的是共享“白板”的Linda风格，其中不同的进程可以从白板上消耗“问题”，向白板添加新问题，并向白板添加“解决方案”。

也许Cassandra项目是 Linda 的更现代版本。

已经有许多尝试在分布式计算机系统中并行化问题。Folding@Home提供了一个执行二进制 blob 'cores' 来解决蛋白质折叠问题的框架。Distributed.net可能已经开始了分布式问题解决的现代化身，并且可能有您可以开始的客户端。

于 2011-05-28T03:40:42.723 回答