機器學習解魔術方塊
機器學習習在各個領域都有重大的貢獻，但神通廣大的機器學習能不能解3x3的魔術方塊呢？Stephen McAleer等人發明Deepcube算法[1]，結合神經網路和蒙地卡羅樹搜尋(Monte Carlo tree search)找到新的方式去找魔術方塊的解法 ，有興趣的讀者可以到Deepcube的網站體驗[2]。
魔術方塊
3x3的魔術方塊大約有10的19次方種排列組合，而真的的解只有一種。魔術方塊有9個軸可以轉動，固定中間能縮減成6個軸，選定軸後可以選擇順時針或者逆時針旋轉，因此每次轉動有12種可能。
訓練資料與神經網路
將原始的魔方打亂，一次只動一格並將打亂的步驟順序當作是最佳解。下個步驟將訓練資料放入神經網路(圖1)進行訓練。最後一層有12顆神經對應到12種轉動的機率。
 |
| 圖1. 神經網路架構 |
蒙地卡羅樹搜尋
除了神經網路，此篇論文還搭配蒙地卡羅樹搜尋去找到魔術方塊的最佳解法。蒙地卡羅樹搜尋每次迭代包含4個步驟[3]，包含:選擇(Selection)、擴充(Expansion)、仿真(Simulation)和反向傳播(Backpropagation)。而仿真時會使用上面經過訓練的神經網路。蒙地卡羅樹搜尋模擬示意圖(圖2 右)。
 |
| 圖2. 右神經網路示意圖。左蒙地卡羅樹搜尋示意圖 |
結果
Deepcube在15步內打亂的魔術方塊都能找到解(圖3)。15步以後亂數的魔方雖然無法百分之百解出，但還是有80％以上。kociemba是利用群論去計算解，因此能百分之百解出。統計Deepcube解出的最佳路經(圖4)，可以發現很常用到aba-1這項技巧。
 |
| 圖3. 不同演算法的正確率比較 |
 |
| 圖4. 統計Deepcube使用到的技巧 |
撰文：謝明儒
參考資料
1. McAleer, S., Agostinelli, F., Shmakov, A., & Baldi, P. (2018). Solving the Rubik's cube without human knowledge. arXiv preprint arXiv:1805.07470. https://arxiv.org/abs/1805.07470
留言
張貼留言