Monte Carlo Tree Search & Monte Carlo Ray Tracing

这学期有两个有意思的大作业都跟Monte Carlo有那么点关系.


人智的大作业是写一个Connect Four 游戏的AI. 当然由于原本这个游戏是有必胜策略 的, 所以老师对这个游戏做了小修改. 给了50个测试AI, 编号2~100的偶数, 越牛的编号越大, 让我们打着玩, 评测时用另外一批AI.

建议的方法是$\alpha-\beta$剪枝, 但是写出来之后效果不行, 貌似缺一个好的估价函数. 但是编估价函数又有点蛋疼....这时候 maskray, zxytim, blahgeek 纷纷表示Monte Carlo Tree Search很靠谱.

关于张益唐的一些八卦

今天听老师说了一些关于Yitang Zhang的八卦相当感慨

因为文革原因,上北大的时候已经20多岁了

78级北大数院公认最优秀的毕业生

硕士在北大师从老潘学解析数论

84年丘先生回国到处演讲招学生,挑选了很多优秀的中国学生, 当时身为San Diego院长的他一年招了20多个中国学生去San Diego,他们几乎都成为了当今最牛的中国数学家

SIFT and Image Stitching

图像处理课期中要写一个图像拼接程序.

这方面的技术当然已经很成熟了, 开源界最著名的当属hugin, 拼全景图效果非常好. 在学术界也已经不是难题了, Lowe在IJCV2007的一篇 Automatic Panoramic Image Stitching using Invariant Features 是一个完整的流程介绍. MSRA的Szeliski有过一本几十页的 Image Alignment and Stitching: A Tutorial, 也详细的介绍了图像拼接的众多方法. 我基本就照着Lowe, Szeliski的一堆论文的方法在搞.

On the Solvability of 8-Puzzle

人智课一次作业是写一个A* 程序算八数码问题 的最优解. 一个自然的问题是, 什么样的初始状态有解?

一个熟知的结论是, 将矩阵元素排成一排,忽略空格,当且仅当逆序对个数为偶数时此问题有解.

必要性很好证明, 因为观察可知所有的移动操作不会改变逆序对个数的奇偶性. 那充分性呢?


要证明充分性, 需要将矩阵用另一种方式展开成一排:$(a_{11}a_{12}a_{13}a_{23}a_{22}a_{21}a_{31}a_{32}a_{33})$.

Recurrent Event

去年11月面试Hulu 的时候,曾经遇到这么一道概率题:

一只猴子随机敲键盘上的26个字母, 期望在多少次之后能首次打出"hulu"?

当时只是直觉觉得答案应该是$26^4$, 没有想出很好的做法. 想出来的唯一方法是列一个四元线性方程组, 四个变量定义如下,有点像Markov Chain的感觉:

  1. 打出hulu的期望次数
  2. 已打出h, 从现在开始算打出hulu的期望次数
  3. 已打出hu, 从现在开始算打出hulu的期望次数
  4. 已打出hul, 从现在开始算打出hulu的期望次数

Work Faster

关于效率..

  • xset r rate 200 40

    设置X Server接收键盘事件的频率. 把按住某个键时触发的事件频率变多, 就相当于键盘变灵了一样. 200, 40只是比较适合我的一组参数.

    用了它以后的一个结果是,没法习惯别人的电脑了, 嫌翻页慢..

  • vim-accelerated-jk

    一个vim插件, 功能是按住j或k时, 触发jk事件的频率随按住的时间而增加. 速度可调, 和xset配合之后,在vim里翻页如飞, 基本不需要C-D, C-U了. 虽说过度用jkhl其实是不好的习惯.

Number of Fixed Points in Random Permutations

概率论课, 一项作业是写篇小论文. 错排数是高中就总结过的, 恰好概率论某次习题课还讲到, 就花了一周时间又整理了下错排数(Rencontres Number)有关的东西. pdf放在github.

对于排列$\pi$, 设$\mathcal{F}(\pi)$是它的不动点集合: $$ \mathcal{F}(\pi) = \{ k \in [1,n]\cap \mathbb{N} : \pi(k) = k \} $$

设$\Pi_n$是所有可能$n$元排列的集合, 则错排数$D_{n,k}$可定义如下: $$ D_{n,k} = \| \{ \pi \in \Pi_n : \| \mathcal{F}(\pi) \| = k \} \|, k = 0,1,\cdots n $$

突然就可以在读秀上下书了..

高中搞竞赛的同时会每天也搞电脑,竞赛资料全是网上找的,也认识了一堆一堆的人.. 然后,跟很多人一样养成了一种强迫症..就是..搜集pdf..

高中搜集的数学竞赛各种, 现在还保留着的pdf还有1G多.. 也做过自己整理的事情,比如把各年联赛题找出来整理了个25年联赛题集..总之强迫症嘛,逼着自己做完.

带来的一个结果就是,搜索能力变强了.比正常的google一下baidu一下ishare一下要有效的多 那时候有北大的学长让我帮忙找一篇很难找的论文, 我搞了三四个小时的样子,一直都在不同的途径上找这篇论文, 现在可不会这么闲了.. 是一篇Hilbert的,由于那个时代的杂志现在都没有收录在乱七八糟的网站,搜了好久最后在Gottingen的某网站找到了图片版的 大概就是经历了很多这样的事之后,搜论文的话,对几个常见的网站也都比较熟了..比如记得有次也是研究了好久springer上的论文下载.

How Many Fibonacci Numbers are also Power of 2

数据结构课上, 比较二分查找与Fibonacci查找. 举例时为了方便, 就让数组长度是8, 因为8既是2的幂又是Fibonacci数, 方便演示算法. 邓俊辉老师随口问了一句像这样的数还有没有呢.答案是没有的.

Fibonacci数有一个有趣等价条件: $x$是Fibonacci数当且仅当$5x^2 \pm 4$中某一个数是完全平方数.

  • 必要性很好证. 验证如下等式: $$ 5F_n^2 + 4(-1)^n = L_n^2 $$ 其中 $F_n$是以$F_0=0, F_1=1$定义的Fibonacci数, $L_n$是以$L_0=2, L_1=1$定义的Lucas数

  • 充分性: $$ m^2 = 5n^2\pm 4 \Leftrightarrow \dfrac{m + \sqrt{5}n}{2}\dfrac{m - \sqrt{5}n}{2} = \pm 1 ,$$ 于是$\dfrac{m \pm \sqrt{5}n}{2}$ 为$ Q(\sqrt{5}) $中的单位元, 那么$\dfrac{m + \sqrt{5}n}{2} = (\dfrac{1 + \sqrt{5}}{2})^k$, 就可以得到$n = F_k$了.

有了这个性质之后, 只需要考虑$5 \cdot 4^k \pm 4 = m^2$有没有非平凡解即可. 这个很容易就..略了.

后来发现一个很强的Carmichael定理, 可以直接秒这道题. 定理的内容是: 对每个$n > 12, F_n$ 必定包含一个没有在之前的Fibonacci序列中出现的因子.

Cantor's Diagonal Method on Computable Numbers

在翻Matrix67的思考的乐趣 的时候,看到集合论那里,依次证明了有理数,代数数,可计算数,可定义数的可数性, 甚舒畅.然后用经典的Cantor's Diagonal Argument证了实数的不可数性, 并说明了此方法对有理数不可用,因为对角线生成的新数未必是有理数.

然后我想,对角线法用在可计算数上似乎也可以啊.. 假设可计算数可数, 排成一列 $[a_1, a_2...]$ 之后, 按照对角线法取出一数, 保证取出数$x$满足$x[k] \ne a_k[k]$, 则$x$也没有被列出. 而进一步,如果我们规定取数时的对应法则 $f: [0, 9] \cap \mathbf{N} \rightarrow [0, 9] \cap \mathbf{N}$, 令$f$无不动点, $x[k] = f(a_k[k])$, 那么取出的新数也就是可计算的了. 那按照Diagonal Argument, 可计算数不就不可数了?