LLM2D
游戏溯源结构及其应用
On the Structure of Game Provenance and its Applications
作者: Shawn Bowers, Yilin Xia, Bertram Lud\"ascher
发布日期: 10/8/2024
arXiv ID: oai:arXiv.org:2410.05094v1

摘要

数据库中的溯源问题已经针对正查询和递归查询进行了深入研究,随后又针对一阶(FO)查询进行了研究,即包含否定但没有递归的查询。查询评估可以理解为一个双人博弈,其中对手争论一个元组是否在查询答案中。这种博弈论方法为 FO 查询提供了一个自然的溯源模型,统一了如何溯源和为什么不溯源。本文研究了博弈溯源的精细结构。一个博弈 $G=(V,E)$ 由位置 $V$ 和移动 $E$ 组成,可以通过计算单个非分层规则的良基模型来求解: \[ \text{win}(X) \leftarrow \text{move}(X, Y), \neg \, \text{win}(Y). \] 在求解后的博弈 $G^{\lambda}$ 中,位置 $x\,{\in}\,V$ 的值要么是赢,要么是输,要么是平局。这个值由溯源 $\mathscr{P}$(x) 解释,即从 $x$ 可达的某些(带注释的)边。我们识别了七种边类型,它们产生了新的溯源类型,即潜在的、实际的和主要的,并证明了“并非所有移动都一样”。我们描述了新的溯源类型,展示了如何在求解博弈的同时计算它们,并讨论了应用,例如,用于抽象论证框架。