我博客上的围棋js程序

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/8506691.html 

  作者:窗户

  QQ:6679072

  E-mail:6679072@qq.com

  作为一个围棋爱好者,就决定在博客里加个围棋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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据之美

BloomFilter 简介及在 Hadoop reduce side join 中的应用

1、BloomFilter能解决什么问题?      以少量的内存空间判断一个元素是否属于这个集合, 代价是有一定的错误率 2、工作原理 ...

26270
来自专栏非典型技术宅

Swift实践:使用CoreData存储多种数据类的通讯录1. CoreData支持存储数据类型2. 使用CoreData存储多种数据类的通讯录3. Codable

21730
来自专栏机器人网

中英文对照,瞬间理解西门子PLC指令

指令( 英文全称意思 ) :指令含义 1、LD ( Load 装载 ) :动合触点 2、LDN ( Load Not 不装载 ) : 动断触点 3、A ( A...

36270
来自专栏一“技”之长

AppleWatch开发入门四——Table视图的应用

        WatchOS中的TableView和iOS中的TableView还是有很大的区别,在开发之前,首先我们应该明白WatchOS中的Table有哪...

11320
来自专栏Java架构沉思录

谈谈Java中常见的线程安全模型

多线程编程一直是老生常谈的问题,在Java中,随着JDK的逐渐发展,JDK提供给我们的并发模型也越来越多,本文摘取三例使用不同原理的模型,分析其大致原理。

14220
来自专栏拭心的安卓进阶之路

并发编程6:CopyOnWriteArrayList 的写时复制

首先提个问题: 线程安全的 List 集合有什么? CopyOnWriteArrayList 的特点以及使用场景? 如果这个问题你答不上来,那这篇文章可能就...

31880
来自专栏FreeBuf

浅析ReDoS的原理与实践

*本文原创作者:MyKings,本文属FreeBuf原创奖励计划,未经许可禁止转载 ReDoS(Regular expression Denial of Ser...

97550
来自专栏Flutter&Dart

DartVM服务器开发(第二十一天)--Dart中的Gson(jaguar_serializer)

将上面的Info改为List<Info> 重新运行命令pub run build_runner build 转换跟上面一样

24410
来自专栏农夫安全

注入学习之sqli-labs-5(第四次)

前言 第七关先跳过,先把get注入系列讲完再来讲 不知道大家有没有玩过一个猜数字的游戏 我给出一个数的范围,比如1-100,然后你去猜,我只会回答你对或者错。 ...

400100
来自专栏沃趣科技

MySQL排序内部原理探秘

一、我们要解决什么问题 二、排序,排序,排序 三、索引优化排序 四、排序模式 4.1实际trace结果 4.2排序模式概览 4.2.1回表排序模式 4.2.2不...

53960

扫码关注云+社区

领取腾讯云代金券