Posted 

Monte Carlo Tree Search & Monte Carlo Ray Tracing

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


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

建议的方法是 剪枝, 但是写出来之后效果不行, 貌似缺一个好的估价函数. 但是编估价函数又有点蛋疼.... 这时候 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):

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

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

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

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

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

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


其他一些资料:

#

Comments

Popular Posts

Tags

Deep Learning12
Math10
Research9
Programming9
Open Source9
PyTorch8
Life7
Course6
Computer Vision6
Contest6
Python6
Linux6
C++4
Algorithm4
GEB3
Computer Graphics3
Design3
Blog1
×