對抗性搜尋

對抗性搜尋是一種搜尋，在此檢查當嘗試在世界範圍內進行計劃而其他代理正在計劃針對
時出現的問題。

• 在之前的主題中，我們研究僅與單個代理相關聯的搜尋策略，該代理旨在找到通常以一系列動作的形式表達的解決方案。
• 但是，可能存在多個代理在同一搜尋空間中搜尋解決方案的情況，這種情況通常發生在遊戲中。
• 具有多個代理的環境被稱為多代理環境，其中每個代理是其他代理的對手並且彼此競爭。每個代理都需要考慮其他代理的操作以及該操作對其效能的影響。
• 因此，搜尋兩個或更多具有相互衝突目標的玩家試圖探索解決方案的相同搜尋空間的搜尋稱為對抗搜尋，通常稱為遊戲。
• 遊戲被建模為搜尋問題和啟發式評估功能，這些是有助於在AI中建模和解決遊戲的兩個主要因素。

AI中的遊戲型別

• 完美資訊：擁有完美資訊的遊戲是代理可以檢視整個電路板的遊戲。代理商擁有關於遊戲的所有資訊，他們也可以看到彼此的動作。例如Chess，Checkers，Go等。
• 不完美的資訊：如果在遊戲中代理商沒有關於遊戲的所有資訊並且不知道正在發生什麼，這種型別的遊戲被稱為具有不完全資訊的遊戲，例如井字遊戲，戰艦，盲人，橋，等等
• 確定性遊戲：確定性遊戲是那些遵循嚴格模式和遊戲規則的遊戲，並且沒有與之相關的隨機性。例如國際象棋，Checkers，Go，tic-tac-toe等。
• 非確定性遊戲：非確定性遊戲是那些具有各種不可預測事件且具有機會或運氣因素的遊戲。這個機會或運氣因素是由骰子或卡片引入的。這些是隨機的，每個動作響應都不是固定的。這種遊戲也被稱為隨機遊戲。
  範例：步步高，壟斷，撲克等

注意：在本主題中，將討論確定性遊戲，完全可觀察的環境，零和，以及每個代理交替行動的位置。

零和博弈

• 零和遊戲是對抗性搜尋，涉及純粹的競爭。
• 在零和遊戲中，每個代理人的效用收益或損失都與另一個代理人的效用損失或收益完全平衡。
• 遊戲中的一個玩家嘗試最大化單個值，而其他玩家嘗試最小化它。
• 遊戲中一個玩家的每次移動都被稱為ply。
• Chess和tic-tac-toe是零和遊戲的例子。

零和遊戲：嵌入式思維

零和遊戲涉及嵌入式思維，其中一個代理人或玩家試圖弄清楚：

• 該怎麼辦。
• 如何決定行動
• 需要考慮他的對手
• 對手也認為該怎麼做

每個玩家都試圖找出對手對他們行為的反應。這需要嵌入式思維或後向推理來解決AI中的遊戲問題。

問題正式化

遊戲可以定義為AI中的一種搜尋，可以通過以下元素形式化：

• 初始狀態：它指定遊戲在開始時的設定方式。
• Player(s)：它指定哪個玩家在州空間中移動。
• Action(s)：它返回狀態空間中的合法移動集。
• Result(s，a)：它是轉換模型，它指定狀態空間中移動的結果。
• 終端測試：如果遊戲結束，終端測試為真，否則無論如何都是假的。遊戲結束的狀態稱為終端狀態。
• Utility(s，p)：效用函式給出遊戲的最終數值，該遊戲以玩家p的終端狀態s結束。它也被稱為支付功能。對於國際象棋，結果是勝利，損失或平局，其支付值為+1,0，?。對於井字遊戲，效用值為 +1，-1和0。

遊戲樹

遊戲樹是樹的節點是遊戲狀態的樹，樹的邊緣是玩家的移動。遊戲樹涉及初始狀態，動作功能和結果功能。

範例：Tic-Tac-Toe遊戲樹：
下圖顯示了tic-tac-toe遊戲的遊戲樹的一部分。以下是遊戲的一些關鍵點：

• 有兩個玩家MAX和MIN。
• 玩家有另一個轉彎，從MAX開始。
• MAX最大化遊戲樹的結果
• MIN最小化結果。

範例說明：

• 從初始狀態開始，MAX首先開始時有9次可能的移動。MAX放置x和MIN位置o，兩個玩家交替播放，直到我們到達一個葉子節點，其中一個玩家連續三個或所有方格都被填充。
• 兩個玩家都將計算每個節點，minimax，minimax值，這是針對最佳對手的最佳可實現效用。
• 假設兩位球員都非常了解井字遊戲並且發揮出最好的發揮。每個球員都在盡力防止另一個球員獲勝。MIN在比賽中對陣Max。
• 所以在遊戲樹中，有一層Max，一層MIN，每層都稱為Ply。最大位置x，然後MIN放置o以防止Max獲勝，並且此遊戲繼續直到終端節點。
• 在這裡MIN贏，MAX贏，或者是平局。這個遊戲樹是MIN和MAX正在玩tic-tac-toe和輪流交替的可能性的整個搜尋空間。

因此，對抗極小極大程式的搜尋工作如下：

• 它旨在找到MAX贏得比賽的最佳策略。
• 它遵循深度優先搜尋的方法。
• 在遊戲樹中，最佳葉節點可以出現在樹的任何深度。
• 將minimax值傳播到樹，直到發現終端節點。

在給定的遊戲樹中，可以根據每個節點的最小極大值來確定最優策略，其可以寫為MINIMAX(n)。MAX更喜歡移動到最大值狀態，MIN更喜歡移動到最小值狀態，然後：