让我们先看个温馨感人的影片 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