快速维护围棋状态

自己YY一天的结果。。

维护几个表

盘面表

{White, Black, NA} [19 * 19]

我们可以压位!每一个位置的状态压到一个2bit中,总共只需要19 * 19 * 2 / 8 = 90字节,比起原来的361字节+对齐好了很多。

再进一步想一想,我们的操作常常是对每几行都进行操作,那么我们其实可以尝试下SSE来进行这种操作。

联通块链表

联通块因为数目不多其实可以做成一个链表方便查询/修改……

struct group
{
    char liberty;
    group *next: 5; // 只有amd64 低40位
    Player player; // char
    char last_update; // 第几步被更新了,低频率的地方我们减少搜索概率
};

这样刚好压成8个字节。。

棋盘位置-联通块表(posgrp)

由于联通块是链表所以每个位置可以直接储存其所在的联通块的指针group *。。同样可以压到5个字节每个位置,总共是1805字节(好大。。心疼Cache)

整个盘面表做一个 -> 64位的hash……由于盘面表使用bitset实现的,std::hash都包办好了。储存上步开始时的hash就行了。

下子

提对方子

首先考虑下的是白棋,先考虑提对方子的情况。

由于有posgrp表,可以很容易知道周围4个位置的联通块情况。。给其中的黑色块去重、减liberty。如果减到0就要提对方的整个块了。

考虑下怎么提一个点……这次只要考虑对白棋影响——因为如果对黑棋有影响这两块一定联通。同样是计算出周围4个位置的联通块情况,给其中的白色块去重、加liberty。

然后设置posgrp表这个地方是NULL,删除对应的联通块表项。

连接白块

先从简单情况开始。如果周围没有联通白块,那么直接新增一个联通块设置posgrp就行了。

其他情况包括:贴上一个旧联通块,使气发生了变化/连接了几个联通块。

注意到不管什么时候,发生的气的变化都只与5×5范围内的棋子有关,因此我们可以打一个表,预处理出下在这一点时对左右上下四个块的气的影响。然后联通时直接合并两个块,取任意一个预处理出的结果就行了。

提白子

我们在任何时候都能维护好每个块的liberty,那么在上一步的末尾我们扫一遍上下左右中的联通块,提掉死了的块,具体方法同提黑子所述。

发表评论