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很靠谱.

Monte Carlo Tree Search比较好的介绍是这篇论文, 里面主要说了MCTS框架下一个比较好的UCT (Upper-Bound Confidential Tree) 算法. UCT的比较好的实现是这个网站. 为什么说实现的好呢, 因为我照着它的代码一晚上糙了一个出来, 就已经能打八九十的test cases了.... 但是其实对于其原理还真不太理解. 大致过程是, 以某个神公式来选取最优子节点进行扩展. 扩展了一点点之后就暴力把这一枝随机落子一直模拟到游戏结束, 赢了加分输了减分. 结果效果就奇迹般的很好....

为了让搜索更多, 接下来就是效率提升的工作. 比如把棋盘用int64来存..位运算优化等等类似的事情. 然后到服务器上跑case来优化筛选UCT神公式里的神常数.最后就可以打100了.

顺便吐槽下, 评测是windows only的, 且需要保证代码能在Visual Studio上编译, 着实费了不少功夫. 最终我的状态就是在服务器上开个VNC, VNC里开一个虚拟机win7, win7里装了Visual Studio在跑test case.. 另外Visual Studio对C++11的支持貌似也很渣, 感觉好像除了auto之外什么都没支持... 代码改了好多才能编译.


图形学是门好课. 胡事民 老师学术造诣很深, 几乎每节课都在讲高端大气的前沿知识, 只不过跟作业的确关系不大. 听说有些挺好的学校里"计算机图形学"这门课的最终作业就是学会用OpenGL画个三维场景, 而我们的一个作业是要写一个能像OpenGL一样画三维场景的程序... 这样一比的话..嗯T大毕竟是T大.

这个作业就是Ray Tracing. Ray Tracing其实是个前沿问题, 像wikipedia里那些绚丽的图片其实都是近年才画出来的, 我们的作业没要求那么绚, 只要用Phong Model 计算光照即可.

Phong Model所做的事情其实就是, 视线打到一个物体表面, 在已知表面属性, 几何位置, 光源属性的条件下, 它有一个公式可以算出视线看到的是什么颜色. 所以这个作业其实理论上没有太多含量, 工程上的活多一些. 要管理好各种物体各种求交求表面属性等东西还是挺麻烦的, 因此设计上借鉴了开哥和Tim的想法, 写了之后回顾一下才觉得自己以前果然是不懂OOP的人..

当然其实这里有一个可以做的有趣的事情是KDTree, 不做的话效率瓶颈太严重, 场景里基本就画不了很多东西了. 查了一下发现光线追踪的KDTree还比较有讲究, SAH-based KDTree 要比一般的KDTree快得多. 经过异常痛苦的调试之后终于写出来了.. (这是个大坑..不少人调光线追踪里的KDTree都调疯了..).. 有了KDTree之后就可以跑各种东西了包括几十万的大模型.. 然后就开始往程序里加小功能, 包括法向插值,抗锯齿, 软阴影, 景深.. Phong Model渲染的最后的效果大概是这个样子:

速度还行, 一两秒就能跑出来, 不过这张图按照Tim的话来说, "太CG了"....Phong Model对光照的描述不够好, 颜色不自然就不说了, 有些东西是Phong Model本身的缺陷, 比如渲染一个透明的球下面会有不应该有的阴影. Phone Model下的软阴影是靠我手动模拟面光源强行加上的(这张图里没有), 效果也不咋样.

这时候Tim教了一个全局光照模型给我, 它基于Kajiya提出的很唬人的"渲染方程"(Render Equation / Light Transport Equation):

$$I(x, x\prime) = g(x, x\prime)\left[\epsilon(x, x\prime) + \int_S \rho(x, x\prime, x\prime\prime)I(x\prime, x\prime\prime) dx\prime\prime\right]$$

它的意思是说, 我从$x$看$x'$的颜色, 应该包括它表面发光的颜色(如果它是光源的话), 加上从$x'$看周围方向看到颜色的平均(那个对$x''$的积分). 挺直观的一个公式(忽略那个$g$吧). 至于那个$\rho$是一个BRDF, 定义了什么叫"周围", 比如对于完美镜面, 它的"周围"只有反射的那一个方向而已.

但是这玩意怎么算呢? 本来我的视线打到物体上, 只要按照Phong Model公式算个颜色, 再递归算反射折射就行了, 现在却有"周围"的无穷多的光线需要递归计算.

然后Monte Carlo法就出现了, 其实就是, 在输出图片的每个像素的位置上发固定数目的视线, 在每次到了表面的时候, 不去管"周围"了, 按照其表面BRDF随机选一个方向继续往前走就好. 这样这个问题就可做了, 相比Phong Model, 其实只改了一个tracing的主函数. 同样场景的渲染效果如下:

这幅图里, 玻璃球下有Caustic了, 粗糙表面的颜色更自然了, 反射的墙和球面也更真实了.(影子少了是因为光源 多了一点) 当然速度也更慢了, 这是按每个像素1000条光线跑的, 速度慢了几千倍.

之后就有各种神奇的优化出现了, Metropolis Light Transport, 看上去很不错. 不过这个全局光照写出来的时候已经快DeadLine了就没再看.

源代码及算法细节报告在github, 以及Tim业余写了一个叫做MaskRay 的光线追踪项目,以后可能会维护, 也值得关注一下. 他首页上放的图比我的好看多了.


其他一些资料:

Comments