1

チェスに似たゲームのAIを書いています。ボードは10x10で、各サイドに15個あり、すべてチェスのような動きがあります。

ゲーム内のすべてがオブジェクトに編成されています。タイル[][]タイル; 10x10、すべてのタイルには、ピースまたはヌルへのピースポインターがあります。

これまで、プルーニングなしでMinMaxアルゴリズムを実装しました。各ラウンドで可能な動きは、チェスゲームの平均2倍です。

アルゴリズムは機能しますが、非常に低速です。平均して、40000ムーブ/pr秒をチェックできます。したがって、深さが4の場合、私のゲームは約4〜5秒を使用してすべての可能な動きを計算します。後でプルーニングを実装しますが、最初に実装に関するフィードバックが必要になる場合があります。

質問：計算を高速化するためにchar-arrays / bit-boardなどに変換する必要がありますか、それともひどく間違ったことをしていますか？

実装:(sudo）多くの二重forループを回避するために、タイルのリストでmyPiecesとopponentPiecesを追跡します。ボードの評価も一度行われ、その後は更新され、移動の値を加算および減算することによってのみ更新されます。minMaxアルゴリズムの実装では、現在のgameStateを保持する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は、valuatedValueのみを更新し、配列全体を通過しません。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

表現の選択には多大なコストがかかります。検討するすべての動きで、多くの状態をコピーする必要があります。私の見方では、2つの選択肢があります。

（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 に答える