所以有anxn游戏板，板上的每个位置都有一个整数。玩家一从第 1 行中选择一个数字，玩家 2 从第 2 行中选择一个数字，他们交替进行直到没有更多行。然后他们将所有数字相加，如果总和等于预定的总和 S，则玩家 1 获胜，否则玩家 2 获胜。对于特定棋盘和总和（B，S），玩家 1 的获胜策略是无论玩家 2 做什么，玩家 1 都能获胜。我想证明这个问题是 PSpace-complete
所以首先我必须证明它在 PSpace 中，我认为这很容易，因为移动的总数受棋盘大小的限制，即 n^2。
我一直坚持证明它很难 PSpace，但我知道我必须从 QSAT 中减少，但我不知道如何。有人可以帮忙吗？
编辑：其实我不知道我必须从 QSAT 中减少，但是在搜索之后似乎 QSAT 是最有可能的候选人。许多其他两人游戏，地理是最突出的例子，从 QSAT 减少，所以我认为这也是必须的。但是，如果我对此有误，请随时纠正我。
如果您从 QSAT 中选择减少，您的任务将从一个公式开始。
您需要构建一个游戏实例，以便如果玩家 1 具有获胜策略，则该公式的否定是重言式。参与者 2 的角色主要是确定普遍量化的布尔变量的估值；玩家 1 在存在量化的布尔变量方面具有类似的作用。
您需要在填充表格时表现出一些独创性，以便玩家 1 在重言式的情况下只能强制执行零和。还要确保您需要的表行数仅与公式中的量词出现数呈线性关系。
[SPOILER 1 开始] 记住我们在家庭作业模式下讨论。我现在将几乎所有的细节添加到提示中，但在解决方案中隐藏三个技术缺陷，我希望你在了解细节后会发现这些缺陷。请尝试找到尽可能多的内容，并在评论中尽可能多地提出自己的修复建议。
首先从博弈论的角度来看 QSAT。不失一般性，假设一个量化的布尔句子（没有自由变量的公式）写在前面，所有量词；首先是一些存在量化的变量，然后是一些普遍的，然后是另一个存在的块，依此类推。第一个玩家通过将特定的布尔值分配（替换）给前几个存在量化变量（到整个第一个块，仅当替换后的公式从最左边的全称量词开始时才停止。然后玩家 2 处理全称的第一个块量化同样；然后玩家 1 继续进行最初存在量化的第二个块，依此类推。如果公式在指定所有变量后计算为“真”，则玩家 1 获胜；
如果您假设对公式进行了一些编码，那么这个 QSAT 游戏也可以以数字方式进行，这样每个公式都有基于语法的唯一编号（这样就可以有效地从公式中确定数字，也可以从数字中确定公式）。玩家将交换数字（公式代码），而不是交换公式。
现在想象一下，我们想要将这个类似 QSAT 的游戏转换为您的棋盘游戏。每行代表一个玩家的移动（代表一个相同类型的量词块）。行中的每个位置将代表该玩家从前一行的任何位置可能的移动；更具体地说，移动产生的数字差异：移动后的公式代码减去移动前的公式代码。这样，在游戏的给定阶段，总和总是等于公式。
作为一个特殊的例外，通过进一步减去公式的代码来修改最后一行的所有位置true。这样，如果玩家 1 获胜，则完成的棋盘游戏的总和将为 0，否则为非零。这是减少棋盘游戏量化公式重言式的期望。[剧透 1 结束]