前言

完整代码见 https://github.com/zong4/AILearning。

零和博弈游戏

正如之前所说，零和博弈中的最优解不是让自己来最多的分，而是让对方拿的分更少，换言之就是保证自己最坏情况下拿的分更多。

如下图，在目前的情况下，假设你（绿色玩家）下一手（上三条线），红色玩家下一手（下九条线），就达到了解空间中的其中一个状态，对应你获得的分数如下。

线是 Path，是 Transition Model。

作为绿色玩家，你应该考虑到红色玩家不会让你得最高的分，只会让你得最少的分。

因此，你此时的三种选择对应的分数分别是 min(4, 8, 5)，min(9, 3, _) 和 min(2, _, _)，那么目前状态下你可以获得的最高分数就是 max(4, $\leq$ 3, $\leq$ 2) = 4。

这也就是 MiniMax 的由来，来实现一下简单的井字棋。

def minimax(board, depth, player):
    if player == 'X':
        best = [-1, -1, -10]
    else:
        best = [-1, -1, 10]
    if depth == 0:
        score = evaluate(board)
        return [-1, -1, score]
    for cell in empty_cells(board):
        x, y = cell[0], cell[1]
        board[x][y] = player
        score = minimax(board, depth - 1, 'O' if player == 'X' else 'X')
        board[x][y] = ' '
        score[0], score[1] = x, y
        if player == 'X':
            if score[2] > best[2]:
                best = score
        else:
            if score[2] < best[2]:
                best = score
    return best

def evaluate(board):
    for row in board:
        if row.count('X') == 3:
            return 10
        if row.count('O') == 3:
            return -10
    for col in range(3):
        if board[0][col] == board[1][col] == board[2][col] == 'X':
            return 10
        if board[0][col] == board[1][col] == board[2][col] == 'O':
            return -10
    if board[0][0] == board[1][1] == board[2][2] == 'X' or board[0][2] == board[1][1] == board[2][0] == 'X':
        return 10
    if board[0][0] == board[1][1] == board[2][2] == 'O' or board[0][2] == board[1][1] == board[2][0] == 'O':
        return -10
    return 0

def empty_cells(board):
    cells = []
    for i in range(3):
        for j in range(3):
            if board[i][j] == ' ':
                cells.append([i, j])
    return cells

def print_board(board):
    ...

最后的输出就会像这样，和棋也是必然的，从第二步 ‘O’ 走中间就可以看出来算法应该没有问题。

-------------
|   |   |   | 
|   |   |   | 
|   |   |   | 
-------------
Player X
-------------
| X |   |   | 
|   |   |   | 
|   |   |   | 
-------------
Player O
-------------
| X |   |   | 
|   | O |   | 
|   |   |   | 
-------------
Player X
-------------
| X | X |   | 
|   | O |   | 
|   |   |   | 
-------------
Player O
-------------
| X | X | O | 
|   | O |   |
|   |   |   |
-------------
Player X
-------------
| X | X | O |
|   | O |   |
| X |   |   |
-------------
Player O
-------------
| X | X | O |
| O | O |   |
| X |   |   |
-------------
Player X
-------------
| X | X | O |
| O | O | X |
| X |   |   |
-------------
Player O
-------------
| X | X | O |
| O | O | X |
| X | O |   |
-------------
Player X
-------------
| X | X | O |
| O | O | X |
| X | O | X |
-------------

ML 的应用

单人游戏

如果考虑寻路的话，一般就是用 ML 来计算 A* 算法中的估价函数。

以现实生活中的导航为例，由于各种未知信息的存在，我们很难准确的给出一个估价函数来预测当前位置到目标位置的成本，因此我们可以在一个小范围内用 BFS 来计算每个点的未来成本，同时给出一些相关的因素。

直线距离	包围盒内是否有桥，如有，桥的长度	直线路径上是否有不可逾越的建筑，如有，占地面积	包围盒内/直线路径上的红绿灯数量	未来成本
…	…	…	…	…

此处只以走路为例，其中包围盒是指当前位置与目标位置形成的包围盒。

通过 ML，就可以挖掘出这些因素是如何影响未来成本的，从而提出一个合适的估价函数。

多人游戏

这就比较常见了，就像 AlphaGo 或者 Dota2 之前职业和 AI 间的比赛都是很好的应用。

那在这种复杂计算中，因为你无法概括出影响结果的因素所以 ML 就不够用了，得用 DL 让 AI 自己玩，让他自己去发掘数据间的联系。

当然了对于上面的寻路也是可以用 DL 的，通过让他自己在地图上随机游走，同时记录路径的特征，来挖掘特征与成本的关系。

这里就不具体给大家展示模型了，如果大家感兴趣的话可以看看这篇文章 https://www.geeksforgeeks.org/alphago-algorithm-in-artificial-intelligence/。

Search篇（二），让AI玩井字棋

前言

零和博弈游戏

ML 的应用

单人游戏

多人游戏