C#极小极大树的实现
我正在尝试编写 C# Chess AI。
那一刻我必须构建我的最小最大树。我尝试使用递归，但我的递归函数必须为每个节点调用自身大约 1 000 000 次。在大约... 60 000 次调用后，我收到堆栈溢出异常。
I'm trying to write C# Chess AI.
At that moment I have to build my minmax tree. I try by using recursion, but my recursive functions has to call itself about 1 000 000 times for every node. I get Stack Overflow exception after about... 60 000 calls.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我猜你正在使用深度优先搜索。当搜索空间很大时，这不太有用。实现极小极大时，您可以使用广度优先搜索作为深度优先搜索，并迭代加深。
您应该将允许递归的最大级别数作为函数的参数，并在每次递归调用函数时将其减少 1，直到停止并回溯时达到零。从较小的最大深度开始，然后慢慢增加它，直到找到可接受的解决方案，否则就会耗尽时间。
I guess you are using a depth first search. This isn't too useful when the search space is so large. When implementing minimax you can use a breadth first search implemented as a depth first search with iterative deepening.
You should have a maximum number of levels you are allowed to recurse as a parameter to your functions, and decrease that by one each time you call your function recursively, until you hit zero when you stop and backtrack. Start with a small maximum depth and slowly increase it until you find an acceptable solution, or else run out of time.
鉴于递归的深度可能未知，您可能希望提前停止到合理的限制（例如 10 次移动）和/或忽略效用分数较低的树。通过添加诸如此类的额外约束，您还可以确保快速找到解决方案，而无需进行广泛优化。
正如其他人所呼应的那样，鉴于您的大量迭代，听起来您可能有一个错误。可以删除各种规则或选择不同的搜索策略来减少所需的迭代次数，例如 迭代深化、A* 或遗传算法为了好玩，
返回一个结果，即使它不完美，也比返回结果要好得多搜索树太深后失败。
祝你好运。
Given that the depth of the recursion might not be known you might want to stop to at a reasonable limit like 10 moves in advance and/or ignore trees that have a lower utility score. By adding extra constraints such as these you can also ensure that a solution will be found quickly without having to optimize extensively.
As echoed by others it sounds like you probably have a bug given your large number of iterations. It might be possible to prune out a variety of rules or chose a different search strategy to reduce the number of iterations required, such as iterative deepenning, A* or perhaps a Genetic Algorithm for fun,
It would be much better to return a result even if it is not perfect rather than failing after searching the tree too deep.
Good luck.
大多数国际象棋搜索程序只能搜索到深度 9 或 10。这根本不足以溢出堆栈。
您的程序可能有错误。无论如何，您确实需要对搜索进行深度限制，因为如果没有深度限制，您将无法进行全角搜索（探索给定深度的所有移动的所有可能性），因为国际象棋游戏是可能具有无限深度（重复头寸或移动规则限制除外）。
当你搜索到大约深度 9 后，你必须使用静态棋盘评估函数来评估和评分该位置。然后，您可以使用最小-最大算法来修剪搜索树的分支。但这仍然是一个指数搜索。
还有一些技术，例如静态搜索，您可以在位置不稳定的情况下继续搜索（即，如果可以吃棋或国王处于控制状态）。
Most chess search programs can only search to depth 9 or 10. This is not enough to overflow the stack at all.
You probably have an error in your program. In any case, you do need to have a depth limit on your search as you will not be able to do full-width search (exploring all possibilities across all moves up to a given depth) without a depth limit, since a chess game is potentially of unlimited depth (except for the repeated positions or limit on moves rule).
After you search to about depth 9, you have to use a static board evaluation function to evaluate and score the position. You then use the mini-max algorithm to prune branches of the search tree. It's still an exponential search though.
There are also techniques such as quiescent search, where you continue searching in positions where the position is not stable (i.e. if a piece can be taken or the king is in check).
如果您有兴趣学习如何编写 C# 国际象棋引擎，我邀请您访问计算机国际象棋博客
该博客描述了 C# 国际象棋引擎的创建的第一步，并提供了 C# 代码示例。
您可能最感兴趣的页面是： Move 搜索和 Alpha Beta
本文详细解释了 Min Max 和 Alpha Beta 搜索算法，包括两者的 C# 代码示例。
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.