Nmbr9 作为一个约束编程挑战
我们报告了建模和解决 Puzznic 的进展情况,这是一款需要玩家计划移动序列以匹配方块从而清理网格的视频游戏,我们在没有移动方块的关卡上比较了计划方法和三种约束编程方法在一小组基准实例上的表现,目前计划方法优于约束编程方法,但我们提出了改进约束模型的建议。
Oct, 2023
本文介绍了一种叫做编程谜题的新型编程挑战,以 Python 编程谜题为例,详细讲述了该类谜题的属性,覆盖了从级别不同的变量操作问题到经典的编程问题(例如汉诺塔),再到算法和数学中长期存在的开放问题(例如因子分解)。通过设计基于枚举的编程合成方法、GPT-3 和 Codex 解题器,可以解决这些谜题。Codex 解题器表现最佳,在没有参考解决方案的情况下,单独尝试解决了 397 个测试问题中的最高 18%,1,000 次尝试解决了 80% 的问题,在小规模的用户研究中,发现人类的难度与 AI 解决程序的难度之间存在积极的相关性。因此,进一步改进编程谜题可能对许多程序合成领域产生重大影响。
Jun, 2021
研究表明,通过推广反事实遗憾最小化,我们可以解决一般约束下的最优策略问题,并且该算法可广泛应用于复杂博弈中,如安全博弈中的风险缓解和扑克游戏中的对手建模。
Sep, 2018
研究人员对 Rubik's Cube 进行算法和数学结构的研究,展示了其具有丰富的算法结构和 “上帝数”(配置空间直径)。在 n x n x n Rubik's Cube 中,寻找最短解决方案的问题可以通过 一个渐进最优的算法来解决。同时,研究发现,忽略一些小魔方的位置和颜色,n x n x 1 Rubik's Cube 的解决方案问题将变得极其困难。
Jun, 2011
本文提出了一种神经符号求解器 (NS-Solver),能够显式且无缝地结合不同级别的符号约束,其中包括问题编码器、符号方程式生成器和符号执行器。在四个新辅助任务的帮助下,我们的求解器不仅能够自我监督数字预测任务,还能进行常识常数预测、程序一致性检查和二元学习任务,有助于提高求解器的理解力。此外,我们还构建了一个新的大规模数学问题基准 CM17K,包括四种类型的 MWP (算术、一元线性、一元非线性和方程集),共超过 17K 个样本。对 Math23K 和我们的 CM17K 的大量实验结果表明,与现有最先进方法相比,我们的 NS-Solver 优越性表现出色。
Jul, 2021
通过使用 SAT 方法解决难题视频游戏,我们证明了直接将游戏转换为 SAT 显著超过了现有的先进规划器的性能,主要原因是 SAT 能够轻松建模可达性属性,从而获得更短的解决方案。
Oct, 2023
本文利用 Bidirectional A * 算法及三种启发式算法(曼哈顿距离、线性位差和行走距离)解决了 Fifteen Puzzle 问题,并将这三种启发式算法混合运用,有效减少了算法生成状态数和扩展节点数,大大降低了空间复杂度,保证了最优解或接近最优解。
Jan, 2023
本研究探讨了生成棋盘游戏的有针对性的起始位置的问题,利用符号方法和迭代模拟搜索了巨大的状态空间,发现了多种不同难度级别的状态,可以方便新手玩家的学习和掌握,同时也会带来有趣的游戏变体。
Nov, 2014