Udacity AI Project 2 - Isolation Game Agent (3)

AI的有趣弔詭

AI領域中嘗試解決的問題通常都是exponential running time problem，所以我們事實上是要找出怎麼hack exponential的方法，但是弔詭的是一但找到了，通常人們就不再認為這是一個AI問題 @@

關於Minimax的小疑問

minimax的令人奇怪的一點是，我們幫min node猜想他的optimal choice的時候，用的是我們的heuristics，對手又不見得會採取一樣的思維，這樣minimax為什麼有用？

理想的search結果是直接search到end state，再讓search tree中的root來判斷一個最好的選擇。問題是我們會用一大堆類似alphabeta-pruning的原因就在於我們無法search到end state，花的時間太大了（除非量子電腦？！）。所以我們才會用heuristics在某個中間state就要評估分數了。

理論上如果我們的heuristics能給出對目前state一個接近真正的判斷分數的話，不論對手是用哪種 heuristics，都能“猜出”對手在每個search depth中的optimal的選擇。因為對手的heuristics如果遜於你，他heuristics中最好的optimal move可能只是你的heuristics的suboptimal move，這樣你幫他猜測的選擇是勝於他的，所以你的選擇已經建立在對手是選optimal move的基礎上。如果對手的heuristics勝於你，那情況仍然是正面的，因為這事你在有限的能力中能猜到對方最好的move，但是可能只是對方的suboptimal move，所以你的猜想錯了，輸了也不冤枉。

3-player game

三人以上的game，minimax就不適用了，這時候game tree還是類似，但是會多一個layer給第三個player，每個layer就update對應的player選擇evaluation score最高者，leaf node就回傳三個player各自觀點的evaluation score，然後往上propagate:

Isolation的小秘訣

isolation還有一些implementation的小技巧：

1. symmetric
由於isolation board是一個square，意思就是如果旋轉棋盤，

旋轉0度：