# RL Lab1-2048 Report
by 314554025 鄭睿宏

[TOC]

## 1. Training Result (Best Method)
- 可參考 Appendix: [Appednix: 4-tuple + 6-tuple (best)](https://hackmd.io/JlcTliGmSwizejIXnkjUDQ?both=&stext=2277%3A46%3A1%3A1758465835%3ASHVwqc)
- mean score & episodes:
- 2048 win-rate: (game_all_6_tuple_p5_4_tuple_p11)

## 2. Implement Detail
### 2-1. Describe the implementation and the usage of 𝑛-tuple network.

N-tuple 是一種特徵提取的方式，類似: CNN 中的 Convolutional Kernel，是用來觀察棋盤盤面 (2048) 的方法。
使用 N-tuple 可以只分析盤面中的特定 pattern ，而不需要觀察整個棋盤盤面
同時觀察特定 Pattern 有以下優點:
1. 節省記憶體:
- 相比較觀察全部盤面，需要考慮: 每格16+1種組合，盤面共16格，
也就是: (1(空格) + 16(可能的數字)) ^ 16 (格數) 種盤面
=> 17^16 = 4*10^19 種盤面
- 而如果只觀察部分 Pattern，如: 6 個 6-tuple，只需要觀察6格
也就是: 6(n-tuple數) * (1(空格) + 16(可能的數字)) ^ 6 (格數) 種盤面
=> 6 * 17^6 = 14.5*10^7 種盤面
(使用 n-tuple 大幅減少考慮的盤面數)

2. 盤面特徵:
在棋盤上觀察時，有時候局部資訊會提供更多的資訊:
分析全盤資訊，並非每格都是十分重要，可能觀察更多是不重要的資訊，
透過觀察局部特徵，才更能了解到盤面的特徵

Implementation:
- 因為本次作業的 n-tuple 會使用 isomorphism 進行 tuple 的簡化，
- 因此默認每個 isomorphism 貢獻的 reward 是一樣的
- 所以在進行 estimate 計算時，會需要將所有 isomorphism 的 reward 計算加總後，再進行平均

N-tuple 選擇
> 在這次作業中，我使用的是 5 個 6-tuple 和 11 個 4-tuple
> 由於，硬體設備問題，6-tuple 是我能使用的最大 tuple
> 因此 6-tuple 的部份，我分析可能出現的 6-tuple 非 isomorphism 組合
> 如下圖的這五種 (3種 L-shape 、2種 rectangle ):
> ```
> 0, 1, 2, 3, 4, 5
> 4, 5, 6, 7, 8, 9
> 8, 9, 10, 11, 12, 13
> 0, 1, 2, 4, 5, 6
> 4, 5, 6, 8, 9, 10
> ```
> 
> (Link: https://link.springer.com/book/10.1007/978-981-96-4596-1)
>
> 而 4-tuple 的部分，我則使用 11 個 非 isomorphism 組合
> (2種 line 、3種 square、 6種 L-shape)
> ```
> 0, 1, 2, 3 // line
> 4, 5, 6, 7 // line-mid
> 0, 1, 4, 5 // square-corner
> 1, 2, 5, 6 // square-edge
> 5, 6, 9, 10 // square-mid
> 0, 1, 2, 4 // L-shape-in
> 1, 2, 3, 5 // L-shape-in
> 4, 5, 6, 8 // L-shape-mid
> 5, 6, 7, 9 // L-shape-mid
> 8, 9, 10, 12 // L-shape-out
> 9, 10, 11, 13 // L-shape-out
> ```
>
> 選擇的理由:
> 當使用 11 個 4-tuple 進行訓練時，[Appendix: 11 個 4-tuple (快速收斂)](https://hackmd.io/JlcTliGmSwizejIXnkjUDQ?both=&stext=3153%3A33%3A1%3A1758465595%3AdZUTnx)
> - 收斂速度極快，很快(20000步)就達到85%的 2048 win-rate
> - 但20,000步後，成長速度極慢，最後10,0000步時，停在87%左右
>
> 當使用 5 個 6-tuple 進行訓練時，[Appendix: 5 個 6-tuple (分數低、穩定成長)](https://hackmd.io/JlcTliGmSwizejIXnkjUDQ?both=&stext=4130%3A38%3A1%3A1758465736%3AoctQih)
> - 收斂效果穩定，最後100,000步時，停在85%，但仍有些微成長空間
>
> 因此，我認為將兩個 feature 結合，可能會同時保有 4-tuple 收斂速度快的特性
> 並在快速收斂後，仍有較複雜的 6-tuple 特徵可以進行捕捉，進行成長
>
> 而實驗結果也如猜想，當兩feature結合，[Appednix: 4-tuple + 6-tuple (best)](https://hackmd.io/JlcTliGmSwizejIXnkjUDQ?both=&stext=2277%3A46%3A1%3A1758465835%3ASHVwqc)
> 83,000步時 2048 的 win-rate 也達到了 93.1%，
> 
> 同時，在100,000步時，8192 也占了 17.7%
> 

### 2-2. Explain the mechanism of TD(0).

Temporal Difference Learning (TD Learning)
在 TD(0) 中，state 的 value 是根據 reward 和 下一個狀態的估計價值進行更新(update)的 ，更新公式如下：

$V(s_t) \leftarrow V(s_t) + \alpha \big( r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \big)$

- $V(s_t)$：當前狀態的估計值
- $\alpha$：學習率 (Learning Rate)
- $\gamma$：Discount Factor (用來收斂的)
- $r_{t+1}$：從 $s_t$ 到 $s_{t+1}$ 的獎勵 (reward)
- $V(s_{t+1})$：下一狀態的估計值 (程式中的 estimate function)

相對於一般的 Monte-Carlo 需要整個 episode 跑完才能更新，使用 TD-Learning 可以即時根據下一狀態的 estimate 進行 value 修正。

### 2-3. Describe your implementation in detail including action selection and TD-backup diagram.

#### Action Selection
在 2048 中，agent 有 上、下、左、右 四種動作
且 pop-up 新方塊出現的機率變成 80%(方塊2)、20%(方塊4)

而我的實作策略如下：
1. 模擬所有可能動作: 對每個動作計算即時獎勵與後續狀態。
2. 使用 N-tuple Network 評估後續狀態的價值。
3. 選擇最高價值(select-best)的動作作為策略。

我的方法是選取最佳 Greedy Policy，但我認為也可透過 UCB algorithm (Upper Confidence Bound) 進行優化，但最後並未嘗試

#### TD(0) Update

執行動作後，會按照 TD(0) 進行更新權重

TD(0) 更新公式：
$w \leftarrow w + \alpha \big( r + \gamma V(s') - V(s) \big) \nabla_w V(s)$

- $w$：n-tuple Network 權重
- $r$：reward
- $s'$：下個狀態

TD(0) 更新時會透過 bitwise 進行 tuple 的 index 編碼(indexof)，並能透過 index 到Lookup Table (權重表) 進行更新

#### TD-Backup diagram


flowchart TD
    A[當前狀態 s_t] -->|選擇動作 a_t| B[執行動作並得到獎勵 r_{t+1}]
    B --> C[轉移到新狀態 s_{t+1}]
    C --> D[估計 V(s_{t+1})]
    A --> E[估計 V(s_t)]
    D --> F[計算 TD 誤差 δ = r_{t+1} + γV(s_{t+1}) - V(s_t)]
    E --> F
    F --> G[更新 N-tuple 權重 w ← w + αδ]

---
## Appendix (Other N-tuple attempt)
### Name: game_all_6_tuple_p5_4_tuple_p11 (最佳)
- Training time: 5hr 46min
- Config

    TDL2048-Demo
    alpha = 0.1
    total = 100000
    seed = 1039561096
    4-tuple pattern 0123, size = 65536 (256KB)
    4-tuple pattern 4567, size = 65536 (256KB)
    4-tuple pattern 0145, size = 65536 (256KB)
    4-tuple pattern 1256, size = 65536 (256KB)
    4-tuple pattern 569a, size = 65536 (256KB)
    4-tuple pattern 0124, size = 65536 (256KB)
    4-tuple pattern 1235, size = 65536 (256KB)
    4-tuple pattern 4568, size = 65536 (256KB)
    4-tuple pattern 5679, size = 65536 (256KB)
    4-tuple pattern 89ac, size = 65536 (256KB)
    4-tuple pattern 9abd, size = 65536 (256KB)
    6-tuple pattern 012345, size = 16777216 (64MB)
    6-tuple pattern 456789, size = 16777216 (64MB)
    6-tuple pattern 89abcd, size = 16777216 (64MB)
    6-tuple pattern 012456, size = 16777216 (64MB)
    6-tuple pattern 45689a, size = 16777216 (64MB)

- mean score & episodes:
- 2048 win-rate: (game_all_6_tuple_p5_4_tuple_p11)

### Name: game_4_tuple_p11 (快速收斂)
- Training time: 3hr 13min
- Config

    TDL2048-Demo
    alpha = 0.1
    total = 100000
    seed = 2822849220
    # [Patterns]
    4-tuple pattern 0123, size = 65536 (256KB)
    4-tuple pattern 4567, size = 65536 (256KB)
    4-tuple pattern 0145, size = 65536 (256KB)
    4-tuple pattern 1256, size = 65536 (256KB)
    4-tuple pattern 569a, size = 65536 (256KB)
    4-tuple pattern 0124, size = 65536 (256KB)
    4-tuple pattern 1235, size = 65536 (256KB)
    4-tuple pattern 4568, size = 65536 (256KB)
    4-tuple pattern 5679, size = 65536 (256KB)
    4-tuple pattern 89ac, size = 65536 (256KB)
    4-tuple pattern 9abd, size = 65536 (256KB)

- mean score & episodes:
- 2048 win-rate: (game_4_tuple_p11)

### Name: game_6_tuple_p5 (效果不好，但穩定成長)
- Training time: 2hr 38min
- Config

    TDL2048-Demo
    alpha = 0.1
    total = 100000
    seed = 3320676156
    6-tuple pattern 012345, size = 16777216 (64MB)
    6-tuple pattern 456789, size = 16777216 (64MB)
    6-tuple pattern 89abcd, size = 16777216 (64MB)
    6-tuple pattern 012456, size = 16777216 (64MB)
    6-tuple pattern 45689a, size = 16777216 (64MB)

- mean score & episodes:
- 2048 win-rate: (game_6_tuple_p5)