來自我的知乎文章：https://zhuanlan.zhihu.com/p/127782718
CSDN插入視訊不友善，就簡單回憶下過程了
最近整理文檔，發現了18年參加的智能車競賽寫的一個遊戲算法，這是我第一次寫的一個超過1000行代碼程式，當時也是完全沒有接觸過算法上的東西，一邊學一邊寫磕磕碰碰竟然也把這個事情做成了。現在上了研究所學生，遇到的都是控制理論這方面的東西，算法未來應該是不會再接觸了，把當時的思路在這裡整理一下 也算對這個方向畫個句号了。
當年決賽的題目是 步步為營 桌遊的對抗，挺益智的一款桌遊（當時隊友寫代碼寫得頭大的時候會來放松一下hh），簡單描述一下規則：
剛開始己方和對方的棋子都在底部中間，每個回合可以選擇放置擋闆或者移動，誰先走到對面就獲勝，但是放置擋闆的時候不能把對方的路堵死。淘寶上有賣這個桌遊的，長這樣：
比賽需要制作小車搬運棋子和障礙完成對抗，我正好是團隊裡面負責算法這一塊的，花了一個多月的時間勉勉強強寫完了這個遊戲，水準也大概是初級玩家的水準，如果要真動動腦子，還是可以擊敗電腦的。
18年正好是Alpha-Go大熱的時候，最開始就打算用增強學習這一套邏輯來實作，自己和自己下棋，在訓練的過程中逐漸提高智力水準，因為評估函數是比較明顯的，誰先到達對岸誰就赢了，那麼隻要把最後一步的評估值設為100，再根據之前的決策推導應該就可以了。
然而真正實作的時候發現沒有那麼簡單。
我用的是Q-Learning算法，最終是要得到一個Q-table表的。卓晴大大可能也是考慮到算法複雜度的問題，我們當時的棋盤格是7X7大小的。即使是縮小版本的，這個Q-table表的狀态和動作資訊依然非常龐大。需要考慮的狀态包括己方的位置、對手的位置、場上擋闆的位置，7*7的棋盤裡，水準/豎直放置擋闆，有36個位置可以擺放，有放置或者不放置兩種選擇，那麼光狀态就
種情況，這也太複雜了！
這種情況根本不可能做訓練，是以做了簡化。把棋子的位置（49種情況）改成到對岸的直線距離（7種情況），放置擋闆隻考慮在棋子位置的正前方/左邊/右邊範圍内放置，那麼此時的狀态大小為：
種情況，棋子可選擇的動作有上下左右移動+放置擋闆（在棋子正前方/左側/右側）一共有16種動作。
如此大規模的簡化後至少在訓練上看到了可行性，但是跑了一個晚上的訓練之後，棋子的水準依舊很智障。
走到了這一步已經花掉了我差不多一個月的時間，離比賽大概還有兩周時間，隻好按照自己的思路莽。
思路其實很簡單，首先在每一次決策之前先判斷場上的局勢，也就是計算己方和對手到對岸最少需要走多少步，這裡要用到尋路算法。然後假設在每一個有效位置放置擋闆，計算放置這塊擋闆以後己方和對手到對岸需要的新的步數，如果對手增加的步數大于己方的步數，那麼說明這一塊擋闆放得有價值。可以執行。
但是這樣的決策隻考慮了未來一步的情況，一個典型的“貪心算法”，目前的決策隻做下一步看起來最優的情況，這樣的考慮不太夠，于是再循環一次，考慮兩步棋局，雖然還是很low，但是至少看起來的決策沒有那麼傻。