量化投资学习笔记102——用电脑下五子棋

发表于 | 分类于
| 字数统计: 6.3k | 阅读时长 ≈ 23

我没偏题，这还是量化交易的内容。交易不就是人跟人(或人背后的代码)在博弈嘛。初步想法是先把框架搭起来，包括下棋规则，判断输赢什么的，然后用传统的人工智能方法实现人机对战，最后试试AlphaGo的强化学习。
找了一些网站，这有个现成的，我就先抄再研究改进了。特此感谢！
首先先实现棋盘类，实现下棋的规则及输赢判断。最后用这个类实现人与人的对战。这一段基本是抄人家的程序再改改，因为没有ai，就略过了。

ok，下棋，判断输赢都没问题了。下面来给程序增加“人工智能”。先用最简单的方法——随机乱下。

1
2
3
4
5
6
7
8
9
10
11
12
# 随机算法确定下棋位置
def randomPut(board, who):
    random.seed(time.time())
    if board.full():
        return False
    while True:
        i = random.randint(0, 14)
        j = random.randint(0, 14)
        if board[i][j] == 0:
            board.put(i, j, who)
            return True
    return False


就是这样，计算机完全随机下棋，想赢很容易，想输却很难。我想把棋盘下满，测试一下棋盘下满的情况，但却都在无意当中就赢了。
下面改进一下:五子棋往往落子的地方是在对方上一次落子的区域附近。就设定在对方上次落子位置为中心的5×5大小的区域内，最多有24个位置可以随机选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 改进随机算法，在对方上次落子位置附近5×5的范围内随机落子
def nearRandomPut(board, who):
    random.seed(time.time())
    if board.full():
        return False
    last = board.getLast()
    if last == [-1, -1]:
        x = 7
        y = 7
    else:
        x = last[0]
        y = last[1]
    count = 0
    while True:
        count += 1
        #  防止所有附近区域都下满的情况
        if count >= 100:
            i = random.randint(0, 14)
            j = random.randint(0, 14)
        else:
            i = random.randint(max(x-2, 0), min(x+2, 14))
            j = random.randint(max(y-2, 0), min(y+2, 14))
        if board[i][j] == 0:
            board.put(i, j, who)
            return True
    return False

现在程序就变得有智能多了

但是程序还是不知道封堵对方已经有三个棋子连线的位置。
再继续改进算法之前，先对程序进行重构吧。无论人下棋还是电脑下棋，程序的结构都是基本一致的，能不能把它们的共同部分提炼出来，以后更改下棋算法的时候直接往里面塞不同的算法就行了?
写了一个contest函数，传入两个不同的算法函数，就可以用这两个算法进行对弈。考虑到先手有优势，随机决定哪个算法先手。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 算法与算法(包括人)之间对弈的一般过程
def contest(method1, method2, show = True):
    random.seed(time.time())
    methods = [method1, method2]
    b = chessboard()
    b.reset()
    if show:
        display(b)
    first = random.randint(1, 2)
    if first == 1:
        second = 2
    else:
        second = 1
    # 游戏循环
    while True:
        while True:
            if methods[first-1](b, first) == True:
                break
        if show:
            display(b)
        if b.check() == first:
            return first
        if methods[second -1](b, second) == False:
            print("无法落子，游戏结束!")
            input("按任意键继续")
            return -1
        if b.check() == second:
            if show:
                display(b)
            return second
        if show:
            display(b)
       
    return -1

返回赢家的代号。再比较一下两种随机算法的获胜概率:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 比较两种随机算法
def compareRandom():
    win = [0, 0]
    b = chessboard()
    while True:
        epochs = input("请输入对弈次数:")
        if epochs.isdigit() and int(epochs) > 0:
            epochs = int(epochs)
            break
    for i in range(epochs):
        b.reset()
        result = contest(randomPut, nearRandomPut)
        win[result-1] += 1
        print("第%d次对弈，%d取胜" % (i, result))
        
    winrate = [win[0]/epochs, win[1]/epochs]
    print("获胜概率:", winrate)
    input("按任意键继续")

开启输出棋盘，大概一秒钟对弈几次，可以看到还是很激烈的。

把显示棋盘关了，多对弈几次看看。

可以看到优化前后的随机算法的胜率比为46.5:53.5，优化后要好一点。
现在研究的工具基本都有了，可以开始正儿八经的研究下棋算法了。
先考虑深度学习之前的算法，找到一本很老的书:《pc游戏编程:人机博弈》，王小春著。用的编程语言是C++。
1.棋盘的表示:用二维数组。
2.走法的产生:所有空白区域都可以落子。产生走法的方式有一次性全部产生和逐渐产生两种。
3.基本搜索技术:
①博弈树:根节点为开局，其子节点为甲的走法，这些节点每个子节点又对应乙的走法。叶子节点是棋局的结局。博弈树即包含所有对弈过程的搜索树。
②极大极小值算法:(Minimax Algorithm)令甲胜为1， 乙胜为-1，和局为0。所以甲选子节点值最大的走法，乙选子节点值最小的走法。对于子节点，甲走时选所有子节点中值最大的，乙选值最小的。其深度为固定的搜索树，其值由评分函数给出。启发式搜索。
③深度优先搜索。
④负极大值算法:父结点的值是各子节点值的负数的极大值。
4.估值: 对棋盘上每个子赋予一个估值，一方的棋盘估值就是其所有子的估值总和。评估棋子的灵活性，将该棋子所有可能的走法的估值总和。棋子之间的关系也会影响评估。双方估值之差为棋局局面的估值。
上述过程太耗时了，改进措施为:
①Alpha_Beta搜索:搜索到一定节点发现无需再进一步搜索时将相应的节点剪枝。
②渴望搜索(Aspiration Search):
③极小窗口搜索(Minimal Window Search)
书中最后有个五子棋的程序，可惜是用C++写的，还是用MFC。我找个python写的来参考一下吧。
几乎完全照搬这里上的代码，只是ta是用python2，我给改成python3，调通了。仅仅用了一层搜索，我已经很难赢程序了。

再跟之前的随机算法PK一下

博弈树算法是碾压式的优势。
程序能跑不是目的，关键是学习。接下来我打算详细研究一下人家的代码。
在这个时候发现一个非常详细的教程 参考一下吧。
现在顺着流程来理一下，首先是博弈树算法下一步棋的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 博弈树算法下棋过程
def treePut(board, who):
    # 如果是先手，随机下一个地方
    last = board.getLast()
    if last == [-1, -1]:
        row = random.randint(0, 14)
        col = random.randint(0, 14)
        if board[row][col] == 0:
            board.put(row, col, who)
            return True
        return False
    s = searcher()
    s.board = board
   
    # 设置难度
    DEPTH = 1
    score, row, col = s.search(who, DEPTH)
    if board[row][col] == 0:
        board.put(row, col, who)
        return True
    return False

核心代码，先设置遍历深度，然后调用搜索树的搜索方法，根据当前棋盘局面找到下一步的走法:

1
score, row, col = s.search(who, DEPTH)

具体搜索过程为:

1
2
3
4
5
6
7
8
9
def search(self, turn, depth = 3):
        self.maxdepth = depth
        self.bestmove = None
        score = self.__search(turn, depth)
        if abs(score) > 8000:
            self.maxdepth = depth
            score = self.__search(turn, 1)
        row, col = self.bestmove
        return score, row, col

先设定最大搜索深度，然后调用具体执行搜索的函数__search(turn, depth)得到棋局评分，在这个函数里应该也设置了bestmove，即最佳落子位置。
现在来看具体执行搜索的步骤:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 递归搜索，返回最佳分数
    def __search(self, turn, depth, alpha = -0x7fffffff, beta = 0x7fffffff):
        # 深度为零，评估棋盘并返回
        if depth <= 0:
            score = self.evaluator.evaluate(self.board, turn)
            return score
           
        # 游戏结束，立马返回
        score = self.evaluator.evaluate(self.board, turn)
        if abs(score) >= 9999 and depth < self.maxdepth:
            return score
           
        # 产生新的走法
        moves = self.genmove(turn)
        bestmove = None
       
        # 枚举当前所有走法
        for score, row, col in moves:
            # 标记当前走法到棋盘
            self.board[row][col] = turn
            # 计算下一回合该谁走
            nturn = turn == 1 and 2 or 1
            # 深度优先搜索，返回评分，走的行和列
            score = -self.__search(nturn, depth-1, -beta, -alpha)
            # 棋盘上清除当前走法
            self.board[row][col] = 0
           
            # 计算最好分值的走法
            # alpha/beta剪枝
            if score > alpha:
                alpha = score
                bestmove = (row, col)
                if alpha >= beta:
                    break
               
        # 如果是第一层，记录最好的走法
        if depth == self.maxdepth and bestmove:
            self.bestmove = bestmove
           
        # 返回当前最好分数，及对应走法
        return alpha

这就是整个算法的核心了。首先如果深度为0了，或游戏有了输赢了，就结束搜索，调用棋盘评分函数得到当前的棋盘评分，具体评分方法先跳过，后面再研究。
如果既没有结束也没有到最底层，就调用另一个函数genmove产生走法。对于每一个走法，包含了局面评分，位置的坐标信息。对于每一个走法，先在棋盘上标注该位置，然后轮到对手走了，再递归调用:

1
score = -self.__search(nturn, depth-1, -beta, -alpha)

之后再恢复调用之前的棋盘状态。
之后计算最好分值的走法，即所谓的Alpha_Beta剪枝。

1
2
3
4
5
6
7
# 计算最好分值的走法
# alpha/beta剪枝
if score > alpha:
    alpha = score
    bestmove = (row, col)
    if alpha >= beta:
        break

这段是我比较疑惑的地方，再找资料看看。
最后，如果搜索到最大层数了，记录最大分值的走法，并返回分值。

1
2
3
4
5
6
# 如果是第一层，记录最好的走法
if depth == self.maxdepth and bestmove:
    self.bestmove = bestmove
    
# 返回当前最好分数，及对应走法
return alpha

下面具体看一下Alpha_Beta剪枝过程。参考了上面的那个教程
还有这篇
博弈树某一层是游戏一方的所有走法，下一层是另一方针对这些走法相应的所有走法，以此类推。每增加一层即代表增加一步走法。可以用递归来遍历整棵树。
选择分支的方法，电脑(己方)走棋的层称为MAX层，需要选分值最高的节点。人(对方)走棋的层称为MIN层，选分值最低的节点。这就是极大值极小值搜索。每个节点的分数由子节点决定，因此要进行深度优先搜索。可以把对方的分数变成负的，就能够统一完成递归过程。即负极大值搜索。层数最好是偶数。
Alpha_Beta剪枝算法是一种安全的剪枝策略，即不会对棋力产生任何负面影响。其原理是，明显对自己不利的节点，就不用考虑了。这个方法是建立在一个思想上的，如果你已经有一个不太坏的选择了，那么当你要作别的选择并知道它不会更好时，你没有必要确切地知道它有多坏。有了最好的选择，任何不比它更好的选择就是足够坏的，因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。
在MAX层，下一层会产生比最大值小的节点就可以删去。在MIN层，下一个节点的下一层产生的值比最小值还大，可删去该节点。
Alpha和Beta分别指MAX和MIN节点。删节点是删本层节点的子节点。
具体做法有点理解了，再来看那段代码:

1
2
3
if score > alpha:
    alpha = score
    bestmove = (row, col)

这应该就是alpha剪枝，即当前节点为最大分值节点时，该位置即为候选节点。
而

1
2
if alpha >= beta:
    break

则为beta剪枝，即当beta节点为最小节点时，舍弃其后的节点。
再来看生成走法的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 产生当前棋局的走法
    def genmove(self, turn):
        moves = []
        board = self.board
        POSES = self.evaluator.POS
        for i in range(self.row):
            for j in range(self.col):
                if board[i][j] == 0:
                    score = POSES[i][j]
                    moves.append((score, i, j))
        moves.sort()
        moves.reverse()
        return moves

就是对棋盘上所有空的位置进行遍历，然后按其分数进行排序，从分值最大的节点进行搜索。这里的排序和逆序，是使得走法更加有序，便于后续的Alpha_Beta剪枝过程。
至于棋盘的评分函数，就是根据棋子落到某位置后能形成的状态，如二连，三连，四连，五连，活三，活四等情况，分别赋予一个分值，再分横，竖，左斜，右斜四个方向来算，最后的分值总额就是棋盘上这个位置的分值。最后棋盘上每个点的分值总和就是该局面的分值。双方的分值之差就是某一方的分值。具体过程比较繁琐，就不赘述了，可以看github上的源代码。
下面再尝试一下用不同深度的博弈树算法进行比较。
这个就比之前的算法慢多了。用最浅的深度1来测试，在我手机上大约6秒完成一局。提高深度到2，棋局的时间就会长很多。

果然差不多。把算法二的深度改成2，再试一次。放到服务器上去跑吧。


跑20次，用了一小时三十九分钟。还是搜索深的胜率要高一点。这太慢了，才两层。试了一次3层的，一个多小时没下完一盘。超出忍耐极限了。优化一下?
参考了一些资料
先减少步数?输出了一下，开局时每次走棋产生的可能走法有220多种，减到10看看。即仅用前10个走法进行搜索。程序立马快了很多，进行4层搜索时，几秒钟走一步。
2层和4层深度pk一下:

17分钟，胜率46%:54%。
再加一下，2层和6层，时间又变得很长，大概三分钟左右下一盘。停了。
再试一下2层和5层

100盘下了近6个小时，可2层的胜率还比5层的高……
比较2层和4层吧，时间还可以接受。

但是发现一个bug，算法会对自己或对方已经四连的情况视而不见。多纳入一些走法，前20个试试。好一点，还是有视而不见的情况，再加10个。还是不行，最后放弃这个优化，选择搜索棋盘上所有空的位置，然后再加上对周围11*11个位置都没落子的位置不搜索，终于正常了。但是搜索层数只能局限于2层了，再深时间就太长了。先到这里吧，下面终于进入本文正题:强化学习了。
先看一篇介绍AlphaGo的文章
有详细的网络结构。但是貌似还用了一些棋谱数据。后来的Alpha Zero更牛，自己跟自己下就行了。就实现这个吧。
背后的思想是蒙特卡洛树搜索，先看一篇介绍这个的文章。
它是完美信息博弈场景中进行决策的一项通用技术。其主要目的是“给出一个‘游戏状态’并选择‘胜率最高’的下一步”。
博弈树是一种树结构，其中每一个节点表征博弈的确定状态。从一个节点向其子节点的转换被称为一个行动（move）。节点的子节点数目被称为分支因子（branching factor）。树的根节点表征博弈的初始状态。我们还区分了博弈树的端节点（terminal nodes），即没有子节点的节点，表示博弈无法再继续进行。端节点的状态可以被评估，并总结博弈的结果。传统的搜索方法是最大值最小值方法，以及对其的优化Alpha_Beta剪枝。
蒙特卡洛树搜索会多次模拟博弈，并尝试根据模拟结果预测最优的移动方案。
如果某个节点作为初始节点模拟过至少一次，它就可以被视为已访问节点。反向传播是从子节点(模拟开始的节点)遍历回根节点，其路径上每个节点都被计算/更新。节点的统计数据包括总模拟奖励和总访问次数。
根据UTC函数的值来选择要访问的节点。

该函数为节点v的子节点vi定义，第一项是节点vi的模拟胜率。第二项是探索组件，用于支持未被探索的节点。当资源(时间/算力)限制达到时即停止搜索，选择访问频率最高的节点。
接下来来看Alpha Zero的原理
与Alpha go相比，最大的优点是不需要预设知识。
蒙特卡洛树搜索算法因为是直接模拟到游戏终局，所以这种算法更加的准确，而且并不需要一个明确的“估值函数”，你只需要实现游戏机制就足够了。而且，蒙特卡洛算法，可以随时终止，根据其训练的时间给予近似的最优结果。
在Alpha Zero中，除了游戏规则，没有任何背景知识，只使用一个神经网络。以棋盘为输入，以下一步各下法的概率和胜率为输出，包含多个卷积层和全连接层。其核心思想是:MCTS生成的对弈可以作为神经网络的训练数据。
下面还是把代码撸起来吧，主要参考这两篇文章:1
2
由于算力的限制，这些文章都把棋盘大小设为8×8，为了一致，我把之前的程序也改成一样大小的棋盘。
主要照第一篇文章的代码来写。
先创建蒙特卡洛搜索树(MCTS)
基本照人家的写，为了匹配之前自己的程序，修改了很多。方法是先跑起来，然后连上自己的程序，运行，报错差什么就加什么，终于跑通了。具体实现在mcts.py里。先跟自己下一盘:

棋力好像不咋滴。再跟博弈树算法对几局看看。

还是能对上一阵的。
进行100次

搜索树碾压式的赢了。
再试一下5000次，用了近三个小时，还是输了。
但是蒙特卡罗树搜索的优点是，不用再人工定死棋盘评估方法了。下面就开始进行本文的核心部分:强化学习吧。
首先定义强化学习用的蒙特卡罗树搜索，树的节点和搜索树的定义都跟之前的一样，直接import。只是player类里获得走法的函数有点不一样。增加了随机噪音。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_action(self, board):
    sensible_moves = board.availables
    move_probs = np.zeros(board.width*board.height)
    if len(sensible_moves) > 0:
        move = self.mcts.get_move(board, temp)
        move_probs[list(acts)] = probs
        if self._is_selfplay:
            # 增加狄利克雷分布噪音，自己训练需要
            move = np.random.choice(acts, p=0.75*probs + 0.25*np.random.dirichlet(0.3*np.ones(len(probs))))
            # 更新根节点
            self.mcts.update_with_move(move)
        else:
            # 默认参数temp = 1e-3，近似等于选择概率最高的叶子节点
            move = np.random.choice(acts, p=probs)
            self.mcts.update_with_move(-1)
           
        if return_prob:
            return move, move_probs
        else:
            return move
    else:
        print("棋盘满了")

下面定义策略值网络。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 策略神经网络
class Net(nn.Module):
    def __init__(self, board_width, board_height):
        super(Net, self).__init__()
        
        self.board_width = board_width
        self.board_height = board_height
        # 普通层
        self.conv1 = nn.Conv2d(4, 32, kernel_size=3, padding=1)
        self.conv2 = nn.Conv2d(32, 64, kernel_size=3, padding=1)
        self.conv3 = nn.Conv2d(64, 128, kernel_size=3, padding=1)
        # 行动策略层
        self.act_conv1 = nn.Conv2d(128, 4, kernel_size=1)
        self.act_fc1 = nn.Linear(4*board_width*board_height, board_width*board_height)
        # 状态值层
        self.val_conv1 = nn.Conv2d(128, 2, kernel_size=1)
        self.val_fc1 = nn.Linear(2*board_width*board_height, 64)
        self.val_fc2 = nn.Linear(64, 1)

完全照人家的代码写的。还有策略值网络PolicyValueNet实现了训练过程，保存模型等过程。在policy_value_net.py里。
最后进行训练过程，在RLtrain.py里。
训练的流程，在run成员函数里。
先指定每次训练自己跟自己对弈的次数。
然后电脑自己跟自己打(collect_selfplay_data)，在里面调用自我对弈程序，取得每种走法的获胜概率值。然后调用get_equi_data扩增数据。主要是使用对数据进行旋转和翻转的方法，使数据规模扩大四倍。
获取数据后，在主函数里调用policy_update计算策略的损失函数，主要为调用策略值网络里的训练步骤进行若干次迭代(就是神经网络的前向传播，反向传播过程)，然后调整学习率等。
间隔一定次数，就用纯蒙特卡罗树搜索算法作为基准对强化学习模型进行评估，如果结果比之前的结果好，就保存当前模型。我又画了一下各次训练的损失函数值。
训练程序放到服务器上跑，跑了十多个小时，100次。

下面再实现用该模型来对弈。

结果，棋力很差……
跟博弈树算法PK一下:

显然不是对手。对战100次看看

98:2，胜率那么低……但起码不是100:0，说明不是完全随机下的，还是有点“智能”在里面的。把每次搜索次数增加到1000次，再试试。训练时间大幅延长了，训练10次，花了30000多秒。再对战一下看看。
结果类似，99:1。把训练次数增加100倍到1000次看看。在我的破服务器上要跑好几天的。
租GPU试试？
租GPU跑了50次，到50次时出现迭代次数超出限制的错误停止了。用训练的模型对弈一下看看，注意要在GPU环境下，如果在CPU环境下就报错。不知道为啥。棋力还是很差。

跟博弈树算法对弈100次看看，结果，99:1。把mcts搜索次数增加到1000次看看。结果还是99:1……
换作者训练好的模型看看。可能作者用的python2的缘故，加载出错。还是想想调参吧。要调参先要理解原理，读读论文吧：
Mastering the game of Go with deep neural networks and tree search
译文:1
2
通过一个估值网络“value network”来评估局面，通过一个策略网络“polic network”来产生下法，采用了以人类选手作为训练特征的有监督学习和以算法自我对弈进行的强化学习。采用蒙特卡罗树搜索来进行随机的棋局对弈。用一个新的搜索算法结合了蒙特卡洛模拟和策略网络。第一次计算机在全尺寸围棋游戏中战胜了人类专业选手。
所有完美信息博弈都有一个最优值函数，可以通过对搜索树进行b*d(b为可能的走法数量，d为搜索深度)次递归搜索而解决。对围棋来说，这个数值十分巨大，超过了算力可能。可以通过最大最小值算法进行优化，降低计算量。但对围棋来说，剩下的可能性仍然很巨大。另外可以通过随机搜索部分可能的走法降低搜索的广度。Alphago采用一个监督学习的神经网络，用人类专业棋手的棋谱来训练一个分类器，然后用训练的结果初始化强化学习策略网络，后者以自我对弈的方式进行训练，以获胜概率最大化为目标，并用回归的形式得到局面估值。Alphago与监督学习策略网络对战，胜率为80%。与之前最好的围棋软件Pachi对战，胜率85%。最终使用了40个搜索线程，48个CPU和8个GPU。还有分布式版本，使用了1202个CPU和176个GPU。

还有AlphaZero的论文Mastering the game of Go without human knowledge
译文
与AlphaGo相比，AlphaZero最大的特点是不再需要人类的知识，只进行强化学习即可。
专业知识通常是昂贵的，不可靠的，甚至不可获得的。即便可以获得可靠的数据，它们也将成为系统的上限。AlphaZero的另一个特点是其只使用棋盘上黑白棋子的位置作为输入特征，另外，它只使用单一的神经网络。最后，它使用更简单的树搜索。模型的输出为走法概率和一个值。

总结一下强化学习的五子棋棋力不高的原因，首先可能是训练时模拟的方法不行，是用的蒙特卡洛树搜索算法，这个也许用在围棋上挺适合的，但是跟博弈树算法对打时棋力很差。第二，可能也是最重要的原因，训练的次数太少，还不够。
接下来打算看看书，详细了解一下强化学习背后的原理。
程序代码

我发文章的三个地方，欢迎大家在朋友圈等地方分享，欢迎点“在看”。
我的个人博客地址：https://zwdnet.github.io
我的知乎文章地址： https://www.zhihu.com/people/zhao-you-min/posts
我的微信个人订阅号：赵瑜敏的口腔医学学习园地

欢迎打赏！感谢支持！