|
|
第二题的副产品是这个会下棋的包，里面只有两个过程，start_game和play
start_game可以带一个参数指定从哪一棋局开始下。不代参数指定从空棋盘开始而且是程序先手。
play带一个参数表明你下一子要下在哪个位置。
程序的应对下子会输出在屏幕上，事先要SET SERVEROUTPUT ON
CREATE OR REPLACE PACKAGE pkg_tictactoe AS
PROCEDURE start_game(p_board IN VARCHAR2 DEFAULT NULL);
PROCEDURE start_game(p_move IN NUMBER);
PROCEDURE play(p_move IN NUMBER);
END pkg_tictactoe;
/
CREATE OR REPLACE PACKAGE BODY pkg_tictactoe AS
gv_board VARCHAR2(20);
gv_empty VARCHAR2(1):='-';
gv_size NUMBER :=9;
gv_player VARCHAR2(1);
FUNCTION f_get_winner(p_board IN VARCHAR2) RETURN VARCHAR2
AS
v_x VARCHAR2(1);
v_o VARCHAR2(1);
BEGIN
WITH
m AS (SELECT LEVEL m,POWER(2,LEVEL-1) b,CEIL(LEVEL/3) r,MOD(LEVEL-1,3)+1 c FROM DUAL CONNECT BY LEVEL<=9)
,w (b,win_bits,cnt,r,c,t) as (
SELECT b,b,1,r,c,t FROM m,(SELECT LEVEL t FROM DUAL CONNECT BY LEVEL<=4)
UNION ALL
SELECT m.b,w.win_bits+m.b,w.cnt+1,m.r,m.c ,w.t
FROM w,m
WHERE w.cnt<3
AND (t=1 AND m.c=w.c AND m.r=w.r+1
OR t=2 AND m.r=w.r AND m.c=w.c+1
OR t=3 AND m.r=w.r+1 AND m.c=w.c+1
OR t=4 AND m.r=w.r+1 AND m.c=w.c-1
)
)
,win as (select win_bits from w where cnt=3)
SELECT (SELECT 'X' FROM win WHERE BITAND(x,win.win_bits)=win.win_bits AND ROWNUM=1) x_win
,(SELECT 'O' FROM win WHERE BITAND(o,win.win_bits)=win.win_bits AND ROWNUM=1) o_win
INTO v_x,v_o
FROM (SELECT NVL(SUM(CASE WHEN SUBSTR(p_board,m,1)='X' THEN m.b END),0) x
,NVL(SUM(CASE WHEN SUBSTR(p_board,m,1)='O' THEN m.b END),0) o
FROM m
)
;
IF v_x IS NOT NULL AND v_o IS NOT NULL THEN
RAISE_APPLICATION_ERROR(-20001,'invalid winner! '||p_board);
END IF;
IF COALESCE(v_x,v_o) IS NULL AND REGEXP_COUNT(p_board,gv_empty)=0 THEN
RETURN 'D';
END IF;
RETURN COALESCE(v_x,v_o);
END f_get_winner;
PROCEDURE print_board(p_board IN VARCHAR2,p_winner IN VARCHAR2 DEFAULT NULL)
AS
BEGIN
IF gv_player IS NOT NULL THEN
DBMS_OUTPUT.PUT_LINE('Your side: '||gv_player);
DBMS_OUTPUT.PUT_LINE('=============');
END IF;
FOR i IN 1..3 LOOP
DBMS_OUTPUT.PUT_LINE(SUBSTR(p_board,(i-1)*3+1,3));
END LOOP;
IF p_winner IS NOT NULL THEN
DBMS_OUTPUT.PUT_LINE('========= '||CASE WHEN p_winner='D' THEN 'It''s a draw, game over' WHEN p_winner=gv_player THEN 'You win!' ELSE 'You lose!' END||' =========');
END IF;
END print_board;
PROCEDURE check_valid(p_board IN VARCHAR2)
AS
v_cell VARCHAR2(1);
v_cnt_x NUMBER :=0;
v_cnt_o NUMBER :=0;
v_winner VARCHAR2(1);
BEGIN
IF NOT LENGTH(p_board) BETWEEN 1 AND gv_size THEN
RAISE_APPLICATION_ERROR(-20001,'invalid board! '||p_board||' size should be 1-'||gv_size);
END IF;
FOR i IN 1..LENGTH(p_board) LOOP
v_cell := SUBSTR(p_board,i,1);
IF v_cell NOT IN (gv_empty,'X','O') THEN
RAISE_APPLICATION_ERROR(-20001,'invalid board! '||p_board||' position:'||i);
END IF;
IF v_cell='X' THEN
v_cnt_x := v_cnt_x +1;
END IF;
IF v_cell='O' THEN
v_cnt_o := v_cnt_o +1;
END IF;
END LOOP;
IF v_cnt_x - v_cnt_o NOT IN (0,1) THEN
RAISE_APPLICATION_ERROR(-20001,'invalid move count! '||p_board);
END IF;
v_winner := f_get_winner(p_board);
IF v_winner='X' AND v_cnt_x = v_cnt_o
OR v_winner='O' AND v_cnt_x <> v_cnt_o
THEN
RAISE_APPLICATION_ERROR(-20001,'invalid board, no move is allowed after game is over '||p_board);
END IF;
END check_valid;
PROCEDURE move(p_board IN VARCHAR2)
AS
v_winner VARCHAR2(1);
BEGIN
v_winner := f_get_winner(p_board);
-- DBMS_OUTPUT.PUT_LINE('gv_player='||gv_player);
IF v_winner IS NOT NULL THEN
print_board(p_board,v_winner);
RETURN;
END IF;
WITH
m AS (SELECT LEVEL m,POWER(2,LEVEL-1) b,CEIL(LEVEL/3) r,MOD(LEVEL-1,3)+1 c FROM DUAL CONNECT BY LEVEL<=9)
,w (b,win_bits,cnt,r,c,t) as (
SELECT b,b,1,r,c,t FROM m,(SELECT LEVEL t FROM DUAL CONNECT BY LEVEL<=4)
UNION ALL
SELECT m.b,w.win_bits+m.b,w.cnt+1,m.r,m.c ,w.t
FROM w,m
WHERE w.cnt<3
AND (t=1 AND m.c=w.c AND m.r=w.r+1
OR t=2 AND m.r=w.r AND m.c=w.c+1
OR t=3 AND m.r=w.r+1 AND m.c=w.c+1
OR t=4 AND m.r=w.r+1 AND m.c=w.c-1
)
)
,win as (select win_bits from w where cnt=3)
-----------把当前局面当作根节点，生成当前局面往下的游戏树
,t(board ----- 到目前为止所有X,O的分布
,x ------- X下过了哪些位置，用二进制之和表示
,o ------- O下过了哪些位置，用二进制之和表示
,step ----- 当前走了几步(双方一共下了几子)
,winner ----- 如果胜负已分，在这里标出
,prior_board ----- 指明当前BOARD是从哪一个变化而来
,rn ------- 利用分析函数ROW_NUMBER()为每一对(prior_board,board)仅仅保留一行数据
)
AS (
------ 从给定棋局开始生成游戏树
SELECT CAST(p_board AS VARCHAR2(9)) board
,x
,o
,step
,CASE WHEN MOD(step,2)=1 THEN (SELECT 'X' FROM win WHERE BITAND(x,win.win_bits)=win.win_bits AND ROWNUM=1) ----看看此棋局是否已分胜负
ELSE (SELECT 'O' FROM win WHERE BITAND(o,win.win_bits)=win.win_bits AND ROWNUM=1)
END AS winner
,CAST('' AS VARCHAR2(9)) prior_board
,1
FROM (------ 从给定棋局计算X,O的二进制的值
SELECT NVL(SUM(CASE WHEN SUBSTR(p_board,m,1)='X' THEN m.b END),0) x
,NVL(SUM(CASE WHEN SUBSTR(p_board,m,1)='O' THEN m.b END),0) o
,9-REGEXP_COUNT(p_board,'-') step
FROM m
)
UNION ALL
SELECT SUBSTR(t.board,1,m.m-1) ------ 把选中的下一个棋子按照其位置拼到棋盘中去。其位置即m.m表示的1-9的整数
||CASE WHEN MOD(t.step,2)=0 THEN 'X' ELSE 'O' END ----- 根据当前步数算出下一个子应该是X或者O
||SUBSTR(t.board,m.m+1) AS board
,CASE WHEN MOD(t.step,2)=0 THEN t.x+m.b ELSE t.x END AS X---- 如果下一子是X, 把其二进制叠加到t.x，否则保持原样
,CASE WHEN MOD(t.step,2)=1 THEN t.o+m.b ELSE t.o END AS O---- 对O的处理，方法同上
,t.step+1
,CASE WHEN MOD(t.step,2)=0
THEN (SELECT 'X' FROM win WHERE BITAND(t.x+m.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 如果轮到X走子，用BITAND判断走后是否出现胜局
ELSE (SELECT 'O' FROM win WHERE BITAND(t.o+m.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 判断O是否获胜，方法同X
END AS winner
,t.board AS prior_board
------ 下面的PARTITION BY按照当前棋局以及拼出的下手棋局来分区，保留任意一种都可以，所以ORDER BY 1
,ROW_NUMBER() OVER(PARTITION BY t.board,SUBSTR(t.board,1,m.m-1)||CASE WHEN MOD(t.step,2)=0 THEN 'X' ELSE 'O' END||SUBSTR(t.board,m.m+1) ORDER BY 1)
FROM t JOIN m ON BITAND(t.x+t.o,m.b)=0
WHERE t.winner IS NULL
AND (t.step=0 AND m.m IN (1,2,5) ----针对空棋盘的一个优化：起点只需考虑1,2,5，其他都是对称的
OR t.step>0
)
AND rn=1 -----每一对(board，prior_board)只需保留一种，其他都是重复
)
, boards AS (
----- 保留所有的上手棋局与当前棋局的对应关系
SELECT board,prior_board,winner,step
FROM t
WHERE rn=1
)
,s (board,step,winner,rn,iterator,steps_to_win,player) as (
---从所有获胜终局反推, 把winner一步一步带到上层，最终判断是否能带到根
select board
,step
,winner
,1 as rn
,max(step) over() AS iterator ---- 推理起点，从最高步数往前倒推，每层递归减 1
,0 as steps_to_win
,DECODE(MOD(step,2),1,'X','O') player
from boards
where winner is not null ------ 选取胜负已分的叶子节点作为递归起点
group by board,step,winner ----- 因为boards里面保存着前后棋局的对应关系，所以board不是唯一的，必须去除重复
union all
select CASE WHEN s.step<>s.iterator THEN s.board ELSE b.prior_board END as board ---- 递归的下一层，是从boards表得来的上一手棋局
,CASE WHEN s.step<>s.iterator THEN s.step ELSE s.step-1 END as step
,case when s.step<>s.iterator THEN s.winner
ELSE NVL(MAX(CASE when s.player=s.winner THEN s.winner END)
OVER(PARTITION BY b.prior_board), ---- 如果这一层的下子的一方(player)有胜局则优先取
------ 当上述MAX取到的值为NULL, 意味着只有平局或者对手胜。
------ 下面的count(distinct b.board)表示对手取胜的数量，REGEXP_COUNT(b.prior_board,'-')则表示有多少空位数，即多少种后续棋局
------ 如果两个数量相等，说明不管怎么走都是对手赢，则把s.winner，即对手带到上层
CASE WHEN count(distinct b.board) over(partition by b.prior_board)=REGEXP_COUNT(b.prior_board,'-') --- 等于所有可能的对手走法
then s.winner
END
---- 如果以上都不满足则WINNER为空，说明双方都没有必胜策略，为和棋
)
END as winner
----- 本轮递归结束后，所有同一个prior_board之下的winner都一致，由上述公式推出
----- ROW_NUMBER用于取出同一个prior_board之下的其中一行进入下轮递归，如果走子方必胜，则取步数最少的，否则取最多的
,ROW_NUMBER() OVER(PARTITION BY case when s.step<>s.iterator THEN s.board ELSE b.prior_board END ---- 分析函数的分区是按照本次递归后的棋局，每个局面保留一行
ORDER BY CASE when s.player=s.winner THEN 1 ELSE 2 END ---- 如果这一层的下子的一方(player)有胜局，则优先取
,s.steps_to_win*CASE when s.player=s.winner THEN 1 ELSE -1 END ---- 如果是对手，要取最坏情况（最多步数），所以乘以-1之后再排序
) AS rn
,s.iterator-1
,case when s.step<>s.iterator OR s.player<>s.winner
THEN s.steps_to_win ---- 如果对手赢，步数不用递增
else s.steps_to_win+1 ---- 如果当前棋手赢，步数要加1，因为要再走一步才到达那个局面
end
,CASE WHEN s.step<>s.iterator THEN s.player ELSE DECODE(s.player,'X','O','X') END
from s left join boards b -------------- 为了使得下次递归能看到所有获胜局，必须用外连接带入下层
on s.step=s.iterator ---- 正在考察的当前步, 只有这一步才需要连接board获取上一手棋局(PRIOR_BOARD)
and s.board=b.board ---- 连接boards获得上一步棋局
WHERE s.winner is not null and s.rn=1 and s.iterator>9-REGEXP_COUNT(p_board,'-') and s.step<=s.iterator
)
SELECT board
INTO gv_board
FROM (
SELECT b.board
FROM boards b LEFT JOIN
(SELECT * FROM s
where iterator=gv_size-REGEXP_COUNT(p_board,gv_empty)+1
) s
ON b.board=s.board
WHERE b.prior_board = p_board
ORDER BY CASE when gv_player<>s.winner THEN 1 WHEN s.winner IS NULL THEN 2 ELSE 3 END
,s.steps_to_win*CASE when gv_player<>s.winner THEN 1 ELSE -1 END
,DBMS_RANDOM.VALUE
)
WHERE ROWNUM=1
;
v_winner := f_get_winner(gv_board);
print_board(gv_board,v_winner);
IF v_winner IS NOT NULL THEN
gv_board :=NULL;
END IF;
RETURN;
END move;
PROCEDURE start_game(p_move IN NUMBER)
AS
BEGIN
IF NOT NVL(p_move,0) BETWEEN 1 AND gv_size THEN
RAISE_APPLICATION_ERROR(-20001,'invalid position! value should be 1-'||gv_size);
END IF;
start_game(LPAD(gv_empty,p_move-1,gv_empty)||'X'||LPAD(gv_empty,gv_size-p_move,gv_empty));
END start_game;
PROCEDURE start_game(p_board IN VARCHAR2)
AS
v_board VARCHAR2(20):=UPPER(COALESCE(p_board,RPAD(gv_empty,gv_size,gv_empty)));
BEGIN
check_valid(v_board);
gv_board := v_board;
IF MOD(REGEXP_COUNT(gv_board,gv_empty),2)=0 THEN
gv_player :='X';
ELSE
gv_player :='O';
END IF;
move(v_board);
END start_game;
PROCEDURE play(p_move IN NUMBER)
AS
BEGIN
IF gv_board IS NULL THEN
DBMS_OUTPUT.PUT_LINE('Please start a new game');
RETURN;
END IF;
IF NOT NVL(p_move,0) BETWEEN 1 AND 9 THEN
RAISE_APPLICATION_ERROR(-20001,'invalid position! value should be 1-9');
END IF;
IF SUBSTR(gv_board,p_move,1)<>gv_empty THEN
RAISE_APPLICATION_ERROR(-20001,'position is already taken by:'||SUBSTR(gv_board,p_move,1));
END IF;
gv_board := SUBSTR(gv_board,1,p_move-1)||gv_player||SUBSTR(gv_board,p_move+1);
move(gv_board);
END play;
END pkg_tictactoe;
/
/*
SQL> exec pkg_tictactoe.start_game('X-------O');
Your side: O
=============
X--
---
X-O
PL/SQL procedure successfully completed.
Elapsed: 00:00:00.10
SQL> exec pkg_tictactoe.play(4);
Your side: O
=============
X-X
O--
X-O
PL/SQL procedure successfully completed.
Elapsed: 00:00:00.04
SQL> exec pkg_tictactoe.play(2);
Your side: O
=============
XOX
OX-
X-O
========= You lose! =========
PL/SQL procedure successfully completed.
*/
|
|
楼主: newkid
IP卡
狗仔卡
楼主
显身卡
发表于 2015-12-21 23:14
