1

我正在为类似于国际象棋的游戏编写人工智能。棋盘为 10x10，每边 15 个棋子，所有棋子都有类似的棋步。

游戏中的一切都组织在对象中。瓦片[][]瓦片；10x10，每个 Tile 都有一个指向一块或空的块指针。

到目前为止，我已经实现了一个没有修剪的 MinMax 算法。每轮可能的移动平均是国际象棋游戏的两倍。

该算法有效，但速度很慢。平均而言，它可以检查 40000 次移动/pr 秒。因此，深度为 4 时，我的游戏使用大约 4-5 秒来计算所有可能的移动。我稍后会实施修剪，但可能需要先对我的实施提供一些反馈。

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

实现：(sudo) 为了避免大量的双 for 循环，我在 Tiles 列表中跟踪 myPieces 和对手Pieces。棋盘评估也只进行一次，然后仅更新，并且仅通过添加和减去移动的值来更新。在我的 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 只更新evaluateValue 而不会遍历整个数组。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 只存储/反向指向旧值的指针，并用移动中的新值替换它们。然后调用evaluateTile，它根据一个枚举类型返回一个1-10 的数字。

4

1 回答 1

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

于 2012-11-20T05:02:06.757 回答