推 s3748679:推前面的想法與插圖.. 後面的問題@_@" 交給樓下加油 12/07 00:10
推 cowbaying:這串差不多可以收精華了 XDDD 12/07 01:08
讓我們先看個溫馨感人的影片
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