logo标签列表

C# 极小化极大树实现

c#treechess
3
我正在尝试编写C#国际象棋AI。
此时，我必须构建我的极小极大树。我尝试使用递归，但是我的递归函数需要为每个节点调用自身约1,000,000次。大约在60,000次调用后，我会遇到堆栈溢出异常。
你确定你不只是出现了空递归吗？为了得到答案，你需要发布代码或更多细节。 - twolfe18
"每个节点循环1,000,000次" - 听起来有点过度。 - Mitch Wheat
4个回答
4
我猜你正在使用深度优先搜索。当搜索空间如此之大时，这并不太有用。在实现极小化算法时，你可以使用广度优先搜索，将其实现为深度优先搜索，使用迭代加深。
你应该将允许递归的最大层数作为函数参数，并每次递归调用函数时将其减少一次，直到达到零时停止并回溯。从一个小的最大深度开始，慢慢增加它，直到找到一个可接受的解决方案，或者时间耗尽。
0

考虑到递归的深度可能未知，您可能希望在合理的限制下停止，例如提前10步和/或忽略效用得分较低的树。通过添加额外的约束条件，您还可以确保快速找到解决方案，而无需进行大量优化。

正如其他人所说，鉴于您的迭代次数很多，这听起来可能是一个错误。可能可以修剪出各种规则或选择不同的搜索策略来减少所需的迭代次数，例如迭代加深, A* 或者也许是遗传算法（仅供娱乐）。

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

祝你好运。

0

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

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

在搜索到大约深度9之后，您必须使用静态棋盘评估函数来评估和打分。然后，您可以使用极小化极大算法来修剪搜索树的分支。尽管如此，这仍然是一种指数搜索。

还有一些技术，例如静态搜索，在其中您可以继续搜索不稳定的位置（即，如果可以拿走一件棋子或国王处于被将军状态）。

2
传统极小极大算法不会修剪任何分支。我想你在考虑alpha-beta修剪：http://en.wikipedia.org/wiki/Alpha-beta_pruning - Mark Byers
0

如果您有兴趣学习如何编写C#国际象棋引擎，我邀请您访问计算机国际象棋博客。

该博客从最初的步骤开始描述了创建C#国际象棋引擎的过程，并提供了C#代码示例。

您可能最感兴趣的页面是：移动搜索和Alpha Beta

本文详细介绍了Min Max和Alpha Beta搜索算法，包括两者的C#代码示例。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接