UCT for Games and Beyond

多年来，人工智能（AI）的研究和价值数十亿美元的电子游戏产业的发展一直密切相关。到目前为止，电子游戏是公众日常接触AI技术的最普遍方式，对更好的电子游戏的渴望推动了AI在移动/路径规划、决策制定、非玩家角色（NPC）行为和游戏内容自动生成等领域的研究。蒙特卡罗方法的最新发展被称为树的上限置信界限（UCT）方法，有望对游戏中的人工智能产生深远的影响。UCT的应用并不局限于游戏，在模拟和统计建模可以用来预测结果的几乎任何领域都有潜在的好处，比如规划、决策支持、经济建模、行为分析等等。自2006/7年问世以来，UCT彻底改变了计算机围棋的走法规划这一难题，今年首次产生了能够击败职业棋手的人工棋手，这一壮举此前被认为是不可能实现的。UCT还成功地应用于一般游戏（GGP）的不太专业的领域，产生了2008年和2009年世界冠军GGP程序。在Go和GGP中，使用了大量特定问题的知识，而在GGP中，不可能使用特定问题的知识，这种成功指出了在这两个极端之间广泛使用UCT的诱人可能性。游戏AI研究人员现在开始对UCT产生极大的兴趣，我们看到蒙特卡洛树搜索（MCTS）这一新的研究领域的诞生。然而，到目前为止，还没有统一的努力来充分理解和利用UCT算法和相关的MCTS方法，我们计划纠正这种状况。拟议的研究将开发和评估UCT方法的新扩展，以增加其在广泛的游戏相关领域的适用性，包括：在无限连续的实时环境中用于移动计划和决策制定；它在涉及不确定性和不完全信息的情况下的应用；及其在多目标集成规划中的应用。我们还将研究它在更一般的游戏相关问题中的应用，包括检测和优化或纠正次优游戏设计和游戏内容，以及自动生成新的高质量游戏和游戏内容。此外，我们将展示我们开发的技术如何应用于更广泛的非游戏领域，通过展示它们在机器人控制和自动音乐生成中的应用，特别是爵士乐即兴创作的创造性挑战任务。UCT和MCTS的潜在影响怎么强调都不为过。推动人工智能研究的里程碑事件包括引入树搜索方法，自20世纪50年代该领域成立以来，树搜索方法一直是人工智能决策的支持，以及20世纪70年代蒙特卡罗方法的形式化，用于在更广泛的更一般和更不明确的问题中进行基于模拟的决策。UCT/MCTS有望成为人工智能方法的下一个重大突破，它将树搜索的强大功能与基于模拟的搜索的通用性相结合。

Artificial Intelligence (AI) research and the development of the multi-billion dollar video games industry have gone hand in hand for many years. Video games are by far the most prevalent way that the public encounter AI techniques on a day to day basis, and the desire for better video games has driven AI research in areas such as move/path planning, decision making, non-player character (NPC) behaviour and the automated generation of game content. A recent development of Monte Carlo methods called the Upper Confidence Bounds for Trees (UCT) method promises to have a profound impact on AI for games. Applications of UCT are not limited to games and have potential benefits for almost any domain where simulation and statistical modelling can be used to forecast outcomes, such as planning, decision support, economic modelling, behavioural analysis, and so on.Since it appeared in 2006/7, UCT has revolutionised the demanding problem of move planning for computer Go to produce artificial players able to beat professional players for the first time this year, a feat previously thought infeasible. UCT has also been successfully applied to the less specialised domain of General Game Playing (GGP) to produce the 2008 and 2009 world champion GGP programs. This success in Go, where substantial problem-specific knowledge is used, and in GGP, where it is impossible to use problem-specific knowledge, points to the tantalising possibility of the broad use of UCT between these two extremes. Game AI researchers are now starting to take such a great interest in UCT that we are seeing the birth of a new research field of Monte Carlo Tree Search (MCTS). However, there has been to date no unified effort to fully understand and exploit the UCT algorithm and related MCTS methods, a state of affairs that we plan to redress.The proposed research will develop and evaluate novel extensions of the UCT method to increase its applicability to a broad range of game-related domains including: its use for move planning and decision making in infinite, continuous real-time environments; its application to situations involving uncertainty and incomplete information; and its application to multi-objective and ensemble planning approaches. We will also investigate its use for more general game-related problems including the detection and optimisation or correction of suboptimal game designs and game content, and the automated generation of new high quality games and game content. Further, we will demonstrate how the techniques we develop can be applied to broader non-game domains by demonstrating their application to robotic control and automated music generation, in particular the creatively challenging task of jazz improvisation.The potential impact of UCT and MCTS cannot be overstated. Landmark events that have driven AI research include the introduction of tree search methods which have been the backstay of AI decision making since the inception of this field in the 1950s, and the formalisation of Monte Carlo methods in the 1970s for simulation-based decision making in a broader range of more general and less well-defined problems. UCT/MCTS promises to be the next major breakthrough in AI methods that combines the power of tree search with the generality of simulation-based search.