瞭解Negamax的限制

代碼片段的構建是爲了計算tictactoe遊戲中位置的bestMove。除了for循環中的條件外，我幾乎獲得了代碼的所有部分，它表示minRating！= LOSING_POSITION。該代碼來自給定僞代碼的實現。瞭解Negamax的限制

moveT FindBestMove(stateT state, int depth, int & rating) { 
for (*each possible move or until you find a forced win*) { 
*Make the move. 
Evaluate the resulting position, adding one to the depth indicator. 
Keep track of the minimum rating so far, along with the corresponding move. 
Retract the move to restore the original state.* 
} 
*Store the move rating into the reference parameter. 
Return the best move.* 
}

我無法比擬的與給定的代碼迴路第二個條件它說，，直到找到一個強制贏得。我找不到這個事實，這minRating！之間的相似性= LOSING_POSITION

moveT FindBestMove(stateT state, int depth, int & rating) { 
Vector<moveT> moveList; 
GenerateMoveList(state, moveList); 
int nMoves = moveList.size(); 
if (nMoves == 0) Error("No moves available"); 
moveT bestMove; 

int minRating = WINNING_POSITION + 1; 

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; 

} 


int EvaluatePosition(stateT state, int depth) { 
int rating; 

if (GameIsOver(state) || depth >= MAX_DEPTH) { 
return EvaluateStaticPosition(state); 
} 

FindBestMove(state, depth, rating); 
return rating; 
}

來源

2012-11-26 motiur

你的程序分配WINNING_POSITION開始（贏得你的對手，我想）到minRating，然後通過移動循環，試圖找到以最大的傷害移動，最小化爲minRating。

當EvaluatePosition返回LOSING_POSITION而不是意味着此舉會導致您的對手在每種情況下都失敗，因此可以終止搜索並且此舉被認爲是最佳舉措。

如果沒有明顯的LOSING_POSITIONS，那麼你的算法根據靜態評估選擇「最佳」移動。

來源

2012-11-26 06:44:24 lenik

只是爲了重申並清楚說明，代碼片段中獲得的最小值int curRating = EvaluatePosition（state，depth + 1）;給當前玩家或對手帶來的好處。我可以認爲這是來自當前球員的情況，否則他不會希望他的對手輸球。只有評估函數給出LOSING_POSITION的值時，循環纔會停止。我是對的，如果你想添加一些，這將是有幫助的。 – motiur

循環在可能的移動中停止。或者很明顯，對手沒有機會贏得他選擇的任何動作。 'curRating'越低越好。相同的'minRating'。然而，在Evaluate（）返回之前，評級改變了符號，因爲對手應該將他的評級向相反的方向移動，因此「NegaMax」。 – lenik

瞭解Negamax的限制

回答

相關問題