前段时间，人工智能阿尔法围棋以总比分4比1战胜人类代表，李世石与AlphaGo 的人机大战把人工智能推成了热门话题。AI 可以在围棋上战胜人类顶尖棋手的时代已经到来。
可以预见，人工智能和机器人将会在更多领域做到比人力更高效、准确、安全。所以未来，掌握编程技能显得更加重要。
笔者是做DBA的，平时除了专业安装数据库三十年，唯一的乐趣就是写写sql了，所以就来说说怎么用sql来写一个最简单棋类游戏：
Tic Tac Toe（又叫井字棋）。
两个玩家，一个打圈(O)，一个打叉(X)，轮流在3乘3的井字格上打自己的符号，最先以任意一行、一列或对角线连成一线则为胜。规定X先手。
一个终局棋谱（MOVES）指的是从开始下子到一方获胜或者下完9个子出现平局，从头到尾的下子情况。一方获胜后，本局即终止。不得提前认输。格子从上到下，从左到右，依次编号1-9
MOVES的第一位表示第一子位置，第二位表示第二子位置，......如果一方获胜，MOVES的长度有可能<9。
局面（BOARD）表示棋盘上呈现的局面，也是按照从上到下，从左到右排列。用X和0填入相应的格子。减号“-” 表示空位。
——维基百科（http://www.gpedia.com/zh/m/gpedia/井字遊戲）
举个栗子：
这里表示出的是：
MOVES=3175968,
BOARD=O-X-OOXXX,
WINNER=X
我给自己设了三个难度：
如何用一条sql列出所有可能终局棋谱和相应的局面
使用pl/sql写出一个可以陪自己下棋的ai
给定一个局面用一条SQL判断出哪一方有必胜策略，以及获胜方最多再下几子必定会获胜。并试着把井字棋的3 3 3 变成nmk
本期我们主要讨论——
这里有必要解释一下：
要求生成所有可能的终局棋谱，只要符合规则即可，哪怕其中有些走法可能看起来很愚蠢，也得包含进去。还没下完的棋谱不要列入。
如果两个终局的局面（BOARD）相同，但是其下子顺序（MOVES）不同，则视为不同棋谱，两个都必须出现在结果中。
如果两个棋谱的MOVES不同，但是其终局局面（BOARD）经过旋转、翻转后重合，仍然被视为不同棋谱，两个都必须出现在结果中
做这道题有两个方向：
先计算 moves，通过 moves 确定 board 和 winner
这是通常的思路,优点是编程容易,因为 moves 能唯一确定 board,只要判断 moves 是否合法就够了,合法的条件很 简单:只要 X 和 O 轮流下,边下边判断,有一方取胜就停止,下完 9 个格也停止,结果可能是 X 胜也可能是平局。缺点是运行速度慢,因为 moves 的基数比 board 大得多 (255168 vs 958),运算量也大。
先计算 board，通过 board 确定 moves 和 winner
这是反常的思路,编程麻烦,因为一个一个合法的终局 board 可能对应多个合法的棋谱 moves,如何演变出合法的棋 步,考虑因素多两个,包括:判断 board 合法性(第一种方向也要做,只不过那里可以改为判断 moves 是否有一方胜),确定所有排列,从中去掉不合法的。但优点是运 行速度快。
先从第一个思路入手：
最自然的解题思路，就是模拟真人下棋的情况，而SQL的优势在于它不会放过每个可能下子的位置，最终自然会得到所有的结局。从空棋盘开始，尝试在每个空位下子，每下一子就查看是否出现胜局，如果胜负已分则不再继续。所有空位已满也不再继续。用sql的劣势也是你不能像高级语言一样定义变量，自定义循环。
我们先创建一张表来存可能的结果，也放便最后去检查是不是做对了
先排列组合出来所有的前4子的情况，并且用两列来存储有顺序的落子顺序（放便后面的like）在落第五子的时候，也就是有一方可以获胜时 用两方的分别去like可以赢的局面，如果已经有人胜出，则剪枝。最后如果每个都落了子还没有人赢则取差集为平棋。
不过这条sql在我的ssd上都要跑近13s这对笔者来说是不可忍受的(虽然这台虚拟机只有800m内存)，所以来优化一下吧：
计算机是采用的二进制，因此它极适合逻辑运算，二进制只有两个数码，和逻辑代数中的“真”“假”相吻合，那就试着用二进制来解一下吧：
第一步先来生成棋盘布局，按要求把棋盘的位置编号1-9, 同时算出这个位子的二进制表示，及其行列坐标，用如下的子查询实现：
WITH
cells AS (SELECT LEVEL pos,POWER(2,LEVEL-1) b,CEIL(LEVEL/3) r,MOD(LEVEL-1,3)+1 c FROM DUAL CONNECT BY LEVEL<=9)
获胜情况总共才八种（三横三纵，加上两个对角线），可以用枚举的方法写出来。如果想要做得灵活一点，以便扩展到M,N,K的情况，可以用如下递归思路：
选任意一个棋子作为起点；
从当前棋子向四个方向各走一步，新加入的棋子的二进制位也加入到总和；
走三步（得到三个棋子）则停止。
用递归WITH实现如下：
,w (win_bits,cnt,r,c,direction) as (
win_bits表示三个连续棋子的二进制之和; cnt表示累计几个棋子，满三个即停；r,c为行列坐标，direction表示哪个方向
SELECT b,1,r,c,direction FROM cells,(SELECT LEVEL direction FROM DUAL CONNECT BY LEVEL<=4) ----从棋盘m任选一点开始，和四种方向做笛卡尔积
UNION ALL
SELECT w.win_bits+cells.b,w.cnt+1,cells.r,cells.c ,w.direction
FROM w,cells
WHERE w.cnt<3 ----满三个即停止
下面从四个方向来加入棋子。并不是每个起点都能得到连续三个棋子，下面的坐标关系自然会过滤掉不合格的
AND (direction=1 AND cells.c=w.c AND cells.r=w.r+1 -----如果方向1, 则加入同列、下一行的位子
OR direction=2 AND cells.r=w.r AND cells.c=w.c+1 -----如果方向2, 则加入同行、下一列的位子
OR direction=3 AND cells.r=w.r+1 AND cells.c=w.c+1 -----如果方向3, 则加入下一行、下一列的位子（右下方）
OR direction=4 AND cells.r=w.r+1 AND cells.c=w.c-1 -----如果方向4, 则加入下一行、上一列的位子（左下方）
,win as (select win_bits from w where cnt=3) ---- 选出那些走满三步的记录，这里有8个二进制数字，代表了8种获胜布局
下面开始用递归WITH来模拟所有可能的棋局。所需要的数据结构如下：
,t(board ----- 到目前为止所有X,O的分布
,x ------- X下过了哪些位置，用二进制之和表示
,o ------- O下过了哪些位置，用二进制之和表示
,step ----- 当前走了几步(双方一共下了几子)
,winner ----- 如果胜负已分，在这里标出
,moves ----- 到目前为止所有下子顺序，即棋谱
)
AS (
递归的起点是从X下第一子开始
SELECT CAST(RPAD('-',pos-1,'-')||'X'||RPAD('-',9-pos,'-') AS VARCHAR2(9)) board ----- 把X的位置拼入空棋盘
,b X
,0 O
,1
,CAST(NULL AS VARCHAR2(1))
,CAST(pos AS VARCHAR2(10))
FROM cells
UNION ALL
下面是递归的部分，在这里算出所有的变化
SELECT SUBSTR(t.board,1,cells.pos-1) ------ 把选中的下一个棋子按照其位置拼到棋盘中去。其位置即m.pos表示的1-9的整数
||CASE WHEN MOD(t.step,2)=0 THEN 'X' ELSE 'O' END ----- 根据当前步数算出下一个子应该是X或者O
||SUBSTR(t.board,cells.pos+1)
,CASE WHEN MOD(t.step,2)=0 THEN t.x+cells.b ELSE t.x END ---- 如果下一子是X, 把其二进制叠加到t.x，否则保持原样
,CASE WHEN MOD(t.step,2)=1 THEN t.o+cells.b ELSE t.o END ---- 对O的处理，方法同上
,t.step+1
,CASE WHEN MOD(t.step,2)=0
THEN (SELECT 'X' FROM win WHERE
BITAND(t.x+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 如果轮到X走子，用BITAND判断走后是否出现胜局
ELSE (SELECT 'O' FROM win WHERE BITAND(t.o+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 判断O是否获胜，方法同X
END,moves||cells.pos ---- 把下一个子的落子情况拼到棋谱中
FROM t JOIN cells ON BITAND(t.x+t.o,cells.b)=0 ----- 将t和9个棋位连接，只要该位子还没有棋子就可以走, BITAND为零表示该位置为空
WHERE t.winner IS NULL ----- 胜负未分
)
递归结束，找出所有叶子节点（胜负已分，或者和棋）
--SELECT WINNER,COUNT(*) FROM (
SELECT moves
,board
,NVL(winner,'D') AS WINNER
FROM T
WHERE WINNER IS NOT NULL OR STEP=9
) GROUP BY WINNER;
SELECT WINNER,COUNT(*) FROM T WHERE WINNER IS NOT NULL OR STEP=9 GROUP BY WINNER;
以上就是以最直接思路实现的版本，它确实能够找出所有的棋局，但还有优化余地，因为有很多的棋局是彼此对称的，可以把一个棋局进行各种旋转翻转变换得到其他棋局，而不需要真正去“下完”那些棋局。
本文作者：冯帅（点融黑帮），目前就职于点融网devops部门，担任DBA，业余喜欢弹吉他，研究美食电影等。
随着点融网新一轮融资，点融网即将开始大规模的扩张，需要各种优秀人才的加入，如果你觉得自己够优秀，欢迎加入我们！获取更多职位信息，请关注点融黑帮。
