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