NYT Engineer Models Puzzle Difficulty Using Reinforcement Learning

NYT工程师利用强化学习建模字谜难度 尽管大语言模型取得了更高的整体解题率，但强化学习求解器为多层语义字谜提供了关键的可解释性。 Shafik Quoraishee 对《Connections》展开了详细分析，解释了其棋盘机制、系统性难度，以及为何单纯依靠语义向量距离无法破解其中的多层语言陷阱。通过类比系统1和系统2的认知处理过程，他将该谜题构建为一个增强图着色问题，并阐明了他设计的定制求解器架构。该系统将结构化词汇图（WordNet 与 ConceptNet）与关系图卷积神经网络（R-GCNN）相结合，并采用了包含部分得分与惩罚奖励的强化学习框架。他最后展示了强化学习智能体如何在语义超空间中导航，并指出尽管人类编辑对于创作高质量谜题而言依然不可或缺，但定制的强化学习模型为深入理解 AI 推理过程与莫拉维克悖论（Moravec's paradox）提供了关键的可解释性。 《纽约时报》的资深游戏与机器学习工程师 Shafik Quoraishee 指出，尽管开展了 AI 求解器研究，《纽约时报》的所有谜题（包括《Connections》）仍完全由编辑人工设计，以保持其细微语感与逻辑连贯性。 (0:04) 《Connections》利用四级难度与注意力误导机制测试推理能力；纯靠随机猜测破解 16 词初始面板的概率仅为 6300 万分之一，极难通过暴力破解完成。 (3:53) 该游戏在计算上被形式化建模为扩展图着色问题，单纯依赖向量相似度不足以解题，需综合成语、词法形态与一词多义等多维关系对齐。 (12:18) 为避免纯黑盒 Transformer 自注意力机制，求解器结合 WordNet 与 ConceptNet 构建概念语义图，并采用关系图卷积神经网络（R-GCNN）配合强化学习（RL）来分析图拓扑结构并学习解题路径。 (21:05) 虽然强化学习模型解题性能目前未超越顶尖大语言模型（LLM），但其提供了更优的可解释性；演讲者计划后续脱敏并开源部分依赖非内部 API 的代码版本。 (33:44)

In an independent research project, New York Times engineer Shafik Quoraishee models the popular word game Connections as an augmented graph coloring problem, pairing relational graph neural networks with reinforcement learning. While high-capacity large language models achieve strong benchmark results, Quoraishee argues that a graph-based reinforcement learning architecture provides critical interpretability into complex semantic reasoning that black-box systems obscure. Framing Connections as Graph Coloring (12:18) Quoraishee models Connections—where players must partition a grid of 16 words into four mutually exclusive groups of four—as an augmented graph coloring problem, a classic NP-complete computer science challenge. In this formulation, words represent graph nodes, categories correspond to target colors, and edges reflect categorical relationship strengths. Human players often rely on intuitive "System 1" pattern matching that falls victim to deliberate red herrings and attentional decoys, whereas success requires slow, deliberate "System 2" reasoning to verify alternate group structures. Combinatorial analysis demonstrates why brute-force guessing is impossible under the game's four-mistake limit. Starting from a full 16-word board, guessing the four correct partitions at random yields a 1 in 63 million chance (effectively 0%). Once one category is resolved (12 words remaining), the odds improve to 1 in 5,775 (~0.0173%), and after solving two categories (eight words remaining), the chance of a correct random guess rises to 1 in 35 (~2.86%). Capturing Complex Lexical Relationships (14:41) A central finding of the research is that standard vector embeddings like Word2Vec or BERT are insufficient on their own, prompting Quoraishee's observation that "simple similarity is not all you need." Daily puzzles frequently hinge on multi-layered linguistic properties that cosine distance misses, including polysemy, meronymy (part-to-whole relationships), wordplay morphology, and pop-culture trivia. To move beyond surface-level proximity, Quoraishee constructs a handcrafted conceptual semantic graph combining Princeton's WordNet for formal hierarchical synsets and ConceptNet for real-world relational properties (such as "used for" or "chased by"). Using pairwise similarity matrices, he derives categorical coherence scores to quantify puzzle difficulty across easy, medium, and hard tiers. Multi-dimensional radar charts map geometric coherence profiles, creating structured inputs that enable algorithms to evaluate diverse relationship types systematically. Relational Graph Learning and Reward Mechanisms (27:11) The solver's core architecture integrates a Relational Graph Convolutional Neural Network (R-GCNN) with a reinforcement learning agent. The R-GCNN analyzes structural graph neighborhoods and edge weights to propose candidate groupings, while the RL agent navigates these structures to evaluate word clusters. Both components learn simultaneously through a unified backpropagation loop, trained on a difficulty-stratified dataset to prevent overfitting on simple boards. The RL agent's reward function directly mirrors human game constraints: +1 point for a correct four-word group, a completion bonus for clearing the board, penalties for incorrect guesses, and partial credit for identifying three out of four correct words ("one away"). Under the hood, the network clusters the 16 words into the four target groups while maintaining a transient fifth "uncertainty" cluster to hold ambiguous words until relational metrics resolve their placement. Interpretability, Benchmark Limits, and Editorial Curation Although the RL solver performs well, Quoraishee acknowledges it does not surpass the raw solve rates of frontier large language models. However, he emphasizes that black-box LLMs conceal how decisions are made, whereas the graph-RL framework provides interpretable performance metrics and structural transparency. He notes that the challenge aligns with Moravec's paradox, where AI easily handles complex calculations but struggles with subtle, intuitive human word associations. Quoraishee emphasizes that his model is specialized for Connections and would likely fail broad abstraction benchmarks like ARC-AGI, while search methods such as Monte Carlo Tree Search remain difficult to apply due to multi-layered semantic ambiguity. Furthermore, he clarifies that The New York Times does not use AI to design official Connections puzzles; synthetic boards were created exclusively to train the solver, as automated puzzle generators consistently fail to reproduce the nuance and cohesion of human editorial curation. Quoraishee emphasizes that these findings represent preliminary personal research rather than official New York Times initiatives, with all evaluations conducted strictly on English-language boards. Future work will investigate reward hacking to lift solve rates and involve decoupling the codebase from internal proprietary APIs to publish an open-source version with a constrained board set.

《纽约时报》资深游戏与机器学习工程师Shafik Quoraishee在一项独立初步研究中指出，热门文字游戏《Connections》具备极高的组合复杂性与多层级语义歧义，单纯依靠表面词向量或暴力搜索无法有效破解；通过将其建模为增强型图着色问题，并融合结构化语义图谱与强化学习驱动的关系图卷积神经网络（R-GCNN），能为分析复杂语义陷阱和评估AI可解释性提供全新路径。 组合爆炸与多维语义的解题挑战 (9:17) 《Connections》由编辑Wyna Liu人工设计，自2023年上线后迅速成为《纽约时报》仅次于《Wordle》的第二大热门游戏。每期谜题提供打乱的16个单词，要求玩家严格划分为4组各含4个关联词的独立类别，且仅允许累计4次错误猜测。Quoraishee的组合数学计算显示，面对初始16词时，盲目纯随机猜中全部4组的概率仅为6300万分之一（约等于0%）；当解出第1组剩余12词时，随机猜中剩余分组的概率为5775分之一（约0.0173%）；解出前2组仅剩8词时，盲猜成功率升至35分之一（约2.86%），这常成为受挫玩家在终局前实施最后一搏的实际概率。 游戏采用黄（最直接）、绿、蓝、紫（最抽象且多含文字游戏）四级色标区分难度，其核心挑战在于大量“注意力诱饵”。Quoraishee指出，标准词嵌入仅能捕捉浅层向量距离，面对一词多义、同义词、部分与整体关系（meronymy）、字形变换（如易位构词）以及通俗文化百科知识时表现乏力，因而简单相似度不足以解题，算法必须综合考量跨维度的多层级语义矩阵与关系对齐。 认知机制映射与图着色建模 (12:18) 在计算形式化上，Quoraishee将该游戏映射为经典的NP完全问题——增强型图着色问题（Augmented Graph Coloring）。在模型中，棋盘上的16个单词被表征为16个图节点，4个隐藏的正确分类对应4种目标色标，节点间的边则代表词对之间分类关联的有效性与强度。求解算法通过动态评估边连接权重，驱动全图收敛并准确划分为4个彼此分离且内部高度凝聚的连通子图。 这一计算架构同时映射了心理学中的双重过程理论。人类解题时往往交替运用直觉驱动、易受模式误导的“系统1”（快速捕捉直观组合，但极易跌入出题人预设的红鲱鱼诱饵陷阱），以及深思熟虑、分步验证的“系统2”（仔细审视潜在结构，但可能因过度推演而错失直白答案）。Quoraishee指出早期的GPT-4o等模型更偏向系统1式的次标记预测，在复杂字谜中表现受限；现代慢速推理模型与图算法则通过显式模拟系统2的推演验证，有效提升了对抗语义欺骗的能力。 知识图谱与强化学习架构设计 (21:05) 为避免过度依赖不透明的黑盒Transformer自注意力机制，Quoraishee构建了专有的人工概念语义图。他整合了普林斯顿大学的WordNet以解析层次化同义词集与词汇属性，并引入ConceptNet捕捉诸如“被追逐”、“用于”等现实常识关系，再将这些显式拓扑结构与Word2Vec、BERT等稠密词向量深度融合。为防止求解器在简单谜题上过拟合，研究基于一致性热图得分构建了涵盖易、中、难难度的分层数据集，确保模型适应多变的数据分布。 求解引擎的核心由关系图卷积神经网络（R-GCNN）与强化学习（RL）智能体直接耦合而成。机制类似于倒立摆（Cart-Pole）平衡控制系统，RL智能体通过环境试错学习长期累积奖励的最大化。在统一的学习循环中，R-GCNN分析图局部邻域并追踪聚类形态演变，将棋盘转换为候选输出图；RL智能体在此结构上导航评估词汇关联，并通过联合误差反向传播促使两个组件同步向正确解收敛。 奖励机制、聚类表征与泛化界限 (31:08) RL智能体的探索行为由严格的反馈函数规范：每正确解出一组4词分类奖励+1分，清盘获得通关积分奖励；非法或错误猜测施加负向惩罚；若选中4词中的3个，系统会给予“仅差一步”（one away）的部分信用奖励，完全复刻了真实游戏机制。神经网络隐层聚类可视化显示，系统在尝试形成4个解聚类的同时，还会动态析出一个“第5聚类”，专门用于存放信息不确定性高的模糊词汇，直至一致性指标足够清晰时再行归类。 Quoraishee承认，尽管该模型在结构透明度与度量可解释性上具备优势，但绝对解题表现并不一定超越高参数量的前沿大语言模型。这反映了莫拉维克悖论（Moravec's paradox），即AI系统在形式化推理上表现出色，却常在人类凭直觉即可处理的常识语境中陷入困境。此外，该求解器针对游戏图结构高度特化，难以直接应对ARC-AGI等通用抽象测试；而在词义多义性高度交织的情境下，蒙特卡洛树搜索（MCTS）等传统搜索策略也面临极高的模拟复杂度。 Quoraishee总结强调，《纽约时报》始终由人工编辑进行全流程谜题创作，第三方使用AI生成字谜的尝试普遍缺乏人工设计的微妙趣味与逻辑连贯性，因此内部并无转向AI出题的计划。该项研究为个人探索性质，测试数据全量基于英文棋盘；作者计划在剥离内部API依赖并完成脱敏后开源代码与基准子集，未来拟探索抗奖励黑客机制，并关注图神经网络在通用抽象推理领域的拓展可能。

## Background 本视频由 Ai4 频道发布于 YouTube 平台（2025年8月28日）。视频描述指出，讲者是来自《纽约时报》的高级游戏/机器学习工程师 Shafik Quoraishee，他分享了强化学习（RL）在游戏与科研领域的演进，并深入探讨了如何利用 RL 及游戏理论对《纽约时报》热门拼图游戏 Connections 进行难度分析与求解评估。 ## TL;DR 讲者介绍了通过自然语言处理（NLP）构建一致性评分与热力图，从而量化 Connections 谜题难度的计算方法。接着，他展示了强化学习智能体在受限超空间中进行语义搜索与归类的过程，并将其与大型语言模型（LLM）求解器及莫拉维克悖论进行了对比。在问答环节中，讲者明确表示《纽约时报》不会使用 AI 来创作谜题，同时讨论了蒙特卡洛树搜索（MCTS）的局限性、奖励黑客问题以及未来的开源计划。 ## Atmosphere & style 整场演讲呈现出专业、严谨且极具技术洞察力的学术交流氛围。讲者以接地气的方式将前沿的机器学习理论与风靡大众的日常拼图游戏紧密结合，既有扎实的数据与图表展示，也有对 AI 局限性与人类独特性（如谜题“灵魂”）的深刻思考。在与听众的互动问答中，氛围活跃而真实，展现了高管/工程师在面对复杂技术边界时的坦诚与热情。 ## Key takeaways - [00:04](https://www.youtube.com/watch?v=eGDCir3KELM&t=4s) 讲者 Shafik Quoraishee 是《纽约时报》的资深游戏/机器学习工程师，主要负责移动端及网页端热门游戏（如 Connections、Wordle）的开发与维护。 - [16:51](https://www.youtube.com/watch?v=eGDCir3KELM&t=1011s) 利用自然语言处理（NLP）技术建立“一致性评分”（Coherence Score），通过计算词语在向量空间中的距离来量化 Connections 谜题的真实难度。 - [16:51](https://www.youtube.com/watch?v=eGDCir3KELM&t=1011s) 通过对历史数据的跟踪发现，简单与高难度拼图在词语一致性得分上存在显著差异，并曾通过数据排查出因数据库缺少记录而导致的分数异常点。 - [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) 强化学习（RL）模型通过在受限超空间（constrained hyperspace）中搜索词语间的语义关联，来形成候选分组并泛化至新游戏面板。 - [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) 尽管 RL 求解器的解题成功率高于基线模型但不及 LLM，其核心价值在于可解释性，能避免 LLM 作为“黑盒”缺乏透明度的缺点。 - [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) Connections 求解器的表现体现了莫拉维克悖论：AI 在复杂计算上极其卓越，但在人类直觉化的常识判断与语义理解上却面临挑战。 - [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 《纽约时报》不会使用 AI 来自动创作 Connections 谜题，因为大模型生成的谜题缺乏人类编辑设计的深度双关语、隐喻与巧妙陷阱。 - [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 由于 Connections 中词语语义相似度与歧义性层次极深，直接应用蒙特卡洛树搜索（MCTS）等搜索策略容易因状态空间过大而失效。 - [37:16](https://www.youtube.com/watch?v=eGDCir3KELM&t=2236s) 当前 RL 模型仍处于初步阶段，尚未深入解决“奖励黑客”（Reward Hacking）问题，这将是提升求解正确率的后续优化重点。 - [37:16](https://www.youtube.com/watch?v=eGDCir3KELM&t=2236s) 由于现有代码直接调用了《纽约时报》内部 API，讲者计划在重构解耦并去除敏感依赖后，于年内开源精简版项目。 ## Detailed walkthrough ### [00:04](https://www.youtube.com/watch?v=eGDCir3KELM&t=4s) 讲者介绍与《纽约时报》Connections 游戏背景 讲者 Shafik Quoraishee 是《纽约时报》（The New York Times，简称为 The Times）的一名游戏与机器学习工程师（Senior Games/ML Engineer）。他在团队中主要负责移动端（Mobile）的游戏开发与维护，涵盖《Connections》、《Wordle》等热门游戏平台与网页应用。在加入《纽约时报》之前，他曾先后在 Business Insider、NBA、MTV 以及美国国防部（Department of Defense）工作，拥有扎实的机器学习、移动开发和数据科学背景。 根据视频转录内容，以下是为您整理的详细且忠实于原意的内容记录： ### [016:51] 基于自然语言处理与连贯性评分评估 Connections 谜题难度 在分析《纽约时报》的 Connections 游戏时，可以通过自然语言处理（NLP）技术建立热力图（Heat Map）与综合评分，以此衡量一期谜题整体是偏向混淆迷茫还是逻辑连贯。具体而言，该方法通过计算词汇在 NLP 向量空间中的关联距离等指标，将其融合成一个最终的“难度评分”。玩家在遇到极具挑战性的谜题时，往往会好奇其真实难度，而这套方法正是试图以严谨的计算手段为谜题难度提供科学量化依据。 主讲人以 2023 年的一组真实数据为例，对比了“简单谜题”与“困难谜题”的差异### 自然语言处理与 Connections 拼图的难度量化 为了以计算上严谨的方式评估《纽约时报》 Connections 拼图的真实难度，演讲者展示了如何利用自然语言处理（NLP）技术来构建“一致性评分”（Coherence Score）。通过计算词语在 NLP 向量空间中的相互距离与关联度，可以生成热力图并汇总出一个综合分数，用来定量描述整个拼图究竟是倾向于清晰连贯，还是充满误导与混乱。当玩家在某天遇到一道极其棘手的拼图时，这套量化指标能够从科学角度精确解释这道题到底有多难。 以 2023 年的数据为例，将简单拼图与高难度拼图进行对比，可以明显看出不同难度拼图在四大词语类别中的一致性得分存在显著差异。通过对跨时间的类别一致性进行持续追踪，能够观察到系统性的模式与波动。在展示的趋势图谱中，演讲者特别指出在去年 12 月 12 日出现了一个分数为零的异常掉落点；经后台排查，这并非数学计算异常，而是由于数据库中缺失了当天的拼图数据，导致系统拉取到了破坏的记录。 在建立了一致性分析的基础上，进一步扩展出多维度的关系对齐（Multi-dimensional Relational Alignment）。演讲者使用极坐标下的雷达图（Radar Chart）将不同一致性维 ### [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) 强化学习在超空间中的搜索与 Connections 求解器评估 演说者通过展示智能体在受限超空间（constrained hyperspace）中的动态尝试过程，解释了强化学习（RL）模型是如何在 Connections 游戏面板中寻找合适词语分组的。每当智能体成功在当前面板找到正确的词组归类后，它就必须将这套类似的泛化推理机制应用到全新的游戏面板中。 ``` +-------------------------------------------------------+ | 超空间 (Hyperspace) | | [ 词语向量 A ] --- 连结 --- [ 词语向量 B ] | | | | | | v v | | ( 语义相似度计算) ------------> ( 候选分组形成) | +-------------------------------------------------------+ | v +-------------------------+ | 强化学习智能体 (Agent) | | 尝试寻找最优词语分组 | +-------------------------+ | v +-----------------------------+ | 应用相同推理机制至新面板 | +-----------------------------+ ``` 在展示完算法运行机制后，演讲者针对模型的成功指标进行了评估。虽然该 RL 模型的总体解题成功率超过了基线模型（baseline），但其表现依然赶不上大型语言模型（LLM）求解器。即便如此，演讲者强调了开发 RL 求解器的独特价值：LLM 虽然功能强大，但本质上仍属于“黑盒”（black box），难以直观呈现内部的推理过程与决策边界。 - **超空间分组（Hyperspace Grouping）：** 智能体在受限空间中不断探索词语间的语义关联，从而得出最合理的四词分组。 - **与 LLM 求解器的对比：** LLM 在 Connections 解题上表现优异，但透明度不足；RL 方法能够提供更可解释的决策轨迹。 - **莫拉维克悖论（Moravec's Paradox）：** AI 在人类认为极其困难的复杂计算与分析任务上表现卓越，但在人类感觉极其直观、简单的自然认知或常识判断上却显得笨拙异常（如 ARC-AGI 基准测试所展示的现象）。 ### [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 问答环节：AI 生成谜题、ARC 校验与搜索策略 在 Q&A 环节中，有听众提问《纽约时报》（The New York Times）是否会尝试使用 AI 来自动生成 Connections 谜题。演说者明确表示不会用 AI 来创作谜题。尽管许多外部团队尝试过利用大模型生成 Connections 游戏，但生成出来的谜题总是“缺少了某种灵魂”，质量与趣味性无法与人类编辑创作的谜题相提并论。演讲者补充道，自己仅在构建合成数据集（synthetic dataset）时会使用 AI 生成谜题，以便针对连贯性得分（coherence scores）训练模型。 针对听众提出的“模型能否通过 ARC-AGI 测试”这一问题，演讲者坦言自己的 RL 模型是专门针对 Connections 游戏的图结构（graph problem）高度定制的（bespoke），因此大概率无法通过 ARC 测试。不过，针对 ARC 测试使用图神经网络（Graph Neural Networks, GNN）构建自定义求解器确实是一个非常有前景的方向。 此外，现场还深入讨论了基于搜索（search-based）的解法，例如蒙特卡洛树搜索（MCTS）： - **AI 生成谜题的局限：** 现有的 AI 很难生成具有深层双关语、隐喻及巧妙陷阱的高质量 Connections 谜题。 - **蒙特卡洛树搜索（MCTS）的难点：** 在 Connections 中，词语间的语义相似度（semantic similarity）与歧义性（ambiguity）具有极深的层次结构，直接应用 MCTS 容易因状态空间过于庞大且语义模糊而失效，必须设计极度复杂的模拟环境。 ### [37:16](https://www.youtube.com/watch?v=eGDCir3KELM&t=2236s) 奖励黑客攻击、开源计划与总结 在谈到强化学习训练中的常见隐患时，演讲者指出当前模型尚未深入探讨或解决“奖励黑客”（Reward Hacking）问题。由于现阶段模型仍处于非常初步的开发阶段，后续可能会考虑引入防范奖励黑客的机制，以进一步提升求解正确率。 关于代码与数据集的开源计划，演讲者解释道，由于当前实验直接调用了《纽约时报》内部的 API 来获取游戏面板数据，因此暂时无法将完整代码公开。演讲者计划在今年晚些时候将代码进行解耦与清洗（clean up），删除对内部 API 的依赖，并在非敏感的受限数据集上将部分代码和模型开源。最后，演讲者确认目前测试的所有游戏面板均基于英文词汇，并在全场的掌声中结束了本次演讲。 - **奖励黑客（Reward Hacking）：** 智能体可能利用奖励函数的漏洞采取非预期手段提高得分，这是下一阶段优化的重点方向。 - **开源计划（Open Source Plans）：** 计划于年内重构代码，脱敏并解耦内部 API 后，向公众开放精简版的 Connections 求解器项目。 - **测试语料范围：** 当前所有训练与测试面板均限定在英文语境下。 ## Notable quotes > [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) 莫拉维克悖论（Moravec's Paradox）：AI 在人类认为极其困难的复杂计算与分析任务上表现卓越，但在人类感觉极其直观、简单的自然认知或常识判断上却显得笨拙异常。 — Shafik Quoraishee > [33:44](https://www.youtube.com/watch?v=eGDCir3KELM&t=2024s) LLM 虽然功能强大，但本质上仍属于“黑盒”（black box），难以直观呈现内部的推理过程与决策边界。 — Shafik Quoraishee > [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 生成出来的谜题总是“缺少了某种灵魂”，质量与趣味性无法与人类编辑创作的谜题相提并论。 — Shafik Quoraishee > [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 现有的 AI 很难生成具有深层双关语、隐喻及巧妙陷阱的高质量 Connections 谜题。 — Shafik Quoraishee > [35:08](https://www.youtube.com/watch?v=eGDCir3KELM&t=2108s) 在 Connections 中，词语间的语义相似度与歧义性具有极深的层次结构，直接应用 MCTS 容易因状态空间过于庞大且语义模糊而失效。 — Shafik Quoraishee > [37:16](https://www.youtube.com/watch?v=eGDCir3KELM&t=2236s) 由于现阶段模型仍处于非常初步的开发阶段，后续可能会考虑引入防范奖励黑客的机制，以进一步提升求解正确率。 — Shafik Quoraishee > [37:16](https://www.youtube.com/watch?v=eGDCir3KELM&t=2236s) 计划于年内重构代码，脱敏并解耦内部 API 后，向公众开放精简版的 Connections 求解器项目。 — Shafik Quoraishee ## Mentioned Shafik Quoraishee, The New York Times, Connections, Wordle, Business Insider, NBA, MTV, Department of Defense, ARC-AGI, MCTS (Monte Carlo Tree Search), GNN (Graph Neural Networks) ## Video description Shafik Quoraishee, Senior Games/ML Engineer, The New York Times Abstracts Reinforcement learning has recently once again surfaced as one of the most important paradigms in machine learning and AI. In this presentation I'll be discussing the power of RL and how it has evolved into a ground breaking technique that been used to do everything from advance the ability of AI to play games, to autonomously develop mind blowing advancements in medical research and technological innovation alike. I will also do a deep dive into the now world famous game Connections, and how I used reinforcement learning techniques to analyze and the intricacies of the game. This is done to demonstrate its resilience in being solved by even some of the most powerful AI techniques. From that point forward I want to extend my RL analysis into the realm of Game theoretics and AI against a number of our other games and help to demonstrate how the New York Times logic and puzzle games reveal interesting nuances being game theory in general. [Source](https://www.youtube.com/watch?v=eGDCir3KELM)

[33:44] Shafik Quoraishee: 莫拉维克悖论（Moravec's Paradox）：AI 在人类认为极其困难的复杂计算与分析任务上表现卓越，但在人类感觉极其直观、简单的自然认知或常识判断上却显得笨拙异常。 [33:44] Shafik Quoraishee: LLM 虽然功能强大，但本质上仍属于“黑盒”（black box），难以直观呈现内部的推理过程与决策边界。 [35:08] Shafik Quoraishee: 生成出来的谜题总是“缺少了某种灵魂”，质量与趣味性无法与人类编辑创作的谜题相提并论。 [35:08] Shafik Quoraishee: 现有的 AI 很难生成具有深层双关语、隐喻及巧妙陷阱的高质量 Connections 谜题。 [35:08] Shafik Quoraishee: 在 Connections 中，词语间的语义相似度与歧义性具有极深的层次结构，直接应用 MCTS 容易因状态空间过于庞大且语义模糊而失效。 [37:16] Shafik Quoraishee: 由于现阶段模型仍处于非常初步的开发阶段，后续可能会考虑引入防范奖励黑客的机制，以进一步提升求解正确率。 [37:16] Shafik Quoraishee: 计划于年内重构代码，脱敏并解耦内部 API 后，向公众开放精简版的 Connections 求解器项目。

[2:39] Shafik Quoraishee: the AI lives in my head. [3:53] Shafik Quoraishee: I got everything else, and maybe everything I didn't get is in purple. [14:41] Shafik Quoraishee: simple similarity is not all you need. [16:51] Shafik Quoraishee: science says it's about this hard

[0:04] I'm going to start off by asking uh how [0:07] many people here play connections. [0:10] [Music] [0:12] All right, great. It's good to know. [0:14] It's a good start. So, um what I'm going [0:17] to be talking today about is uh the [0:19] title AI and a case study on our the New [0:24] York Times connections. So uh yeah and [0:28] because this is an AI conference [0:29] obviously I've kind of found a way to [0:32] intersect the two things but uh the [0:35] point is connections is still humanmade. [0:38] It's a puzzle made uh you know by our [0:41] editors and I'll get into that and the [0:43] history of all that in a little bit. So [0:46] uh let me just make sure I can control [0:49] this. Okay, great. So a little bit about [0:51] me. Um I'm a game developer at the New [0:54] York Times. I I work on connections um [0:57] Wordle uh in just a number of our [1:00] platforms like I uh and my team work to [1:03] build these games out and provide them [1:05] in our games app and on the website and [1:08] in other places and I'm mostly working [1:10] on the mobile side of things. Um [1:12] previously I worked for Business [1:13] Insider, the NBA, MTV and the Department [1:16] of Defense. Um I have a background in [1:20] machine learning, mobile development and [1:22] uh some data science but uh mostly in uh [1:25] machine learning and core mobile [1:26] development. So that's uh my uh main [1:29] background and there's some of my [1:30] information. So just a few caveats to [1:32] the work that I'm going to be talking [1:33] about. Um this is all my own independent [1:36] research and experimentation uh and not [1:39] currently specifically based on our [1:41] times internal research. Uh we do have [1:43] internal research that we uh do on a lot [1:46] of things including um our games [1:48] playability and uh user case studies and [1:51] things like that but this is a little [1:53] different. Um the result results of this [1:55] work are preliminary and subject to [1:57] refinement uh with additional [1:59] experimentation. So this is an ongoing [2:01] project [2:03] and uh again this is mostly [2:05] investigatory for me and this started uh [2:08] a while ago because I was interested in [2:11] overall the difficulty of connections as [2:15] human players experience it and you know [2:17] how it applies to AI and that's been [2:19] studied a bit as I'll get into already [2:21] but um you know uh there's a few papers [2:25] there's several there's benchmarks that [2:27] are out there um and I didn't, you know, [2:30] use any of that. This is all my own [2:32] work, but I did use some inspiration [2:33] from those to kind of uh kind of like [2:36] push this forward. So, again, for those [2:39] who haven't played, which there are a [2:41] few uh connections is uh was launched by [2:44] the Times in 2023 and officially [2:47] released uh in August of 2023. Uh beta [2:50] in June and release in August. Uh the [2:52] game is edited by Winnoo who's awesome. [2:55] She's a editor that I work with. She [2:57] writes the puzzles and yeah, they're [2:59] they're great. Uh and it uh quickly [3:02] became one of our most played games, [3:04] second only to Wordle with hundreds of [3:06] millions of plays within the first year. [3:08] And uh just to emphasize once again, all [3:10] connection puzzles and the game itself [3:12] are humanmade. All right, so that's not [3:14] where the AI lives. The AI lives in my [3:16] head. All right, so um how connections [3:19] work just for the the people who haven't [3:20] played it before. Uh each uh daily [3:23] puzzle provides 16 words to be grouped. [3:25] So there's a visualization in case [3:27] anyone wants to see the game being [3:29] played. Uh well, but in this case, I [3:32] knew the puzzle ahead of time. Uh the [3:34] goal is to form four groups of four [3:36] related words. Each group belongs only [3:38] to one group, no overlaps, and players [3:41] can make up to four incorrect guesses [3:43] before losing. So uh once you win, you [3:46] you can see the entire board filled out [3:48] and then you'll get a celebratory toast [3:50] and all is happy in the world. [3:53] So basically u anybody who plays [3:56] connections knows that the game is [3:57] difficult in certain ways right um in [4:00] some some days it's more difficult than [4:02] others uh but if you're familiar with at [4:04] least the highle difficulty that we talk [4:06] about the categorical difficulty um you [4:10] know that uh colors of categories [4:12] corresponds to how challenging a [4:14] particular word association group is [4:16] right so uh the yellow colors are the [4:19] easiest stuff the things that are very [4:20] easily groupable right like fruits, [4:23] colors, etc. Um, green slightly less [4:26] obvious, but still conceptually clear. [4:29] Um, they're so green and yellow, you [4:31] know, they're usually the easier [4:32] categories, right? Uh, but then when you [4:35] get to the blue categories, uh, or the [4:37] blue the words that fall into the blue [4:39] category, they're trickier. They're more [4:41] like idiomatic lexical themes. Uh, the [4:44] lexical, uh, tricks are involved in [4:46] solving them. Some of them are trivia [4:47] based, right? So, you know, movie, [4:49] trivia, movies could fall into a [4:51] category and they could also be words. [4:53] They could confuse. And then obviously [4:55] purple, right? Purple is the challenging [4:58] category. And that's the one everyone [4:59] kind of is like, well, you know, I got [5:01] everything else and maybe everything I [5:03] didn't get is in purple. Um, so that's [5:05] the difficulty structure. So, um, why is [5:09] connections interesting uh in relation [5:11] to AI? So, [5:14] uh, connections can challenge AI's [5:16] ability to, uh, figure out non obvious [5:19] relationships, uh, and of non-obvious [5:23] lexical relationships in words. Well, if [5:25] you've ever again played connections, [5:26] you know that some word groups don't [5:28] seem to make any sense, right? You're [5:29] like, "Oh, I don't know why these fit [5:31] together at all, and I'm really [5:32] frustrated. I'm going to post on Twitter [5:34] about it." Um, but that's AI also [5:38] traditionally had the same problem. And [5:39] I say traditionally because it's not [5:42] been too many years since people were [5:43] trying to do this. Uh the game's [5:45] attentional decoys test whe whether AI [5:48] can avoid overfitting and superficial [5:49] similarities. So can AI avoid the same [5:52] things you know people do by thinking [5:54] groups of words that look like they can [5:56] fit in the same category are actually of [5:58] the category that uh the game solves for [6:02] the game. Uh, and again, um, the nice [6:06] thing about like AI and playing with a [6:09] game like connections, the game is still [6:11] conceptually straightforward, right? [6:13] Even though the, uh, the words [6:15] themselves and the connections between [6:17] the words are complicated. Um, you can [6:20] sort of use this as a test to determine [6:22] whether AI will behave a certain way [6:24] when it comes to lexical groupings of [6:26] words. So what you see on the right is [6:27] just uh me adding a GPT uh adding a [6:32] connections board to GPT40 and GPT40 [6:35] solving it um not solving it actually [6:38] and so uh essentially what I'll say is [6:41] that obviously we know models have come [6:43] quite a way since 40 and uh the later [6:46] models are able to solve connections [6:48] mostly still not perfectly across 100 [6:50] all 100% of all puzzles but still [6:53] generally better than people but for a [6:55] long time even the the higher level [6:56] models had trouble uh solving the harder [7:00] puzzles. And I'll get into puzzle [7:02] difficulty in a little while, so we can [7:04] we can sus that out a bit. But um so uh [7:08] I guess the uh thing that we'll go into [7:11] first is like how people kind of solve [7:13] the game. Now, this isn't an exact [7:15] analogy, but this will give you an idea. [7:17] If anyone has heard of like system one, [7:19] system two thinking, it's a, you know, a [7:21] concept popular in pop psychology, in [7:24] psychology. Um so the idea is that if [7:26] you're a system one thinker or if you're [7:28] using a system one proc system one [7:30] thinking uh to solve a process what [7:33] you're doing you're looking at like [7:35] patterns you're doing like quick [7:37] analysis and you're like oh this all [7:38] makes sense right like so uh there [7:41] there's some if there's some obvious [7:43] grouping of words like fruits you're [7:45] like looking for things like oranges [7:46] bananas um uh and the first thing that [7:48] comes to your mind fits into that [7:50] category that oh these are these are all [7:52] obviously fruits so you're using your [7:53] system on thinking Um and I'm again [7:56] trying to draw analogy here. Uh system [7:58] two thinking is like slow and deliberate [8:01] thinking which is more step by step. Uh [8:03] which is like now I have to actually not [8:06] look at obvious things. I have to think [8:08] more about the underlying mechanism of [8:10] what's happening. And usually when [8:12] you're thinking about a problem or most [8:14] people are thinking about a problem, [8:15] they're using some sort of hybrid uh [8:17] between system one and system two [8:18] thinking where they're like okay this [8:21] looks obvious but then is obvious the [8:23] right answer? let me think deeper. And [8:25] then sort of like, you know, sort of [8:27] like failure modes really, not really [8:29] failure, but like for example, if you're [8:31] if you're like not in the game, uh able [8:34] to pick out the harder category, you're [8:36] probably employing you could have been [8:37] employing too much system one thinking [8:39] thinking, "Oh, I'm going to try for the [8:41] obvious relationship." Or, uh, let's say [8:44] that you were thinking too much about [8:45] the obvious relationship and you're [8:47] like, "This is too obvious. Let me pick [8:48] something else." And then it's actually [8:50] was the obvious relationship, then you [8:52] were overthinking it. So that's kind of [8:54] system one fast thinking versus slow [8:56] thinking uh you know colloially speaking [8:59] and you can also if you're uh if you're [9:01] familiar with reasoning models you can [9:03] also think about how this applies to [9:05] reasoning versus in old LLMs that were [9:08] pre-reasoning they were like next word [9:10] prediction right like fast uh response [9:13] versus slow thoughtout response [9:17] um so there are studies on connections [9:19] out there and benchmarks exist they're [9:21] not the time specific specific [9:22] benchmarks or time specific studies but [9:25] a lot of the studies can be found on the [9:27] public archives papers of past [9:29] connections puzzles being used uh for [9:31] benchmarking purposes. Um the reason [9:34] benchmarks are important because they uh [9:36] evaluate uh they enable consistent [9:38] solver accuracy to be tested and um a [9:41] lot of other things like uh things that [9:44] about like how how well a system is at [9:47] reasoning and obviously everybody here [9:49] is in a in the AI world and you're [9:51] familiar with the familiar AI benchmarks [9:53] and creating a benchmark is is a pretty [9:56] commonplace thing these days um and so [9:59] many studies have used real puzzles to [10:02] evaluate LOM and algorithmic [10:04] performance. So there's solvers that are [10:06] not al not LLM based solvers and then [10:08] there are LLM based solvers out there. [10:10] Um but there's studies that attempt to [10:13] do analyze the performance of both. You [10:14] can find those on Google and again um as [10:17] of 2020 at this at this point in time [10:20] from my understanding uh not every [10:22] puzzle can be solved perfectly. Uh but [10:24] you know I think we're pretty close that [10:26] we're like s considered saturation if [10:28] we're going to officially consider that. [10:30] But at the same time uh the idea that [10:33] what I'm doing here is more an interest [10:36] project and I wanted to I'll draw a [10:38] parallel later towards the end as to you [10:40] know why I went through all of this. So [10:43] in the theory of connections [10:45] so uh this little graph here graphic uh [10:49] kind of demonstrates if has anyone tried [10:52] to solve the game randomly like when you [10:53] really don't have a clue. Okay. Um so [10:57] you're like oh I don't know what's going [10:58] on. So, if you're ever interested, uh, [11:01] if you tried to solve the game randomly [11:02] from the get-go because you really [11:04] didn't see any relationship and you're [11:05] just like, I'm going to pick random [11:06] categories of words, you have a one, [11:09] according to the combinotaurics of the [11:11] game, which there are combinotaurics [11:13] associated with it, you have a 1 in 63 [11:15] million chance of uh, solving the game, [11:19] like winning the game. So, that's [11:20] basically zero. Now, let's say you get [11:22] one category correct and then the rest [11:24] of the words are all random. like you're [11:25] like, "Oh, I'm just going to guess [11:26] randomly because the rest of the [11:28] categories I can't figure out." Then at [11:30] that point, you have a one in about five [11:33] 6,000 chance or a.173 [11:36] point. 00173% chance of beating the [11:39] game. Uh if you're guessing randomly [11:42] with the remaining two categories and [11:44] now the more realistic situation, you've [11:46] solved three categories and or you solve [11:48] two categories and then you're in the [11:50] final two categories and you're like, I [11:51] don't know what fits in what. So now I'm [11:53] really just going to guess randomly. And [11:55] now we're in the realm of what other [11:57] people are doing. And you actually have [12:00] if you do that a one in about 3% chance. [12:02] Yeah, you have about a 3% chance like [12:04] one over 35 3% chance of solving the [12:08] game. Which is actually a realistic [12:09] chance like if you if you're like [12:11] desperate and you're like I can't think [12:12] of this. I'm just going to solve it [12:13] randomly. Um so uh has anyone heard of [12:18] graph coloring before? Is a concept. [12:20] Okay. All the computer science folk [12:22] here. Um so uh there's the problem [12:24] called the graph coloring problem which [12:27] is a famous problem in computer science [12:29] which is basically taking a [12:31] computational graph and saying that um [12:34] I'm going to color the nodes in this [12:35] graph such that uh no two adjacent nodes [12:39] and what we mean by adjacent is that two [12:41] nodes are connected by an edge are going [12:44] to be the same color. Okay. Um and as [12:46] the visualization demonstrates the [12:48] attempt to color a graph on the right [12:50] with a few uh about three colors. So [12:54] common algorithm for solving graph [12:56] coloring. There's back backtrack [12:58] backtracking algorithms, greedy [12:59] algorithms, all kinds of like dynamic [13:01] programming algorithms that you can use [13:03] to solve a coloring uh scheme. [13:06] And uh again graph coloring has [13:10] applications in all kinds of uh all [13:12] walks of computational life including [13:14] like if you're trying to figure out [13:16] optimal like schedules or college [13:18] schedules or um if you're in a compiler [13:20] and you're trying to figure out which [13:21] registers get allocated so that no two [13:23] registers are um conflicting in their [13:25] memory uh allocation or uh if you're [13:28] trying to assign frequency uh capping in [13:30] uh of bands in wireless networks and [13:33] then this got cut off but it says and [13:35] now connections. So um what I tried to [13:38] do was try to say that connections can [13:41] be sort of formulated as an augmented [13:43] graph coloring problem. Uh what that [13:45] means is that the each of the 16 words [13:47] in a connections puzzle is represented [13:49] as a node. Right? So um and this uh [13:52] solver I created on the right will [13:54] demonstrate solving a connections board [13:57] according to the coloring process. [13:59] Right? And so it goes through several [14:00] boards and tries to create coloring [14:02] associations. Um, so again, you have the [14:05] hidden categories that the words belong [14:07] to are represented by the four distinct [14:09] colors. So once it's solved, I I created [14:12] the colors that you're familiar with [14:14] associated with the game in the solver. [14:16] And the goal is to color each word node [14:18] with one of four category colors. [14:21] And the edge can the edge between the [14:25] two two things that are connected can be [14:27] thought of as uh the two things being in [14:30] the same category. Okay, so that's just [14:32] more like of a um you know just to frame [14:36] the problem in attempting to build a [14:38] solver to solve it. So one of the things [14:41] that everybody knows about when playing [14:42] the game is that there's the concept of [14:45] uh uh simple semantic similarity is not [14:47] enough. It's uh almost analogous to [14:50] attention is all you need. Well, simple [14:52] similarity is not all you need. Um so [14:55] what you do have to understand here is [14:57] that there's lots of different word [14:59] relationships, right? Um so you can have [15:02] uh relationships that are like and let [15:04] me bring it up because my vision is not [15:06] the best here. Okay. So you have you [15:10] have word relationships like um you have [15:12] synonyomy which is you know words that [15:14] are similar to each other. You have [15:15] meonomy which is words that are like [15:18] contain parts of other words. You have [15:20] morphology like for example anagrams [15:22] words that are mixed together. That [15:24] could be an entire connections category [15:26] right. Um uh you could have other kinds [15:29] of things that are encyclopedic [15:30] knowledge, right? For example, like um [15:32] what is like uh movies, things that are [15:36] uh movie titles. Um and you could have [15:39] uh polyme words that have multiple [15:41] meanings. So like the word bass or bass [15:43] could mean a fish or it could be a bass [15:46] drum or it could be a bass guitar, [15:48] right? Uh so um the the idea is that [15:51] semantic relationships are mapped out [15:53] and are actually fairly complicated and [15:55] they have this they can be structured in [15:57] this treel like uh situation here. So [16:00] how do we make use of that in if we're [16:02] like trying to do some sort of AI [16:04] solver? Well um if we're trying to do [16:06] that there's this idea of which there's [16:09] this idea of categorical coherence or [16:11] what I call it as relational alignment. [16:13] You'll see it called coherence if you [16:15] look up papers, but it's also called I'm [16:17] calling it alignment here. Um, and what [16:20] that means is that uh how well do uh two [16:24] words and if you can see there's this [16:25] like matrix on the right like of several [16:27] words and uh they're lined up against [16:30] other words. How well those words [16:33] associate based on different similarity [16:35] type scores, right? So you can have [16:37] things like cosine similarity, you can [16:40] have several other similarity scores, um [16:42] jakard similarity, etc. I'm not going to [16:45] go through all of them, but the point is [16:46] that uh the idea is that um you because [16:51] you can create this sort of heat map, uh [16:53] you can create a sort of aggregate score [16:56] that determines how confusing really or [16:59] coherent the game is overall. So if [17:01] you're ever like I want and this is [17:03] again using natural language processing [17:05] techniques um in order to do things like [17:08] distance of words associated with each [17:10] other in in NLP space or in some sort of [17:12] space uh or uh and again um you can [17:17] combine these into a a final score that [17:19] says this is kind of how hard the puzzle [17:22] is, right? If you're ever curious like [17:24] one day you're playing a really hard [17:25] puzzle and you're like, "Wow, this is [17:27] this is tough. I I don't know. I I want [17:29] to know exactly how hard it is. And then [17:31] you go through some of these and you [17:32] could be like, "Oh, okay. Well, science [17:34] says it's about this hard." Um, it's not [17:36] that straightforward, but the idea is [17:38] that I want to be computationally [17:39] rigorous when I'm talking about these [17:41] kinds of problems or mostly rigorous. [17:44] So, here's an idea like I have an easy [17:46] puzzle. This was taken from 2023. I [17:49] forgot what day. Um, compared to a hard [17:52] puzzle. Uh and the hard puzzle was uh [17:55] you know the hard puzzles are like [17:56] really hard like um but the idea is that [18:00] uh I computed uh one of the coherence [18:02] scores that I created against of the [18:05] easy puzzle versus the hard puzzle and [18:06] you can see that there's a difference uh [18:08] in each category right because a [18:10] connections game has four categories [18:12] right so each category can have a [18:15] coherence score associated with that [18:16] particular category um and then again [18:19] you can look at categorical coherence [18:21] over time to see patterns [18:23] um as you can see that you know it sort [18:25] of fluctuates except on like December [18:28] 12th of last year where that's actually [18:30] a broken puzzle. So I was computing from [18:32] our puzzle data and that was missing in [18:34] the database. So that was you can yeah [18:37] that was zero. Um but yeah essentially [18:40] there's patterns that can be derived [18:42] from considering coherence parameters or [18:44] coherence properties and you can you can [18:46] get flexible you can create different [18:48] kinds of scores for this. So um what's [18:51] interesting now because you can create [18:52] different scores is that you can have [18:54] multi- multi-dimensional relation [18:57] alignments meaning that I can have [18:59] scores that are uh I can create sort of [19:03] like visualizations which uh give me a [19:06] sort of um smearing or like a sort of [19:08] basis vector space for how much of uh a [19:12] particular score is contained within a [19:15] particular grouping of words. So if [19:17] you've ever has that has anyone is [19:18] people are familiar with radar charts [19:20] how they work. Okay. So these are like [19:22] radar charts on the right like they're [19:24] sort of I animated them out for [19:26] different categories of coherence and um [19:29] these the rel relational alignment can [19:31] vary cost dimensions um again like [19:34] forsinkable like idioms tools things [19:36] like that. Um and I created these [19:38] profiles to to deal with that. And just [19:40] again I explained that this is a radar [19:42] chart. And so what this means is that [19:44] because I have these unique surfaces, I [19:46] can try to attempt to have something for [19:49] the AI to detect a pattern. Okay, let me [19:53] just make sure I'm at Okay, so um again, [19:57] now we have multi-dimensional relational [20:00] alignment. We can and we have scores and [20:02] because we have scores, we can create a [20:04] distribution. And so what I did again I [20:07] I'm building solvers and other things [20:09] that calculate these properties against [20:11] some of our boards, some of our real [20:13] board data and some synthetic board [20:14] data. And the idea is to take several [20:17] connection puzzles over time, track [20:19] category frequencies cumulatively using [20:21] a time evolving bar graph. That's this [20:23] thing on the right. So this that this [20:25] blue bar I I I hope at least it kind of [20:28] makes sense. I'm saying that the blue [20:30] bars themselves are different categories [20:32] of uh word semantic complexity or like [20:35] of like existence. So like hyponomy, [20:38] moronomy, etc. And then this uh [20:40] categorical solver is just figuring out [20:43] like you know which uh how many of the [20:46] categories fall into these um into these [20:49] buckets here. So it's almost like a [20:51] histogram sort of. The intent is to use [20:53] this data to assess AI's capability over [20:56] several categories and relationships, [20:58] right? Um, so now now with that I have [21:00] my base data that I can now um apply to [21:03] my solving system. Now now we get to a [21:05] little bit of a like the trickier part [21:08] here, but um so I'm not going to go like [21:10] too deep into this here because I don't [21:12] want to put anyone to sleep, but I again [21:14] I'm I'll see. I'm not practiced at not [21:17] doing that. So we'll see. Um so uh what [21:21] I we start with is the idea of building [21:23] a conceptual semantic graph, right? So [21:26] the idea is that like um at this point [21:29] people are familiar with the transformer [21:31] model right uh without a doubt right the [21:33] LLM the model that makes LM how do how [21:35] do transformer models work to uh create [21:38] like coherent language they essentially [21:41] use self attention right so basically [21:44] you give them a corpus you give them a [21:46] huge corpus they can use you know their [21:48] self-attention mechanism they can derive [21:50] um relationships between words or [21:52] anything that's fed to them uh and they [21:54] can be fine-tuned etc [21:56] etc. But then that's how sort of [21:58] organically the transformer will create [22:00] a sort of word relationship situation. [22:02] So what I tried to do was not that [22:04] necessarily. What I tried to do was use [22:06] um something called wordnet. Um any [22:09] anybody knows what word net is? Has seen [22:10] it? Okay, cool. There's a few word [22:12] netters here. Um so word net is [22:15] basically a dictionary or database of [22:18] hierarchical lexical relationships. It's [22:20] maintained by Princeton. um it contains [22:23] sin sets of words which are like you [22:25] know they have relationships in them and [22:27] so if you ever were interested in [22:29] analyzing like lexical properties you [22:31] can use word net to look at groupings of [22:33] words and that's what I did to help [22:35] establish this uh conceptual semantic [22:37] graph and then there's a you know [22:39] analogous thing I used called concept [22:41] net right which now not only contains [22:44] word categorizations but actually [22:47] contains relationships between words so [22:49] concept net means like I'm using things [22:51] like oh like I have a cat and a cat is [22:54] like chased by a dog right if you look [22:56] at the relationship between dog and cat [22:58] a cat um likes milk right a cat can is a [23:02] type of pet so there's use there's [23:04] relationships here like used for part of [23:06] related to and those are what concept [23:10] net is used what I've used concept net [23:12] to create this sort of semantic graph to [23:14] give understanding to connections uh to [23:16] get to the connection solver that I'm [23:18] working in and I did this again [23:19] deliberately because I wanted to avoid [23:21] using the sort of I don't I you know a [23:24] little bit of the blackbox just [23:25] self-attention mechanism to try to do [23:27] this. This is this is actually more like [23:29] handcrafted right. Um and then of course [23:32] I still use word embeddings so I'm going [23:34] to use like bird like wordtovec etc. And [23:37] that's because I'm I'm doing a bunch of [23:40] things and I not all of it I'm going [23:42] into but I experimented a bit with the [23:44] kind of solver that I tried to build [23:46] here. Um, [23:48] and so let's talk about reinforcement [23:50] learning for a second because that's [23:52] part of the title. Uh, reinforcement [23:55] learning, I think everybody's familiar [23:57] with RL here, right? Yeah. Okay. So re [24:01] reinforcement learning is basically um a [24:05] a type of machine learning or type of [24:07] like AI where uh a system is set to [24:11] learn from interaction with the [24:12] environment such that interaction with [24:15] the environment uh gets progressively [24:17] better over time because the system is [24:19] rewarded for performing better and penal [24:22] penalized for performing worse. So um [24:26] the idea of uh reinforcement learning [24:28] system is to maximize cumulative reward [24:30] over time and uh there's ways to control [24:34] the the reinforcement learning uh [24:36] process. How much it learns, what kind [24:38] of steps it'll take. One of those is [24:40] called a discount factor. Uh so that's [24:42] basically how um you know how a how [24:44] greedy versus not greedy uh the [24:47] algorithm is. Is it like looking at [24:49] short-term ways to improve its uh the [24:51] systems performance or long-term ways to [24:53] improve the systems performance? And [24:55] then um again the learning is completely [24:57] through trial and error. And so this is [24:59] what I used um I created this [25:01] visualization of uh the cart and pole [25:04] problem which is one of the simplest [25:05] reinforcement learning problems out [25:07] there. It's basically you have this cart [25:09] this robotic cart that tries to balance [25:11] a pole. So if you could think of like a [25:13] a clown or something trying to balance a [25:15] pole on their nose, this is the similar [25:17] idea. The idea is that like over time [25:20] the clown starts out pretty bad, but how [25:22] does the clown learn or how does the [25:23] cart learn? It attempts to balance [25:25] itself uh or try adjust itself until it [25:28] stops dropping the pole and eventually [25:31] after it just the intuition is developed [25:33] in how to balance the pole. The same [25:35] with this robotic cart. It makes choices [25:37] and continuously adjusts and uses the [25:40] state of the system which includes lots [25:41] of things like orientation of the pole [25:43] etc. Um that's just a quick primer. So [25:46] like back to connections. See I'm I'm [25:48] jumping around here and there just for [25:49] context. But um so what I wanted to do [25:52] is sort of build like a training set uh [25:55] a test set and validation set etc. But [25:57] like the idea is that I wanted to create [25:59] a sort of uh a sort of grouping of data [26:03] of connections boards via like [26:05] approximate like challenging difficulty [26:08] versus easy difficulty versus medium [26:10] difficulty. And the idea was to make [26:12] sure that I could create sort of a [26:15] stratified set of like a stratified and [26:18] balanced set of all kinds of puzzles [26:20] because the idea is that the solver that [26:22] is being built can you know use [26:25] different strategies. If it's a simple [26:26] puzzle and it it may just be solving the [26:29] puzzle um using like again a system one [26:32] process but if it's like harder then it [26:34] will fail and you want essentially the [26:37] solver to be able to solve everything [26:38] ideally. So we need to create like a [26:40] balanced set. So the solvers intern [26:42] toler mechanics internal mechanics adapt [26:44] to the more um the more complex the more [26:48] widely distributed and balanced set of [26:50] connections boards. So we have all kinds [26:52] here and this is for example why I [26:54] talked about the coherence scores later [26:56] because I wanted to attempt to find a [26:58] difficulty metric to create a balanced [26:59] set of data. Um again the balance is [27:03] ensured through several ways testing the [27:06] model just testing the coherence and you [27:08] know manual testing etc. Um so again uh [27:11] now u moving to that essentially at a [27:14] high level I'll go over what I did here [27:16] but um if anyone's familiar with like a [27:18] graph neural network uh this is a [27:21] particular the solver that I worked with [27:23] is a particular variant of a graph [27:25] neural network called a relational uh g [27:28] uh relational graph convolutional neural [27:31] network um attached to a reinforcement [27:34] learning process. And the idea is to [27:36] figure out how to do several things but [27:38] one of them is like kind of rank the [27:40] similarity uh internally of the of the [27:44] game board against the sort of semantic [27:47] graph that I created so that it can [27:48] understand the connections board better. [27:50] So the idea here is that uh firstly I [27:53] like graphs is is probably apparent. Um [27:56] so that's why I went down this route. [27:58] Secondly, um again framing the [28:01] connections problem as a graph problem [28:03] allows us to kind of like frame the [28:05] problem more in the realm of oh this is [28:07] a we can we can use a a particular [28:10] neural network that's geared towards [28:12] geometrical uh data sets uh to solve the [28:17] uh to solve the connections issue or [28:19] problem or to solve a connections board. [28:22] Um so basically um so again the the way [28:26] a graph neural network works is that [28:27] like essentially it looks at a graph it [28:29] it uh it looks at the neighborhood of [28:32] the input graph area the regions and it [28:36] looks at similar nodes and then [28:37] basically what it does is it figures out [28:40] a an optimal output and you can think of [28:43] it it's the same way similar to how a [28:44] regular neural network works except a [28:46] graph neural network is is your your [28:49] input isn't just numbers it's actual [28:51] like uh structure uh like these [28:53] structured graphs that I showed you [28:54] before. And so um a graph's properties [28:58] include edge weights, node [29:00] representations over time um and then [29:02] like each edge has a similar similarity [29:04] score. So there's lots of things that [29:06] goes along with graphs. Um and again the [29:08] idea we track cluster morphology across [29:10] steps to learn stable partitioning [29:13] patterns. What that means is that the [29:15] structure of the graph is the when I say [29:18] morphology I mean the the structure of [29:20] the graph is uh is learned right the [29:23] optimal output structure for any input [29:25] structure is learned and so convergence [29:28] the the graph will converge to a stable [29:30] output over several iterations. So uh [29:33] maybe like yeah you know like a very [29:36] complicated graph will turn into a [29:38] simpler graph or something. I have some [29:39] visualizations to uh later to show um [29:42] what that kind of looks like from my con [29:45] conception of it. But um again, so the [29:47] idea is that you have this uh graph [29:50] graph system uh graph neural network [29:52] connected to an RL agent and the idea is [29:55] that um the the agent and the graph [29:58] network neural network learn together. [30:00] So they both kind of um attain [30:03] intelligence. The agent the the graph [30:05] learns from input connections boards. it [30:08] it it alters its internal structure to [30:11] another output structure. The [30:12] reinforcement learning agent then kind [30:14] of goes through the graphs the different [30:16] options and tries to figure out the [30:18] different word relationships in a graph [30:20] in in an output graph and then based on [30:22] sort of the error in that it will you'll [30:24] do sort of uh a back propagation kind of [30:27] step um not exactly but some sort of [30:29] combined step in order to have the the [30:32] system learn simultaneously together and [30:34] then converge towards a a correct [30:36] solution. This is just the system [30:38] diagram of that um at a high level and [30:41] again from puzzle input to solution [30:45] output input connections board that's [30:48] mixed up output connections boards [30:49] that's solved properly um another system [30:52] diagram don't need to go too deep into [30:53] that but if you know what I'll do is [30:56] I'll share some handouts or slides later [30:58] and then you can look at kind of the [30:59] highle system diagram there but the [31:01] basically what it is is there just a [31:03] bunch of pieces connected to each other [31:05] um of this different solving parts of [31:07] this AI system. Uh and then we design a [31:10] reward strategy. So the idea is in uh in [31:13] any RL system, you need to figure out [31:15] how to reward the agent, right? The [31:18] agent has to know how to like win the [31:21] game so to speak or what's better. [31:23] Otherwise, the agent will just be [31:24] playing randomly and nothing will [31:26] actually happen. So uh the what I did is [31:29] essentially created like a reward [31:30] metric. So a a full reward and a partial [31:33] reward metric. So um we give like [31:36] essentially these scores are sort of [31:38] arbitrary but I give like a plus one [31:39] score for a completed group and a bonus [31:41] for a full completed board. Um uh we [31:44] penalize we also penalize the agent with [31:46] negative uh illegal for illegal guesses. [31:50] Uh so we give you lower score um you [31:54] know things that are wrong. And um this [31:57] it's a small cost right now per guess in [31:59] the way that the game works. You only [32:00] have four guesses by the way as a as a [32:02] human player. So you can only um you can [32:05] mess up four times and then you'll [32:07] actually uh you'll lose the game. So um [32:10] then the there's a few more details in [32:12] here, but the idea is that um there's [32:15] you can if you get partial if if the [32:17] agent gets partial success, for example, [32:19] they get three words in the same [32:20] category but not four, they still get [32:23] the category wrong but they get a reward [32:26] for it because they were close. This is [32:28] not exactly how a human would learn [32:30] because you don't actually learn the [32:33] three categories until you actually fail [32:35] at the board that the the that the words [32:37] are but you do get like a signal that [32:38] says one away. So you get partial [32:40] credit. So this is sort of a way of [32:41] giving partial credit to the agent. Um [32:44] and then uh and so again there's some [32:48] formulations of the visualizations that [32:50] I did for what the network is kind of [32:52] doing under the hood. essentially is [32:54] trying to cluster into four gra four [32:56] four groups and uh the fifth group you [33:00] see here is sort of what I call like [33:01] anformationally [33:03] uh uncertain group. So these four groups [33:05] on top are like like oh these are like [33:08] where the words tend to cluster into [33:10] that are the correct solutions for the [33:13] connections board and then the fifth [33:14] group is like anything that is like left [33:16] too ambiguous for a particular metric or [33:19] group of metrics to solve. Um [33:22] uh let's see. Okay, again another uh [33:26] visualization of this how this works is [33:28] that uh I and again I created this [33:30] visualization to demonstrate because [33:32] it's a little like it's a little like um [33:34] you know unclear by maybe just [33:36] describing what the visualization is to [33:38] what what this process is to to [33:40] demonstrate how it works. But [33:42] essentially we're creating these like uh [33:44] these hyperspaces here and the agent is [33:47] trying to figure out from the uh [33:49] constrained hyperspace what is the [33:51] appropriate um grouping of words and I I [33:54] added a little motion there essentially [33:56] to be like okay well this is sort of the [33:58] agent trying you know because again once [34:01] the agent sort of figures it out for one [34:03] board then you have it app has to apply [34:05] the similar process for another board. [34:07] Um, okay. And so I'm close to the end [34:09] here. About uh uh 5 minutes left. So uh [34:13] there's some success metrics that I have [34:15] here. And um overall did pretty well. [34:18] Not not as good as necessarily an LLM [34:20] solver. So the idea is why even do that? [34:24] Because LLMs are really good already, [34:26] but they're still black boxes. Um and uh [34:29] if interested in like performance [34:31] metrics and things like that, there are [34:33] um uh repos out there uh that do that [34:36] that are not affiliated with us. Um [34:38] here's some more information. And just [34:41] my last slide is on Moravex paradox [34:43] which says that sometimes AIS are really [34:46] good at doing things. Um and they're bad [34:48] at good at doing things that we are much [34:51] better than us and they're really bad at [34:52] doing things that we're really good at. [34:53] And that's like the idea behind like the [34:55] Arc AGI benchmark and things like that. [34:57] So that's basically my presentation. Um [35:01] does yeah anybody have any questions? [35:08] Okay. So the question was what about [35:10] building a connections puzzle? Correct. [35:12] So um we we would actually not use AI to [35:15] build a puzzle. Um that is an [35:17] interesting challenge in general because [35:20] um building we we found and we've seen [35:22] that people have tried to use AI to [35:24] build connections puzzles but they [35:26] haven't been and you know we've tested [35:27] this with different groups they haven't [35:29] been as sort of like you know successful [35:31] at doing that um because I don't know [35:34] there's something missing I wouldn't say [35:35] I haven't rigorously analyzed that and I [35:37] know it's possible to build a puzzle and [35:39] I do some synthetic data set building [35:41] actually to help you know train the [35:43] model against the coherence scores that [35:44] I'm working with but it's not something [35:46] that that we would ever do, but I you [35:49] know, so I'm not 100% sure. Did I do the [35:52] arc test with my model? I I think the I [35:54] think my model would fail the arc test [35:57] because it's very bespoke to connections [35:59] and this graph problem. But uh I yeah, [36:02] maybe I'll maybe I'll try that. Uh I bet [36:05] there are people who have done uh graph [36:07] neural networks type solutions to create [36:09] custom solvers to the ARC test. Um I [36:12] haven't looked into it, but yeah, that's [36:14] an idea worth a shot. [36:16] a searchbased approach. So you're saying [36:18] like search for search the space of the [36:22] semantic graph for the um this is sort [36:25] of that uh in a way that it's looking [36:28] for relationships that are optimal. Um I [36:32] that's the most search kind of structure [36:34] that I've done. Um there's probably some [36:36] other like things I haven't tried in [36:38] that space. Do you have a a thought as [36:40] to what kind of [36:43] >> Oh, [36:45] sure. Um I I I'm not 100% sure how like [36:48] something like that would perform, but I [36:50] think that like a Monte Carlo research. [36:52] Uh but um I would guess I mean this is [36:55] just like an un sort of semi uneducated [36:57] guess because I haven't played around [36:58] with it in this case but that it there [37:01] would it wouldn't be as straightforward [37:02] um to do that because again the semantic [37:05] similarity and ambiguity is actually [37:08] much deeper layered. Um so it would it [37:12] would have to be a complex simulation to [37:14] solve that. That's my guess. So reward [37:16] hacking. Um no I I actually not not [37:19] really but I it's something to extend [37:22] this uh model to do. Um I again this is [37:26] actually very preliminary. So I I may [37:29] add that to improve the solutions [37:31] because right now like uh my total solve [37:34] rate is actually good against some [37:36] boards better than baseline but still [37:39] not um they can it can still be [37:41] improved. So I might attempt to reward [37:43] hacking too to try to do that. Yeah. Uh [37:46] for this I don't have the I don't have [37:47] the code public for the boards because [37:49] they source our internal APIs. Um but uh [37:52] you know I I I am planning on putting [37:54] some of this public later in the year um [37:57] on like a constrained set of boards that [37:59] um are not using our APIs. I have to [38:01] just decouple all of that and you clean [38:03] it up and make it more publicly [38:05] sanitary. Yeah. Was it all in? Um, the [38:08] all the words that I tested were in [38:09] English because all all of our boards [38:11] are in English or Yeah, I think they [38:12] are. Yeah. Well, I guess that's it. I [38:15] don't see any more hands. So, uh, thank [38:16] you very much. Appreciate it.