CODEWITHSUNDEEP
javaalgorithmartificial-intelligencechess
Bendik
Bendik

Reputation: 217

Chess AI: MinMax on object implementation

I'm writing an AI for a game similar to chess. The board is 10x10 with 15 pieces for each side which all have chess similar moves.

Everything in the game is organized in objects. Tile[][] tiles; 10x10, every Tile has a piece-pointer to a piece or null.

I've implemented a MinMax algorithm with no pruning so far. Possible moves each round are on average twice as many as in a chess game.

The algorithm works but it's very slow. On average it can check 40000 moves/pr sec. So with a depth of 4 my game uses around 4-5 seconds to calculate all possible moves. I will implement pruning later, but could need some feedback on my implementation first.

Question: Do i have to convert to char-arrays/bit-board or similar to speed up the calculation or am i doing something horribly wrong?

Implementation: (sudo) To avoid lots of double for-loops i keep track of myPieces and opponentPieces in Lists of Tiles. Board evaluation is also done once and then only updates and only updated by adding and subtracting the value of a move. In my implementation of the minMax algorithm i use a GameState class that holds the current 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 only updates the evaluatedValue and does not go through the whole array.myPieces and otherPieces are also updated by apply/undo.

MinMax:

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
}

Edit: Added information about applyMove and Profiler

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

applyMove and undoMove only store/reverse pointers to the old value off from and to and replace them with the new ones from the move. Then calls evaluateTile which returns a number from 1-10 depending on a enum Type in piece.

Upvotes: 1

Views: 1723

Answers (1)

Rafe
Rafe

Reputation: 5295

Your choice of representation is going to cost you a great deal - every move you consider requires you to copy a lot of state. The way I see it, you have two choices:

(1) make your state representation very small (in chess you can do this in 64 x 4 bits, or 4 Int64s in .NET) so copying it is very cheap; or

(2) make your state representation immutable with deltas, so creating an updated state is cheap.

I'd try option (1) first and see how you go.

Here's some links you may find useful: http://en.wikipedia.org/wiki/Board_representation_(chess) http://www.cis.uab.edu/hyatt/boardrep.html

Upvotes: 1

Related Questions