對抗搜索
- 博弈問題
博弈問題窮舉有時可以獲得必勝結果，但是稍微復雜一點的問題就很難窮舉了线欲。 - 極大極小過程
- alpha-beta剪枝
- Monte-Carlo博弈
極大極小過程
極大極小過程的想法非常直白明场，即：我方走步，則選擇極大值李丰；對方走步苦锨，則選擇極小值。
極大極小過程是博弈問題的一個最基本的決策模式趴泌，alpha-beta剪枝法是建立在極大極小過程基礎上的舟舒。
alpha-beta剪枝法
假如A和B博弈，不妨令局面估值函數為A的利益嗜憔，那么A追求節(jié)點值極大秃励，B追求節(jié)點值極小。
定義：極大節(jié)點的下界為alpha吉捶，極小節(jié)點的上界為beta夺鲜。
剪枝：后輩節(jié)點的beta<=祖先節(jié)點的alpha，alpha剪枝呐舔；后輩節(jié)點的alpha>=祖先節(jié)點的beta币励，beta剪枝。
MyRemark
這個地方可能會給出一個樹然后考手寫求解過程珊拼，一個比較簡單的手寫方法是食呻，先把每一層是極大還是極小標出來，然后標注這一行寫alpha還是beta，之后從最后一層開始向上推搁进。正常情況下一定是alpha小于beta的浪感。如果出現alpha大于beta，就從中間剪開饼问。這時候影兽，被剪開上面是誰，就是誰剪枝莱革。
實際實現的時候會發(fā)現峻堰，在ab剪枝法中，局面評價函數是非常重要的盅视。深藍能夠依靠這個算法實現捐名，很大程度上是因為成功構造出了一個局面評價函數。
在做大作業(yè)的時候闹击，實在是沒想出來合適的局面評價函數镶蹋，效果特別差，所以最后用了蒙特卡洛赏半。不過alpha-beta剪枝的效率真的是很好贺归，現在想想假如用蒙特卡洛的結果訓練神經網絡，把這個作為估值函數断箫，這樣就相當于沒有時間限制拂酣，算是一種cheat的方式吧（攤手）。
Monte-Carlo模擬
蒙特卡洛方法就很簡單仲义，就是不斷地試婶熬，然后選擇最優(yōu)的。
主要就是UCT算法埃撵。每次模擬赵颅，假如沒有拓展就拓展，每次拓展走子的時候暂刘，都選擇UCB1最大的點走子饺谬。
最終選擇被模擬次數最多的節(jié)點作為最佳走步。
AlphaGo用的是Monte-Carlo鸳惯，顯然是因為圍棋比象棋復雜太多商蕴，局面估值函數實在是不好做叠萍。
AlphaGo在實際做的時候有以下幾個操作：
- 利用策略網絡縮小搜索范圍
- 將估值網絡的結果結合到信心上限的計算中
- 一個節(jié)點被模擬一定的次數之后才擴展（這個還是挺重要）
- 最終選擇模擬次數最多的節(jié)點作為最佳走步
這個部分做了一個大作業(yè)芝发，可能就不考了吧（天真臉）
