Re: [請益] 關於一些遊戲的AI

[LaPass (LaPass)]

讓我們先看個溫馨感人的影片
http://www.youtube.com/watch?feature=player_embedded&v=Q4gTV4r0zRs



演算法真的很重要.....
如果想用隨機落子去算完五子棋所有可能的話
迴圈總共要跑 (15*15)! 次



其實，只要稍微加上一點方式去計算一下
就可以知道哪些是廢步，那些是可能棋步，那些是必要的步數(不下那邊就會輸)
http://i.imgur.com/NMOWU.jpg



最左上角是相鄰判斷
判斷方式很簡單，就是

１０００１０００１
０２１１２１１２０
０１３２３２３１０
０１２４４４２１０
１２３４棋４３２１
０１２４４４２１０
０１３２３２３１０
０２１１２１１２０
１０００１０００１

不論黑白、權重都一樣
這樣可以把可能的走法壓縮到25步之內



右上角是棋型評分判斷
簡單來講，就是假設落子到那點後
會生成怎麼樣的棋型......

這部分先擱著
來講一下勝負判斷

五子棋因為是「棋子連在一起」才能得勝
也就是說，所有勝負、威脅都只跟落子那一點有關

因此，我判斷勝負時
會指定某點(落子點)，以那一點向外(上下左右、以及四個斜向)去找看看棋型種類
最後找到的可能棋型，會是這21種之一

        落子點   → 向外
        Ｏ      Ｏ      Ｏ      Ｏ      Ｏ
        Ｏ      Ｏ      Ｏ      Ｏ      Ｘ
        Ｏ      Ｏ      Ｏ      Ｏ      。
        Ｏ      Ｏ      Ｏ      。      。
        Ｏ      Ｏ      Ｏ      Ｘ      ＊
        Ｏ      Ｏ      Ｏ      。      Ｘ
        Ｏ      Ｏ      Ｘ      ＊      ＊
        Ｏ      Ｏ      。      Ｘ      ＊
        Ｏ      Ｏ      。      。      ＊
        Ｏ      Ｘ      ＊      ＊      ＊
        Ｏ      。      Ｘ      ＊      ＊
        Ｏ      。      。      ＊      ＊
        Ｏ      Ｏ      Ｏ      。      Ｏ
        Ｏ      Ｏ      。      Ｏ      Ｏ
        Ｏ      。      Ｏ      Ｏ      Ｏ
        Ｏ      Ｏ      。      Ｏ      。
        Ｏ      Ｏ      。      Ｏ      Ｘ
        Ｏ      。      Ｏ      Ｏ      。
        Ｏ      。      Ｏ      Ｏ      Ｘ
        Ｏ      。      Ｏ      Ｘ      ＊
        Ｏ      。      Ｏ      。      ＊

Ｘ是異色或是牆壁
。是空格
＊是任意，代表是什麼都不會有影響

然後再去找對稱的位置，看另外一邊的棋型是什麼
就能知道，這一條線上是連成五子，或是單四、跳格四、活三....

＊＊＊ＯＸＸ。Ｏ＊      0
＊＊＊ＯＸＸ。。＊      21 單二
＊＊＊ＯＸＯ＊＊＊      0  沒有
＊＊Ｏ。ＸＸＸＸＸ      50 五子
＊＊Ｏ。ＸＸＸＸＯ      41 單四
＊＊Ｏ。ＸＸＸＸ。      42 雙四
(略)



兩邊組合一下，可能性有 21*20/2+21=231種 (兩邊可以互換，所以不是21*21)
因為才231種而已，就手動判斷一下棋型，做成列表
在跑程式時讓程式去查表，判斷棋型



回到右上角的棋型評分判斷

只要能知道落子後會生成什麼棋型
就可以給每種棋型一種分數，然後去計算那個點的分數
這實質上跟判斷勝負是一樣的

/*
link[0][5]=0; //直接獲勝 (五子)
link[0][4]=0; //單四、活四
link[0][3]=0; //活三
link[0][2]=0; //活二、單二
link[0][1]=0; //被完全堵死
link[0][0]=0; //block數 block越多越糟糕
*/
//評價公式
int ans= k[0][4]*50+k[0][3]*30+k[0][2]*2-k[0][1]*3-k[0][0]*2
        +k[1][4]*35+k[1][3]*10+k[0][2]*1-k[1][1]*2+k[1][0]*1;

這邊就只是調整參數而已
我不期望每次都能算出最佳解答
我寫這個只是，想用暴力去找出必勝棋步時，比較有效率一點而已
是期望將正確棋步壓縮在十五步之內，最好在十步之內就能找出來。

至於下面那張圖是把距離跟相鄰判斷做一下相加
因為有時候AI會下到遠的地方去



目前是想把算過的棋步記錄在資料庫中
這樣可以省下很多重覆計算的步驟
例如，同樣的盤面，不論落子順序為何，都不會影響判斷出來的棋步

還有，在存棋步時，其實可以旋轉一下、鏡射一下
這樣馬上就能做出其他8張棋譜的數據了。(三次旋轉、一次鏡射)



是想問.....
算完這些步數後，怎麼抓出必勝棋譜的路徑樹出來？



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.38.75.195
推 s3748679:推前面的想法與插圖.. 後面的問題@_@" 交給樓下加油
推 cowbaying:這串差不多可以收精華了  XDDD
推 cowbaying:暫時收錄在z-4-13-7-22
→ cowbaying:幫我更正一下  是z-4-13-7
推 LayerZ:睡前靈光一閃，如果是找必敗棋步呢..
→ LayerZ:感覺有兩個問題，計算權重應該只有8個方向有意義吧，再判斷
→ LayerZ:有沒有被擋住或是牆壁，才會歸零，另外就是防守，有時候對
→ LayerZ:方要連起來會不得不防守，原本預測就會被打亂?
→ LayerZ:變成，黑、白要同時計算權重，在勝利的權重減掉對方會勝利
→ LayerZ:的權重才會做出更好的預測? 不然就要計算這步下去幾步內會
→ LayerZ:不會被封死或被勝利，如果必敗就跳過，再來選比較好的?
→ LayerZ:唔，我又發作了= =我臨時想的可能沒你考慮的多，如果有亂七
→ LayerZ:八糟的地方歡迎打臉(死
推 ddavid:如果是要用窮舉逆推，你要把所有跑過的盤面都存下來並建立
→ ddavid:關聯，也就是你要知道從那個盤面走一步可以到哪些盤面。
→ ddavid:然後就是做逆推判斷了，簡單的幾點判斷：
→ ddavid:1.一個輪到X下的盤面只要能通往任何一個被標為勝的盤面，那
→ ddavid:  這個盤面就也是該被標為勝的盤面。
→ ddavid:2.一個輪到X的盤面只要所有可通往的盤面都被標為敗，那這個
→ ddavid:  盤面就要標為敗。
→ ddavid:上面那些勝、敗都要改為X勝跟X敗XD
→ ddavid:然後就用以上原則，從下到結束確定勝負的盤面逆推回去這樣
推 Grunt:哈哈哈，開頭的影片快把我笑死了
→ LaPass:等等，那是刪除多餘節點後的樹才會通往全勝。
推 LayerZ:"要通往全勝"本身就是個盲點了不是?
→ LayerZ:這句話我解釋成，"去掉所有不會贏的節點，再加入所有會贏的
→ LayerZ:節點"..這東西不管怎麼用演算法包起來，還是窮舉法阿
→ LaPass:找路徑好像還蠻難的.... orz.....
推 LayerZ:一個節點找下去就是一個tree 如果找到底是能破解所有組合
→ LayerZ:問題應該在怎麼加判斷，找到第幾層該收手?
→ LaPass:http://www.bf92.com/soft/five/five.htm 是說2006年就有了
→ LaPass:那我就來寫個網頁板的 XD
→ enthos:象棋有程式設計前輩,白醫師的殘局庫:http://ppt.cc/8OA3
推 s3748679:難道就不能用窮舉法把結果存起來.. 對戰時再取要的部分?
推 cowbaying:這個資料結構要很強...
→ LaPass:好像翻到Alpha-Beta 搜索之類的關鍵字，可是我看不懂 = =
→ LaPass:誰來個連半路出家的看的懂的教學啊 囧"
→ LaPass:http://www.xqbase.com/computer/search_minimax.htm 這個?
推 yoco315:觀念好像怪怪的 XD
→ LaPass:那邊怪怪的? @@
→ ddavid:首先我先澄清一下，當你提到「窮舉法」的時候基本上我假設
→ ddavid:你是要算到完的，這種情況下就是用我的方法逆推回去就好。
→ ddavid:如果你並沒有要算到完，那你就必須要寫有一個基本規則之外
→ ddavid:的評分機制（人為制定的）來算出每個子節點的分數。Alpha-
→ ddavid:Beta就是往下算個n層，然後又從那n層逆推回來找出最佳的分
→ ddavid:數。那個逆推過程其實很接近窮舉逆推，只是把「必勝」跟「
→ ddavid:必敗」調整為分數的高低。
→ ddavid:比如一個輪到我方下A node，其child分別為10 20 30分，因為
→ ddavid:是輪我下，所以我一定可以選最高分的，因此A就可計為30分。
→ ddavid:反之一個輪對手下的B node，其children分別為10 20 30（都
→ ddavid:當做是你的得分，實際寫時有可能要考慮分數是我方的或對方
→ ddavid:的），那因為你要認為對手一定可以走到對你最不利的下法，
→ ddavid:因此B node的分數逆推上來計為10分。就這樣一路回推回目前
→ ddavid:著手的node，選最高分的走下去這樣。
→ ddavid:簡單原則：我方著手的分數是所有子節點取最高分，對方著手
→ ddavid:的分數是所有子節點取最低分。
→ ddavid:剩下就看你推的層數及Evaluation function夠不夠好了這樣。
→ ddavid:然後因為取最高最低的情況，就會有些東西你發現不用算完就
→ ddavid:肯定可以被cut掉，那就是alpha-beta裡面做的pruning了
推 ddavid:致歉修正一下，上面那個逆推過程其實只是Minimax這樣，加入
→ ddavid:預測函數做pruning之後才是alpha-beta這樣XD