论文标题
游戏拼布的状态表示和多莫诺
State Representation and Polyomino Placement for the Game Patchwork
论文作者
论文摘要
现代棋盘游戏对许多人来说是丰富的娱乐来源，但还包含有趣且具有挑战性的结构，用于玩研究和实施游戏代理商。本文研究了游戏拼布，这是一种使用Polyomino Tile Arafting和Plotement的两个玩家策略游戏。使用常规约束在约束模型中实现了核心多粒子放置机械师，从而扩展和改进了模型（Lagerkvist，Pesant，2008年），使用：显式旋转处理；可选位置；以及用于资源使用的新约束。对于实施良好的游戏代理商，至关重要的是，在面对大型分支因素时，要有出色的启发式方法来指导搜索。本文将瓷砖放置在两个部分中：用于放置零件的策略和用于在不同位置之间进行选择的评估。政策是基于经典包装文献以及常见的标准约束编程启发式方法而设计的。为了进行评估，引入了全球传播引导的遗憾，根据不排除以后的安置来选择安置。进行了广泛的评估，表明使用良好的评估的重要性，而拟议的全球传播引导的遗憾是非常有效的指南。
Modern board games are a rich source of entertainment for many people, but also contain interesting and challenging structures for game playing research and implementing game playing agents. This paper studies the game Patchwork, a two player strategy game using polyomino tile drafting and placement. The core polyomino placement mechanic is implemented in a constraint model using regular constraints, extending and improving the model in (Lagerkvist, Pesant, 2008) with: explicit rotation handling; optional placements; and new constraints for resource usage. Crucial for implementing good game playing agents is to have great heuristics for guiding the search when faced with large branching factors. This paper divides placing tiles into two parts: a policy used for placing parts and an evaluation used to select among different placements. Policies are designed based on classical packing literature as well as common standard constraint programming heuristics. For evaluation, global propagation guided regret is introduced, choosing placements based on not ruling out later placements. Extensive evaluations are performed, showing the importance of using a good evaluation and that the proposed global propagation guided regret is a very effective guide.
