AI 筆記15 - Minimax演算法

演算法

不是很好懂，最好搭配視覺化的例子：

以下例子的minimax DFS search tree來說：

0. function Decision是main function，我們讓max先下，所以先呼叫maximize(initial state)

1. root node是max ply，所以max檢查其目前的state並非終局，就對max所有可以下的move形成的child node選擇一個最大的utility score的move。但是要怎麼計算這些moves的utility score呢？ 由於下一個ply是min的，所以要把新的state丟進去minimize，讓min去計算符合他利益的，然後我們根據min的選擇，才能知道怎麼克服對手的選擇（maximize)。

2. min ply的邏輯和1.相似

3. 最終會抵達terminal state, 最後再return到root。


看起來minimax是一個每次要下一個move的時候就必須search過一次，因為DFS抵達end state就結束了，不會再search ancestor / siblings，所以每個ply都要計算一次minimax score。

Performance

就是DFS的performance。
不過看不懂他的terminal nodes數目怎麼算出來的？

所以很明顯，不可能每次search都抵達terminal state（通常game下一步是有時間限制），我們需要有方法來:

1. 夠好的決定就好：多幾步(ply) 的score即可
2. 限制搜尋深度 (IDS)
3. 避免不必要的搜尋 （pruning)

以上三者可以相輔相成，不是互斥的。