在現今的撞球電子遊戲產業中，較受人注目的領域為撞球遊戲的人工智能而不是關卡生成，因此關於撞球遊戲的關卡生成領域的相關參考文獻非常稀缺。以我個人的觀點，有下列兩個原因。

其一為該領域的難度過高。撞球關卡生成為一連續空間問題，即使一個關卡常以某幾種特定的 Pattern 組成，但要在無限的空間中找到符合使用者需求的某組 Pattern 組合實在太過困難。其二是市場需求不高。目前的市場上的撞球電子遊戲中，玩家最主要是追求與更高端的對手對戰，因此各家公司與團隊都以開發強大的擬人 AI 為目標，讓這些 AI 玩家扮演線上玩家的角色。我們若以另外一個角度來思考，正因為沒有一套好的關卡生成系統生成優秀的關卡，導致玩家對撞球解題模式沒有興趣，這個領域的需求也因此變得更低了。

本論文最大的貢獻在於提供了一套自動化生成的框架，利用 L-system 與 MCTS 的搭配達到關卡生成的功能。本論文最主要的細節在於如何表達盤面幾何的資料結構，因該資料結構在字串與盤面間作為銜接的存在，使得該系統得以有效的運作。若該資料結構能根據各遊戲進行設計，本框架可以套用在任何遊戲的關卡生成上。

Nowadays, the application which get most attension in industry of pool games is not the level generation but the artificial intelligence, so the related references on the level generation of billiards' puzzle are very scarce. In my opinion, there are two reasons for that.

Firstly, the difficulty of development. Level generation of billiards' puzzle is a continuous space question. Although a puzzle are often composed of several specific patterns, there are still infinite possibilities of combinations of these patterns. Is's too difficult to find the most matching puzzle from the infinite possible results with the requirement of user.

Secondly, the demand on the market. For the current commercial billiards video games, the requirement for the AI is more than level generation. Because the players' main demand is to challenge the opponents with higher skills, almost companies or teams are developing a strong and anthropomorphic AI instead of designing the levels of billiards' puzzle. On the other hand, without a usefull and efficient level generation system may be the reason why players are not interested in puzzle mode because they have never played any interesting puzzle.

Our contribution is offering a level generation framework which can apply to every video games by using L-system and Monte Carlo Tree Search (MCTS). The most important part in our framework is the data structure to represent the puzzle's placement. Because of this structure, L-system and MCTS can work together. If we can transfer this structure to fit another game's mechanism, we can apply this framework to that game.

1. 緒論
1.1 研究背景與動機
1.2 研究目的與問題
1.3 方法概述
1.4 本論文之章節結構
2 相關研究
2.1 程序化內容生成
2.2 L-system
2.3 蒙地卡羅樹搜尋 MCTS
2.4 撞球相關資訊簡介
3 實驗方法
3.1 字串生成器
3.1.1 L-system
3.1.2 參數化生成
3.1.3 字串生成流程
3.2 盤面表達法
3.2.1 點與盤面元素
3.2.2 字串轉換為盤面表達法
3.2.3 樹狀結構
3.2.4 盤面幾何校正
3.3 盤面生成器
3.3.1 狀態與行動
3.3.2 參數化與盤面評鑑
3.3.3 盤面生成流程
3.4 物理校正
4 實驗結果與分析
5 結論與後續工作

[1] J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, “Search-based procedural content generation: A taxonomy and survey,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, no. 3, pp. 172–186, 2011.
[2] N. C. Hou, N. S. Hong, C. K. On, and J. Teo, “Infinite mario bross ai using genetic algorithm,” in 2011 IEEE Conference on Sustainable Utilization and Development in Engineering and Technology (STUDENT), pp. 85–89, Oct 2011.
[3] Chen, Pin-Ling and Tai, Wen-Kai, “Procedural Level Content Generation of Action Games using Tactics,” Master’s thesis, National Taiwan University of Science and Technology, Department of Computer Science and Information Engineering, 2018.
[4] A. Summerville and M .Mateas, “Super mario as a string: Platformer level generation via lstms,” arXiv preprint arXiv:1603.00930, 2016.
[5] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial networks,” 2014.
[6] V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. Smith, and S. Risi, “Evolving mario levels in the latent space of a deep convolutional generative adversarial network,” Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’18, 2018.
[7] A. Lindenmayer, “Mathematical models for cellular interactions in development i. filaments with one-sided inputs,” Journal of theoretical biology, vol. 18, no. 3, pp. 280–299, 1968.
[8] F. Boudon, C. Pradal, T. Cokelaer, P. Prusinkiewicz, and C. Godin, “L-py: an l- system simulation framework for modeling plant architecture development based on a dynamic language,” Frontiers in plant science, vol. 3, p. 76, 2012.
[9] Li, Yun-Pin and Tai, Wen-Kai, “A Procedural Modeling System for Chinese Cold Weapons Based on Parametric L-system and Gameplay Statistics,” Master’s thesis, National Taiwan University of Science and Technology, Department of Computer Science and Information Engineering, 2019.
[10] R. Coulom, “Efficient selectivity and backup operators in monte-carlo tree search,” in In: Proceedings Computers and Games 2006, Springer-Verlag, 2006.
[11] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al., “Mastering the game of go with deep neural networks and tree search,” nature, vol. 529, no. 7587, p. 484, 2016.
[12] D. Churchill and M. Buro, “Hierarchical portfolio search: Prismata’s robust ai archi- tecture for games with large search spaces,” in Eleventh Artificial Intelligence and Interactive Digital Entertainment Conference, 2015.
[13] L. Kocsis and C. Szepesvári, “Bandit based monte-carlo planning,” in European conference on machine learning, pp. 282–293, Springer, 2006.
[14] H. Robbins and S. Monro, “A stochastic approximation method,” The Annals of Mathematical Statistics, vol. 22, no. 3, pp. 400–407, 1951.