极客挑战赛-笔记一

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

第一个游戏是类似回合制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找每次击败怪兽的最优策略，到后面靠运气通关，然后再去思考怎么样通过破解随机种子开天眼，想想是不是一步步成长的过程，一步步通过对的思维和方法解决问题的过程。

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