无递归的 Alpha-beta 树搜索
我希望看到一个无需递归的 alpha-beta 搜索（更准确地说是 negamax）的实现。我知道基本的想法 - 使用一个或多个堆栈来跟踪级别，但是拥有真正的代码可以节省我很多时间。
使用 Java、C# 或 Javascript 就完美了，但 C/C++ 也可以。
这是（简化的）递归代码：
function search(crtDepth, alpha, beta)
{
if (crtDepth == 0)
return eval(board);
var moves = generateMoves(board);
var crtMove;
var score = 200000;
var i;
while (i<moves.length)
{
crtMove = moves.moveList[i++];
doMove(board, crtMove);
score = -search(crtDepth-1, -beta, -alpha);
undoMove(board, crtMove);
if (score > alpha)
{
if (score >= beta)
return beta;
alpha = score;
}
}
return alpha;
}
search(4, -200000, 200000);
I'd like to see an implementation of an alpha-beta search (negamax to be more precise) without recursion. I know the basic idea - to use one or more stacks to keep track of the levels, but having a real code would spare me a lot of time.
Having it in Java, C# or Javascript would be perfect, but C/C++ is fine.
Here's the (simplified) recursive code:
function search(crtDepth, alpha, beta)
{
if (crtDepth == 0)
return eval(board);
var moves = generateMoves(board);
var crtMove;
var score = 200000;
var i;
while (i<moves.length)
{
crtMove = moves.moveList[i++];
doMove(board, crtMove);
score = -search(crtDepth-1, -beta, -alpha);
undoMove(board, crtMove);
if (score > alpha)
{
if (score >= beta)
return beta;
alpha = score;
}
}
return alpha;
}
search(4, -200000, 200000);
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Knuth 和 Moore 于 1975 年使用特殊的 Algol 语言发布了迭代 alpha-beta 例程。
Alpha Beta 剪枝分析（第 301 页）
同样在“算法分析论文精选”的第 9 章中
转换成 C# 看起来并不容易，但它可能会帮助那些想要纯粹为了优化的乐趣而这样做的人。
我对国际象棋编程非常陌生，所以这超出了我的能力。另外，我最大的性能提升是当我从“Copy-Make”切换到“Make-Unmake”时。我正在使用 XNA，因此将 GC 延迟降低到几乎 0 解决了我的所有性能问题，现在它在我的 360 上的运行速度比在我的 PC 上运行得更快，因此这种优化似乎很难满足我的需求。
另请参阅递归到迭代
Knuth and Moore published an iterative alpha-beta routine in 1975 using an ad-hoc Algol language.
An Analysis of Alpha Beta Pruning (Page 301)
Also in Chapter 9 of "Selected Papers on Analysis of Algorithms"
It doesn't look very easy to covert into C# but it might help someone who wants to do it for the pure joy of optimization.
I'm very new to chess programming so it's beyond my abilities. Plus, my biggest performance gain was when I switched from "Copy-Make" to "Make-Unmake". I'm using XNA, so getting my GC latency down to almost 0 fixed all my performance issues, now it runs faster on my 360 than it does on my PC so this optimization seems too difficult to attempt for my needs.
Also see Recursion to Iteration
对于最近的代码，我编写了一个非递归 Negamax 例程作为 EasyAI python 库中的一个选项。具体源码在：
https://github.com /Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py
它使用一个带有固定对象数组（大小由目标深度决定）的简单循环，以有序的方式在树上上下移动。对于我使用它的特定项目，它比递归版本快六倍。但我确信每个游戏都会有不同的反应。
无可否认，这是一些密集且复杂的代码，转换为 C/Java/C# 将是......具有挑战性。这几乎只是边界案件。 :)
如果你将它转换为 C/Java/C#，我很想看到结果。在评论中放置链接？
For a more recent bit of code, I wrote a non-recursive Negamax routine as an option in the EasyAI python library. The specific source code is at:
https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py
It uses a simple loop with a fixed array of objects (size determined by target depth) to move up and down the tree in an ordered fashion. For the particular project I was using it on, it was six times faster than the recursive version. But I'm sure each game would respond differently.
There is no way to deny that this is some dense and complex code and conversion to C/Java/C# will be ... challenging. It is pretty much nothing but border cases. :)
If you convert it to C/Java/C#, I would love to see the results. Place an link in the comment?