背景：
從三月份到現在也自學小一年了。今年的目標本來是搞懂阿法狗怎麼回事。但是，期間被很多東西所吸引，比如自然語言處理、神經網絡翻譯、Cambridge data、文本情感分析。回顧下今年過得很充實，也收穫很多。雖然還是時不時地拖更，但是也是因為公眾號的存在，讓懶散的我覺得我有一種義務感，也行成了一種學習的動力。不過，對於最初的目標還是沒有啥進展。當初也是完全因為Alphago的驚豔使得我踏上自學的路程。開啟本系列也是為了重拾初心，一方面督促自己學習，另一方面希望能與大家分享我自學過程中的收穫。並且由於我自己沒有技術、數學、編程背景，所以可能會更貼近及瞭解大家的疑惑。
Why Minimax
AlphaGo誕生於2016年度，它誕生的一個巨大意義在於用計算機成功的戰勝了人類圍棋。AlphaGo誕生也很大程度上推動了AI的火爆。而圍棋之前一直被認為是不可戰勝的。而早在1997年IBM的Deep Blue 就已經在國際象棋項目打敗了國際象棋大師。電腦掌握國際象棋與圍棋的時間居然相隔了近20年。那麼Deep Blue為什麼不能在圍棋上勝出呢？ AlphaGo 與 Deep Blue的差異在哪裡呢？
所以覺得從Deep Blue 的核心算法學習開始學習，從Deep Blue來開啟Toward AlphaGo系列更容易被接受。
而Deep Blue的核心算法是 Minimax，而我會用井字棋來講述Minimax算法。此篇文章的圖片和算法描述部分大部分來自於Toward DataScience
井字棋的英文名字是Tic Tac Toe，其規則很簡單，就是橫、豎、斜 都是同樣的圖案方獲勝。並且井字棋是回合制的
Minimax&Tic Tac Toe
這個遊戲中分為兩方，X和O。假設我方為X。
如上圖所示，假設我們當前的狀態為0.0，我們有三種選擇的可能（1.0，1.1，1.2）
1.0狀態下我方獲勝（+1）；
1.1 給了對手方兩個可能的選擇（2.0，2.1）。 其中2.0狀態下，對方直接獲勝，所以對於我方來說是落敗（-1）；其中2.1後只有一種可能3.0，其狀態下我方獲勝（+1）
1.2 給了對手方兩種可能（2.2，2.3），其中2.2對方獲勝，我方落敗（-1）；其中2.3只有一種可能性就是3.1，我方獲勝（+1）
那麼我們怎麼用Minimax來理解和解決這種狀態呢？
下棋最重要的是關注未來趨勢的變化，當然井字棋沒那麼複雜，因為變化不多。那麼我用上圖中最簡單的一個例子來說明。
比如上圖中的狀態2.3 之後只有一種可能性就是狀態3.1。而狀態3.1是X方必贏的局面，那麼可以說明狀態2.3也是X方必贏的局面（因為之後只有一種可能性）。那這就是一種勝負判斷的反向傳遞的過程。你走到2.3，你就能知道X方是要必贏的局來。那麼如果3.1是+1分，那麼2.3也相應的是+1分；
但是很多狀態下並不是像2.3一樣接下來只有一種可能性。對於多種可能性怎麼樣去做分數的反向傳遞呢？這裡就要講到Minimax的思想了。
首先，井字棋是一種雙方回合制的遊戲，那麼假設X獲勝是 正數分；O方獲勝是負數分；
那麼，每一層的走向其實取決於下棋方，比如我在狀態0.0是選擇1.0，1.1，還是1.2呢？ 這取決於X方。那麼自然他就會選擇正數。比如，在狀態0.0肯定車選擇1.0咯。
結果，minimax就能解決從 1.0，1.1，1.2 反向傳遞到0.0的選擇。同樣的道理，那麼也能將分數從3傳到2，2傳到1.
Minimax 思考
通過上一部分，我們知道了Minimax是通過將分數反向傳遞的過程，並且假設對方也採用最優解，從而能夠對未來的走向做出判斷。但是，我最初看到這個方法時，有幾個疑問與大家分享：
Q1. Minimax在分數反向傳遞的過程種有一個前提，就是你構建了整個未來的Game Tree，即你已經算出來了未來所有的可能，從而能進行反向傳遞。對於井字棋這種簡單的遊戲（3⁹ = 196839 種可能）可能行得通，對於國際象棋是行不通的；
Q2. 另外，井字棋是將確定的勝負反向傳遞回去。但是對於象棋來說，可能要50回合才能分勝負，再疊加上50個回合的變化，是沒辦法算出來的。
對於這些問題，我看了一些文章。大概有兩個解釋：
A1. 對於Minimax有一種優化的方法，alpha-beta pruning。其大概的思路就是，比如你個人下棋的時候，對於那種送車的棋是不會去下的。所以這也可能減少計算這種無謂的可能性，這個將在下一篇介紹；
A2. 對於井字棋是將最終勝負作為分數來計算。但是，其實可以有其他的方法。比如，我們對於狀態的評分可以改為車100分，馬50分，兵10分。那麼這樣我們就能計算任何狀態下的分數來。舉個例子，你知道如果下某部棋，你會比對方少一個車，那麼就應該儘量避免這種選擇；
另外，也能通過控制層數來限制計算量。比如我們只需要計算5層，我能夠大概肯定在5步之後，我能獲得優勢，比如比對方多一個馬。
當然對於棋局狀態的評分，並不能完全依靠子的數量來定，位子也很重要。後續如果講到Chess Minimax AI，我會再找找資料。
總結
本期作為Toward AlphaGo的開篇，也是從Deep Blue的Minimax學起。看完以上部分大家也能看出來，其實Minimax還是屬於Brutal Force強搜，構建一個完成的Game Tree。這個在圍棋上應用肯定效果不佳。不過對於井字棋綽綽有餘。下面是Github上一個Minimax在Tic Tac Toe的遊戲，感興趣的朋友可以嘗試下。https://github.com/Cledersonbc/tic-tac-toe-minimax
閱讀更多 繁林林與機器學習 的文章
