用6个六面骰子设计字母颜色组合,能拼出最多单色或彩虹词。
Letters, Colors, and Words: Constructing the Ideal Building Blocks Set
- 用遗传算法优化6个骰子的字母与颜色分配。
- 成功拼出2846个单色或彩虹单词,是现有方法最佳结果。
- 适合对组合优化和语言游戏感兴趣的读者。
定义一个积木块集合为由n个立方体(每个有六个面)组成,每个面分配一个字母和一个来自m种颜色调色板的颜色。我们提出一个新问题:如何为每个面分配字母和颜色,以最大化从选定语料库中可拼出的单词数量,这些单词可以是单色词(所有字母同色)或彩虹词(所有字母颜色不同)。我们研究了从美国14岁青少年常用词汇表中选取的、长度不超过六位字母的英文单词,在n=6且m=6的情况下,且每种颜色在每个立方体上恰好出现一次的约束下。由于解空间过大,暴力搜索不可行,因此我们采用随机搜索、模拟退火、两种树搜索方法(贪心和最佳优先)以及遗传算法求解。此外还尝试了强化学习,但模型未能在约束内收敛。在所有方法中,遗传算法表现最优,共实现2846个单色与彩虹词。
原文摘要 · Abstract (English)
Define a building blocks set to be a collection of n cubes (each with six sides) where each side is assigned one letter and one color from a palette of m colors. We propose a novel problem of assigning letters and colors to each face so as to maximize the number of words one can spell from a chosen dataset that are either mono words, all letters have the same color, or rainbow words, all letters have unique colors. We explore this problem considering a chosen set of English words, up to six letters long, from a typical vocabulary of a US American 14 year old and explore the problem when n=6 and m=6, with the added restriction that each color appears exactly once on the cube. The problem is intractable, as the size of the solution space makes a brute force approach computationally infeasible. Therefore we aim to solve this problem using random search, simulated annealing, two distinct tree search approaches (greedy and best-first), and a genetic algorithm. To address this, we explore a range of optimization techniques: random search, simulated annealing, two distinct tree search methods (greedy and best-first), and a genetic algorithm. Additionally, we attempted to implement a reinforcement learning approach; however, the model failed to converge to viable solutions within the problem's constraints. Among these methods, the genetic algorithm delivered the best performance, achieving a total of 2846 mono and rainbow words.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。