2015-11-09 60 views
0
/* finds the best move for the current player given the state of the game. 
* depth parameter and MAX_DEPTH are used to limit the depth of the search for games 
* that are too difficult to analyze in full detail (like chess) 
* returns best move by storing an int in variable that rating points to. 
* we want to make the move that will result in the lowest best move for the position after us(our opponent) 
*/ 
moveT findBestMove(stateT state, int depth, int &rating) { 
    Vector<moveT> moveList; 
    generateMoveList(state, moveList); 
    int nMoves = moveList.size(); 
    if (nMoves == 0) cout << "no move??" << endl; 
    moveT bestMove; 
    int minRating = WINNING_POSITION + 1; //guarantees that this will be updated in for loop 
    for (int i = 0; i < nMoves && minRating != LOSING_POSITION; i++) { 
     moveT move = moveList[i]; 
     makeMove(state, move); 
     int curRating = evaluatePosition(state, depth + 1); 
     if (curRating < minRating) { 
      bestMove = move; 
      minRating = curRating; 
     } 
     retractMove(state, move); 
    } 
    rating = -minRating; 
    return bestMove; 
} 

/* evaluates the position by finding the rating of the best move in that position, limited by MAX_DEPTH */ 
int evaluatePosition(stateT state, int depth) { 
    int rating; 
    if (gameIsOver(state) || depth >= MAX_DEPTH) { 
     return evaluateStaticPosition(state); 
    } 
    findBestMove(state, depth, rating); 
    return rating; 
} 

這是我的代碼,用於實現一個極小極大算法,用於在計算機上完成井字遊戲的完美遊戲。代碼有效,還有許多其他的幫助函數沒有在這裏顯示。我明白了算法的性質,但是我完全有一個很難在findBestMove()函數的末尾包裹我周圍的行頭:Minimax算法:爲什麼評分爲負?

rating = -minRating; 

這是我的書說:負號包括因爲觀點已經轉移:從對手的角度評估職位,而評級則表示從你自己的角度來看移動的價值。讓對手處於負面位置的舉動對你有好處,因此具有正面價值。 但是當我們最初調用函數時,它是從計算機的角度來看的。我想當我們評估每個位置時,這個函數是從我們的對手的角度來調用的,那是爲什麼?有人能夠讓我更深入地瞭解遞歸的內容以及到底爲什麼評級需要消極的原因。 一如既往非常感謝你的時間。

回答

1

想象一下兩個位置A和B,其中A對於球員a更好,B對球員b更好。當玩家a評估這些位置時,eval(A)> eval(B),但當玩b時,我們需要eval(A)< eval(B),但不要。如果b將-eval(A)與-eval(B)進行比較,那麼我們就會得到期望的結果,因爲你的書說的原因。

+0

我想我對玩家b所做的比較感到困惑。因爲當評估玩家a的每一個動作時,for循環還沒有完成,所以評級仍然是正面的。當您在evaluatePosition()中調用該函數時,是否需要將評分存儲爲 - 這樣,當findBestMove的初始執行選擇備份時,評分是否正確? – andypf

+0

'findBestMove'調用'evaluateafePosition',它調用'findBestMove',哪個(但是深層次的東西都去那裏),最終會返回已被否定的評分*。 –