【不是我藏着掖着，是茶壶里有饺子，此外各位可以配合jianghr的回复食用
注：2016/5/29 6:00 代码大改，高度优化代码以及提升棋力（虽然还有偷懒没优化的）
Hello，大家好，我是乙烯，这阵子我捣鼓了一个五子棋AI，觉得速度上可以接受，下起来也不会显得太傻，所以今天我就发帖，来给大家说说，我是如何实现五子棋AI的。
五子棋，作为一个拥有着先手必胜属性的棋类，实际上是不公平的，就算是后人给加上了禁手，换子这样的规则，先手依旧有着极大的优势。正是因为这样的不公平，五子棋的AI早就可以啪啪啪打死人类几条街了，因为机器只要是先手，就很容易推导出必胜下法。今天我带来的五子棋AI，是一个无禁手的后手AI，理论上基本上是不能下赢人类的，
那么，闲谈也就先告一段落，接下来来具体说说思路与方法。这里附带两张被奕心吊打的棋局，顺带一提，奕心的elo是保持在2000以上的，属于世界冠军级别的AI。奕心被限制在深度探索两层，而这个ai没有深度探索，所以不被吊打才不正常。
楼下有几波带节奏的，这个AI的特性就是计算量小，所需时间要小，计算时间短到足以和人对弈，比那些强行搬运复制别人的AI代码的制作方式要好到不知道哪里去了。如果说我抄的某些人的，那么别酸溜溜的只撂一句话，拿代码出来啊，我核心的代码通通丢出来了，我写帖子是为了普及制作方法的，你们将制作方法束之高阁，不爽不要来。
一、思路。
对于整个五子棋AI来说，玩家只会在意两点，时间和棋力。我们的目标是计算时间消耗更短，且棋力达到不会很蠢的地步。
网上所能找到的大多数五子棋AI，都有着这样的特征，也就是每次局面更新的时候，都会对棋盘进行一次遍历估值，或许对于别的平台或者别的语言来说，这并没有什么问题，但是，如果我们需要用mc来进行编写的话，第一道难关就是mojang的辣鸡优化。事实证明，每次对局面遍历一次都将极大程度的延长计算时间。那么我们的首要目标就是，通过代码的优化来弥补这以先天不足。对于五子棋AI来说，则是减少需要读写的范围。这里也有大量的AI将遍历区域缩小至棋子的周围四格，这是很合理并且很容易执行的策略，这将是核心思路之一。
在时间压缩下来后，我们需要提高AI的棋力，通常市面上的解法是博弈树，但是这往往对于我们来说是无法忍受的，因为博弈树就代表深度探索，不仅要遍历棋局，更要遍历各种可能性，这就代表着时间将呈指数级别的延长。就算是一些高优化的AI，对于一些局面的探索也会需要几十秒甚至几分钟的计算，同样的计算量放在mc里就有可能需要几小时甚至几天来运行，那么这样的一个AI是没有意义的。同样的，mc对于变量的管理方式虽然不至于像前几个版本那样贫瘠，但是也是远远不能达到一般程序的需求的，所谓在夹缝中求生存嘛。
那么我们只有仅进行当前局面估值，完全放弃可能性计算。这也就代表了第一层的下法得尽可能的好。此外，经过实验证明，过于频繁的棋型判断也会造成极大程度的延时，所以这一点我们也得尽可能的压缩。
二，实际演练。
提前说一下，下子以及胜利判定之类的可替换操作我就不深入来说了，因为毕竟可替换也就是说有一万种方法来实现，能看懂这篇文章的也就代表能够自己制作出来了，所以篇幅留给核心算法。因为是要求快速的算法，所以基本上是简约不简单。
棋盘规格是19*19。以下这些不要问我为啥不用代码格式而用引用格式，被吞无数次，这是不得已的下策。棋盘上所有点将会拥有一个Start标记，为了防止和别的实体产生干扰。每个点会根据当前的状态拥有不同的名字。
a为已下子，这样的话计算局面时将直接剔除该点的计算。因为你并不会在一个已经有子的地方下子。
b为正在下子。
o为当前无子。
我方棋子为黑色染色玻璃，敌方则为白色染色玻璃。
x
y
l
h 以上四个计分板是属于每个格子的固有属性，是代表着这个格子的行，列，以及第几条斜线，所存储的值是绝对不会更改的。
xc
yc
lc
hc以上四个是用来计算落子点与该格的行列差值的，0代表和落子点处于同一行。
b1
b2
b3
b4
w1
w2
w3
w4以上八个计分板是用来存储各个方向上的权值的。b代表防守，w代表进攻，下同。在开局时会根据格子位置给予一个微小的初始量，如最中间的是10，最外围的是1。
b01 =b1+b2
b02 =b1+b3
b03 =b1+b4
b04 =b2+b3
b05 =b2+b4
b06 =b3+b4
w01
w02
w03
w04
w05
w06 以上12个计分板仅用来做取最大值的中间计分板。加法缓存用，用于综合评价该点的威胁度。最后最大值将被存储至w01
attack 计算该位置敌方的威胁度。wow 计算我方对对方的威胁度
以上是我全部的计分板。此外额外有个名为head的实体用于暂存最大值，这个其实就比较随意了，你愿意的话存储到玩家身上也可以。
接下来来从指令层面讲解整体的流程。有关于一些特定棋型的判断就是通过叠加execute然后探测方块实现的，难是不难，就是很卡，所以为了防止你们想不到更好的答案，我这里就讲到这里。补充：如出现必须堵上的点会给这个点一个high的tag标记。如果出现不堵上会有可能输的点，会给这点的attack计分板+1。同样的，ohhh对应黑棋的high，wow对应黑棋的attack。这里加上了对白棋的必胜着法的优先度。
这里补充一下棋型的检测，
首先各种四连珠情况，即不堵上就会输的情况
活三
活二
并不是检测不出来，而是预防万一而进行检测。
- execute @e[name=o] ~ ~ ~ detect ~1 ~1 ~ stained_glass 15 execute @e[name=o,r=0] ~ ~ ~ detect ~2 ~1 ~ stained_glass 15 execute @e[name=o,r=0] ~ ~ ~ detect ~3 ~1 ~ stained_glass 15 execute @e[name=o,r=0] ~ ~ ~ detect ~4 ~1 ~ air 0 scoreboard players tag @e[name=o,c=1] add high
这是一个检测x轴上的活三的例子，
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] xc = @e[type=ArmorStand,c=1,r=0] x
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] yc = @e[type=ArmorStand,c=1,r=0] y
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] hc = @e[type=ArmorStand,c=1,r=0] h
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] lc = @e[type=ArmorStand,c=1,r=0] l
以上四条是为了给每个单元的计算计分板读取所在的坐标值。
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] xc -= @e[name=b,c=1] x
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] yc -= @e[name=b,c=1] y
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] hc -= @e[name=b,c=1] h
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] lc -= @e[name=b,c=1] l
以上四条是计算该点与刚刚落子的那一点的坐标差值，0即代表是和落子位处于同一斜线。
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=6,score_yc=0,score_yc_min=0,name=o,score_b2=4100] b2 1000
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=6,score_xc=0,score_xc_min=0,name=o,score_b1=4100] b1 1000
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=4,score_hc=0,score_hc_min=0,name=o,score_b4=4100] b4 1000
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=4,score_lc=0,score_lc_min=0,name=o,score_b3=4100] b3 1000
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=6,score_yc=0,score_yc_min=0,name=o,score_w2=4100] w2 1300
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=6,score_xc=0,score_xc_min=0,name=o,score_w1=4100] w1 1300
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=4,score_hc=0,score_hc_min=0,name=o,score_w4=4100] w4 1300
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=4,score_lc=0,score_lc_min=0,name=o,score_w3=4100] w3 1300
这里是落子点对周围处在统一斜线上的空位权值的修正，这样每次最多只需要重新修改32个位置的权值，比重新遍历一遍棋盘不知道高到哪里去了。
此外，这里也要注意一下半径有微妙的调整，这是因为斜向的四格会更长一些，根号二倍。
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 = @e[type=ArmorStand,c=1,r=0] b1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 += @e[type=ArmorStand,c=1,r=0] b2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b02 = @e[type=ArmorStand,c=1,r=0] b1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b02 += @e[type=ArmorStand,c=1,r=0] b3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b03 = @e[type=ArmorStand,c=1,r=0] b1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b03 += @e[type=ArmorStand,c=1,r=0] b4
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b04 = @e[type=ArmorStand,c=1,r=0] b2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b04 += @e[type=ArmorStand,c=1,r=0] b3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b05 = @e[type=ArmorStand,c=1,r=0] b2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b05 += @e[type=ArmorStand,c=1,r=0] b4
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b06 = @e[type=ArmorStand,c=1,r=0] b3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b06 += @e[type=ArmorStand,c=1,r=0] b4
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 = @e[type=ArmorStand,c=1,r=0] w1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 += @e[type=ArmorStand,c=1,r=0] w2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w02 = @e[type=ArmorStand,c=1,r=0] w1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w02 += @e[type=ArmorStand,c=1,r=0] w3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w03 = @e[type=ArmorStand,c=1,r=0] w1
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w03 += @e[type=ArmorStand,c=1,r=0] w4
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w04 = @e[type=ArmorStand,c=1,r=0] w2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w04 += @e[type=ArmorStand,c=1,r=0] w3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w05 = @e[type=ArmorStand,c=1,r=0] w2
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w05 += @e[type=ArmorStand,c=1,r=0] w4
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w06 = @e[type=ArmorStand,c=1,r=0] w3
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w06 += @e[type=ArmorStand,c=1,r=0] w4
这里是计算出之前结构的12个估值变量，注意，是每个格子都拥有各自的12个变量。
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 > @e[type=ArmorStand,c=1,r=0] b02
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 > @e[type=ArmorStand,c=1,r=0] b03
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 > @e[type=ArmorStand,c=1,r=0] b04
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 > @e[type=ArmorStand,c=1,r=0] b05
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] b01 > @e[type=ArmorStand,c=1,r=0] b06
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] w02
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] w03
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] w04
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] w05
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] w06
entitydata @e[name=b] {CustomName:"a"}
每个格子都选出自己最大的当前权值。
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] w01 > @e[type=ArmorStand,c=1,r=0] b01
判断进攻权值是否大于防御权值，取二者最大值。
scoreboard players add @e[name=o,tag=high] w01 2000
判断这个点是否是需要被特殊照顾一下，如果是，进一步加大权值。
/scoreboard players operation @e[tag=head,c=1] x > @e[tag=Start,name=o] w01
/scoreboard players operation @e[tag=Start,name=o] w01 -= @e[tag=head,c=1] x
entitydata @r[type=ArmorStand,score_w01_min=0,c=1,name=o] {CustomName:"b"}
选出拥有最大权值的格子，并给予落子标签。
execute @e[tag=Start,name=b] ~ ~ ~ setblock ~ ~1 ~ stained_glass 0
落子！
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] xc = @e[type=ArmorStand,c=1,r=0] x
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] yc = @e[type=ArmorStand,c=1,r=0] y
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] hc = @e[type=ArmorStand,c=1,r=0] h
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] lc = @e[type=ArmorStand,c=1,r=0] l
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] xc -= @e[name=b,c=1] x
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] yc -= @e[name=b,c=1] y
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] hc -= @e[name=b,c=1] h
execute @e[tag=Start,name=!a] ~ ~ ~ /scoreboard players operation @e[type=ArmorStand,c=1,r=0] lc -= @e[name=b,c=1] l
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=6,score_yc=0,score_yc_min=0,name=o,score_b2=4100] b2 1000
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=6,score_xc=0,score_xc_min=0,name=o,score_b1=4100] b1 1000
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=4,score_hc=0,score_hc_min=0,name=o,score_b4=4100] b4 1000
execute @e[name=b] ~ ~ ~ scoreboard players remove @e[r=4,score_lc=0,score_lc_min=0,name=o,score_b3=4100] b3 1000
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=6,score_yc=0,score_yc_min=0,name=o,score_w2=4100] w2 1300
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=6,score_xc=0,score_xc_min=0,name=o,score_w1=4100] w1 1300
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=4,score_hc=0,score_hc_min=0,name=o,score_w4=4100] w4 1300
execute @e[name=b] ~ ~ ~ scoreboard players add @e[r=4,score_lc=0,score_lc_min=0,name=o,score_w3=4100] w3 1300
与之前相同的权值修正。
entitydata @e[name=b] {CustomName:"a"}
将落子点的标记修正成已落子的标记。
/scoreboard players set @e[tag=head,c=1] x 0
清理最优解缓存。
【根本看不下去，好吧我懒得看】