导语

最近在学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的分数，就叫此算法为“富贵险中求”算法，可以使用此算法的前提是必须知道方块完整的掉落顺序。

导语

上周记录了极客挑战赛的情况，其中一道非常有趣的题，本周继续，本周题目也是游戏，大概的游戏形式是横版闯关类的：

还是借用网上游戏的图片说明下大概的意思，玩家一个英雄，进入一个场景（横版的），会有一个（每个场景仅一个）怪物与玩家英雄对抗，玩家有血条，有蓝量，6个技能（其中1个技能是升级其他5个技能），然后需要做的就是打到场景中的怪物，冲往下一个关卡。

摸索

有了之前游戏的经验之后，我知道了，上来就是一顿摸索，其实和上周说的游戏类似，客户端是个状态机，英雄有血量和蓝量，每次和怪物对抗之后，客户端会上传一堆指令到服务端，服务端重放这一堆指令，看最终的英雄状态和怪物状态是否合法，是不是英雄还活着，怪物已经死亡，然后就可以进行到下一关。

一共是有9个怪物，一旦进入游戏，可以得到所有怪物的属性：

bosses = [
    {
        "Name": "小壶守卫",
        "Model": "Boss_ball",
        "Hp": 396,
        "Skill1_harm": 63,
        "Skill2_harm": 71,
        "Award_hp": 133,
        "Award_mp": 1695,
        "New_star": 0
    },
    {
        "Name": "苇名二心",
        "Model": "Boss_sword",
        "Hp": 532,
        "Skill1_harm": 59,
        "Skill2_harm": 89,
        "Award_hp": 157,
        "Award_mp": 1678,
        "New_star": 0
    },
    {
        "Name": "古达",
        "Model": "Boss_guda",
        "Hp": 643,
        "Skill1_harm": 57,
        "Skill2_harm": 97,
        "Award_hp": 142,
        "Award_mp": 1362,
        "New_star": 1
    },
    {
        "Name": "中壶守卫",
        "Model": "Boss_ball",
        "Hp": 668,
        "Skill1_harm": 59,
        "Skill2_harm": 67,
        "Award_hp": 178,
        "Award_mp": 1458,
        "New_star": 0
    },
    {
        "Name": "苇名三心",
        "Model": "Boss_sword",
        "Hp": 687,
        "Skill1_harm": 31,
        "Skill2_harm": 101,
        "Award_hp": 212,
        "Award_mp": 2659,
        "New_star": 0
    },
    {
        "Name": "黑古达",
        "Model": "Boss_guda",
        "Hp": 852,
        "Skill1_harm": 77,
        "Skill2_harm": 91,
        "Award_hp": 132,
        "Award_mp": 4157,
        "New_star": 2
    },
    {
        "Name": "大壶守卫",
        "Model": "Boss_ball",
        "Hp": 1502,
        "Skill1_harm": 71,
        "Skill2_harm": 105,
        "Award_hp": 154,
        "Award_mp": 3089,
        "New_star": 0
    },
    {
        "Name": "苇名零心",
        "Model": "Boss_sword",
        "Hp": 1611,
        "Skill1_harm": 97,
        "Skill2_harm": 127,
        "Award_hp": 189,
        "Award_mp": 6493,
        "New_star": 0
    },
    {
        "Name": "超黑古达",
        "Model": "Boss_guda",
        "Hp": 2988,
        "Skill1_harm": 101,
        "Skill2_harm": 153,
        "Award_hp": 0,
        "Award_mp": 0,
        "New_star": 3
    }
]

简单讲一下“Award_hp”和“Award_mp”这两个值，就是你击败怪物后，得到的奖励，可以分别增加对应的hp和mp，其他字段就是对应意思了。

hero = {
    "Hp": 520,
    "Mp": 1806,
    "Power": {
        "Cost_mp": 233,
        "Attack_increase": [
            {
                "skill_i": 1,
                "skill_j": 1,
                "skill_k": 1,
                "skill_l": 1,
                "skill_u": 1
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 4,
                "skill_u": 5
            }
        ]
    },
    "Skills": {
        "skill_i": {
            "Cost_mp": 489,
            "Attack_hp": 187
        },
        "skill_j": {
            "Cost_mp": 134,
            "Attack_hp": 50
        },
        "skill_k": {
            "Cost_mp": 186,
            "Attack_hp": 70
        },
        "skill_l": {
            "Cost_mp": 251,
            "Attack_hp": 95
        },
        "skill_u": {
            "Cost_mp": 352,
            "Attack_hp": 134
        }
    }
}

经过几次手打的尝试之后，客户端上传的指令，类似["skill", "skill_j"]，["attack", "Hero", "Boss", "skill_j"]这两条连续指令，表示英雄发动了技能skill_j，并且命中了怪物，反过来，怪物击中英雄也有类似连续指令，不展示了。手打很容易通过前三关，后面几关越来越难，手残党直接放弃。

思考一番之后，其实客户端只需要传送英雄攻击怪物的动作序列即可，不需要构造英雄“挨打”的序列，嘻嘻～所以问题转换为英雄的蓝量够不够击败怪物。如果不存在技能升级，那么就是一个背包问题，算是一个无限背包问题（实际上整体问题属于一个有限背包问题，因为技能其实是有施放次数上限，这里计算背包问题时，先不考虑）。

确定了是无限背包问题，也有两条建模路径：

• 确定的蓝量能够产生最大的耗血量；
• 确定的血量用最少多少蓝量可以完成；

OK，二选一，上来我选择了第一条，很快能写出背包问题代码：

# W指的是最大的蓝量，w是技能耗的蓝量树组，v是技能产生的伤害
# 最后dp返回的数组，每一个元素有两位[x, y]，x表示产生的最大伤害，y表示达到这个最大伤害使用的技能序号
def knapsack01D(w, v, W):
    n = len(w)
    dp = []
    for i in range(W+1):
        dp.append([0,-1])

    for i in range(n):
        knapsackComplete(dp, w[i], v[i], i)

def knapsackComplete(dp, w, v, i):
    W = len(dp)
    j = w
    while j < W:
        if dp[j-w][0]+v > dp[j][0]:
            dp[j][2] = i
        dp[j][0] = max(dp[j-w][0]+v, dp[j][0])
        j += 1

虽然背包代码写得很轻松，但是后面就陷入了一个死胡同，我拿着这个函数，疯狂尝试，怎么试呢？前面1～3关我不升级技能，看能不能通过，发现不行，那升一级，发现可以通关，升两级不行，那我就升一级，然后到了4～6关，我再用此策略，结果发现弄来弄去，只能通过4～6关，获得第二颗星星的奖励，死活打不过7～9关怪物。

问题建模

当我要放弃的时候，我看了一眼答案提示，答案没有代码实现哈，但其中有一句话点醒了我：

设状态 dpAi 表示强化i次的情况下，伤害j血量的最小蓝耗，dpBi 表示强化i次的情况下，完成j这个boss之后剩余的最大蓝耗，然后两个dp依次计算，就可以得到最终策略了。

这句话得多读几遍，也就是说，我们可以把所有升级后的对应血量蓝耗情况都计算出来，然后还得多算一个矩阵，表示强化了i次情况下，击败第j个怪物之后，剩余的最大蓝耗，首先上面我算的蓝耗和血量的背包问题，反过来建模，通过确定血量耗最少蓝的结果，去计算击败某个怪物之后剩余蓝量。

想清楚整体模型之后，动手写了代码，确定血量消耗最小蓝耗问题，也不是特别难，基于这个结果，去构建完成j这个boss之后剩余的最大蓝耗，稍微多想下，也可以写出来，代码大致如下：

# 根据hero和boss的数组初始化背包问题相对应的值
# dp最后保存的是血量j对应消耗最小蓝耗
# dp2表示哪个技能实施后达到的最小蓝耗（就是去往下一个最佳状态，需要施放的技能）
v = [489, 134, 186, 251, 352]
w = [187, 50, 70, 95, 134]
ws = [[]] * 11
W = 2988
dp = []
dp2 = []
skills = ["skill_i", "skill_j", "skill_k", "skill_l", "skill_u"]
for i in range(11):
    for j in range(len(skills)):
        w[j] = w[j] + hero['Power']['Attack_increase'][i][skills[j]]
    ws[i] = copy.deepcopy(w)
    t1, t2 = knapsack01D2(ws[i], v, W)
    dp.append(copy.deepcopy(t1))
    dp2.append(copy.deepcopy(t2))

# matrix[i][j]表示i次强化后，怪物j被打败之后，剩余的蓝量
matrix = []
for i in range(11):
    matrix.append([-1]*9)

bosses_hp = [396, 532, 643, 668, 687, 852, 1502, 1611, 2988]
bosses_award = [1695, 1678, 1362, 1458, 2659, 4157, 3089, 6493, 0]
initial = 1806-134

for i in range(11):
    if initial >= (i+1)*233+dp[i][bosses_hp[0]]:
        matrix[i][0] = initial-(i+1)*233-dp[i][bosses_hp[0]]

    if matrix[i][0] >= 0:
        matrix[i][0] += bosses_award[0]

for i in range(9)[1:]:
    if matrix[0][i-1] >= dp[0][bosses_hp[i]]:
        matrix[0][i] = matrix[0][i-1] - dp[0][bosses_hp[i]]

    if matrix[0][i] >= 0:
        matrix[0][i] += bosses_award[i]

print(dp[6][1502])

tracing = [[]]*9
for j in range(9)[1:]:
    r = 0
    for i in range(11)[1:]:
        for k in range(i+1):
            if matrix[k][j-1] >= 233*(i-k) and matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]] >= 0:
                matrix[i][j] = max(matrix[i][j], matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]])

            if matrix[i][j] > r:
                r = matrix[i][j]
                tracing[j] = [k, i]
        if matrix[i][j] >= 0:
            matrix[i][j] += bosses_award[j]

matrix矩阵的最终结果：

[[2096, 2382, 2065, 1779, -1,   -1,   -1,   -1,   -1],
 [1897, 2232, 1967, 1743, 2671, 4680, 3981, -1,   -1],
 [1696, 2067, 1851, 1666, -1,   4508, 3923, -1,   -1],
 [-1,   1866, 1692, 1556, -1,   4331, 3844, 6507, -1],
 [-1,   1679, 1548, 1461, -1,   4160, 3777, 6547, -1],
 [-1,   -1,   1364, -1,   -1,   -1,   3642, 6520, -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3510, 6502, 2],
 [-1,   -1,   -1,   -1,   -1,   -1,   3382, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3236, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3095, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1]]

可以看到，最终要打败第9个怪物，只有一种升级的可能性，其他升级方法都不可行，但是具体怎么升级呢？眼睛看，也能看出来，就没有写代码找了，因为需要升级的话，肯定是越早越好的，应该在打第一个怪物时做1次升级（本来游戏规定要升级1次，也就是第1行已经是升级过的情况），第5个怪物升级3次，第6个怪物再升级2次，叭叭叭，顺利通关～～

结论

这题的关键是怎么把背包问题建模，并且有连续好几个动态规划的子问题，层层相扣，加上出题人卡的数值，刚刚好只有一个解，我在疯狂尝试我自己方法的时候，也是差不多无助的状态，等到看到提示之后，又充满信心，解决了问题，也算是波谷到波峰的爽感。类似动态规划问题，在极客赛可能算简单的，但是放在平时刷题时，算难度高的，涉及到好几个状态矩阵的计算，又是一个和一个相关联的情况。挺有意思的一题，后面再继续写一篇极客挑战赛～

最近参加了一场极客挑战赛，挺有意思的，准备简单写下笔记。整个比赛是以游戏形式让大家参与的，一共四个，一开始的时候，我以为真的可以靠纯手打，去进行通关，后来发现，想得太天真了。四个游戏，都是需要通过一些编程去解决的，我过了大部分关卡，不过有些是靠的运气，看完官方的题解后，又有了新的认知。

第一个游戏是类似回合制RPG游戏，类似：

画面没这么好哈，版权原因不能用游戏原图，总之有一个行动条，到了时间就可以行动，英雄（就1个）和怪物（一场战斗也就1个）互相攻击，主角在一个地下城堡，总共24层，一层一层往下冲关，每层会有一个宝箱，每次进入下一层，地图都是随机选择的，地图模式有简单、困难和BOSS，每经过8层，地图中怪兽会升级。

英雄是有技能池的，选择什么技能攻击怪兽，是可以进行策略选择的。
英雄的数据：

hero = {
    "Attack": 30,
    "Hp": 200,
    "Mp": 200,
    "Skills": {
        "skill_0": {
            "Cost_mp": 0,
            "Power": 1
        },
        "skill_1": {
            "Cost_mp": 10,
            "Power": 1.5
        },
        "skill_2": {
            "Cost_mp": 20,
            "Power": 2
        },
        "skill_3": {
            "Cost_mp": 30,
            "Power": 2.5
        }
    },
    "Speed": 30
}

典型的怪物数据：

"Monsters":[
    {
        "Attack":30,
        "Hp":40,
        "Speed":25
    },
    {
        "Attack":20,
        "Hp":50,
        "Speed":20
    }
]

上面的Monsters数据是简单地图的，字段都还比较好理解哈，不多做解释了。
游戏还有一个设定，如果是非8、16、24层，每层都有一个宝箱，这个宝箱是随机开出来奖励或者惩罚，一共有4种情况：

1. empty_box，空箱子；
2. add_hp_mp，加血又加魔法值，Hp+10且Mp+50；
3. del_hp，扣10血；
4. 升级属性，可以选择Attack+10，Speed+1，Hp+100，Mp+200；

是不是感觉这些写出来变量都有点多了，而且都是靠自己抓包，分析出来的，其实玩的时候，真的需要一点点琢磨。然后我通过手打1～8层，发现了一些规律：

• 如果英雄和怪兽Speed一样，英雄是占先的，也就是速度这块，玩家是占点便宜的；
• 通过抓包发现，整个游戏和后端交互的协议就三条吧，new_level（重开游戏），next_layer（进入下一层），和open_box（开宝箱）；

new_level请求和回包：

{token: "YOUR_TOKEN"}
{"code":0,"data":{"hero":{"Attack":30,"Hp":200,"Mp":200,"Skills":{"skill_0":{"Cost_mp":0,"Power":1},"skill_1":{"Cost_mp":10,"Power":1.5},"skill_2":{"Cost_mp":20,"Power":2},"skill_3":{"Cost_mp":30,"Power":2.5}},"Speed":30},"star_num":3},"message":""}

open_box请求和回包：

{"Layer_idx":1,"token":"YOUR_TOKEN"}
{"code":0,"data":{"box":{"BoxType":"add_hp_mp","Value":[30,50]}},"message":""}

next_layer请求和回包：

{"Layer_idx":1,"Choice":"left","Layer_ops":[["start_battle",0],["battle_op",170,200,[["Hero","skill_0"],["Monster","skill_0"],["Hero","skill_0"]]],["start_battle",1],["battle_op",150,190,[["Hero","skill_1"],["Monster","skill_0"],["Hero","skill_0"]]],["open_box"]],"token":"06xyzzou0074CFBD948B14E238FB24BC"}
{"code":0,"data":{"layer":{"Layer_idx":2,"Map_mode":"boss_map","Monsters":[{"Attack":30,"Hp":100,"Speed":40}]}},"message":""}

• 在客户端清理了一层的怪物后，可以选择去下一层的两扇门（left or right），这时候客户端会发送后端，玩家在这一层执行的所有动作序列（看上面的示例），然后后端会根据客户端上传的序列，在后台重放，看看动作序列是否合法，合法就可以进入下一层；

上面这些都是我通过手打1～8层，发现的一些规律，然后我进入第9层，发现怪物确实变强了些，那么通过上面的观察，我第一个想法是每次对怪物的击打，都要经过最优策略的选择，这个最优策略我想了下，每次打怪物的时候，我最终击败他时，保证Hp+Mp是最大的，这个算法我通过bsf，广度优先搜索，大概写了3个小时（也debug了一会），终于写出来了，其实最开始，我天真的以为每次只要固定动作序列即可，什么意思，就是我手动计算一遍简单、困难和boss的地图，会产生什么合法的对列，然后直接发几个构造好的next_layer的请求即可，后来发现，果然是天真了，极客挑战赛，不可能是这么蠢的解法（当然我觉得也是有可能能通过的，毕竟怪物属性值不是随机的，就那么几种）。但是作为程序员，怎么能都通过手动算呢，所以我就写了一个和怪物战斗时的最优策略选择算法。代码不贴了，思路是这样的：

1. 通过计算总共可能的最多攻击次数，英雄最多的攻击次数 = 怪物血量/英雄普通攻击（不耗魔的那个），怪物攻击的最多次数 = 英雄血量/怪物攻击力，选较小的次数保留下来；
2. 在最小的次数规定的时间内，把英雄和怪物可以行动的时间点插入到一个数组（理论上速度够快的一方，其实可以“套圈”，当然实际游戏数据中未出现这种数据）；
3. 把2计算得到的数组进行排序，得到一个按时间排序好的有序时间数组，数组元素记录了轮到哪一方行动，这里有一个小tip，因为上面发现了英雄和怪物速度一样的时候，英雄占先，所以偷偷给怪物行动时间加一个小的偏移量，这样排序后的结果保证了相同速度时，英雄在怪物前行动；
4. 按上述有序数组，挨个做动作，如果怪物动，就一种行动，用他的普通攻击攻击英雄，如果英雄动，英雄有4种行动可选，挨个试，合法状态继续bfs；
5. 直到怪物死掉，这个动作序列是有效的，保存下来（不仅保存动作，也保存英雄剩余的Hp和Mp）；
6. 得到所有可能的有效动作序列后（有效指的是英雄杀死了怪物），看看哪一个序列Hp+Mp最大，执行这个动作序列；

宝箱我就每层都打开，这里也有策略，因为有一个宝箱是提升英雄属性，我一开始是Hp<1.5Mp，加Hp，Mp<150加Mp，Hp和Mp都健康，加Attack，后来发现这个策略不行，第二阶段（9～16层），里面有个怪物的Speed是31，英雄默认的Speed是30，这不欺负人吗？

果断在1～8层有机会先Speed+1，然后尽可能在血量健康状态下加Attack，这样跑了4个小时，被我跑到了接近16层，但是后面还是会挂，那怎么办呢，嗯，我想到了，启动一个后台进程，一直跑，嘻嘻。。。

一值跑的过程很煎熬，因为不知道这么做是不是能打穿24层的地堡，我当时觉得组委会肯定不是这么设计题目的，后来证明这确实是暴力过题的一种方法，跑了20+小时，我查看了日志，发现一个问题，有些运气爆棚的时候，确实可以避开扣血宝箱，而且尽可能加属性，加Hp和Mp，地图也是大多数是简单的，达到过21层，在22层时，遇到一个攻击400，Speed超级快的Boss，基本没有还手之力，我突然郁闷了。。。

在内部的讨论群，我发现很多人都说自己就是暴力通过的，得靠人品，所以又等了接近一天，皇天不负有心人，真的通过啦，那一刻，我快乐得像个孩子，好开心啊～

但是故事还没结束，官方题解下来后，我发现自己漏了一个（或者不是漏了，是根本没往那方面想）点，在第七层，有一段代码会展示给选手，大概是这样的：

func ProcessOneUser(nowLayerId int, queryCMD string, choice string) string {
    r := rand.New(rand.NewSource(time.Now().UnixNano()))

    for {

        if queryCMD == "open_box" {
            if nowLayerId == 8 || nowLayerId ==16 || nowLayerId == 24 {
                return "new_star"
            } else if nowLayerId == 7 {
                return "secret_code"
            } else {
                switch r.Int63() % 4 {
                case 0:
                    return "empty_box"
                case 1:
                    return "add_hp_mp"
                case 2:
                    return "del_hp"
                case 3:
                    return "add_skill"
                }
            }
        } else if queryCMD == "next_layer" {
            newLayerId := nowLayerId + 1

            // rest_map 休息房，没有怪物
            // easy_map 简单层，有两个怪物
            // hard_map 困难层，有三个怪物
            // boss_map boss层，有一个boss
            if newLayerId == 8 || newLayerId == 16 || newLayerId == 24 {
                return "rest_map"
            } else {
                switch r.Int63() % 6 {
                case 0:
                    if choice == "left" {
                        return "easy_map"
                    } else {
                        return "hard_map"
                    }
                case 1:
                    if choice == "left" {
                        return "hard_map"
                    } else {
                        return "easy_map"
                    }
                case 2:
                    if choice == "left" {
                        return "easy_map"
                    } else {
                        return "boss_map"
                    }
                case 3:
                    if choice == "left" {
                        return "boss_map"
                    } else {
                        return "easy_map"
                    }
                case 4:
                    if choice == "left" {
                        return "hard_map"
                    } else {
                        return "boss_map"
                    }
                case 5:
                    if choice == "left" {
                        return "boss_map"
                    } else {
                        return "hard_map"
                    }
                }
            }
        }
    }
}

当时我手打的，我也看到过这段代码，但当时我看了半天，只做了一件事情，测试了一下选择"left"和选择“right”门，简单、困难和Boss地图的几率是不是一样的，我发现次数足够大时，是一样的，当时也就放弃了，其实本题的奥义就在此。
关键代码是这句：

r := rand.New(rand.NewSource(time.Now().UnixNano()))

首先随机种子在每一次new_level之后只取一次，后面都是用这个随机种子生成的rng去生成随机数，如果我们能知道这个随机数，那岂不是开了天眼，每次都选择easy map即可，那怎么才能知道这个随机数呢？

看一下Go的官方库rng随机数的实现：

// Seed uses the provided seed value to initialize the generator to a deterministic state.
func (rng *rngSource) Seed(seed int64) {
    rng.tap = 0
    rng.feed = rngLen - rngTap

    seed = seed % int32max
    if seed < 0 {
        seed += int32max
    }
    if seed == 0 {
        seed = 89482311
    }

    x := int32(seed)
    for i := -20; i < rngLen; i++ {
        x = seedrand(x)
        if i >= 0 {
            var u int64
            u = int64(x) << 40
            x = seedrand(x)
            u ^= int64(x) << 20
            x = seedrand(x)
            u ^= int64(x)
            u ^= rngCooked[i]
            rng.vec[i] = u
        }
    }
}

敲黑板，注意这句seed = seed % int32max，int64的seed会进行截断，而后台服务器使用的是nanoseconds时间戳，也就是后半段表示nanoseconds的时间戳（如果是前半段时间戳，就结束了），官方给出的意思是可以通过枚举所有1～math.MaxInt32的候选种子，看看他们前几个随机的数字是多少，通过开宝箱、进入下一层，玩家是可以观察到，我开的是哪种类型的宝箱，下一层地图是哪种模式，比如我玩到第10层，观察到的结果是：

next Map_mode easy_map
BoxType add_hp_mp
next Map_mode hard_map
BoxType add_hp_mp
next Map_mode easy_map
BoxType add_skill
next Map_mode easy_map
BoxType del_hp
next Map_mode boss_map
BoxType add_hp_mp
next Map_mode boss_map
BoxType add_skill
next Map_mode hard_map
next Map_mode easy_map
BoxType del_hp
next Map_mode hard_map

地图类型和宝箱类型都能通过代码，推算出随机数取4或者6模是什么数值，我上面的序列对应序列是0111030221231021，这个自己想下，应该比较容易想明白吧。

那枚举所有1～math.MaxInt32，也通过一样的操作，得到可能的宝箱和地图类型序列，结果存在一个map中，key是宝箱和地图类型序列，value就是seed，用自己观察到的序列查询下map，既可以找到这个seed。

我试了下，如果要枚举所有的math.MaxInt32种子，还是很耗时的，当然完全通过并行计算，拆成30个并发任务，每个任务算个1亿多的种子，这也行，但是有参赛的极客想到了一个更好的策略，假设服务器的时间和客户端相差不大，在客户端记录下发送请求的nanosecond时间戳，然后加减10ms，去寻找这个时间戳，我自己试了下，前后10ms没有找到，然后我扩大范围，每扩大10ms，要多计算1000w的种子，我扩大到向后100ms时，激动人心的一刻到来了，我终于找到了：

1655533609434000000...
1655533609435000000...
1655533609436000000...
1655533609437000000...
1655533609438000000...
1655533609439000000...
1655533609440000000...
find key=[1655533609394757619]

其实，尽管在知道了反向查找随机种子之后，我还是花了非常久时间，大概有5～6个小时，才准确找到这个随机种子的，非常不容易，看来任何事情都是知易行难。但是尽管辛苦，我觉得很值得，我要求自己不仅要得到好的结果，也要用正确的方法得到好的结果，这样才是思考解决问题的正确方式吧。

整个极客赛过程，都是自己和自己较劲，我真的想了很多方法，包括一上来通过抓包，慢慢摸索游戏的规律，后来写bfs找每次击败怪兽的最优策略，到后面靠运气通关，然后再去思考怎么样通过破解随机种子开天眼，想想是不是一步步成长的过程，一步步通过对的思维和方法解决问题的过程。

哦，对了，这题充分说明，不要使用时间戳做随机种子，随机种子不要固定下来，嗯，否则是有可能让别人通过观察数据破解的，当然前提是对方猜测到了你的实现方式。

上海疫情封在家中有三个月，辅导了小孩子功课，每每小孩遇到不会做的题目，比她更着急。有时也会想起自己学生时代的样子，遇到难题，心中升起必须克服难题的决心，现在自己娃，怎么没有我当年的风采了。哈哈，扯远了，这两天网上看到一道小学二年级的题目，其实我之前做过类似的题目，但是当下还是震惊了，怎么现在小学二年级题目有这么难？

题目是这样的：

配合网友的回复，我马上想到了之前类似的问题，说是25匹马，5个赛道，至少比几场保证找出最快的2匹马。赛马这题答案我记得很清楚7场比赛，先分组进行小组赛：

首先一个虚线框就是一场比赛，上来25匹马，分5组，进行5场预赛。5组比赛会得到组内的名次，比如A组，A1->A2->A3->A4->A5，每组第一名就是A1，B1，C1，D1和E1，然后第一名之间安排一场决赛：

假设结果就是A1->B1->C1->D1->E1(真正结果不重要，不管怎么样，总能推理出最后的结论)，这时候我们就通过4场比赛，知道了第一名是A1，那第二名是谁呢，是不是B1，不一定哦，有可能是在小组赛中被A1淘汰的A2，所以安排场附加赛吧，A2 vs B1：

附加赛之后，就能知道前两名了。话说回小学二年级赛车这道题目，其实思路一模一样，就是通过小组赛->决赛->附加赛，完成前两名的确认，也就是说赛车的话，通过至少5场比赛，保证找出前两名的赛车。

作为小学二年级的题目很变态了吧，但是出题的人还多问了一句，怎么证明这件事情呢，为什么通过4场比赛一定不能保证找出前两名呢？这个证明难倒我了，抓耳挠腮半天，没想出来。然后我就看了下出题老师的分析，茅塞顿开，原来还可以使用图论+反正法来证明。大致的过程如下：
首先把每一辆赛车想象成点，那么我们一共有9辆赛车，一共9个点，每场比赛，只能进行3辆赛车的比拼，每次比拼完，我们会有一个名次，紧挨着的前后两名之间，使用一条有向边连接，这个我文字讲得有点绕口，一图解千愁：

圆圈表示赛车，1号比2号快，2号比3号快，所以每次比赛，我们仅仅能得到2条有向边，如果进行4场比赛，那么总共的有向边数量是4*2 = 8条，而赛车的数量是9，也就是节点数量是9，8条边，9个点，如果要保证所有边都连接到一张图中，不能出现环，否则边的数量不够。

出现环就意味着9个点形成了若干个分开的子图，上面图中9个节点，分为了两个子图，那么就会有一个问题，第一名都不知道是谁，为什么？因为在1～8节点所在的图中，1号赛车最快，9号赛车单独成子图，9号赛车和谁都没有比过，那么到底9号和1号赛车谁快呢？不知道。所以8条边，安排的比赛结果，划分为多个子图，这样是无法确认前两名的。

那我们4场比赛的结果，如何是可以前两名的图形呢，如下：

左边就是分3场比赛（1、4、7，2、5、8和3、6、9分别比赛），得到结果后，4、2、3比一次，结果是4->2->3，转化这张单图，得到右侧的结果，其实就是一个树形的图，那么前两名就是1、4号赛车。

这样我们很容易举出反例，你不是就8条边么，我最后4、2、3的结果是2->4->3，图就变成非树形图，如下：

这样又回到之前多个子图的问题，我们是没法确认1号赛车和2号赛车谁快的，也就没法真正确认前两名是哪两辆赛车。

OK，至少5场比赛，而非4场比赛保证找出最快的2辆赛车得证。是不是挺难的，至少我是没有想出来，通过图论+反证法证明这个数据结论，由衷发出感慨，活学活用好难啊，能做到的大佬，真的太强了。