ARTICLE DETAIL

资讯详情

深耕网站视觉设计与运营推广的一线实战洞察。

DIGITS 数字猜测游戏:从 1978 年 BASIC 版到多语言移植的模式识别算法剖析

DIGITS 数字猜测游戏:从 1978 年 BASIC 版到多语言移植的模式识别算法剖析 示例工程【免费下载链接】basic-computer-gamesAn updated version of the classic Basic Computer Games book, with well-written examples in a variety of common MEMORY SAFE, SCRIPTING programming languages. See https://coding-horror.github.io/basic-computer-games/项目地址https://gitcode.com/gh_mirrors/ba/basic-computer-games点击查看免费下载导读本文基于 34_Digits/README.md 及其所在仓库的完整源码深入剖析 DIGITS 这款经典猜数字游戏玩家随机写下 30 个 0/1/2 数字计算机则借助三个记忆矩阵和一条加权求和方程实时统计你的数字序列特征并逐位预测下一个数字。你将了解到游戏规则、猜测方程的逐行数学拆解、状态变量的滚动更新机制、原始代码中神秘常量与A恒为 0 的历史怪癖以及同一算法在 BASIC、Python、Java、C#、JavaScript、Perl 中的移植实现差异与运行方式。一、游戏是什么规则与玩法DIGITS 是一个人机对抗的序列预测游戏玩法极其简单玩家先取一张纸随机写下 30 个数字每个数字只能是 0、1 或 2排成三行、每行 10 个计算机分三轮向玩家索要数字每轮 10 个对每个数字计算机总是先猜测再查看玩家给出的真实数字判断自己是否猜中连续 30 次预测之后统计猜中次数判定胜负。游戏的核心悬念在于如果纯粹靠运气0/1/2 各占 1/3计算机 30 次预测的期望命中数是10 次即 1/3。但正如 README 所述It is uncanny how much better it generally does than that!——由于它会对玩家刚输入的数字序列做统计学习实际表现往往远超 10 次这正是本游戏的乐趣所在。README 同时记载了该程序的出处程序起源于达特茅斯学院Dartmouth原作者不详它作为《Basic Computer Games》1978中的经典程序之一被收录原版程序由 Vintage Basic 网站流传而来。完整规则说明也原样保留在各移植版的指令文本中例如 34_Digits/csharp/Resources/Instructions.txt。二、核心算法猜测方程的逐行拆解整个游戏的核心只有一条方程位于原始 BASIC 源码 34_Digits/digits.bas 的第 700 行700 S1A*K(Z2,J)B*L(Z1,J)C*M(Z,J)它对候选数字JJ 0、1、2分别计算一个加权得分S1得分最高的候选即为计算机的猜测。三个加权项分别来自三个记忆矩阵项系数矩阵行索引含义A*K(Z2,J)A 0K(2,2)Z2 上一个真实数字按上一数字统计的历史频率B*L(Z1,J)B 1L(8,2)Z1 最近两位组合编码按最近两位组合统计的历史频率C*M(Z,J)C 3M(26,2)Z 两位历史三进制状态按历史状态统计的历史频率系数 A 0、B 1、C 3 在 BASIC 中通过DATA 0,1,3读取digits.bas。注意C 的权重3远高于 B1即两位历史状态 M 矩阵对猜测的贡献最大这暗示原作者的意图是捕捉数字序列中的二阶bigram统计规律。猜测的选择逻辑digits.bas690 FOR J0 TO 2 700 S1A*K(Z2,J)B*L(Z1,J)C*M(Z,J) 710 IF SS1 THEN 760 720 IF SS1 THEN 740 730 IF RND(1).5 THEN 760 740 SS1: GJ 760 NEXT J即初始S0遍历 J 后取S1最大的 J 作为猜测G若两个候选得分相等平局则抛一枚硬币RND(1).550% 概率随机改选——这是一个让行为不至于死板的随机扰动机制。所有移植版都忠实保留了这一逻辑例如 Python 版 34_Digits/python/Digits.pyif s s1: s s1 my_guess j elif s1 s and random.random() 0.5: my_guess j三、三个记忆矩阵与状态变量3.1 矩阵初始化BASIC 中三个矩阵的初始化digits.bas400 FOR I0 TO 26: FOR J0 TO 2: M(I,J)1: NEXT J: NEXT I M 全部填 1 410 FOR I0 TO 2: FOR J0 TO 2: K(I,J)9: NEXT J: NEXT I K 全部填 9 420 FOR I0 TO 8: FOR J0 TO 2: L(I,J)3: NEXT J: NEXT I L 全部填 3 450 L(0,0)2: L(4,1)2: L(8,2)2 但对角线三项改为 2M27×327 行对应 27 个两位历史状态下文详述每行 3 列对应候选数字 0/1/2初值全部为 1L9×39 行对应两位组合的 9 种编码初值为 3但L(0,0)L(4,1)L(8,2)2三个对角线位置被压低到 2——同样属于 README 所说的看似随意的神秘常量K3×33 行对应上一数字初值全部为 9。3.2 状态变量 Z、Z1、Z2 的滚动更新三个矩阵的行索引不是固定的而是随游戏进程滚动变化的480 Z26: Z18: Z22 初始状态 ... 830 M(Z,N)M(Z,N)1 840 L(Z1,N)L(Z1,N)1 850 K(Z2,N)K(Z2,N)1 860 ZZ-INT(Z/9)*9 等价于 Z Z MOD 9 870 Z3*ZN(U) 三进制左移并入新数字 ... 880 Z1Z-INT(Z/9)*9 Z1 Z MOD 9 890 Z2N(U) Z2 当前真实数字从源码结构可以推断Z 是一个以 3 为底的最近两位数字状态编码。Z 3*a b中a对应倒数第二个数字、b对应最近一个数字取值 0~26每当猜中并观察到新数字N后先取Z MOD 9丢弃最高位再3*ZN并入新数字从而滚动记录最新的两位组合。Z1 Z MOD 9是两位组合的 0~8 编码用作 L 矩阵的行索引Z2就是当前真实数字用作 K 矩阵的行索引。因此三个矩阵实际构成了不同粒度的条件计数表M[Z][j]在历史状态 Z最近两位数字之后出现 j 的次数二阶统计L[Z1][j]在两位组合 Z1 之后出现 j 的次数一阶/二阶折中K[Z2][j]在数字 Z2 之后出现 j 的次数一阶统计。得分方程S1 0*K 1*L 3*M实质是对三个粒度的条件频率做加权投票权重偏向更精细的二阶状态。而权重最高的 M 矩阵之所以初值填 1、L 填 3、K 填 9是一种拉普拉斯平滑式的先验设计——初值越大冷启动阶段对某种数字的倾向越保守。3.3 面向对象版C# 的实现印证C# 移植版将这套逻辑清晰地对象化见 34_Digits/csharp/Memory.cs 与 34_Digits/csharp/Matrix.cs_matrices new[] { new Matrix(27, 3, (_, _) 1), // M27 行权重 3全 1 new Matrix(9, 1, (i, j) i 4 * j ? 2 : 3), // L9 行权重 1对角线 2 new Matrix(3, 0, (_, _) 9) // K3 行权重 0全 9 };C# 版把原来散落在 BASIC 全局变量里的系数 A/B/C内嵌为 Matrix 对象的weight字段3、1、0 分别对应 M、L、K每次猜测时对三个矩阵的加权值求和34_Digits/csharp/Guesser.cs学习更新则集中在ObserveDigit中三个矩阵各自IncrementValue并同步滚动Index对应 BASIC 的 Z/Z1/Z2。这与 BASIC 原版的逐行逻辑一一对应可以作为理解原始方程的最佳带注释版本。四、输入校验与游戏流程每轮输入 10 个数字时程序会强制校验取值范围。BASIC 的写法相当精妙digits.bas570 WN(I)-1 580 IF WSGN(W) THEN 620 只有 N0、1、2 时 W 才等于 SGN(W) 590 PRINT ONLY USE THE DIGITS 0, 1, OR 2. 600 PRINT LETS TRY AGAIN.:GOTO 530即对每个输入数字减 1 后与符号函数比较巧妙地排除了 0/1/2 以外的任何整数非法的整轮输入都会被驳回重输。移植版则改用更直白的范围判断如 Python 版 34_Digits/python/Digits.py 的if number 0 or number 2并在读取时对非数字输入提示!NUMBER EXPECTED - RETRY INPUT LINE。三轮共 30 个数字猜测完毕后进入胜负判定digits.basX 10I GUESSED MORE THAN 1/3 OF YOUR NUMBERS. I WIN.计算机赢BASIC 还会连响 10 声铃CHR$(7)X 10I GUESSED EXACTLY 1/3 OF YOUR NUMBERS. ITS A TIE GAME.平局恰等于纯随机的期望值X 10I GUESSED LESS THAN 1/3 OF YOUR NUMBERS. YOU BEAT ME. CONGRATULATIONS *****玩家赢。随后询问是否再来一局DO YOU WANT TO TRY AGAIN (1 FOR YES, 0 FOR NO)选择继续则重新初始化三个矩阵和状态变量回到第 400 行保证每局之间互不影响。整个游戏主循环在 C# 版中被拆分为GameSeries.Play()与Game.Play()34_Digits/csharp/Game.csGameSeries负责介绍 → 指令 → 循环开局 → 告别Game负责单局的三轮预测结构比原始 BASIC 的 GOTO 网清晰得多。五、移植注意事项神秘常量与 A0 的怪癖README 的 Porting Notes 部分给出了两个重要的移植警示这两点在源码中都能得到印证The program contains a lot of mysterious and seemingly arbitrary constants. Its not clear there is any logic or rationality behind it.The key equation involved in the guess (line 700) involves a factor ofA, butAis always 0, making that term meaningless. As a result, all the work to build and update array K and value Z2 appear to be meaningless, too.其一神秘常量遍地矩阵初值 1/9/3、L 的三个对角线值 2、Z/Z1/Z2 的初始 26/8/2、系数 0/1/3……这些数值从算法层面难以完全解释其设计动机移植时照搬即可不必强行赋予意义。其二A 恒为 0 导致 K 矩阵与 Z2 的更新成为死代码猜测方程第 700 行S1A*K(Z2,J)B*L(Z1,J)C*M(Z,J)中A通过DATA 0,1,3恒定为 0因此A*K(Z2,J)这一项对最终得分永远没有贡献。相应地第 850 行K(Z2,N)K(Z2,N)1对 K 矩阵的更新、以及第 890 行对 Z2 的维护从结果上看都属于无用功。Python 移植版的作者在源码中直接以注释标注了这一发现34_Digits/python/Digits.py# What did the original author have in mind ? # The first expression always results in 0 because a is always 0有趣的是C# 版把 A0 这个怪癖固化进了设计K 矩阵的weight参数正是 034_Digits/csharp/Memory.cs同时在ObserveDigit中仍然忠实执行 K 矩阵的更新与 Z2 的滚动——即移植版完整保留了原始代码的结构与行为包括其无效的部分这对理解原始程序、保持跨语言行为一致而言反而是值得肯定的移植态度。这也解释了为何 README 建议移植者照原样翻译而不是自作聪明地删掉 K 矩阵。六、多语言移植与运行方式DIGITS 是该仓库中移植语言最丰富的游戏之一除原始 BASIC 外至少包含 6 种实现且各版本逻辑逐行对应语言文件特点BASIC34_Digits/digits.bas原始版GOTO 结构RND/CHR$(7)等经典语法Python34_Digits/python/Digits.py函数化拆分附原作者意图注释Java34_Digits/java/Digits.java单文件Digits类printf对齐表格输出C#34_Digits/csharp/Program.csOO 重构Guesser/Memory/Matrix分层文本资源外置JavaScript34_Digits/javascript/digits.js浏览器交互版async/await模拟输入Perl34_Digits/perl/digits.pl1-based 数组技巧0 . $Answer占位各版本的运行方式BASIC使用 Vintage BASIC 等兼容解释器加载 34_Digits/digits.bas 后RUNPythonpython3 34_Digits/python/Digits.py需要 Python 3使用了typing与random标准库Java编译并运行 34_Digits/java/Digits.javajavacjava Digits依赖java.util.ScannerC#dotnet run --project 34_Digits/csharp/Digits.csproj该项目面向 .NET 6.0见 34_Digits/csharp/Digits.csproj并引用仓库公共库00_Common/dotnet/Games.CommonJavaScript直接用浏览器打开 34_Digits/javascript/digits.html在页面中交互Perlperl 34_Digits/perl/digits.pl依赖use strict; use warnings;。七、小结DIGITS 是一个以简驭繁的经典案例30 行规则 1 条加权方程 3 个计数矩阵就让一台 1978 年的计算机具备了超越纯随机的模式识别能力。透过 34_Digits/README.md 的规则说明与移植笔记再对照 34_Digits/digits.bas 及各语言移植版可以清晰看到猜测的本质是对一阶/二阶条件频率的加权投票系数 0/1/3 与矩阵初值构成隐式的先验平滑Z/Z1/Z2是一个滚动更新的三进制历史状态机是整条算法的记忆指针原版代码中A恒为 0、K 矩阵与 Z2 更新无意义属于忠实移植时必须知晓的历史遗留怪癖各移植版尤其 C# 的对象化重构为理解这套算法提供了极佳的可读性增强版本。如果你对让计算机学会猜你的统计游戏感兴趣DIGITS 是一个小而完整的入门样例——既适合作为学习马尔可夫式条件计数思想的练手项目也适合作为跨语言移植对比的基准程序。赞分享示例工程【免费下载链接】basic-computer-gamesAn updated version of the classic Basic Computer Games book, with well-written examples in a variety of common MEMORY SAFE, SCRIPTING programming languages. See https://coding-horror.github.io/basic-computer-games/项目地址https://gitcode.com/gh_mirrors/ba/basic-computer-games点击查看免费下载相关推荐Archon Monorepo 上下文预热指南用 Prime 命令为 AI Agent 建立完整的代码库认知Archon Monorepo 上下文预热指南用 Prime 命令为 AI Agent 建立完整的代码库认知 本文围绕 Archon 仓库中面向编码 Agen示例工程basic-computer-games 的 Bombardment 替代语言移植从 1978 年 BASIC 到 Go 与 MiniScript 的实战剖析basic computer games 的 Bombardment 替代语言移植从 1978 年 BASIC 到 Go 与 MiniScript 的实战剖析示例工程Basic Computer Games 之 Tower从汉诺塔传说看 1978 年经典 BASIC 游戏的多语言移植Basic Computer Games 之 Tower从汉诺塔传说看 1978 年经典 BASIC 游戏的多语言移植 导读 本文围绕经典书籍 Basic C示例工程上一篇深度解析BsMax插件架构3ds Max工作流迁移的3大技术实现优势下一篇FluentValidation 终极指南避免常见错误的15个实用技巧创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表