Game solving is a similar, yet more difficult task than mastering a game.
Solving a game typically means to find the game-theoretic value (outcome given
optimal play), and optionally a full strategy to follow in order to achieve
that outcome. The AlphaZero algorithm has demonstrated super-human level play,
and its powerful policy and value predictions have also served as heuristics in
game solving. However, to solve a game and obtain a full strategy, a winning
response must be found for all possible moves by the losing player. This
includes very poor lines of play from the losing side, for which the AlphaZero
self-play process will not encounter. AlphaZero-based heuristics can be highly
inaccurate when evaluating these out-of-distribution positions, which occur
throughout the entire search. To address this issue, this paper investigates
applying online fine-tuning while searching and proposes two methods to learn
tailor-designed heuristics for game solving. Our experiments show that using
online fine-tuning can solve a series of challenging 7x7 Killall-Go problems,
using only 23.54% of computation time compared to the baseline without online
fine-tuning. Results suggest that the savings scale with problem size. Our
method can further be extended to any tree search algorithm for problem
solving. Our code is available at
this https URL

应用在线微调的方法解决游戏问题，在计算时间上相比基准方法仅使用了 23.54%，表明节约的规模与问题的大小成正比。

在线微调的游戏求解

Game Solving with Online Fine-Tuning

Driven by recent successes in two-player, zero-sum game solving and playing,
artificial intelligence work on games has increasingly focused on algorithms
that produce equilibrium-based strategies. However, this approach has been less
effective at producing competent players in general-sum games or those with
more than two players than in two-player, zero-sum games. An appealing
alternative is to consider adaptive algorithms that ensure strong performance
in hindsight relative to what could have been achieved with modified behavior.
This approach also leads to a game-theoretic analysis, but in the correlated
play that arises from joint learning dynamics rather than factored agent
behavior at equilibrium. We develop and advocate for this hindsight rationality
framing of learning in general sequential decision-making settings. To this
end, we re-examine mediated equilibrium and deviation types in extensive-form
games, thereby gaining a more complete understanding and resolving past
misconceptions. We present a set of examples illustrating the distinct
strengths and weaknesses of each type of equilibrium in the literature, and
prove that no tractable concept subsumes all others. This line of inquiry
culminates in the definition of the deviation and equilibrium classes that
correspond to algorithms in the counterfactual regret minimization (CFR)
family, relating them to all others in the literature. Examining CFR in greater
detail further leads to a new recursive definition of rationality in correlated
play that extends sequential rationality in a way that naturally applies to
hindsight evaluation.

通过适应性算法的考虑以确保比修改行为所能达到的结果更好，我们可以基于相关学习动态产生新的博弈理论分析，这样做比基于平衡策略算法更加有效，因为前者可以处理非零和多人博弈问题。我们重新审视了博弈理论中的中介均衡和偏差类型，证明了没有可行的概念包含所有其他类型，并引出了一个追溯与规避策略算法的平衡类别的定义。