前言

个人认为，这是一道非常经典的 LeetCode Hard 题目，第一次碰到时，感觉觉得如此之精妙，想破脑袋也不会想到使用什么样合适的数据结构去解决这道问题。时隔快5年，在2024年农历新年最后一个工作日，重温下这道经典的题目。

题目描述

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：

你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

原题快速门

说句题外话，以现在卷的程度，是不是很多校招生必会解此题呢，想当年，这样的题目，是不太可能出现在现场笔试题目中的。^.^

解题思路

首先，拿到一道题目后，要分析输入规模，那其实老的题目这点是不太规范的，往往没有给你输入规模的描述，也就少了一些提示。我理解这道题目的输入规模应该如下：
n = len(nums)
1 <= k <= n <= 10^5
那么如果是这样的数据规模，所有O(n^2)的算法可以直接劝退，不用费脑子和精力去想了。接下来，要仔细想下题目的考点是哪一个，或者哪几个组合。显然这道题目非常贴心的告诉你一个考点，滑动窗口，什么是滑动窗口，题目的示例解释的非常清楚了，k表示滑动窗口的长度，窗口往右滑动时，前面的数出窗口，后面的数进入窗口，就是这么个过程。其次，要求窗口内数据的中位数，如果每次暴力的重新计算，那么需要排序，取中间值，显然这个方案的复杂度，最坏情况下会变成O(n^2logn)，应该是过不了testcase，那么这里就要引入数据结构，以O(1)时间计算中位数，如果滑动窗口内的数字保存在一个有序数组，那么计算中位数的复杂度为O(1)就很轻松了，但是删除和添加一个元素到有序数组，操作是O(N)的，那什么数据结构删除和添加一个元素是O(logn)以下的复杂度呢？啊，想到了，类似堆或者红黑树的数据结构。
那怎样使用有序的这些数据结构，实现滑动窗口中位数呢？最巧妙的设计在于，使用两个堆或者有序树的实例，一个维护前半段，一个维护后半段，那么中位数和前半段的最大值和后半段的最小值相关。如果是堆的话，前面半段使用最大堆，后面半段使用最小堆。如下图所示：

这里还有一个细节点，如果k是偶数，那么前半段和后半段的数字数量相等，否则前半段多维护一个数，所以前半段维护数字的数量是 k+1 除以 2 下取整，后半段维护数字的数量是 k 除以 2 下取整。所以当 k 为奇数时，前半段堆最大值就是中位数，否则，需要将两个堆顶的数字取平均。

代码实现

通过上面的分析，思路有了，我实际实现时，使用了Python3，以及SortedList这个有序List（底层实现采用了二分查找和分块算法。在插入元素时，它会将列表分块，并在每个块内部使用二分查找来维护有序性。这样可以在保证列表有序的同时，提高插入和查找元素的效率），效果和堆是类似的，就是优化插入和删除元素的时间复杂度。代码如下：

from sortedcontainers import SortedList

class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    n = len(nums)
    l = (k+1) // 2
    r = k // 2

    L = SortedList(nums[:k])
    R = SortedList()

    def L2R():
        x = L.pop()
        R.add(x)

    def R2L():
        x = R.pop(0)
        L.add(x)

    while len(L) > l:
        L2R()

    ans = []
    if l > r:
        ans.append(L[-1])
    else:
        ans.append((L[-1] + R[0]) / 2)

    for i in range(k, n):
        out_val = nums[i-k]
        if out_val in L:
            L.remove(out_val)
        else:
            R.remove(out_val)
        
        in_val = nums[i]
        if not L or in_val < L[-1]:
            L.add(in_val)
        else:
            R.add(in_val)
        
        if len(L) == l-1:
            R2L()
        elif len(L) == l+1:
            L2R()

        if l > r:
            ans.append(L[-1])
        else:
            ans.append((L[-1] + R[0]) / 2)
    
    return ans

结论

上述实现的代码，时间复杂度O(nlogk)，空间复杂度O(k)。所谓温故知新，最近也有些堆顶堆的题目出现在周赛上面，只是比起以前的题目，现在的题目不会直接把题目考点赤裸裸写在标题里面，需要你自己抽象转换，这步其实非常难，需要你特别熟悉这些题目考点，才能在关键时刻想到如何转换。

引言

强化学习是蛋糕顶上缀着的一颗樱桃，这不是我说的，而是深度学习领域Yann LeCun教授在CoRL 2017大会上做的演讲时提及的。他著名的“蛋糕”理论。“真正的”强化学习好比蛋糕上的樱桃，监督学习好比蛋糕上的糖衣，而蛋糕本身是非监督学习（预测学习）。这里LeCun也表示，这一比喻对做强化学习的兄弟可能不太友好。

认识下“樱桃”

什么是强化学习呢？举个通俗的例子，强化学习就好比一个女猎手（为啥是女猎手，因为我下面用了阿塔兰忒的图像，哈哈）进入了一个迷雾森林，里面充满了各种挑战和奖励。她得自己摸索，判断哪个方向更有“糖果”，哪个方向有“陷阱”。在这个过程中，她会慢慢学会，哦，原来这样做能得到糖果，那样做会掉进陷阱。

不过，这个魔法森林可不是那么容易走的。有时候，她会走错路，掉进陷阱，或者绕着同一个地方转圈圈。这时候，就需要神出手啦，给她点提示，让她知道哪个方向可能更有糖果。这就是我们常说的“智能体（agent）”和“环境（evironment）”之间的互动。

通过这样的摸索和学习，阿塔兰忒最终会走出迷雾森林，这就是强化学习的魅力所在啦！

小姐姐好看吧，也是我用AIGC生成的，嘿嘿。

其实上面简单通俗的语言，就已经把强化学习的原理展露出来了，强化学习（Reinforcement Learning，RL）是一种通过试错来学习的方法。在深度学习中，强化学习用于训练智能体（agent）在环境（evironment）中采取行动，以最大化累积奖励。与监督学习不同，强化学习没有明确的输入输出对，智能体需要通过与环境的交互来学习最佳策略。

深度学习中的强化学习原理涉及到状态（state）、动作（action）、奖励（reward）等核心概念。状态是指环境的当前状态，动作是智能体可以执行的操作，奖励是智能体采取某个动作后获得的正面或负面反馈。智能体在环境中不断尝试不同的动作，根据奖励信号来调整策略，以期获得最大的累积奖励。

深度强化学习在许多应用领域取得了显著的成果，例如自动驾驶、游戏AI、机器人控制等。在实际应用中，智能体需要与环境进行大量的交互来学习最佳策略，这通常需要大量的计算资源和时间。

实践环节

当然只知道上面的原理是不够的，实践出真知，这块怎么去实验呢？我想起了2017年，Deepmind公司发表在nature科学杂志上的AlphaGoZero论文，当时也是通过在围棋比赛上战胜人类冠军而出圈，零人类经验，其自我训练的时间仅为3天，自我对弈的棋局数量为490万盘。但它以100:0的战绩击败前辈。围棋显然我没法找到足够算力支持，但是找个简单的游戏，还是可行的，那么我想到了一个简单好玩的小游戏《flappy bird》，我首先做了一个通过玩家控制的版本：

是不是很熟悉，画面不够精致，但是也够用了，小白球作为小鸟，需要往前飞，又不能碰到白色障碍物。我自己来控制，还是比较难掌控的，很快就会死了。

那么怎么实现AI控制小鸟，就是我要完成的事情。首先上面说的环境（evironment）在这个游戏中就是这个游戏本身，智能体（agent）就是这个小鸟的大脑，控制小鸟的行动。关于环境（evironment），如何抽象状态（state）是关键，我想到有好几种方法：

1. 整个游戏画面作为state，画面的每个像素点就是state，智能体（agent）需要自己理解这个画面意味着什么，障碍物的距离，小鸟的位置等等；
2. 计算某一帧时环境变量，最近的障碍物顶部占据画面高度的比例，小鸟离最近障碍物的距离占画面宽度的比例，小鸟的垂直方向的位置，小鸟的速度等等；

显然不管环境（evironment）如何抽象，智能体（agent）都应该可以学会如何应对某一个具体的state，我在这篇文章中，先尝试了2这个方法，定义了5个变量：

environment[0] = closest.x / (WIN_WIDTH - bird.x) # 最近的障碍物的横坐标 = closest.x，小鸟的横坐标 = bird.x，屏幕的宽度 = WIN_WIDTH
environment[1] = closest.top / WIN_HEIGHT # 最近的障碍物上半部分下沿 = closest.top，屏幕的高度 = WIN_HEIGHT
environment[2] = closest.bottom / WIN_HEIGHT # 最近的障碍物下半部分上沿 = closest.bottom，屏幕的高度 = WIN_HEIGHT
environment[3] = bird.y / WIN_HEIGHT # 小鸟的纵坐标 = bird.y，屏幕的高度 = WIN_HEIGHT
environment[4] = bird.velocity / 10 # 小鸟的往前的速度 = bird.velocity

智能体（agent）简单定义为一个深度神经网络（4层的全连接网络），输入就是上面的evironment数组变量，输出为action，在这个游戏中就是两种行为：1、向上飞；2、保持不动，所以神经网络最终输出为2。

brain = Sequential(
    Linear(5, 16, name='linear1'),
    ReLU(name='relu1'),
    Linear(16, 64, name='linear2'),
    ReLU(name='relu2'),
    Linear(64, 16, name='linear2'),
    ReLU(name='relu3'),
    Linear(16, 2, name='linear2'),
)

那么就来到了最难设计的部分，奖励（reward）如何设计，这里又必须展开一些强化学习训练细节来讲下。强化学习的训练数据，是通过智能体（agent）和环境（evironment）不停的交互，产生的一系列动作（action）概率和一系列奖励（reward）来进行训练的。所以奖励（reward）的设计尤为关键，简单讲就是在迷雾森林中，你要准确的告诉阿塔兰忒往左是陷阱，会被扣分，往右是糖果，是个奖励，会加分。所以在每个具体游戏中，都需要去明确的制定合理的奖励（reward）规则，最后智能体（agent）才会做出利益最大化的动作（action），那么我这里是这样定义的：

for pipe in self.pipes:
    if pipe.hits(bird):
        reward = -450 # 撞到障碍物 pipe，扣450分
        done = True
        break
    elif pipe.avoid(bird):
        reward = 60 # 躲避障碍物 pipe，得60分

if bird.hitBottom():
    reward = -450 # 小鸟撞到底部，扣450分
elif bird.hitTop():
    reward = -450 # 小鸟撞到底部，扣450分

别小看这几句代码，简单但是扣分和得分是会影响智能体（agent）学习的速度的。我这里是调试了不少时间，才完成了整个训练，如果有朋友有兴趣，我可以详细来讲下这部分的训练实现和调试过程，这篇文章里我不进行展开。

结论

展示下最终的效果：

感觉效果还是十分nice的，视频转gif没处理好，感觉gif图的质量一般，我自己看AI玩的效果是真的6，我想下次可以再继续使用图片作为环境（environment），改一下模型结构（可能需要换成resnet等cnn作为backbone），硬train一发，也能得到类似的效果，这个就留作后续的任务，挖个小坑。

导语

好久没更新，从去年十月份来，工作突然很忙，平时剩下的时间用来学习、健身，给到总结写作，没剩下时间。加上人每隔一段时间，都会产生懈怠，就停更个人技术博客近半年。想想去年因为疫情在家办公期间，某种程度上来看，还是很幸福的，上班不用来回坐车，节省下来的时间，可以花在自己感兴趣的事情上，产生一些输出。

OK，言归正传，今天闲来无事，我翻出了女儿去年玩过的小游戏，她妈妈给她买的这类智力小游戏有不少，很偶尔会瞧见她们娘俩一起玩，估计是不太感兴趣。今天这款游戏，我小时候没见过，是一个新的小游戏，我就起一个应景的名字，《兔兔大战小狐狸》，今年是兔年，兔子要逃脱小狐狸的围追堵截，逃到安全的小土坑里，躲起来。

游戏介绍

游戏棋盘是一个5*5的方盘，左上、右上、左下、右下以及正中间有5个小土坑，如果棋盘上所有的兔子，都在土坑待着，就完成了任务。具体规则，我不码字，看如下说明：

如上面所说，游戏内置了60个关卡（因为随便摆放，是不一定能完成任务的），也有最少步骤的解答，我自己尝试玩了几个简单关卡（最少10步以内可以完成的），貌似还挺简单的。

然后，我翻到了关卡的最后4个关卡，哇，一下子震惊了，好难，最后一关官方解答，需要87步完成任务。

一些疑问

小朋友如果自己完成前面简单、中等题目，已经很不容易了。至于困难、专家级别的题目，如果能完成，小脑瓜不是一般聪明，非常了不起。但我想了下，官方说最后一题87步是最少步骤，这个怎么证明官方没错呢？或者有更少步骤的解法？我心想，是不是写个算法求解，看看是否是对的。

求解过程

首先是需要有个建模过程，棋盘规格是5*5方盘，上面有25个位置，5个位置是土坑。可以放置的角色是小狐狸、兔兔和蘑菇。兔兔和蘑菇都只占用一个格子，狐狸占用两个格子，还有头和尾巴，但我仔细想了下，狐狸头和尾巴，其实在算法中不需要区分，只需要区分狐狸是竖着还是横着放置的，你可以理解为狐狸的头总是在左边或者上方，尾巴在右边或者下方。这样对算法实现更简单。

比如60题，我会使用5个字符串表示5行，

"...X."
"FF.R."
"..X.R"
"X...."
"...R."

字符X表示蘑菇，F表示小狐狸（头或者尾），R表示小兔兔，最后.表示空位。

算法显然就是搜索算法，DFS还是BFS呢？我先用DFS实现了半天，会TLE，根本算不出最少步骤的解法。我后来想了下，最少步骤的解法确实不太适合DFS，因为DFS可能需要搜索完所有的解法空间（也可能我剪枝还不够），所以无法算出最少步骤。在DFS上，我其实花了不少时间优化，这个题目比刷题难，因为是自己出给自己的，也没有什么参考答案，都只能自己去想，如何建模和实现搜索算法，总之，自己试了半天，也不work。

OK，那么我就来试下BFS搜索，大概的逻辑步骤如下：

1. 建立一个队列，将游戏初始棋盘局面放到队列中；
2. 一一取出当前局面，评估可能变为的下一个局面；
3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
6. 将2～5变化的到的局面插入队列（下一轮）；
7. 遍历完上一轮队列，步骤+1；
8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；

代码实现：

int smartGame(vector<string> board) {
    int n = board.size();

    // 判断游戏是否结束
    set<vector<int>> finish_pos = {{0, 0}, {0, n-1}, {n-1, 0}, {n-1, n-1}, {n/2, n/2}};
    function<bool(vector<vector<int>>)> isFinished = [&](vector<vector<int>> ani_pos) -> bool {
        int n = ani_pos.size();

        for (int i = 0; i < n; ++i) {
            if (ani_pos[i][2] != -1) continue;
            vector<int> pos = {ani_pos[i][0], ani_pos[i][1]};
            if (finish_pos.find(pos) == finish_pos.end())
                return false;
        }

        return true;
    };

    // 分析棋盘局面，哪些可能移动的小兔兔、小狐狸所在位置
    function<void(vector<string>, vector<vector<int>>&)> analyzeBoard = [&](vector<string> board, vector<vector<int>>& ani_pos) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'X') {
                    continue;
                } else if (board[i][j] == '.') {
                    continue;
                } else if (board[i][j] == 'F') {
                    if ((i == 0 || board[i - 1][j] != 'F') && (i < n - 1 && board[i + 1][j] == 'F')) {
                        // vertical fox
                        ani_pos.push_back({i, j, 1});
                    } else if ((j == 0 || board[i][j - 1] != 'F') && (j < n - 1 && board[i][j + 1] == 'F')) {
                        // horizontal fox
                        ani_pos.push_back({i, j, 2});
                    }
                } else if (board[i][j] == 'R') {
                    ani_pos.push_back({i, j, -1});
                }
            }
        }
    };

    // 棋盘局面上某个小兔兔、小狐狸，做出某个移动后，返回新的局面
    function<vector<string>(vector<string>, vector<int>, vector<int>)> applyBoard = [&] (vector<string> board, vector<int> pos, vector<int> move) -> vector<string> {
        if (pos[2] == -1) {
            board[pos[0]][pos[1]] = '.';
            board[pos[0]+move[0]][pos[1]+move[1]] = 'R';
        } else {
            if (pos[2] == 1) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]+1][pos[1]] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]+1][pos[1]+move[1]] = 'F';
            } else if (pos[2] == 2) {
                board[pos[0]][pos[1]] = '.';
                board[pos[0]][pos[1]+1] = '.';

                board[pos[0]+move[0]][pos[1]+move[1]] = 'F';
                board[pos[0]+move[0]][pos[1]+move[1]+1] = 'F';
            }
        }

        return board;
    };

    // 分析棋盘局面，可能移动的小兔兔、小狐狸，能做出哪些移动
    function<vector<vector<int>>(vector<string>, vector<int>)> nextMoves = [&] (vector<string> board, vector<int> pos) -> vector<vector<int>> {
        vector<vector<int>> moves;

        if (pos[2] == -1) {
            // up
            vector<int> t = pos;
            while (t[0] >= 0 && board[t[0]][t[1]] != '.') t[0] -= 1;
            if (t[0] >= 0 && board[t[0]][t[1]] == '.' && t[0] < pos[0]-1) {
                moves.push_back({t[0]-pos[0], 0});
            }
            // down
            t = pos;
            while (t[0] < n && board[t[0]][t[1]] != '.') t[0] += 1;
            if (t[0] < n && board[t[0]][t[1]] == '.' && t[0] > pos[0]+1) {
                moves.push_back({t[0]-pos[0],0});
            }
            // left
            t = pos;
            while (t[1] >= 0 && board[t[0]][t[1]] != '.') t[1] -= 1;
            if (t[1] >= 0 && board[t[0]][t[1]] == '.' && t[1] < pos[1]-1) {
                moves.push_back({0, t[1]-pos[1]});
            }
            // right
            t = pos;
            while (t[1] < n && board[t[0]][t[1]] != '.') t[1] += 1;
            if (t[1] < n && board[t[0]][t[1]] == '.' && t[1] > pos[1]+1) {
                moves.push_back({0, t[1]-pos[1]});
            }
        } else if (pos.size() == 3) {
            if (pos[2] == 1) {
                // up
                if (pos[0] > 0 && board[pos[0]-1][pos[1]] == '.') {
                    moves.push_back({-1, 0});
                }
                // down
                if (pos[0] < n-2 && board[pos[0]+2][pos[1]] == '.') {
                    moves.push_back({1, 0});
                }
            } else if (pos[2] == 2) {
                // left
                if (pos[1] > 0 && board[pos[0]][pos[1]-1] == '.') {
                    moves.push_back({0, -1});
                }
                // right
                if (pos[1] < n-2 && board[pos[0]][pos[1]+2] == '.') {
                    moves.push_back({0, 1});
                }
            }
        }

        return moves;
    };

    // 棋盘局面的签名，用作去重
    function<string(vector<string>)> signature = [&](vector<string> board) -> string {
        string r;
        for (auto l : board) {
            r += l;
        }
        return r;
    };

    // 1. 初始棋盘局面，入到队列
    queue<vector<string>> q;
    unordered_set<string> seen;
    q.push(board);
    seen.insert(signature(board));

    int ans = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size --) {
            // 2. 一一取出当前局面，评估可能变为的下一个局面；
            vector<string> t = q.front();
            q.pop();
            vector<vector<int>> ani_pos;

            // 3. 评估当前局面可能可以行动的小兔兔、小狐狸坐标；
            analyzeBoard(t, ani_pos);

            if (isFinished(ani_pos)) {
                return ans;
            }

            // 4. 一一取出小兔兔、小狐狸，评估她们可能的移动到的位置；
            for (auto pos: ani_pos) {
                vector<vector<int>> moves = nextMoves(t, pos);
                for (int i = 0; i < moves.size(); ++i) {
                    vector<int> move = moves[i];
                    // 5. 通过改变小兔兔、小狐狸位置，得到下一个局面；
                    vector<string> nxtBoard = applyBoard(t, pos, move);
                    string sig = signature(nxtBoard);
                    if (seen.find(sig) == seen.end()) {
                        // 6. 将2～5变化的到的局面插入队列（下一轮）；
                        q.push(nxtBoard);
                        seen.insert(sig);
                    }
                }
            }
        }

        // 7. 遍历完上一轮队列，步骤+1；
        // 8. 把下一轮队列变为需要遍历的当前队列，重复2～7步骤；
        ans++;
    }

    return -1;
}

还要强调一点优化，我用了一个unordered_set去做棋盘局面去重，曾经看见过的局面，就不需要再去考虑了，因为即使从该局面出发有解，肯定也不会比之前出现时更优的，这个很好理解吧。

结论

最终通过算法验证，最后4题的最优解确实和官方的步骤数量一样，并且我后来记录了最优解算法的到的步骤，虽然有些顺序和官方题解不一致，我仔细比对了下，仅仅是某些步骤中，可以交换顺序而已，不是计算错误。别看是思路很简单，就是BFS搜索算法，但是面对一个没有参考答案的问题，建模、优化和调试，哪一样都不轻松，很开心，今天可以完成任务，并且写下这篇文章，明天继续加油～

导语

最近在学python数据处理的几个常用库，分别是numpy、matplotlib和pandas。这几个库应该是python数据处理的第三方神器库，学了一招图像手绘风格处理，非常有意思，记录下来。

图像手绘风格

手绘风格示例：

第二幅就是有手绘的感觉，当然是基于第一章图片处理得到的。手绘风格可以总结为以下几点：

• 黑白灰色
• 边界线条较重
• 相邻的像素，如果是相同或者相近色彩趋于白色
• 略有光源效果

具体如何通过程序实现呢？接下来就来逐一介绍下。

梯度的重构

利用像素之间的梯度值和虚拟深度值对图像进行重构，根据灰度变换来模拟人类视觉的明暗程度。代码如下：

import numpy as np
from PIL import Image

a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float')

depth = 10.
grad = np.gradient(a)
grad_x, grad_y = grad
grad_x = grad_x*depth/100.
grad_y = grad_y*depth/100.

下面这行代码是通过pillow库读取原先图像，RGB值转为灰度值。

a = np.asarray(Image.open('xxx.jpeg').convert('L')).astype('float')

这几行代码是计算灰度图像的像素间梯度，并且根据虚拟深度重构梯度值，depth初始化为10，depth取值0～100。

depth = 10.
grad = np.gradient(a)
grad_x, grad_y = grad
grad_x = grad_x*depth/100.
grad_y = grad_y*depth/100.

光源效果

根据灰度变化来模拟人类视觉的远近程度。

• 设计一个位于图像斜上方的虚拟光源
• 光源相对于图像的俯视角为Elevation，方位角为Azimuth
• 建立光源对各个点梯度值的影响函数
• 运算各个点的新像素值

代码如下：

vec_el = np.pi/2.2                  # 光源的俯视角度，弧度值
vec_az = np.pi/4.                   # 光源的方位角度，弧度值
dx = np.cos(vec_el)*np.cos(vec_az)  # 光源对x轴的影响
dy = np.cos(vec_el)*np.sin(vec_az)  # 光源对y轴的影响
dz = np.sin(vec_el)                 # 光源对z轴的影响

A = np.sqrt(grad_x**2 + grad_y**2 + 1.)     # 光源归一化
uni_x = grad_x/A
uni_y = grad_y/A
uni_z = 1./A
b = 255*(dx*uni_x+dy*uni_y+dz*uni_z)

最后，对像素值进行裁剪至0～255，防止越界。

b = b.clip(0, 255)
im = Image.fromarray(b.astype('uint8'))
im.save('xxxHD.jpeg')

最后

程序虽然小，效果还是比较有意思的，我给女儿看了，她说你画画不是很丑的吗，为啥画的这么好？哈哈，我和她说，这是计算机处理的，不是我手画的，小小的年纪充满大大的问号。

其实，这里最重要的是对图像灰度值计算梯度，这是Computer Vision里面传统图像处理的关键，CV相关的技术，由于可以可视化，实现之后，还是比较有意思的。

导语

作为80后，小时候一定玩过一款经典游戏，俄罗斯方块，英文名称Tetris。玩的画面在脑海中已是“上古”时期的事情，但也并不陌生，因为刷视频时，偶尔还能看到顶尖世界高手对决，他们玩的俄罗斯方块难度极大，游戏模式是对决，比谁的分数高，有些比赛到最后不仅自己消砖块得分，而且还可以通过得分不停给对手制造麻烦。

看到鹅厂组织的一次极客挑战赛，主题就是俄罗斯方块游戏，当然游戏名称叫“鹅”罗斯方块，蛮鹅厂风格的，可可爱爱。

我比较感兴趣，当时也报名参加了，最后是在2000+入场选手排名在9位，比赛结束后，我又花了点时间调试了自己的算法参数，最终比赛分数可以刷进TOP3。谨以此文，记录自己的所思所想。

如何活着

第一步想到的是，如何“活着”，就和当前经济形势下，各行各业都得考虑先“活着”，能不能得到高分其次，先得“不死”。

我自己写了一个俄罗斯方块的游戏界面，和传统俄罗斯方块游戏一样，如何拼搭这些小图形，让高度不超过游戏规定的高度，满行就会消除，消除的行数有4种情况1行、2行、3行和4行。针对如何活着的俄罗斯方块AI算法比较多了，全网比较有名的是Pierre Dellacherie算法。我这里搜索到一篇El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm，大家可以参考下。

首先，分析下俄罗斯方块中方块的种类，一共有7种图形：

上面图中有7种不同的形状，我在代码里面的表示为坐标法，以(0, 0)为原点，标示周围那几个点对应图形需要占用。

BrickShapes = [
    # I
    [[[-2, 0], [-1, 0], [0, 0], [1, 0]],
     [[0, -1], [0, 0], [0, 1], [0, 2]]],

    # L
    [[[-2, 0], [-1, 0], [0, 0], [0, 1]],
     [[0, 0], [0, 1], [0, 2], [1, 0]],
     [[0, -1], [0, 0], [1, 0], [2, 0]],
     [[-1, 0], [0, -2], [0, -1], [0, 0]]],

    # J
    [[[-2, 0], [-1, 0], [0, -1], [0, 0]],
     [[-1, 0], [0, 0], [0, 1], [0, 2]],
     [[0, 0], [0, 1], [1, 0], [2, 0]],
     [[0, -2], [0, -1], [0, 0], [1, 0]]],

    # T
    [[[0, -1], [0, 0], [0, 1], [1, 0]],
     [[-1, 0], [0, -1], [0, 0], [1, 0]],
     [[-1, 0], [0, -1], [0, 0], [0, 1]],
     [[-1, 0], [0, 0], [0, 1], [1, 0]]],

    # O
    [[[-1, 0], [-1, 1], [0, 0], [0, 1]]],

    # S
    [[[-1, 0], [-1, 1], [0, -1], [0, 0]],
     [[-1, -1], [0, -1], [0, 0], [1, 0]]],

    # Z
    [[[-1, -1], [-1, 0], [0, 0], [0, 1]],
     [[-1, 0], [0, -1], [0, 0], [1, -1]]]
]

比如竖棍“I”的图形，有两种rotation，所以有两组坐标的标示方式，其他图形类似，只不过rotation数量不同：

    # I, two rotations
    [[[-2, 0], [-1, 0], [0, 0], [1, 0]],
     [[0, -1], [0, 0], [0, 1], [0, 2]]],

El-Tetris算法是传统AI人工智能，不要因为人工智能，就觉得很复杂，其实不论传统的AI算法还是目前深度学习的人工算法，一般都不会很复杂，深度学习AI算法不在此文讨论范围。基本上传统AI算法就是列举所有的可能性，通过计算预先建模的公式，评估最优秀的一个局面，做出选择，一直循环往复，直到游戏结束。我们看下El-Tetris算法的公式：
f(x) = b0x0+b1x1+b2x2...bnxn
其中x0,x1,x2...xn都是一些特征，b0,b1,b2...bn是一些系数（通过数学方法或者机器学习方法等手段推算出的经验值），对应特征和系数相乘相加之后，得到的就是当前局面+此选择的局面评估分数，是不是很简单，看上去是一个线性公式，但是效果出奇的好，原因还是在于每一个特征x的合理性以及系数b的合理性。

系数b不需要我们实现，就是一组常数字，作者说是通过particle swarm optimization寻找到的，具体怎么找，我也不太清楚，先拿来用吧。

另外要提一下，算法可以通常可以考虑当前图形+下一个图形，也可以只考虑当前图形，据说效果差不多，我这里只考虑当前图形的所有可能的操作，每一个图形出来，其实只需要考虑图形放置的position和rotation两个变量。所以整体的流程：

while the game is not over:
  examine piece given
  find the best move possible (an rotation and a position)
  play piece
repeat

上面铺垫这么多，那么一共建模了几种特征呢？一共是6种，如下：

• Landing Height: The height where the piece is put (= the height of the column + (the height of the piece / 2)).
• Rows eliminated: The number of rows eliminated.
• Row Transitions: The total number of row transitions. A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa.
• Column Transitions: The total number of column transitions. A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa.
• Number of Holes: A hole is an empty cell that has at least one filled cell above it in the same column.
• Well Sums: A well is a succession of empty cells such that their left cells and right cells are both filled.

Landing Height和Rows eliminated比较好理解，其他对着下图解释下：

Row Transitions总数是16，最底部一行为2，依次往上2、2、2、2、4、2，注意我这里处理为左右边界外是被占据的，所以倒数第四行靠最左边有个空，算存在一次row transition，另外空行我没算（我猜测也可以计算row transition，不影响最后结果）。
Column Transitions总数是26，如果理解了Row Transitions，这个计算方法是一样的。
Number of Holes总数是4，看下上图，应该知道什么叫“洞”，被封闭了的空单元格。
Well Sums总数是5，如果左右两边单元格被占，顶上又没有被封闭，可以算作一个“井”格子，第一列一个单元格，左边界外算占据，右边也被占据，所以也算作“井”格子，深度为1，第三列就一个单元格，井深度为1，第六列有2个空单元格，井深度和为1+1+1+2。这个比较难理解，多看几遍。

对应的系数如下：
Landing Height = -4.500158825082766
Rows eliminated = 3.4181268101392694
Row Transitions = -3.2178882868487753
Column Transitions = -9.348695305445199
Number of Holes = -7.899265427351652
Well Sums = -3.3855972247263626

计算代码如下：

def find_best_play(current_piece, grid):
    if current_piece.y < 0:
        False, 0, 0

    rotations = len(current_piece.shape)
    x_moves = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
    rotation = 0
    x_move = 0
    best_play_score = float("-inf")
    for i in range(rotations):
        for j in x_moves:
            candidate_piece = copy.deepcopy(current_piece)
            candidate_grid = copy.deepcopy(grid)
            candidate_piece.rotation += i
            candidate_piece.x += j

            if not (valid_space(candidate_piece, candidate_grid)):
                continue

            valid, score = evaluate(candidate_piece, candidate_grid)
            if valid and score > best_play_score:
                best_play_score = score
                rotation = i
                x_move = j

    return True, rotation, x_move


def evaluate(current_piece, grid):
    while True:
        current_piece.y += 1
        if not (valid_space(current_piece, grid)) and current_piece.y > 0:
            current_piece.y -= 1
            break

    shape_pos = convert_shape_format(current_piece)

    for i in range(len(shape_pos)):
        x, y = shape_pos[i]
        if y > -1:
            grid[y][x] = current_piece.color

    heights_points = (20 - current_piece.y + current_piece.height[current_piece.rotation % len(current_piece.height)]) * float(-4.500158825082766)
    rows_removed = get_rows_removed(grid) * float(6.4181268101392694)
    rows_transitions = get_row_transitions(grid) * float(-3.2178882868487753)
    cols_transitions = get_col_transitions(grid) * float(-9.348695305445199)
    num_of_holes = get_num_of_holes(grid) * float(-14.899265427351652)
    wells = get_well_sums(grid) * float(-6.3855972247263626)

    return True, heights_points + rows_removed + rows_transitions + cols_transitions + num_of_holes + wells

find_best_play列举所有可能的操作，evaluate就是评估局面的分数，其中几个计算特征值的函数：

def get_row_transitions(grid):
    rows = len(grid)
    cols = len(grid[0])
    transitions = 0
    last_pos = True
    for i in range(rows - 1, -1, -1):
        if is_empty_row(grid[i]):
            continue

        for j in range(cols):
            if (grid[i][j] in brick.SHAPES_COLORS) != last_pos:
                transitions += 1

            last_pos = (grid[i][j] in brick.SHAPES_COLORS)

        if not last_pos:
            transitions += 1

        last_pos = True

    return transitions

def get_col_transitions(grid):
    rows = len(grid)
    cols = len(grid[0])
    transitions = 0
    last_pos = True
    for j in range(cols):
        for i in range(rows - 1, -1, -1):
            if (grid[i][j] in brick.SHAPES_COLORS) != last_pos:
                transitions += 1

            last_pos = (grid[i][j] in brick.SHAPES_COLORS)

        if not last_pos:
            transitions += 1

        last_pos = True

    return transitions

def get_num_of_holes(grid):
    rows = len(grid)
    cols = len(grid[0])
    holes = 0
    previous_row_holes = [0 for _ in range(cols)]
    for i in range(rows)[1:]:
        for j in range(cols):
            if grid[i][j] == (0, 0, 0) and (grid[i-1][j] != (0, 0, 0) or previous_row_holes[j] == 1):
                holes += 1
                previous_row_holes[j] = 1

    return holes

def get_well_sums(grid):
    rows = len(grid)
    cols = len(grid[0])
    well_sums = 0

    # Check for well cells in the "inner columns" of the board.
    # "Inner columns" are the columns that aren't touching the edge of the board.
    for j in range(cols-1)[1:]:
        for i in range(rows - 1, -1, -1):
            if grid[i][j] == (0, 0, 0) and grid[i][j-1] != (0, 0, 0) and grid[i][j+1] != (0, 0, 0):
                well_sums += 1

                k = i+1
                while k < rows:
                    if grid[k][j] == (0, 0, 0):
                        well_sums += 1
                    else:
                        break
                    k += 1

    # Check for well cells in the leftmost column of the board.
    for i in range(rows - 1, -1, -1):
        if grid[i][0] == (0, 0, 0) and grid[i][8] != (0, 0, 0):
            well_sums += 1

            k = i + 1
            while k < rows:
                if grid[k][0] == (0, 0, 0):
                    well_sums += 1
                else:
                    break
                k += 1

    # Check for well cells in the rightmost column of the board.
    for i in range(rows - 1, -1, -1):
        if grid[i][cols-1] == (0, 0, 0) and grid[i][cols-2] != (0, 0, 0):
            well_sums += 1

            k = i + 1
            while k < rows:
                if grid[k][cols-1] == (0, 0, 0):
                    well_sums += 1
                else:
                    break
                k += 1

    return well_sums

完成后的效果特别好，尽管一度高度和累积的形状不太好看：

但是AI会慢慢控制住局面，变成如下局面：

我尝试自己手动玩了下，鹅厂给出的图形顺序，还真的不是很好玩，稍不小心就挂了，因为图形的占比不是均分的，S型和Z型比较多，过了一会，貌似EI-Teris算法也会“顶”不住。。。

仔细看了下方块图形生成的代码，每个方块图形的生成概率不等，比如长条“I”型的生成概率才2/29：

def getShapeIndex(self):
    weight = self.rand_number % 29
    shape_index = 0

    if 0 <= weight <= 1:
        shape_index = 0
    elif 1 < weight <= 4:
        shape_index = 1
    elif 4 < weight <= 7:
        shape_index = 2
    elif 7 < weight <= 11:
        shape_index = 3
    elif 11 < weight <= 16:
        shape_index = 4
    elif 16 < weight <= 22:
        shape_index = 5
    else:
        shape_index = 6

    return shape_index

所以正常的俄罗斯方块AI算法远远不够，调整了一下估值函数的系数（针对掉落方块形状分布不均的情况），我发现最多也只能获得20w分不到（方块图形数量仅仅10000块），离当天的第一名130w+分，差距很大。

追求“财富”

仔细理解下鹅罗斯方块的积分规则，“富贵险中求”：

由于就仅仅有10000块方块，我考虑使用动态规划，将所有可能的局面求出，再计算能够累积得到的最大分数，当然，由于状态总数有2^200之多，保存所有的局面不现实，必须要舍去大部分的局面。一开始的想法是：在扩展的过程中，按照安全性估价函数筛查出固定数目状态进行保存（目标是局面安全），经过固定步数，再对分数进行贪心，取出唯一最高分状态继续扩展（目标是高分），这样反反复复尝试，不行，因为太早贪心，容易丢失掉“潜力”的局面，后面会得到高分局面，所以尽可能保留安全局面，所谓“留得青山在，不怕没柴烧”，直接把分数的因素引入估价函数，不再额外对做分数做贪心。

evaluation = board_evaluator.Evaluate(k) - v.score * self.score_weight

其中board_evaluator.Evaluate(k)中，k就是当前局面，self.score_weight我手动尝试出来的取值为1/38，Evaluate函数就是：

PARAMS = [
    -1,
    3.2178882868487753,
    9.348695305445199,
    7.899265427351652
    # 3.3855972247263626
]


def Evaluate(board):
    return PARAMS[0] * board.getCount() + PARAMS[1] * board.getRowTransition() + \
           PARAMS[2] * board.getColTransition() + PARAMS[3] * board.getNumberOfHoles()

其中Landing Height和Well sums两个特征不再评估函数内，甚至我觉得“井”的局面对取得高分是有益的（没尝试加回来，可以试试看），另外增加了当前局面下的被占据了的格子总数和当前可以得到的分数和。靠着这个估值函数，对于当前方块放置完成的局面只保留100个最好的（评估分数最高的），一直迭代到10000个，取出得分最高的局面，还原出所有的操作列表，在本地模拟AI的操作，效果特别棒，AI会自动的留一条缝，尝试将其他空间填满填好，比赛期间取得了85w的分数，赛后我手动调试后，分数涨到125w左右，效果图如下所示：

总结

总结的文章看上去很简单，其实过程特别煎熬，反反复复在本地尝试，实现过程也有不少小问题，调试起来也很麻烦，有怀疑、有纠结、有确定，到最后的效果符合预期，真的不容易，比如为啥score_weight要取1/38，估值函数的整体建模，为什么要减除这个特征，要加另外一个特征，怎么剪枝。整个比赛期间，我只取得了85w的分数，赛后再经过调试得到了125w的分数，就叫此算法为“富贵险中求”算法，可以使用此算法的前提是必须知道方块完整的掉落顺序。