博弈論是二人或多人在平等的對局中各自利用對方的策略變換自己的對抗策略,達到取勝目標的理論。博弈論是研究互動決策的理論。博弈可以分析自己與對手的利弊關系,從而確立自己在博弈中的優勢,因此有不少博弈理論,可以幫助對弈者分析局勢,從而采取相應策略,最終達到取勝的目的。
最小最大問題
最小最大問題( minimax ):用于確定計算機玩家在諸如井字游戲、跳棋、奧賽羅和國際象棋中的哪一步。這類游戲被稱為完美信息游戲,因為它可以看到所有可能的動作。拼字游戲并不是一個完美信息的游戲,因為你看不到對手的手,所以無法預測對手的動作。
可以把這個算法想象成人類的思維過程:如果我做這個動作,那么我的對手只能做兩個動作,每個動作都會讓我贏。所以這是正確的選擇。
用博弈樹數據結構表示井字游戲如圖 13-1 所示。
■ 圖 用博弈樹數據結構表示井字游戲
如果你認為所謂最小最大就是窮舉過程中找到的最差走法和最佳走法那就錯了,既然是對立的概念,當然是兩個對象,這里的最小最大是當前輪到 AI 走了, AI 進行窮舉并選擇一條對于 AI 來說最佳而對于人來說最差的走法,但是再考慮一下,機器也是有限的,對于象棋這樣棋盤較大的游戲,窮舉完博弈樹在當前科技下不可能,因此我們的最小最大算法需要一個深度,即向前走幾步,計算機就能在這個指定的比較小的整數下完成對博弈樹的窮舉。
當遍歷若干樹枝后不可能就結束了,如果在游戲沒有結束的情況下我們還需要一個評價啟發函數,這個函數用于判斷當前策略的價值,如果使用某走法能贏,就返回一個大的正數;如果這種走法會輸,就返回一個大的負值;如果走法會產生和局,就返回一個 0 左右的數;如果由于當前博弈樹深度沒辦法判斷局面,那么評價函數就會返回一個啟發值。
參考程序：
