欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

我博客上的围棋js程序

程序员文章站 2022-07-02 17:58:27
作为一个围棋爱好者,就决定在博客里加个围棋js程序。于是,申请了博客的js权限,美化美化我的博客。 好在js的语法像C系的,看了看,写个程序应该还是可以的。 围棋里,设计好基本的数据结构: 画图用canvas,之前并未接触,一样,baidu上搜搜,知道了画圆、画线、画方块的办法,OK了,我画围棋说白 ......

  作为一个围棋爱好者,就决定在博客里加个围棋js程序。于是,申请了博客的js权限,美化美化我的博客。

  好在js的语法像C系的,看了看,写个程序应该还是可以的。

  围棋里,设计好基本的数据结构:

  

//a是19X19数组,用来存放围棋,每个位置0为空,1为黑,2为白
//b是检测禁手、提子时临时使用
var a = new Array(19);
var b = new Array(19);
for(var i=0;i<19;i++) {
    a[i] = new Array(19);
    b[i] = new Array(19);
    for(var j=0;j<19;j++) {
        a[i][j] = 0;
    }
}
//当前棋的步数,从0开始
var step = 0;
//选择qa变量的第qipu_seq个棋谱
var qipu_seq = Math.floor(10000*Math.random())%qa.length;
//所有的棋谱,这个数据结构是本文重点,后面讲
var qa;

 

  画图用canvas,之前并未接触,一样,baidu上搜搜,知道了画圆、画线、画方块的办法,OK了,我画围棋说白了就是圆、线、方块组成。过程中有个BUG,后来才知道,是我对moveTo、LineTo的理解有问题,最终画棋盘、棋子的函数如下:

function draw_weiqi()
{
    var c=document.getElementById("myCanvas").getContext("2d");

    c.fillStyle="#808080";
    c.fillRect(0,0,8*20,8*20); 
    c.beginPath();
    c.strokeStyle="#000000";

    for(var i=0;i<19;i++) {    
        c.lineWidth = 1;
        c.moveTo(8+i*8,8);
        c.lineTo(8+i*8,19*8);
        c.stroke();
        c.moveTo(8,8+i*8);
        c.lineTo(19*8,8+i*8);
        c.stroke();
    }
    for(var i=0;i<19;i++) {
        for(var j=0;j<19;j++) {
            if(a[i][j] != 0) {
                if(a[i][j] == 1) {
                    c.fillStyle="#000000";
                } else {
                    c.fillStyle="#FFFFFF";
                }
                c.beginPath();
                c.arc(8+i*8,8+j*8,4,0,Math.PI*2,true);
                c.fill();
            }
        }
    }
    if(step!=0) {
        var n = qipu[Math.floor((step-1)/2)];
        if(step%2==1) {
            n = n%361;
        } else {
            n = Math.floor(n/361);
        }
        var x = Math.floor(n/19);
        var y = n%19;
        c.fillStyle="#FF0000";
        c.fillRect(6+x*8,6+y*8,4,4);
    }
        for(var i=0;i<9;i++) {
                var x = 3+6*(i%3);
                var y = 3+2*(i-i%3);
                if(a[x][y] == 0) {
                        c.fillStyle="#c0c0c0";
                        c.fillRect(8+x*8,8+y*8,1,1);
                }
        }
}

 

  我的想法是js默认的情况是反复播放alphago master和alphago zero的二十局棋,鼠标点上去之后可以手动下棋(但不支持AI),于是还要去考虑鼠标的操作。

  鼠标的操作网上有太多的文章来讲,但讲的似乎又不清晰,不过反复调试,试验下,鼠标的支持还是没问题了。

  var n = document.getElementById("myCanvas");

  var ev = event || window.event;
  var x = ev.PageX||ev.clientX;
  var y = ev.PageY||ev.clientY;
  x += document.documentElement.scrollLeft || document.body.scrollLeft;
  y += document.documentElement.scrollTop || document.body.scrollTop;

  x -= n.offsetLeft;
  y -= n.offsetTop;

  找到点击的位置在画布里的相对坐标为以上代码,可是这里还是有一个BUG,对于Firefox不支持,我也没去找原因,如果有知道的,欢迎和我联系或者写在评论里,让我可以补掉这个BUG。

 

  围棋的规则也没什么问题,我有篇文章(《围棋规则的计算机实现》)里专门讲围棋的规则可以看成是一个连通图遍历,如此可以判断有没有气,从而禁手、提子、打劫,乃至后面点掉死子、数子计算胜负都可以归结于连通图遍历。

  

  放进去棋谱是个问题,这需要相对较大的数据量,我虽然只放20个棋谱,但是我的强迫症总觉得棋谱的数据多了。

  我拿到的sgf文件,是围棋界的标准存储文件,以master和zero的第一局为例,棋谱如下:

(;FF[4]CA[UTF-8]KM[7.5]OT[3x60 byo-yomi]PB[AlphaGo Master]PW[AlphaGo Zero]
RE[W+R]RU[Chinese]TM[7200];B[dd];W[pp];B[cp];W[pd];B[fp];W[cc];B[cd];W[dc];
B[fc];W[ec];B[ed];W[fb];B[dj];W[nq];B[mp];W[hq];B[qf];W[qk];B[nc];W[pf];B[pg];
W[of];B[qd];W[qc];B[qe];W[pc];B[qi];W[md];B[og];W[mc];B[gb];W[gc];B[fd];W[hb];
B[gd];W[ga];B[hp];W[ip];B[ho];W[gq];B[fq];W[io];B[np];W[mq];B[in];W[jq];B[jn];
W[op];B[lq];W[lr];B[lp];W[kq];B[ek];W[dp];B[dq];W[bj];B[bl];W[cq];B[me];W[le];
B[lf];W[mf];B[ne];W[nf];B[ke];W[ld];B[kd];W[nd];B[cr];W[ch];B[eh];W[be];B[bd];
W[cf];B[rn];W[rp];B[qo];W[qp];B[mr];W[nr];B[ir];W[iq];B[on];W[eg];B[dh];W[dg];
B[fg];W[bg];B[mh];W[lg];B[kf];W[nh];B[mj];W[mg];B[kg];W[lh];B[kh];W[hf];B[gf];
W[hd];B[hg];W[ml];B[nl];W[nm];B[om];W[ck];B[cl];W[nk];B[ol];W[mk];B[pj];W[eq];
B[dr];W[fr];B[fo];W[qm];B[qn];W[pn];B[po];W[oo];B[pk];W[er];B[ep];W[ri];B[rh];
W[do];B[es];W[gr];B[kj];W[pm];B[rm];W[ql];B[qj];W[hn];B[hm];W[dk];B[dl];W[ej];
B[co];W[rj];B[pl];W[fk];B[el];W[di];B[fj];W[ei];B[fi];W[fh];B[gh];W[rk];B[si];
W[ff];B[gg];W[ie];B[ge];W[kc];B[lj];W[ko];B[lm];W[nj];B[mi];W[ni];B[kr];W[ms];
B[jd];W[kk];B[nn];W[km];B[kn];W[ng];B[jk];W[jl];B[bk];W[cj];B[rc];W[rb];B[jc];
W[jj];B[ik];W[gi];B[gj];W[ij];B[hj];W[il];B[hk];W[ki];B[ji];W[gn];B[dn];W[hl];
B[gl];W[gm];B[kb];W[lb];B[mb];W[nb];B[bc];W[bb];B[ab];W[ba];B[da];W[db];B[ma];
W[na];B[ea];W[eb];B[sd];W[ln];B[lo];W[im];B[aj];W[ai];B[sb];W[ra];B[jr];W[hr];
B[ii];W[la];B[he];W[id];B[if];W[ro];B[rl];W[lk];B[li];W[sn];B[sk];W[fn];B[eo];
W[sm];B[sj];W[ib];B[jb];W[kp];B[jo];W[mm];B[mn];W[qb];B[jp];W[ks];B[fm];W[em];
B[fl];W[en];B[fs];W[sa];B[ef];W[ak];B[al];W[dm];B[cm];W[ee];B[fe];W[de];B[ae];
W[ce];B[af];W[sc];B[rd];W[ph];B[qg];W[oh];B[pe];W[oe];B[pr];W[rr];B[rq];W[qq];
B[so];W[sp];B[sl];W[so];B[ic];W[hc];B[ag];W[ah];B[gs];W[is];B[eh];W[je];B[jf];
W[ia];B[aj];W[bf];B[ad];W[ak];B[gp];W[js];B[aj];W[lc];B[no];W[ak];B[sb];W[aj])

  我不用解释,应该也能猜的出来,前面是信息,B[dd];W[pp];B[cp];这样的是一步一步的棋,采用坐标的方法,横纵坐标都是a-s这19个字母中的一个。

  因为最开始对js不熟悉,想全部用整数存储棋谱,每一步棋存成0~360的一个数字,方法是把a-s对应于0~18,然后X*19+Y(其中X,Y是横纵坐标),然后搞成数组,20个棋谱的qa变量就是数组的数组。

  用shell设计出来就是这样:

#!/bin/bash
export LANG=C
for i in *.sgf; do
        cat $i | tr -d '\r\n\t() ' | tr ';' '\n' | sed -nr '/^[BW]\[([a-s][a-s])\]$/!d;s//\1/;H;${x;s/\n//gp;}' | od -t u1 -An -v | gawk '
        BEGIN {n=0}
        {for(i=1;i<=NF;i++){a[n++]=$i-97;}}
        END {
                m=0;
                for(i=0;i+2<=n;i+=2)b[m++]=a[i]*19+a[i+1];
                for(i=0;i<m;i++) {
                        x = b[i];
                        if(i!=0)printf(",");
                        printf("%d",x);
                }
                printf("\n");
        }
        ' | sed -nr 's/^/\[/;s/$/\],/;p' | tr -d '\n'
done | sed -nr 's/,$//;s/^/var qa = \[/;s/$/\];/;p'
echo

var qa = [[60,300,53,288,110,40,41,59,97,78,79,96,66,263,243,149,309,314,249,290,291,271,307,306,308,287,312,231,272,230,115,116,98,134,117,114,148,167,147,130,111,166,262,244,165,187,184,281,225,226,224,206,86,72,73,28,30,54,232,213,214,233...

  因为js是解释型语言,最终从服务器上下下来的是代码,一数,字节数很多,19788字节。强迫症犯了,要压一下。

   于是每两步棋合一起,比如前一步棋为A,后一步棋为B,AB范围都为0~360,则用B*361+A表示两步棋。如果整局棋的步数为奇数,最后一步棋找不到配的,那么最后一个数字就是361*361+A(正常范围是0~360,361并不是真实棋步,可以直接判断出来这一步没有)

  shell程序如下

#!/bin/bash
export LANG=C
for i in *.sgf; do
        cat $i | tr -d '\r\n\t() ' | tr ';' '\n' | sed -nr '/^[BW]\[([a-s][a-s])\]$/!d;s//\1/;H;${x;s/\n//gp;}' | od -t u1 -An -v | gawk '
        BEGIN {n=0}
        {for(i=1;i<=NF;i++){a[n++]=$i-97;}}
        END {
                m=0;
                for(i=0;i+4<=n;i+=4)b[m++]=a[i]*19+a[i+1]+(a[i+2]*19+a[i+3])*361;
                if(i+2<=n)b[m++]=a[i]*19+a[i+1]+361*361;
                for(i=0;i<m;i++) {
                        x = b[i];
                        if(i!=0)printf(",");
                        printf("%d",x);
                }
                printf("\n");
        }
        ' | sed -nr 's/^/\[/;s/$/\],/;p' | tr -d '\n'
done | sed -nr 's/,$//;s/^/var qa = \[/;s/$/\];/;p'
echo

  再来看一看,数据如下这样:

var qa = [[108360,104021,14550,21340,28255,34735,95009,54032,113663,104939,98122,110773,103915,83703,83302,41991,48472,41271,60435,47077,60037,88346,67672,101625,81811,74590,26078,10181,19524,77125,84327,91223,76726,90443,16300,8386,15545,122354,115477,95549,60817,29881,22807...

  这里的数据压缩到16489字节,还是很多。

  其实,当初有个很好的选择,就是直接提出a-s的坐标,然后来表示,那么master和zero第一盘棋就变成以下字符串

  “ddppcppdfpcccddcfcecedfbdjnqmphqqfqkncpfpgofqdqcqepcqimdogmcgbgcfdhbgdgahpiphogqfqionpmqinjqjnoplqlrlpkqekdpdqbjblcqmelelfmfnenfkeldkdndcrchehbebdcfrnrpqoqpmrnririqonegdhdgfgbgmhlgkfnhmjmgkglhkhhfgfhdhgmlnlnmomckclnkolmkpjeqdrfrfoqmqnpnpooopkereprirhdoesgrkjpmrmqlqjhnhmdkdlejcorjplfkeldifjeififhghrksiffggiegekcljkolmnjminikrmsjdkknnkmknngjkjlbkcjrcrbjcjjikgigjijhjilhkkijigndnhlglgmkblbmbnbbcbbabbadadbmanaeaebsdlnloimajaisbrajrhriilaheidifrorllklisnskfneosmsjibjbkpjommmnqbjpksfmemflenfssaefakaldmcmeefedeaeceafscrdphqgohpeoeprrrrqqqsospslsoichcagahgsisehjejfiaajbfadakgpjsajlcnoaksbaj”

  shell如下:

#!/bin/bash
export LANG=C
for i in *.sgf; do
        cat $i | tr -d '\r\n\t() ' | tr ';' '\n' | sed -nr '/^[BW]\[([a-s][a-s])\]$/!d;s//\1/;H;${x;s/\n//gp;}' | sed -nr 's/^/"/;s/$/",/;p'
done | sed -nr 's/,$//;s/^/var qa = \[/;s/$/\];/;p'
echo

 

  这个其实已经很不错,10730字节。只是最开始的时候对js不熟,不知道怎么处理字符到整形,强迫症也没犯。

  不过,这个10730字节我还是不满足,后来想了想,

  其实用一个整数来代表两步棋,B*361+A(B为0~361,A为0~360),那么这个整数范围为0~130681,

  而217=131072>130681

  而且数值非常接近,

  于是决定每步棋编码17bits,编成二进制数据,又因为js不是编译型语言,需要给二进制数据一个编码,base64是合适的,理论上可以再压缩的多那么一点点,比如不只64个可见字符,用的更多一些也可,只是程序比较复杂,因为不再是2的整数次方个不同的用来编码的可见字符,压缩率提高也有限。于是就此作罢。

  

#!/bin/bash
export LANG=C
for i in *.sgf; do
        cat $i | tr -d '\r\n\t() ' | tr ';' '\n' | sed -nr '/^[BW]\[([a-s][a-s])\]$/!d;s//\1/;H;${x;s/\n//gp;}' | od -t u1 -An -v | gawk '
        BEGIN {n=0}
        {for(i=1;i<=NF;i++){a[n++]=$i-97;}}
        END {
                m=0;
                for(i=0;i+4<=n;i+=4)b[m++]=a[i]*19+a[i+1]+(a[i+2]*19+a[i+3])*361;
                if(i+2<=n)b[m++]=a[i]*19+a[i+1]+361*361;
                for(i=0;i<m;i++) {
                        x = b[i];
                        y = 65536;
                        for(j=0;j<17;j++) {
                                if(x>=y) {
                                        x-=y
                                        print "1"
                                } else
                                        print "0"
                                y/=2;
                        }
                }
        }
        ' | gawk 'BEGIN{i=0;j=128;v=0;}
        {if($1==1)v+=j;j/=2;i++;if(i==8){printf("%c",v);i=0;j=128;v=0}}
        END{if(i!=0)printf("%c",v)}
        ' | base64 | tr -d '\n' | sed -nr 's/^/"/;s/$/",/;p'
done | sed -nr 's/,$//;s/^/var qa = \[/;s/$/\];/;p'
echo

  var qa = ["06RllUcaxTXDcvoevuZC0xDd/+Z67+lbC1yvXRveisykB16sKE3dgmt+V1QtZGoQsYz5n8nI14y7wnxSYiS1FpLPZFeV21hSx/WCDCHlz3fLhit1PXbInS5LIuI6aYDVm8aVzzFcYa+wD+oyVuPSJjWqaqFmguJPHW+CdK74wDQiZ0x4ytK5GdHMb2CZ42Xww8EPUYEqclwAO24kD3rByOYm46Q82kENad20QdbtY1bR3esshAVshMnKKX9AqysccI5mmL4qzymWrLIrlHDXp0OJIazCkB10zNnDOmd0EYLUeRpNRCk6y2xzt602Ifq6Jms+cY2SCQ4NTKdeFSYKPkGfevxW4OazCsHECKzQOz7yjudCsEX33f8FFxJP8aP3ZV98gnleB89xprhAh4QcOwsGlMoDx8HBAA==",...

  总算满意了,数数字节数,

# ./deal.sh | wc -c

7680

 

  7680字节,算是交代了。

  最后,再把代码中的一堆变量、函数名给用单个字符替换了,去掉所有的换行、空格,甚至括号都没有多余的,

  遇到if(cnt1 != 0 && cnt2 == 0),都被我简写成了if(cnt&&!cnt2),当然,后面cnt、cnt2都被搞成了单字符。

  最后贴了出去,可读性极差,不过代码小,如果我自己需要改动,就用原本的代码改动了。接下去想在此基础上搞个简易的AI,再看时间了。

  

  刚才想了想,base64的解码是从网上找过来然后修改的,我看那个字符串表示不是太长了一点,强迫症又来了,我是不是该再裁它一刀。

  

function base64_decode(c){
        var s="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
        var x="";
        var e=new Array(4);
        var i=0;
        c=c.replace(/[^A-Za-z0-9\+\/\=]/g, "");
        while(i<c.length){
                for(var j=0;j<4;j++)
                        e[j]=s.indexOf(c.charAt(i++));
                x+=String.fromCharCode((e[0]<<2)|(e[1]>>4));
                if (e[2]!=64)
                        x+=String.fromCharCode(((e[1]&15)<<4)|(e[2]>>2));
                if (e[3] != 64)
                        x+=String.fromCharCode(((e[2]&3)<<6)|e[3]);
        }
        return x;
}