2020.07.13-2020.07.20

● 2019级经数的小伙伴们

用一行行代码

开启2020年的夏天

暑期编程集训的二三事

以下介绍来自张家玮同学，特此感谢！

●

本次编程集训的内容，用两个字来概括就是“搜索”。与以往“输出hello world”，“输出hello word加强版“，“输出hello world 函数版”不同的是，搜索的逻辑性更强，更加抽象，难度也更大。当然，这里的搜索不是百度的搜索，而是让电脑每走一步都要在所有可能的下一步中进行搜索，包括bfs, dfs，贪心算法，A*算法，博弈算法，爬山法以及α-β剪枝等等。

●

当然啦，太过学术性的定义只会让人头秃。那么下面我就举个简单的例子来给大家介绍一下搜索。

●

想象一下你是一个巨佬，你在人大20院之间穿梭。你在法学院听了一节课，然后马上转到商学院，接着是统计学院……（bfs，广度优先探索）。突然有一天，你发现还是经济学院适合你，于是你开始学习微观经济学导论，然后是中微，高微……你越学越深，但是学着学着发现微观好像并不适合自己。于是你把微观经济学扔到了一勺池里，开始学习初宏，中宏，高宏……（dfs，深度优先探索）。你学经济学有一个目的，就是让自己尽可能获得最大的利益（贪心算法）。但随着发际线一天一天上涨，**越吃越饱，你发现你错了。你只考虑了每一步的收益，但是你却没有考虑代价（A*算法）。于是，你决定重新做人，而重新做人的标志就是开始在各大学院寻找对象。你首先否定了A学院的所有女生，因为她们发际线比你还高（α-β剪枝），你学习了海王和渣男的本领（此处请忽略道德因素），每当看见一个更好的妹子就抛弃现在的（爬山算法，模拟退火算法）。但是你发现，你有一个数学学院的情敌，他在“蛇王争霸赛”里的成绩比你好。于是你俩开始博弈，你每次看见妹子，都要狠狠的吹嘘一下自己，并且不忘说几句数院的坏话……（minimax算法）

够清楚了吗？

所以说，有时候编程比贸易更能使每个人的生活变得更好。

●

下面就是几个简单的例题：

八皇后问题：

在8×8格的国际象棋上摆放8个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

●

比如说，五子棋问题：对方每下一个子，AI都要考虑自己下在哪里才能“损人利己”。五子棋棋盘那么大，AI不能傻傻的挨个分析，而要借助算法，这实际上就是搜索。

●

比如说，我们的人生：“我们的人生就是一个不断向下搜索的过程（dfs）很难遇到最优解，毕竟回头的成本太大了，我们只能一往无前。”

这是我这辈子听到的最高端的鸡汤。

Day1-Day3｜八数码

● 规则：设计算法，使计算机通过对空白格与相邻数字的交换移动，把数字矩阵从初始状态变换到目标状态。

● 心路历程：刚刚看见第一个大作业八数码我的内心是崩溃的，上学期搞了许久也没有搞明白八皇后，现在又来了一个更难的八数码，上课听懂了DFS和BFS的搜索方法，但却发现写起来才是最大的困难，在网上找到了相关代码，一点点琢磨理解，按照思路写出自己的可运行程序，自己也理解了那些上课没有听太明白的理论，收获是很大很大的呢

——祁晓丛

Day4-Day6｜AI五子棋

● 规则：为AI设计算法，实现玩家与AI的五子棋人机对抗，游戏规则与传统五子棋相同。

● 心路历程：五子棋我选用了极大极小值算法，对于形成成五，活四，死四等情况分别记录分数。分别计算人机与操作者的分数，并用score记录人机减操作者的分数，轮到人机操作时，对全棋盘进行遍历，选择score分最高的位置落子。最后判断出现五子连续的一方胜利。

——张怡然

Day7-Day8｜蛇王争霸赛

● 介绍：蛇王争霸赛是每年编程集训营的压轴节目，由同学们根据所学的知识，为自己的AI贪吃蛇设计代码。比赛中多蛇同台竞技，在避开危险的情况下尽可能地吃到更多的食物，获得更多的分数。比赛分为小组赛和总决赛两个阶段：小组赛在各班级内部分成若干个小组进行竞争，各自的前三名进入总决赛，相互竞争决出最终胜者。

● 心路历程：实际上，我的贪吃蛇算法比较简单，整个文件也就差不多180行代码。开始编写之前，我仔细地思考了贪吃蛇必要的功能（找豆子吃以及自保）。考虑到运行时间的限定，我采取了最简单的方式——比较所有豆子的价值/距离——来实现寻找豆子。俗话说得好，“活着才有输出”，所以我在自保的实现上做了不少文章，基本将所有可能遇到的情况都囊括在内。如此我就实现了十分简单但又有效的算法（当然还一度发现了游戏机制上的漏洞耍了点小聪明，不过后来改规则了），整个过程用时也不算太长，倒是后面debug用了不少时间（毕竟找到自己在哪把加号写成减号还是很难的）。

——胡奕博

在这次比赛中，很多小伙伴分别在小组赛和决赛里，获得一等奖至优胜奖不等的好成绩，奖状将于开学后统一颁发(箭头所指均为获奖同学)。

● 小组赛1

● 小组赛2

对这段难忘的时光，我们想说：

刘希

在这次集训中，学到了很多实用的算法和技巧，也进一步掌握了时间管理的方法。尤其是在最后编写贪吃蛇AI的时候，通过不断改善代码，我看到了自己的"蛇"的一步步的成长。看着它在众多"蛇"里脱颖而出，我感觉非常喜悦和欣慰。总的来说，这次编程集训给我带来的收获很大，我也希望自己以后的编程技术能够更上一层楼。

张怡然

这次集训中我印象最深刻的就是做五子棋游戏，我在网上查找了相关的算法结构，结果编写出来的AI对战好强啊，我到现在都没赢过它。这就是自己被自己打败的赶脚吗？爱了爱了。。。（个人愿望：有生之年打败一次那个破AI，我不要再看到“愚蠢的人类，你已经被AI打败了”这句话了！！！）

胡奕博

虽然每天六小时加高强度编程以及八天的三个大作业确实带来了不少痛苦，但每个作业完成之时，debug失落后的苦尽甘来，这是一种不可名状的独特感受。此外，这次集训在最后还给我带来了意想不到的收获，也算是为这一段的学习画上了圆满的句号吧。

梅佳滢

“人在追求算法优化的时候：我只想要界面美如画”

我的AI="A_rtificial+I_ntellectual-disability

张家玮

这七天的集训让我对“潜力”一词有了更加深刻的认识。在开始之初，所有人的心里都只有紧张，担心。或许没有人想过，我们能在短短2天时间内完成一个完善的AI。这七天或许是我人生中睡的最少的七天，是我最秃头最熬夜最痛苦而又最兴奋最满足最充满惊喜的七天。徘徊在失望，坚持与希望之间，或许我最后并没有获得鲜花与掌声，但这都已经不重要了。这七天教会我的，不仅仅是编程的技术，更是一种不断追求永不言弃的态度。

未来将至

● 我们在深夜看星光沿途散播

而长路尽头有灯火

于我们而言，这八个日夜

是一种成长，更是一种蜕变

前路昭然，愿你我共进