这棵Java树怎么能快1000倍呢？
我正在为一个类似国际象棋的游戏编写AI程序，基于8x8网格上的两种棋子。
我想构建一种minmax树，它表示游戏中的每一步可能的走法，第一步是白人玩家，第二步是黑人玩家。
我有这个generate()方法，它是递归调用的。我需要能够显示大约8个可能的移动水平。在没有优化的情况下，这三个有8^8个叶子。
我实现了一个简单的系统，它确定网格是否确实被计算过，如果是这样的话，系统只是将一个子引用指向不断计算的子引用。
我不知道我的解释是否清楚，我将加入一部分你应该能够理解的代码。
问题是，实际上，我能够生成大约3到4个级别的所有可能性。我已经8岁了。
我希望能够在不到5秒的时间内计算出它。
所以伙计们，你们有没有想办法优化我的算法？
这是生成函数:如果移动是非法的，则leftDiagonalMove()、rightDiagonalMove()和frontMove()返回false；如果移动是合法的，则在网格中移动该块并返回true。
clone()创建一个具有与其"parent“相同属性的新实例，而backMove()只需返回到上一次移动。
public void generate(Node root, boolean white, int index) {
Grid grid = root.getGrid();
Stack<Piece> whitePieces = grid.getPiecesByColor(WHITE);
Stack<Piece> blackPieces = grid.getPiecesByColor(BLACK);
Node node;
String serial = "";
// white loop
for (int i = 0; i < whitePieces.size() && white; i++) {
Piece wPiece = whitePieces.get(i);
if (grid.leftDiagonalMove(wPiece)) {
serial = grid.getSerial();
if(!allGrids.containsKey(serial)){
node = new Node(grid.clone());
node.setMove(grid.getLastMove());
root.addChild(node); // add modified grid
allGrids.put(serial, node);
//actualGrid.display();
if (index < 5 && grid.getPosition(wPiece).x > 0)
generate(node, !white, index + 1);
actualGrid.backMove(); // back step to initial grid
}
else{
root.addChild(allGrids.get(serial));
}
}
if (grid.frontMove(wPiece)) {
// same code as leftMove
}
if (grid.rightDiagonalMove(wPiece)) {
// same code as leftMove
}
}
// black loop
for (int i = 0; i < blackPieces.size() && !white; i++) {
Piece bPiece = blackPieces.get(i);
if (grid.leftDiagonalMove(bPiece)) {
// same code as white loop and replacing wPiece by bPiece
}
if (grid.frontMove(bPiece)) {
// same code as white loop and replacing wPiece by bPiece
}
if (grid.rightDiagonalMove(bPiece)) {
// same code as white loop and replacing wPiece by bPiece
}
}
}回答 2
Stack Overflow用户
发布于 2012-03-15 04:01:13
您需要在生成的移动MinMax trees上使用名为AlphaBeta pruning的东西。更多信息请点击这里：http://en.wikipedia.org/wiki/Alpha-beta_pruning
http://www.progtools.org/games/tutorials/ai_contest/minmax_contest.pdf
基本上，你做一个级别的分支，然后使用修剪，你可以提早消除坏的分支。然后，从未消除的分支计算(为每个)另一个级别。您再次修剪，直到您达到所需的深度。
这里有更多关于minmax的链接供你阅读：
- http://en.wikipedia.org/wiki/Minimax
- MinMax trees - when Min can win in two steps
这篇文章是关于优化国际象棋游戏的剪枝：
- http://en.wikipedia.org/wiki/Alpha-beta_pruning#Heuristic_improvements
- http://en.wikipedia.org/wiki/Refutation_table#Related_techniques
Stack Overflow用户
发布于 2012-03-15 06:55:25
我不明白你为什么要在随机访问元素的时候使用堆栈。A低级，你可以通过使用Piece[]数组来获得改进。
https://stackoverflow.com/questions/9709288
复制相似问题
腾讯云开发者
