# AI Homework Project

## 題目要求和基本注意事項

### 基本介紹：

### 需要修改和注意的檔案：


### 題目設計：

## 解題過程

### Question 5a：


要修改 `inference.py` 中的 class：`DiscreteDistribution`
其中的 Function `normalize` 還有 `sample`

#### normalize：

註解中有此 Function 的範例結果：

注意：
* 直接修改值 Instead of 回傳
* 依照 Example，normalize 過後再加入值並不會直接對新加入的值 Normalize
（但我不知道如果之後有需要再呼叫 `normalize()` 的話會如何，暫時先不管）

Implementation：

> 先暫存所有值的總和，並直接 iterably 將每個值除上總和

在 Testing 時發生 Divide by zero 的錯誤，所以加上例外判斷：
> 如果全部元素都是 0 時就不做任何處理

#### sample：

此 Function 的範例結果：

題目說明中有說到可以運用內建的 `random.random()`

我的想法：
* 用 `random.random()` 隨機產生一個 0~1 之間的數字
* 配合 Distribution 當作 range，用比大小的方式來決定應該回傳哪個 sample

另外，題目說明中提到在 call 這個 function 前不一定會先 call `normalize()`
但是我覺得先 normalize 後比較好處理，所以在 function 中有建立一個 temp 並 normalize
（避免直接修改原本的內容而影響到其他部份，雖然目前不確定直接 normalize 會不會有影響）

Implementation：
> 製作以下示意圖呈現我的想法：
> 
> 看看選出的 random value 座落於哪個範圍，就回傳哪個 key

小修改，效率更高：
> 直接在 runtime 對每個 value 進行 normalize，效率更高

### Question 5b：


要修改 class `InferenceModule` 中的 `getObservationProb`
return $P(noisyDistance ∣ pacmanPosition, ghostPosition)$

可以運用已經寫好的：
* `busters.getObservationProbability(noisyDistance, trueDistance)`，回傳 $P (noisyDistance ∣ trueDistance)$
* `manhattanDistance()`，回傳 Pacman 和 Ghost 之間的距離

同時，如果我們已經將 Ghost 送進 jail 後，Sensor 就要持續回傳 None
（Funtion 接收到的 observation 會是 None，所以 None 的機率為 1）

Implementation：

>依照題意處理到所有狀況就結束了：
>* 先判斷特殊的 None 情況，分三種 case，只有在 Ghost 在 jail 時會是 None（return 1），其餘不可能（return 0）。必須先判斷因為 NoneType 沒辦法拿去算 distance
>* 剩下的狀況用 `pacmanPosition` 和 `ghostPosition` 算 manhattan distance（true distance），接著當作參數傳入 `busters.getObservationProbability(noisyDistance, trueDistance)`，得到的即為 $P(noisyDistance ∣ pacmanPosition, ghostPosition)$

Quetion 5 通過：

### Question 6


修改 class `ExactInference` 中的 `observeUpdate` function
可以運用上一題寫的 `getObservationProb`，而且應該要看過每一個點（`self.allPositions`）
（應傳入參數： observation, `gameState.getPacmanPosition()` , 其中一個點, `self.getJailPosition()`）
此 Function 要更新 `self.beliefs`，是一個 `DiscreteDistribution` object


要從 large cloud 開始，並慢慢依照 observation 縮小
可以參考課程中 prior distribution 和 posterior distribution 概念：

式子為：

將 belief 印出，可以看到起始的 uniform distribution 已經被處理好：

所以我們只要依照式子做後續的機率累積就好。

Implementation：
> 當 Observation 傳入時，iterate 過每個點，得到各個點的 observation probability，並乘上 prior probability 得到 posterior probability，更新每個點的 belief。

Question 6 通過：

### Question 7


Agent 除了知道 Ghost 可能的位置之外，也會知道 Ghost 可能的移動情形
例如：Ghost 不能穿牆、不能在一個 time step 移動超過一格

實做 class `ExactInference` 中的 `elapseTime`
依照目前 Distribution，將每個 position 的 belief 更新成下一個 time step 的機率分佈

可以運用 `self.getPositionDistribution` 得到如果 ghost 目前在某個 position 的話，下一個 time step Ghost 會在哪些點的機率分佈

> 製作以下示意圖呈現：
> 

所以在此 Function 中，我們有目前 Ghost 所在位置的機率分佈
下一個 time step 機率分佈會依照 newPosDist 擴散出去

Implementation：
> * 建立一個新的 DiscreteDistribution 物件作為下一個 time step (t+1) 的機率分佈
> * iterate 每個點，將現在這個點的機率值 `currentProb` 乘上下一個 time step 的機率分佈，累加這些值並 normalize 就可以得到下一個 time step 的機率分佈
> * 將 `beliefs` 更新成下一個 time step 的機率分佈

Question 7 通過：

### Question 8


實做 class `GreedyBustersAgent` 中的 `chooseAction`
先依照機率求出每個 Ghost 最有可能的位置，然後選擇一個動作來讓 Pacman 更靠近最近的 ghost
可以運用 `self.distacer.getDistance` 來求出兩個點的 maze distance
另外，可以用 `Action.getSuccessor` 求出如果選擇某個動作的話，Pacman 新的位置會在哪裡
`livingGhostPositionDistributions` 含有每個 uncaptured ghost 的機率分佈，是一個 list

補充：可以運用文中沒提到的 argMax function 得到 Distribution 中值最大的 key：

Implementation：
> 變數：
> * `most_likely_positions`：每個 Ghost 最有可能的位置
> * `distances`：Pacman 和每個 ghost 的 maze_distance
> * `nearest_ghost_pos`：最近的 ghost 的位置
> * `nearest_ghost_distance`：最近的 ghost 與 Pacman 的 maze distance
>
> 流程：iterate 過每個可行的 Action，測試選擇此 Action 後會到達哪個位置，比對到該位置後是否可以縮小跟最近的 Ghost 之間的 maze distance，找出可以讓 distance 變得最小的 action 並回傳。

Question 8 通過：

### Question 9


接下來幾題改用 particle filtering 的方法來實做
修改 class `ParticleFilter` 中的 `initializeUniformly` 和 `getBeliefDistribution`
`initializeUniformly` 要將 particles 均勻的分佈在所有 position 中。用一個 list 儲存 positions（代表某個 particle 位於哪一個 position），可以善用 modular operation
`getBeliefDistribution` 要將 particles 轉為 DiscreteDistribution

Implementation：
> `self.numParticles`：particle 的總數
> 要均勻的分佈 particles 在各個 position，意思就是將 legal positions 平均的放入 `self.particles`，直到 `self.particles` 長度等於 `self.numParticles`

> 建立 DiscreteDistribution 物件，統計 particle 所在位置的機率分佈並 Normalize

Question 9 通過：

### Question 10

修改 class `ParticleFIlter` 中的 `observeUpdate`
依照目前 particles 的分佈和 observation，運用 `self.getObservationProb` 建立出一個 weight distribution，並從利用此分佈重新 sample particles
例外：如果所有 particle 的 weight 都是 0，則呼叫 `initializeUniformly`

> iterate 過所有 particles（裡面存的是某個 particle 的位置），依照 observation 求出 particle 在此位置的機率作為 weight，將這個 weight 累加到 新的 weights 分佈上
> 處理例外狀況：如果新的 weights 分佈總和為 0 的話，呼叫 `initializeUniformly`，否則依照 weights 分佈 sample 新的 particles

Question 10 通過：

### Question 11
修改 class `ParticleFilter` 中的 `elapseTime`
求出下一個 time step 的 particle 分佈，取代原本的 `self.particles`
一樣可以運用 `self.getPositionDistribution` 取得下一個 time step 的機率分佈，當給定目前 ghost 的位置時

Implementation：
> `newPosDist`：給定目前 particle 位置，下一個 time step 的位置機率分佈
> 因為 particle 總數不會變（一個 particle 對應到一個新的 particle），所以直接依照 `newPosDist` sample 一個新的 particle 位置
> 得到一個新的 particle list，即為下個 time step 的 particle 分佈狀況

Question 11 通過：