我一直在撰寫一個簡單的 Minimax 演算法，但偶然發現了一個我無法解決的問題。該演算法首先確定游戲是否結束（通過平局或任一玩家獲勝）或深度是否命中== 0（depth在每個遞回呼叫中減少 1）。
我遇到的問題是演算法通常會很快達到深度 0（因為初始深度很低）。但是，正如我給出的偽代碼所指出的那樣，如果發生這種情況，演算法應該回傳當前板的靜態評估。就我而言，該棋盤處于CONTINUE（意味著沒有滿足游戲結束條件）的狀態。
我設定了我的評估演算法，所以如果圈子獲勝，它回傳 -1，平局回傳 0，交叉獲勝回傳 1。如果游戲還沒有結束，我應該回傳什么depth==0才不會弄亂演算法的最大化/最小化？
評估代碼：
int getGameResult() {
//check for possible win
//check vertical lines
for (int i = 0; i <= BOARD_SIZE - 4; i ) {
for (int j = 0; j < BOARD_SIZE; j ) {
//if circle has 4 verticals
if (board[i][j] == FieldStatus::CIRCLE
&& board[i 1][j] == FieldStatus::CIRCLE
&& board[i 2][j] == FieldStatus::CIRCLE
&& board[i 3][j] == FieldStatus::CIRCLE) {
return -1;
}
//if cross has 4 verticals
else if (board[i][j] == FieldStatus::CROSS
&& board[i 1][j] == FieldStatus::CROSS
&& board[i 2][j] == FieldStatus::CROSS
&& board[i 3][j] == FieldStatus::CROSS) {
return 1;
}
}
}
//check horizontal lines
for (int i = 0; i < BOARD_SIZE; i ) {
for (int j = 0; j <= BOARD_SIZE - 4; j ) {
//if circle has 4 horizontals
if (board[i][j] == FieldStatus::CIRCLE
&& board[i][j 1] == FieldStatus::CIRCLE
&& board[i][j 2] == FieldStatus::CIRCLE
&& board[i][j 3] == FieldStatus::CIRCLE) {
return -1;
}
//if cross has 4 horizontals
else if (board[i][j] == FieldStatus::CROSS
&& board[i][j 1] == FieldStatus::CROSS
&& board[i][j 2] == FieldStatus::CROSS
&& board[i][j 3] == FieldStatus::CROSS) {
return 1;
}
}
}
//check diagonals
//right diagonals
for (int i = 0; i < BOARD_SIZE - 3; i ) {
for (int j = 0; j < BOARD_SIZE - 3; j ) {
if (board[i][j] == FieldStatus::CIRCLE
&& board[i 1][j 1] == FieldStatus::CIRCLE
&& board[i 2][j 2] == FieldStatus::CIRCLE
&& board[i 3][j 3] == FieldStatus::CIRCLE) {
return -1;
}
if (board[i][j] == FieldStatus::CROSS
&& board[i 1][j 1] == FieldStatus::CROSS
&& board[i 2][j 2] == FieldStatus::CROSS
&& board[i 3][j 3] == FieldStatus::CROSS) {
return 1;
}
}
}
//left diagonals
for (int i = BOARD_SIZE - 1; i > BOARD_SIZE - 2; i--) {
for (int j = 0; j < BOARD_SIZE - 3; j ) {
if (board[i][j] == FieldStatus::CIRCLE
&& board[i - 1][j 1] == FieldStatus::CIRCLE
&& board[i - 2][j 2] == FieldStatus::CIRCLE
&& board[i - 3][j 3] == FieldStatus::CIRCLE) {
return -1;
}
if (board[i][j] == FieldStatus::CROSS
&& board[i - 1][j 1] == FieldStatus::CROSS
&& board[i - 2][j 2] == FieldStatus::CROSS
&& board[i - 3][j 3] == FieldStatus::CROSS) {
return 1;
}
}
}
//check for draw
for (int i = 0; i < BOARD_SIZE; i ) {
for (int j = 0; j < BOARD_SIZE; j ) {
if (board[i][j] != FieldStatus::EMPTY) {
return -5; //!! This is the part that confuses me
}
}
}
return 0;
}
極小值代碼（isCross基本上是指isMaximizer）：
int minimax(int depth, bool isCross) {
//cross maximizes, circle minimizes
//check if game is done
if (depth == 0 && isGameOver()) {
int result = getGameResult();
if (result == -5 && isCross) {
return 1;
}
else if (result == -5) {
result = -1;
}
return result;
}
//if maximizing
if (isCross) {
int bestMoveScore = INT_MIN;
for (int i = 0; i < BOARD_SIZE; i ) {
for (int j = 0; j < BOARD_SIZE; j ) {
if (board[i][j] == FieldStatus::EMPTY) {
board[i][j] = FieldStatus::CROSS;
int fieldScore = minimax(depth - 1, false);
board[i][j] = FieldStatus::EMPTY;
if (fieldScore > bestMoveScore) {
bestMoveScore = fieldScore;
}
}
}
}
return bestMoveScore;
}
else { //minimize
int bestMoveScore = INT_MAX;
for (int i = 0; i < BOARD_SIZE; i ) {
for (int j = 0; j < BOARD_SIZE; j ) {
if (board[i][j] == FieldStatus::EMPTY) {
board[i][j] = FieldStatus::CIRCLE;
int fieldScore = minimax(depth - 1, true);
board[i][j] = FieldStatus::EMPTY;
if (fieldScore < bestMoveScore) {
bestMoveScore = fieldScore;
}
}
}
}
return bestMoveScore;
}
}
uj5u.com熱心網友回復：
首先，您的代碼中存在一些問題：
您寫（正確地）平局被評估為 0，但代碼沒有這樣做。相關代碼為：
//check for draw for (int i = 0; i < BOARD_SIZE; i ) { for (int j = 0; j < BOARD_SIZE; j ) { if (board[i][j] != FieldStatus::EMPTY) { return -5; //!! This is the part that confuses me } } } return 0;final
return 0只能在if條件永遠不為真時執行，這 - 如果我們仔細觀察 - 意味著所有單元格都是空的！這顯然是錯誤的。的if條件應該是：if (board[i][j] == FieldStatus::EMPTY) {并且 now
-5將是在getGameResult游戲尚未結束的狀態下呼叫時的回傳值。它表示“我不知道價值是什么”之類的東西。由于您有一個
getGameResult函式可以正確識別游戲是否結束，因此您實際上并不需要gameOver單獨的函式。如果getGameResult回傳-5，那么游戲是不是結束，在所有其他情況下（-1,0或1），它是結束了。您的代碼并不總是檢查游戲是否結束
int minimax(int depth, bool isCross) { //cross maximizes, circle minimizes //check if game is done if (depth == 0 && isGameOver()) { int result = getGameResult();這段代碼只會在
depth為 0時檢測游戲是否結束，但也有可能是游戲提前結束。所以這個條件depth == 0不應該放在這里，而是在處理完游戲結束的情況后作為一個單獨的案例：int result = getGameResult(); if (result != -5) { // Game is over! return result; } // Game is not over yet... check if we should search deeper if (depth == 0) { // We should stop searching. return evaluate(); // Use some heuristic to give an estimated value }
所以現在我們來解決你的核心問題：如何實作evaluate（在上面的代碼塊中使用）
對于手頭的游戲，您可以使用以下特征來獲得游戲的估計值：
計算一個玩家可能仍然可能的 4-in-a-row 數量。對于要計入該總和的一行 4 個單元格，它不應包含對手的任何動作。所以它們應該是空的或者有玩家自己的符號。如果對于 4 個單元格的行是這樣，則它應該作為 1 貢獻給為所有 4 個單元格的行計算的總和。從每個玩家的角度分別計算這個總和。
為了改進，如果在這些潛在的 4 行中，有一些被玩家占據了 3，那么給它們更多的權重（比如將它們計為 3 而不是總和中的 1）。類似地，對那些占用 2 個單元格的應用系數。
給定這樣計算的兩個總和，計算差異。如果為正，則表示它對 X 玩家有利，否則對 O 玩家有利。
最后轉換這個數字（例如除以 1000），以保證它在 (-1, 1) 之間，并且與贏/輸的值不同。使用整數可能會更好，因此使用值 1000 和 -1000 來表示輸贏，而不是 1 和 -1。
uj5u.com熱心網友回復：
如果您無法對樹進行足夠遠的評估以到達游戲結束，那么您需要有一些函式可以為不完整的游戲狀態生成近似分數。因此，如果 1 表示交叉獲勝，那么 0 和 1 之間的數字表示他們獲勝的可能性越來越大，而 0 和 -1 之間的數字表示他們可能會失敗。這個評估函式的細節完全取決于你正在玩的游戲，可能并不明顯這樣做的“正確”函式是什么。
例如，在國際象棋中，您可以撰寫以下一些函式來嘗試估計誰獲勝：
- 將玩家 A 的棋子數相加，減去玩家 B 的棋子數
- 與 #1 相同，但相對于它們通常的好壞來衡量棋子（例如，皇后比棋子更有價值）
- 與#2 相同，但撰寫一些復雜的邏輯來查看片段的排列，以嘗試猜測這種排列是否好。也許它會給有許多可用動作的棋子提供獎勵，而不是被困在其他棋子后面，或者當棋子對角排列以相互支持時會增加獎勵。
- 與 #3 相同，但使用神經網路和數十億個訓練游戲為您生成復雜的邏輯。
你的游戲有什么好的評價函式？恐怕我真的沒有一個很好的答案給你。弄清楚這一點需要一些游戲專業知識，并且很可能需要一些實驗。首先，也許您可??以做一些事情來確定哪些部分是“死的”（即，它們被包圍，因此它們不能促成一行 4），然后總結剩余的部分。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409390.html
標籤：