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

看板GameDesign作者LaPass (LaPass)時間11年前 (2012/12/06 23:10)推噓12(12推 0噓 49→)

留言61則, 8人參與討論串21/22 (看更多)

讓我們先看個溫馨感人的影片 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

12/07 00:10, , 1^F

12/07 00:10, 1^F

推

cowbaying

12/07 01:08, , 2^F

12/07 01:08, 2^F

推

cowbaying

12/07 01:10, , 3^F

12/07 01:10, 3^F