通过迭代缩小相关区域，显著减少博弈求解的搜索空间。
Relevance-Zone Reduction in Game Solving
- 迭代约束策略逐步缩小博弈相关区域，提升搜索效率。
- 7x7 Killall-Go上平均相关区域缩小至原大小的85.95%。
- 可存储小型相关区域作为未来求解的可复用知识。
博弈求解旨在为所有玩家找到最优策略并确定游戏的理论结果。然而，由于博弈树呈指数增长，许多游戏仍无法求解，尽管像AlphaZero这样的方法已在游戏对弈中表现出超人类水平。相关区域（RZ）是一种局部策略复用技术，将搜索限制在与结果相关的区域，显著减少了搜索空间。然而，RZ并非唯一；不同解可能产生大小不同的RZ，更小的RZ通常更有利，因其提高复用可能性并增强剪枝效率。为此，我们提出一种迭代式RZ缩减方法，通过反复求解同一位置并逐步限制涉及区域，引导求解器趋向更小的RZ。我们设计了三种约束生成策略，并集成RZ模式表以充分利用过往解。在7x7 Killall-Go上的实验表明，该方法将平均RZ大小降至原始大小的85.95%。此外，缩减后的RZ可永久存储为可复用知识，适用于更大棋盘或不同开局场景。
原文摘要 · Abstract (English)
Game solving aims to find the optimal strategies for all players and determine the theoretical outcome of a game. However, due to the exponential growth of game trees, many games remain unsolved, even though methods like AlphaZero have demonstrated super-human level in game playing. The Relevance-Zone (RZ) is a local strategy reuse technique that restricts the search to only the regions relevant to the outcome, significantly reducing the search space. However, RZs are not unique. Different solutions may result in RZs of varying sizes. Smaller RZs are generally more favorable, as they increase the chance of reuse and improve pruning efficiency. To this end, we propose an iterative RZ reduction method that repeatedly solves the same position while gradually restricting the region involved, guiding the solver toward smaller RZs. We design three constraint generation strategies and integrate an RZ Pattern Table to fully leverage past solutions. In experiments on 7x7 Killall-Go, our method reduces the average RZ size to 85.95% of the original. Furthermore, the reduced RZs can be permanently stored as reusable knowledge for future solving tasks, especially for larger board sizes or different openings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。