冬令营 Day 1.

 

上午

内容: 游戏中的数学模型与解题思路

授课人: 吴文虎教授,TSU.

 

今天上午是冬令营的第一堂课，按照惯例，第一堂课都是国际信息学奥林匹克中国队总教练清华大学教授吴文虎教授上的。

吴老一上课就给我们演示了一个“人鬼渡河”游戏，游戏规则是：有3人3鬼在东岸，有一条船容量为2，初始停在东岸，若某一岸（包括停在该岸边的船）上的鬼比人多，那么人就会被鬼吃了。请问如何将3人3鬼安全送到西岸？（注意：船不是电动的，必须要人或鬼划船）。

吴教授首先按照东岸的人数与鬼数表示一个状态：东岸的（人数，鬼数），有一些状态是安全的，有一些是不安全的（东岸或西岸鬼比人多），然后考虑状态的转移方式（即决策），转移（人数，鬼数），有：(1,0),(0,1),(1,1),(2,0),(0,2). 然后我们看我们的转移次数，当目前转移是奇数次时，一定是从东到西，所以是状态量减去决策量；若是偶数，则是从西到东，是状态量加上决策量。接下来我们要考虑判重，当我们东岸状态已经达到过并且船在同一侧时，我们需要剪枝。这样，一个标准的广搜就完成了（最初吴教练是用类似递推的方法，不记录历史状态，其实这样是有反例的：当我们把决策的考虑顺序打乱时，我们很容易走进死胡同，没有历史状态就没法回溯，所以是不正确的）。

休息几分钟后，吴教练开始讲递归，简单介绍了与或节点图，然后又简要地提了一下评估函数，东西都很简单，都是讲一下思想，我在这里就不写了。

 

当然，作为国家队总教练，吴教授讲的都是一些程序设计时的思想方法，比如说人鬼渡河这个例子，我们要从冗长的题目描述中提炼出关键信息，抽象成数学模型，然后从考虑数学模型中转移的方式，找到在数学模型中的转移决策，我们就能够很快地找到解决问题的较优方法。

另外，递归思想事实上是很奇妙的，在数学中也有很广泛的应用，还有很有趣的递归构造的分形Sierpinski三角形，以后我接着写吧。

 

下午

内容：IOI 2008 试题分析

授课人：周冬，原国家队队员,TSU.

这个试题分析其实就是简要地分析一下年鉴上的 IOI 2008 试题解法。有兴趣的可以去看看年鉴，我就不写了。

内容：博弈论相关

授课人：余林韵,TSU.

很有意思的课，首先这位同学简要介绍了 TSU 的“BIDU杯”程序设计大赛，然后他介绍了最近一届大赛“TankCraft”的情况，事实上就是 AI 竞赛，选手们的 AI 间互相打游戏，胜者为王。我们看了决赛的几个回放，真的很精彩，AI 算法都很强大。只是有一次出了一点小 Bug ，双方的3辆 Tank 都相持不动，因为双方都采用了预测对方策略的算法，而且两边都预计对方下一步会攻击，所以原地不动，很有意思。接下来，这位同学简要介绍了一下博弈论，提到的有 Nash均衡点 等博弈知识，其中有一个例子很有意思：有两个囚犯带枪准备犯案，被警察抓住了，警察发现他们以前也犯过罪，但找不到证据，于是拘留了他们俩，隔离突击审讯。如果两个都没招，那么他们俩因“非法携带枪支”各判一年；若有一个招了，另一个没招，那么，没招的那个会判15年，招了的那个因为是证人所以没有被起诉；如果两个都招了，则各判10年。我们来看一看 Nash 均衡点 在哪里：甲想如果甲不招，乙很可能会招，甲会判15年，而甲招了的话，有可能不会被起诉，也有可能是被判10年。所以，甲会招。同理，乙也会招。所以他们两个各被判10年。所以这个问题的 Nash均衡点 在两个都招了的状态这。说明 Nash均衡点 对于某些问题并不是最优的方案。

 

晚上

我们去了位于办公楼的机房，很惊讶地发现装的系统是基于 Ubuntu (Linux) 的 NOI Linux 系统，是中国计算机学会 (CCF) 联合北京航空航天大学开发的一套系统，包括一套开源的信息学竞赛 IDE 系统和一套信息学竞赛评测系统，估计 NOIp 2008 就是在这个环境下评测的。很不错的一套系统。