我正在为一个类似于国际象棋的游戏编写AI。这个棋盘是10×10的，每一方有15个棋子，这些棋子的移动方式类似于国际象棋的棋子。
游戏中的所有元素都以对象的形式组织。Tile[][] tiles; 10×10，每个Tile都有一个指向棋子的指针，或者是null。
到目前为止，我已经实现了一个没有剪枝的MinMax算法。每轮可能的移动平均是国际象棋游戏的两倍。
算法可以工作，但速度非常慢。平均每秒可以检查40000个移动/秒。因此，在深度为4的情况下，我的游戏需要大约4-5秒来计算所有可能的移动。我稍后会实现剪枝，但首先需要对我的实现进行一些反馈。
问题：我是否需要转换为字符数组/位板或类似的方法来加速计算，或者我做错了什么？
实现：（伪代码）为了避免大量的双重for循环，我通过Tiles的列表来跟踪myPieces和opponentPieces。棋盘评估也只进行一次，然后只通过添加和减去移动的值来更新。在我的MinMax算法实现中，我使用了一个GameState类来保存当前的游戏状态。
GameState { Tile[][] board List<Tile> myPieces; List<Tile> otherPieces; int[][] evaluatedBoard int evaluatedValue Piece moveFrom, moveTo //用于在应用移动时保存指针 int moveFromValue, moveToValue //用于在应用移动时保存评估值 void applyMove(Tile from, Tile to) void undoMove(Tile from, Tile to) GameState createCopy()}ApplyMove只更新evaluatedValue，而不遍历整个数组。myPieces和otherPieces也通过apply/undo进行更新。
MinMax:
maxMove(GameState state, int depth) { for(Tile from : state.getMyPieces().clone()) { //列表将被更改 for(Tile to : from.getPiece().getPossibleMoves()) { if(depth == 0) //找到最佳移动等 else { state.applyMove(from, to); minMove(state.createCopy(), depth - 1) //与maxMove类似，但使用otherPieces state.undoMove(from, to) } } } //返回最佳移动}编辑：添加了关于applyMove和Profiler的信息
Profiler: instructionsapplyMove() 3200ms 11 430 000 undoMove() 1800ms 11 430 000evaluateTile() 1400ms 22 400 000minMove() 1700ms 315 493 applyMove和undoMove只存储/恢复从和到旧值的指针，并用移动的新值替换它们。然后调用evaluateTile，它根据棋子中的枚举类型返回1-10之间的数字。
回答：
你的表示选择将花费你很多成本——你考虑的每一个移动都需要复制大量的状态。我认为你有两个选择：
(1) 使你的状态表示非常小（在国际象棋中，你可以用64 x 4位，或者在.NET中用4个Int64来实现），这样复制它就非常便宜；或者
(2) 使你的状态表示为不可变的增量状态，这样创建更新的状态就很便宜。
我会先尝试选项(1)，看看效果如何。
你可能会发现以下链接有用： http://en.wikipedia.org/wiki/Board_representation_(chess)http://www.cis.uab.edu/hyatt/boardrep.html
