无递归的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;
}搜索(4，-200000,200000)；
回答 2
Stack Overflow用户
发布于 2011-06-17 16:11:58
Knuth和Moore在1975年使用特别的Algol语言发布了一个迭代的alpha-beta例程。
An Analysis of Alpha Beta Pruning (第301页)
也在“算法分析论文选集”的第9章中。
它看起来并不是很容易转换成C#，但它可能会帮助那些想要做这件事的人，纯粹为了优化的乐趣。
我对国际象棋编程非常陌生，所以这超出了我的能力范围。另外，当我从"Copy-Make“切换到"Make-Unmake”时，我获得了最大的性能提升。我正在使用XNA，所以让我的GC延迟降到几乎为0解决了我所有的性能问题，现在它在我的360上比在我的PC上运行得更快，所以这种优化似乎很难满足我的需要。
Stack Overflow用户
发布于 2018-01-31 18:45:26
对于较新的代码，我编写了一个非递归的Negamax例程作为EasyAI python库中的一个选项。具体源代码在：
https://github.com/Zulko/easyAI/blob/master/easyAI/AI/NonRecursiveNegamax.py
它使用一个具有固定对象数组(大小由目标深度决定)的简单循环，以有序的方式在树中上下移动。对于我正在使用它的特定项目，它比递归版本快六倍。但我相信每个游戏都会有不同的反应。
无可否认，这是一些密集和复杂的代码，到C/Java/C#的转换将是...很有挑战性。它几乎什么都没有，只是边界案例。:)
如果您将其转换为C/Java/C#，我希望看到结果。是否在评论中添加链接？
https://stackoverflow.com/questions/4104372
复制
相似问题
无递归的树迭代
递归搜索树
递归树搜索
MySQL递归树搜索
无环尾递归树遍历
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
