3

我正在尝试编写 C# Chess AI。

在那一刻，我必须建立我的 minmax 树。我尝试使用递归，但我的递归函数必须为每个节点调用自己大约 1 000 000 次。在大约... 60 000 次调用后，我得到了 Stack Overflow 异常。

4

4 回答 4

4

我猜你正在使用深度优先搜索。当搜索空间很大时，这不太有用。在实现极小极大时，您可以使用广度优先搜索实现为具有迭代深化的深度优先搜索。

您应该有一个最大数量的级别，您可以将其作为函数的参数进行递归，并在每次递归调用函数时将其减少一，直到您在停止和回溯时达到零。从较小的最大深度开始，然后慢慢增加，直到找到可接受的解决方案，否则时间用完。

于 2010-01-10T02:30:31.777 回答
0

鉴于可能不知道递归的深度，您可能希望停在一个合理的限制上，例如提前 10 次移动和/或忽略效用得分较低的树。通过添加诸如此类的额外约束，您还可以确保快速找到解决方案，而无需进行大量优化。

正如其他人所回应的那样，鉴于您的大量迭代，您可能有一个错误。有可能删减各种规则或选择不同的搜索策略以减少所需的迭代次数，例如迭代深化、A*或可能是为了好玩 的遗传算法，

即使结果并不完美，也比在搜索树太深后失败而返回结果要好得多。

祝你好运。

于 2010-01-10T02:30:58.823 回答
0

大多数国际象棋搜索程序只能搜索到深度 9 或 10。这根本不足以溢出堆栈。

您的程序中可能有错误。在任何情况下，您都需要对搜索进行深度限制，因为如果没有深度限制，您将无法进行全宽度搜索（探索所有移动到给定深度的所有可能性），因为国际象棋游戏是潜在的无限深度（重复位置或移动限制规则除外）。

搜索到大约 9 深度后，您必须使用静态板评估功能来评估和评分位置。然后，您使用 mini-max 算法修剪搜索树的分支。尽管如此，它仍然是一个指数搜索。

还有一些技术，例如静止搜索，您在位置不稳定的位置继续搜索（即，如果一个棋子可以被拿走或国王被控制）。

于 2010-01-10T02:33:14.743 回答
0

if you are interested in learning how to write a C# Chess Engine I invite you to visit the Computer Chess Blog

The blog describes a creation of a C# Chess Engine from the first steps, providing C# code examples.

The page you might be the most interested in is: Move Searching and Alpha Beta

This article gives a detailed explanation of Min Max and the Alpha Beta search algorithms including C# code examples of both.

于 2010-01-23T16:11:36.237 回答