专栏首页arxiv.org翻译专栏位置博弈与QBF:纠错编码(CS LO)
原创

位置博弈与QBF:纠错编码(CS LO)

位置对策是一类包含Tic-tac-toe及其推广的两人对策的数学类。我们提出了一种新的量化布尔公式(QBF)编码方法,使得当且仅当对应的公式为真时,博弈实例允许第一个博弈者的获胜策略。我们的方法在多个方面比以前的游戏QBF编码有所改进。首先,它是通用的,让我们编码其他位置游戏,如十六进制。第二,位置游戏的结构特性以及对非法移动的仔细处理让我们生成了更紧凑的实例,这些实例可以通过最先进的QBF求解器更快地解决。我们通过大量实验证实了后一个事实。最后,我们的新编码的紧凑性使得翻译现实的博弈问题成为可能。我们发现了一些具有历史意义的问题,并将它们作为越来越困难的里程碑提交给QBF社区。

原文题目:Positional Games and QBF: The Corrective Encoding

原文:Positional games are a mathematical class of two-player games comprising Tic-tac-toe and its generalizations. We propose a novel encoding of these games into Quantified Boolean Formulas (QBF) such that a game instance admits a winning strategy for first player if and only if the corresponding formula is true. Our approach improves over previous QBF encodings of games in multiple ways. First, it is generic and lets us encode other positional games, such as Hex. Second, structural properties of positional games together with a careful treatment of illegal moves let us generate more compact instances that can be solved faster by state-of-the-art QBF solvers. We establish the latter fact through extensive experiments. Finally, the compactness of our new encoding makes it feasible to translate realistic game problems. We identify a few such problems of historical significance and put them forward to the QBF community as milestones of increasing difficulty.

原文作者:Valentin Mayer-Eichberger

原文地址:https://arxiv.org/abs/2005.05098

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于大脑接口的残疾人轮椅控制系统一种先进和可行的方法(CS HC)

    本文介绍了利用电子眼图(EOG)信号构建一种高效可行的基于脑机接口的轮椅控制系统的研究进展。 该系统利用眼睛的运动作为控制轮椅运动的目的元素。 皮肤表面电极被放...

    用户7095611
  • 以动能为基础,确保学习动态系统的稳定性(CS RO)

    非线性动力系统是一种紧凑、灵活、有力的反应运动生成工具。 动态系统的有效性依赖于它们精确表示稳定运动的能力。 为了从演示中学习稳定和准确的运动,已经提出了几种方...

    用户7095611
  • 系统级预测维修: 研究文献综述和差距分析(CS AI)

    本文从系统的角度回顾了当前预知维修领域的文献。 我们区分现有的能力,状态估计和故障风险预测目前应用于简单的组件,从能力需要解决相同的任务复杂的资产。 系统级分析...

    用户7095611
  • 第5篇:对ATAC-Seq/ChIP-seq的质量评估(二)——ChIPQC

    第4篇:对ATAC-Seq/ChIP-seq的质量评估(一)——phantompeakqualtools

    生信技能树
  • 中科院步态识别技术:不看脸 50米内在人群中认出你!

    如果你觉得好的话,不妨分享到朋友圈。 导语:新华社北京10月2日电(记者董瑞丰)中国科学院自动化所的专家日前介绍了一种新兴的生物特征识别技术——步态识别:只看走...

    IT派
  • url编码本质

    其实url本质就是将中文字符串进行utf8编码,然后得到编码后的对象转换字符串去掉开头的b'以及末尾的',然后再将\x转换成%,再将里面内容x变成e最后将字符串...

    小小咸鱼YwY
  • 使用深度神经网络回归在移动应用程序上预测寄宿房租赁价格(CS CY)

    寄宿房是人们最重要的需求,尤其是对于住在远离城市、原籍或住所的大学生。然而,我们现在看到的问题是印度尼西亚的学习场所分布不均,其中75%的最顶尖教育机构来自爪哇...

    毛艺漩8078803
  • 文献阅读: ABLUP-GBLUP-SSGBLUP模拟数据比较

    全基因组选择, 参考群需要建多大, 这篇文章用实际数据和模拟数据证明, 参考群至少要有500才有效果. 另外, 多性状SSGBLUP比单性状SSGBLUP要好....

    邓飞
  • 多插槽多核服务器上内存密集型工作负载的近线性操作系统调度优化 (CS)

    多插槽多核服务器用于解决计算中的一些重要问题。远程 DRAM 访问可能会影响在此类服务器上运行的某些应用程序的性能。本文提出了一种新的近线性操作系统(OS)调度...

    孙孙孙
  • 2018 TCO Algorithm-Round 1B 600-points题解报告

    Consider the set of integers between 1 and n, inclusive, and two positive intege...

    海天一树

扫码关注云+社区

领取腾讯云代金券