对于底层棋盘的搜索的一种低复杂度优化

种肉肉的农夫

我要拿出我认为是我整个程序中最厉害的内容：空间换时间：

查找一次列表的时间是O(1)，那么遍历一次棋盘的时间复杂度是否也可以做到O（1）

注意，我们这里并不打表，并不用哈表这类工具，不是因为不道德什么的，而是因为

根本没有那么多的空间给你

我们做个简单的计算，就按19*19的棋盘来说吧

不考虑对称棋盘的角度下，可能性是：

3^361次幂，那么就是17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603种可能

假定全以short类型存入（实际上不可能全是short，因为3万可能根本不可能包含），那么需要

3的160次方TB的空间

试问，你有哪怕是1TB的内存条嘛？哪怕是64G的内存条你怕是都拿不出来吧（不知道有没有64G了，反正我的电脑就俩8G的）

那么我们如何做到O（1）呢？

那么就只能是理论上的O（1）了，因为真实的O（1）已经被验证（上述）不行了，那么我们只能造个伪O（1）

那么就需要进行一系列的转换

首先，对棋盘进行单次扫描

这就需要对每一个跳，每一个空进行记录

五子棋需要有4个维度，横着，竖着，左斜，右斜

将4个维度压缩起来，可以先进行预处理：


def get_larger_check(the_dict,its_board_order):
    for y in range(its_board_order):
        for x in range(its_board_order):
            ready_append = []
            flag_range = [0,1]
            x_y,x_y_2 = abs(y-x),y+x
            if x_y <= its_board_order-5:
                flag_range.append(2)
            if 4 <= x_y_2 < its_board_order*2-5:
                flag_range.append(3)
            for flag in range(len(flag_range)):
                for i in range(-1,-its_board_order,-1):
                    tx,ty = x + i * SPEED_X[flag_range[flag]],y + i*SPEED_Y[flag_range[flag]]
                    if tx < 0 or tx >= its_board_order or ty < 0 or ty >= its_board_order:
                        break
                    ready_append.append((tx,ty))
                for i in range(1,its_board_order):
                    tx,ty = x + i * SPEED_X[flag_range[flag]],y + i*SPEED_Y[flag_range[flag]]
                    if tx < 0 or tx >= its_board_order or ty < 0 or ty >= its_board_order:
                        break
                    ready_append.append((tx,ty))
            the_dict[y,x] = tuple(ready_append)
    return the_dict


def get_huge_sec_check(the_dict,its_board_order):
    for y in range(its_board_order):
        for x in range(its_board_order):
            x_y,x_y_2 = abs(y-x),y+x
            is_2,is_3 = False,False
            if x_y <= its_board_order-5:
                is_2 = True
            if 4 <= x_y_2 < its_board_order*2-5:
                is_3 = True
            the_dict[y,x] = (is_2,is_3,y-x,y+x)
    return the_dict

种肉肉的农夫

1. 
   
2. def zobrist_bw_generate():
   
3. 
   
4.     counting = 0
   
5.     for y in range(20):
   
6.         for x in range(20):
   
7.             zobrist_b[y,x] = blackdata[counting]
   
8.             zobrist_w[y,x] = whitedata[counting]
   
9.             hugeCoord15[y,x] = [(cy,cx)
   
10.                                 for cy in range(max(0,y-2),min(15,y+3))
    
11.                                 for cx in range(max(0,x-2),min(15,x+3))
    
12.                                 if cx != x or cy != y]
    
13.             hugeCoord19[y,x] = [(cy,cx)
    
14.                                 for cy in range(max(0,y-2),min(19,y+3))
    
15.                                 for cx in range(max(0,x-2),min(19,x+3))
    
16.                                 if cx != x or cy != y]
    
17.             hugeCoord20[y,x] = [(cy,cx)
    
18.                                 for cy in range(max(0,y-2),min(20,y+3))
    
19.                                 for cx in range(max(0,x-2),min(20,x+3))
    
20.                                 if cx != x or cy != y]
    
21.             hugeCoord15[y,x] = tuple(hugeCoord15[y,x])
    
22.             hugeCoord19[y,x] = tuple(hugeCoord19[y,x])
    
23.             hugeCoord20[y,x] = tuple(hugeCoord20[y,x])
    
24.             counting += 1

复制代码

当然，真实情况必须要先在程序开始运行前运行一遍

这些就是将所有的点坐标全都存起来

因为你遍历的顺序是恒定的，点也是恒定的

其次，有个小技巧，就是要用tuple，这会比list快很多。

其次，就是要在check前准备好预处理数据：
shu = [[False,0,False,0,0,0] for _ in range(the_board_order)]
xie_1 = [[False,0,False,0,0,0] for _ in range(xie_static)]
xie_2 = [[False,0,False,0,0,0] for _ in range(xie_static)]   

嗯是的，我是设了6个维度，六个变量，如果有更好的更精简的可以和我说
而且我前两天的确想到了一个只存一个变量的方法，但没空实现，等我真的做好后实现

其次

1. extern "C" short get_cal_hash(const short key[4]){
   
2.     return ((key[0] << 12) | (key[1] << 8) | (key[2] << 4) | key[3]) % 83;
   
3. }

复制代码

转换哈希值

是的，这是我用c++代码加速的函数，一开始你们可以用python写这个

准备一个打包好的表，像这样：

1. 
   
2. const short hash_list[83] = {40, 0, 0, 2, 3, 0, -55, 55, 0, 0, 4, 5, -65, 65, 0, 0, 0, 0, 0, -200, 1, 0, 0, 0, 0, 0, 0, 0, -75, 75, 0, 0, 0, 0, 0, -200, 1, 0, 0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 4, 5, 2, 3, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 2, 3, -40, 40, 0, 0, 0, 0, 0, -55, 55, 0, 0, 0, 0, 2, 3, 0, -40};
   

复制代码

你看这个肯定看不懂，但是你看看这个东西怎么生成的就明白了

额生成的那个文件给我删了

就说下逻辑吧，就是先准备好这个：

1. 
   
2. complex_values = {
   
3.     (5,2,1,2): 5,
   
4.     (4,2,0,2): 5,
   
5.     (5,2,1,1): 4,
   
6.     (4,2,0,1): 4,
   
7.     (4,2,1,2): 3,
   
8.     (4,1,0,2): 3,
   
9.     (4,1,1,2): 3,
   
10.     (5,0,1,2): 3,
    
11.     (4,0,1,2): 3,
    
12.     (5,1,1,2): 3,
    
13.     (4,2,1,1): 2,
    
14.     (4,1,0,1): 2,
    
15.     (4,1,1,1): 2,
    
16.     (5,0,1,1): 2,
    
17.     (4,0,1,1): 2,
    
18.     (5,1,1,1): 2,
    
19.     (3, 2, 1, 2): 1,
    
20.     (3, 2, 0, 2): 1,
    
21.     ####### 不可以是 1 2 3，4 5
    
22.     (3, 1, 1, 2): 75,
    
23.     (3, 1, 0, 2): 65,
    
24.     (2, 2, 0, 2): 55,
    
25.     (2, 2, 1, 2): 55,
    
26.     (2, 1, 0, 2): 40,
    
27.     (2, 1, 1, 2): 40,
    
28.     (3, 1, 1, 1): -75,
    
29.     (3, 1, 0, 1): -65,
    
30.     (2, 2, 0, 1): -55,
    
31.     (2, 2, 1, 1): -55,
    
32.     (2, 1, 0, 1): -40,
    
33.     (2, 1, 1, 1): -40,
    
34.     (3, 2, 1, 1): -200,
    
35.     (3, 2, 0, 1): -200,
    
36. }
    

复制代码

代表每种可能的值

其次，例如（3，2，0，1），就用上面那个c++函数转化成哈希值，然后存到表里面去

最后生成那个外星人也看不懂的表格

看懂了这些，O（1）就实现了

不过自然，这和真实的O(1)还是有区别的，但是在形式上至少做到了O（1）

---

最后，真挚的像黄泓睿同学道歉