我想知道如何使用negamax算法。我正在嘗試在C＃中爲遊戲mancala編寫一個代理。當給定遊戲節點時，該算法給你一個單一的數字。如何使用negamax算法
假設我的AI玩家想要移動。 negamax函數返回一個單一的數字。所以它告訴我從這一點來看，最佳舉動的得分是多少。我怎樣才能用這個一個號碼？
如果是玩家A輪到我試着做出他可能的動作並檢查每個人的negamax。但是，如果我首先進行移動並檢查negamax，那麼當negamax運行時（讓我們假設我們仍然只有1個深度），它將評估移動，然後下一步必須是玩家B的移動。
我對此非常困惑。當我看到negamax僞代碼（例如在維基百科頁面上）時，它說要嘗試該玩家的移動。如果我這樣做，它會返回最高得分而不告訴我哪一次得分。
negamax應該如何使用？
這是一個有趣的。
這是關於探索可能移動樹中的每個節點。如果使用alpha-beta修剪，可以通過「修剪」（不評估）樹的某些分支來使算法更高效。我假設你沒有使用修剪，並且要看完整的樹。
如果Mancala是一個非常簡單的遊戲，就像Tic-Tac-Toe一樣，您可以在不需要「評估函數」的情況下實現算法。用井字遊戲，如果你玩完所有可能的動作，你可以獲得勝利，失敗或平局。你將在那裏執行一個negamax算法，而不考慮遊戲的中間狀態（即，在最後一個之前的任何移動），因爲可能的移動數量非常有限，並且AI引擎將容易地計算所有的一直到最後的可能性。另一方面，在國際象棋中，「評估函數」（以下簡稱EF）是必不可少的，因爲這個星球上沒有任何硬件可以計算出每一個可能的棋盤移動序列，直到遊戲結束。因此，大多數國際象棋AI將進入12-14級的深度，然後評估結果的位置，爲女王分配8點，爲白嘴鴉分配5點，爲主教或騎士分配3點，爲典當分配1點，諸如方格控制的東西（更多中心點控制點），國王安全等等。
對於曼卡拉，據我所知，可能需要一個評估函數足夠複雜，但也許該評估函數將是簡單的，例如仍然擁有的種子數量，也爲處於先進位置的種子增加點數。 （我查閱了Wiki Mancala，看起來好像有很多可能的變體 - 我不確定你在使用哪一個。）
因此，negamax算法需要實現一定的深度即，直到遊戲結束時使用所有可能的遊戲），並且使用簡單的EF。讓我們假設你將執行AI看5次深入。 negamax的好處在於它是完全對稱的和零和;換句話說，如果AI的位置評估爲5，則對於人類玩家評估爲-5。如果對於人類運動員評價爲13，則評價爲AI的-13。這是討論的「單數」。有了這一切在腦海中，AI算法將是這個樣子（再次，沒有修剪）：
1）檢查每一個可能的AI移動
2）對於每一個這種舉動，檢查每一個可能的對手響應
3）對於每一個這種可能的響應的，檢查每個可能的AI移動
4）對於每一個的那些可能的AI移動時，檢查每個可能的對手響應
5）最後，對於每個這些可能的運Ponent（波納恩特）的反應，檢查每一個可能的AI移動
現在我們已經達成了深度5，並且已經建立了一個樹與5級，大概葉十萬或數百萬（底層節點）的樹。您可以用這樣的方式編碼，即每個節點都引用其父節點，並引用其所有子節點，以便您可以輕鬆遍歷樹，從父節點到子節點，然後返回。
一旦樹設置不當，現在是時候實現negamax算法，具體如下（我們假定一個更高的分數是對AI玩家更好）：
6）對於每個4在所有AI兒童移動中找到HIGHEST評估，並修剪所有其他兒童。你正在決定從現在開始移動你的AI，以響應每個可能的第4個對手的反應。所以現在每個4級響應恰好有一個假設的5級響應。現在，您將您所做的五級孩子的評估分數分配給四級家長。這就是說，如果你達到第四級的對手移動，AI會讓這個特定的第五級移動，並且董事會將評估該分數。
7）接下來，您將評估每個第3級AI動作，並且對於每個第4級從現在的對手動作中找到LOWEST評估，修剪所有其他孩子，並指定第4級評分從最高的第五級節點）到第三級。除了使用LOWEST子分數（b/c這是一個AI動作而不是對手動作）之外，您的步驟與步驟6相同。
8）做第2級爲第6步一樣，發現在所有3 - 從 - 現在移動的最高評價，並分配到第二級節點的最高評價。
9）做第一級爲第7步一樣，發現在所有第二個從 - 現在移動的評價最低，並指定1級節點的最低評價。
10）看看所有的第一級節點，你的AI應該打出HIGHEST得分。
很明顯，你會作出深度不硬編碼爲5，而是一個參數，你會使用遞歸（如在Wiki）來做到這一點。要選擇深度，請查看運行需要多長時間，並將n設置爲等於最高深度，仍然可以實現快速AI響應。一旦你在這裏建立基礎知識，你可以在稍後添加修剪策略，通過不評估樹的整個分支來實現更大的深度，這顯然不是正確的行爲，但是這是我爲你規劃的完整的基本負分。
祝你好運，它應該是一個有趣的編程！
Onemancat給出了一個非常詳盡的解釋 - +1。
你的問題的簡短答案是，negamax返回某個特定位置的分數，所以你要做的是在第一層中播放每一個動作，爲每個產生的位置調用negamax來評估它，然後選擇移動以最好的成績作爲結果。
所以根據你的解釋，我一直在做對，並沒有意識到它。這是一個棘手的算法。我覺得它有點「奇怪」，但實際上我已經按照這裏的所有說明進行了操作。我正在使用alpha beta修剪。我確實需要評估功能（儘管如您所說，這非常簡單）。根本無法評估mancala的整個遊戲樹。感謝 – 2013-02-10 08:46:19
哦，至於遊戲規則，我使用的是諾基亞3310遊戲bantumi（這是一個mancala遊戲本身的實現）中實現的遊戲規則。 – 2013-02-11 08:41:10
我知道這是一箇舊的帖子，但當時我仍然無法完全理解它。昨晚我坐下來再讀一遍你的指示。主席先生，你現在是我沮喪的主要來源。因爲你，我設法寫了一個我自己無法戰勝的遊戲。感謝：D – 2013-05-14 08:31:58