C＃minimax树实现

Question

我想写C＃国际象棋AI。

那时我必须建立我的minmax树。我尝试使用递归，但我的递归函数必须为每个节点调用自己大约1 000 000次。在约60 000次呼叫后，我得到堆栈溢出异常。

Answer 1

考虑到递归的深度可能不知道，你可能想要停止在一个合理的限制，如提前10次移动和/或忽略具有较低效用分数的树。通过添加额外的约束，如这些，您还可以确保快速找到解决方案，而无需进行大量优化。

正如其他人所回应的那样，听起来您可能因为您的大量迭代而出现错误。这也许可以修剪出各种规则或选择不同的搜索策略，以减少所需的迭代次数，如iterative deepenning，A*或者是一个有趣的Genetic Algorithm，

这将是更好的返回结果即使它不是完美的而不是在搜索到太深的树后失败。

祝你好运。

Answer 2

我想你正在使用深度优先搜索。这在搜索空间非常大时不太有用。在实施minimax时，您可以使用宽度优先搜索作为深度优先搜索与iterative deepening实施。

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

Answer 3

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

您的程序中可能有错误。在任何情况下，您都需要对搜索有深度限制，因为您无法进行全角搜索（探索所有棋步达到指定深度的所有可能性）而没有深度限制，因为棋局是潜在的无限深度（重复位置或移动限制规则除外）。

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

还有一些技术，例如静态搜索，您可以在位置不稳定的位置继续搜索（即，如果一件作品可以被拍摄或国王被检查）。

Answer 4

，如果你有兴趣学习如何编写C＃象棋引擎我邀请您来参观的Computer Chess Blog

的博客描述了创作从第一个步骤的C＃象棋引擎，提供C＃代码示例。 Move Searching and Alpha Beta

本文给出了最小值最大值和α+β搜索算法包括两个C＃代码示例的详细说明：

的页面是你可能是最感兴趣的。