java - 国际象棋 AI : MinMax on object implementation

Question

我正在为类似于国际象棋的游戏编写 AI。棋盘为 10x10，每面 15 block 都有象棋相似的走法。

游戏中的一切都组织在对象中。瓷砖[][] 瓷砖; 10x10，每个 Tile 都有一个 piece-pointer 指向一个 piece 或 null。

到目前为止，我已经实现了一个没有剪枝的 MinMax 算法。每轮可能的走法平均是国际象棋比赛的两倍。

该算法有效，但速度非常慢。平均它可以检查40000 次移动/每秒所以深度为 4 我的游戏使用大约 4-5 秒来计算所有可能的 Action 。我稍后会实现修剪，但可能需要首先是对我的实现的一些反馈。

问题:我是否必须转换为 char-arrays/bit-board 或类似的来加速计算还是我做错了什么？

实现:(sudo)为了避免大量的双 for 循环，我跟踪 myPieces 和 opternalPieces在瓷砖列表中。董事会评估也进行一次，然后仅更新并且只能通过增加和减少移动的值来更新。在我的 minMax 算法的实现中，我使用了一个 GameState 类持有当前的游戏状态。

GameState {
 Tile[][] board
 List<Tile> myPieces;
 List<Tile> otherPieces;
 int[][] evaluatedBoard
 int evaluatedValue
 Piece moveFrom, moveTo //used to save pointer when applying move
 int moveFromValue, moveToValue //used to save evaluationValue when applying move


 void applyMove(Tile from, Tile to)
 void undoMove(Tile from, Tile to)
 GameState createCopy()
}

ApplyMove只更新evaluatedValue，不经过 整个 array.myPieces 和 otherPieces 也通过 apply/undo 更新。

最小最大:

maxMove(GameState state, int depth) {
 for(Tile from : state.getMyPieces().clone()) { //list will be changed
   for(Tile to : from.getPiece().getPossibleMoves()) {
       if(depth == 0)
         //find best move and so forth
       else {
        state.applyMove(from, to);
        minMove(state.createCopy(), depth - 1) //similar to maxMove except it uses otherPieces
        state.undoMove(from, to)
       }
   }
 }
 //return best move
}

编辑:添加了有关 applyMove 和 Profiler 的信息

Profiler:          instructions
applyMove()     3200ms  11 430 000 
undoMove()      1800ms  11 430 000
evaluateTile()  1400ms  22 400 000
minMove()       1700ms  315 493 

applyMove 和 undoMove 只存储/反转指向旧的指针重视 from 和 to 并用来自的新值替换它们此举。然后调用 evaluateTile 返回 1-10 之间的数字取决于一个枚举类型。

Answer 1

您对表示的选择会让您付出很大的代价——您考虑的每一步都需要您复制大量状态。在我看来，您有两种选择:

(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