negaMax algorithm producing some odd results

I'm currently implementing a checkers game and the only thing holding me be back is the poor state of my AI. It's being written in Groovy.

I have the following (attempted) negaMax algorithm with alpha, beta pruning. I've followed several pseudo guides but I'm obviously failing somewhere as the results are rather nonsensical.

The method is called as follows: negaMax(3, Integer.MIN_VALUE, Integer.MAX_VALUE, 1)

I've decided 1 will be the computer player; anything else being the user.

def negaMax(int depth, int alpha, int beta, int player) {
    int score
    int bestScore = Integer.MIN_VALUE
    def moves = getMoves(player)                                        // this function returns a hashmap as I felt I needed not just the move but the checker
    // loop through all moves
    for (move in moves) {
        Position origin = move.key.location                             // save original position to allow undo
        move.key.location = move.value                                  // move piece
        if (depth == 0) {
            score = evaluateGameState(player)
        } else {
            score = -negaMax(depth - 1, -beta, -alpha, -player)         //  move score = - opponents best move
        }
        move.key.location = origin                                      // undo move
        if (player == 1) {                                              // save successor evaluations for the computer to search
            evaluations.put((move.key) , new PositionAndScore(score, move.value))
        }
        bestScore = Math.max(bestScore, score)
        alpha = Math.max(alpha, bestScore)
        if (alpha >= beta) {
            break                                                       // prune
        }
    }
    return bestScore
}

I made the choice to have a hash-map of moves, the key as a checker (Piece object) and the value as the actual move. I didn't see any sense in storing just the moves as I need to keep track of what can actually make it.

I utilise another hash-map to store the successor evaluations again storing the checker as the key but instead this time I store both the position and position-score for the value (I made a Class PositionAndScore just for this).

The evaluateGameState function initilises a score as how many pieces can move for that player, adds a point for any kings and retracts a point for any pieces in a takable position.

When playing, the first two moves the computer makes seem intelligent, from then on though, it goes downhill. A lot of the time the computer is trying to make moves that aren't valid and so they don't execute.

I would greatly appreciate anyone giving me their time just to look over what I've done so far and comment if anything stands out as wrong.

Many thanks.

---

edit: ok I've made some progress. As I may not have mentioned the evaluations hashmap is used to calculate the computers best move. It gets the highest score from it.

The problem this was causing was the evaluations hashmap was being added for every loop where the player was 1 and so moves that were not legal (yet ie they were future moves) were being added.

To solve this I decided to add a precursor method called callSearch() which is called instead of negaMax with all the same arguments, however it also sets the rootDepth to that of the depth .

Then I made this small change to the algorithm

if (player == 1 && depth == rootDepth) {

}

My thinking is that I only want to add a successor evaluation once the search has travelled back to a root.

Anyway, having done all this the computer no longer tries to make illegal moves however it's still not making competent moves. This could be my evaluation function though being a little rudimentary.

链接地址: http://www.djcxy.com/p/56318.html

上一篇: 如何在棋盘评估中考虑移动次序

下一篇: negaMax算法产生一些奇怪的结果