腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >改进的Hangman博弈，最优算法

问改进的Hangman博弈，最优算法
EN

Stack Overflow用户

提问于 2018-11-26 10:09:53

回答 1查看 93关注 0票数 2

计算机现在随机选择其中一个单词，程序应该尽可能少地猜测单词。

在提示之后，计算机给它提供了以下提示

一开始
尾声
包含
不包括

让我们以单词house为例:如果我们猜到"h“，那么我们得到的答案是搜索的单词以"h”开头。如果我们猜到"ous“，我们得到的答案是搜索到的单词包含"ous”usw，如果我们猜到"house“，那么我们得到的答案是我们找到了正确的单词。

对于这个问题，有没有最优的策略？天真的方法是简单地尝试每一个单词。当然，这很糟糕。我想是更好的方法。作为第一小贴士，选择最常见的字母等等。但是我认为你可以更有效地做到这一点。

algorithm

回答 1

Stack Overflow用户

发布于 2018-11-26 14:19:29

是的，有一个最优的策略。然而，该策略取决于求解给定单词列表的游戏树。单词列表是有限的；在每个节点上都有有限的选择；可以配置每个猜测，以保证结果会添加大量的信息，从而使您更接近解决方案。所以，游戏树是有限的。

为给定的词汇(单词列表)构建游戏树。如果您想要有保证的最优攻击，您需要解决游戏树，包括minimax和剪枝。如果您想在较短的时间内找到非常好的攻击，请从决策树的ML (机器学习)区域中提取。

这足以让你朝着解决方案的方向前进吗？

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/53486787

复制

UVA Hangman Judge

c 语言

英语太烂啊。 In ``Hangman Judge,'' you are to write a program that judges a series of Hangman games. For each game, the answer to the puzzle is given as well as the guesses. Rules are the same as the classic game of hangman, and are given as follows: The contest

用户1624346

2018/04/11

7000

用Python写的HangMan游戏

python

选自一本用Python编写自己的电脑游戏一书 import random HANGMANPICS = [''''' +---+ | | | | | | =========''', ''' +---+ | | O | | | | =========''', ''' +---+ |

py3study

2020/01/07

2.2K0

刽子手游戏（Hangman Judge）

游戏

在本题中，你的任务时编写一个裁判程序，输入单词和玩家的猜测，判断玩家赢了（You win）输了（You lose.）

Vincent-yuan

2020/06/15

6880

算法博弈论（一）

游戏

在小罗同学的技术支持下，本公众号开设一个博弈论专栏，不定期更新，无限期拖稿。欢迎大家一起来学习有趣的博弈论。

秃头哥编程

2019/07/04

2.6K0

PSO算法的改进策略

编程算法

PSO（PSO——Particle Swarm Optimization）（基于种群的随机优化技术算法）粒子群算法模仿昆虫、兽群、鸟群和鱼群等的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断改变其搜索模式。

里克贝斯

2021/05/21

1K0

算法Blog之博弈原理

编程算法

博弈入门寻找平衡状态（也称必败态，奇异局势），（满足：任意非平衡态经过一次操作可以变为平衡态）一．巴什博奕（Bash Game）只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1

赵腰静

2018/03/09

9010

博弈论及算法实现

其他

在生活中五子棋也是一种先手有必赢策略的游戏，有人会说五子棋先手我也会输啊，所以博弈论问题都有个类似如“参与者足够聪明”，“两人都不犯错"的前提。在此前提下，讨论几种常见的博弈情形。 {====================} 一、巴什博弈（Bash Game）只有一堆n个物品，两个人从轮流中取出（1~m）个；最后取光者胜。考虑到若n=m+1 那么第一个人不论如何取都不能取胜。进一步我们发现若 n=k*(m+1)+r; 先取者拿走 r 个，那

Angel_Kitty

2018/04/08

1.2K0

KMP算法及其改进算法

数据结构

注意:MP算法中的i不需要回溯这里隐藏着一个考点。i不需要回溯意味着对于规模较大的外存中字符串的匹配操作可以分段进行，读入内存一部分进行匹配，完成之后即可写回外存确保在发生不匹配时不需要将之前写回外存的部分再次读入，减少了IO操作，提高了效率，在回答KMP算法较之于简单模式匹配算法的优势时，不要忘掉这一点。

犰兔

2020/11/20

7090

有趣的算法（七） ——快速排序改进算法

其他

有趣的算法（七） ——快速排序改进算法（原创内容，转载请注明来源，谢谢）一、概述快速排序，被认为是最好的排序算法之一。快速排序是20世纪60年代被提出的，其基本过程如下：现假设长度为n的数组a[n]，需要进行排序。步骤如下： 1）随机选其中一个元素，假设为a[i]，将所有值比a[i]小的元素，移到a[i]的左边，假设为数组b；所有比a[i]大的元素，移到a[i]的右边，假设为数组c。 2）将数组b、c分别递归执行步骤1，即将数组不断的分割成大的半部分和小的半

用户1327360

2018/03/07

1.2K0

链表排序最优算法_链表算法题

c++java 编程算法 https 网络安全

全栈程序员站长

2022/11/07

1K0

DeepMind VS Meta：实现纳什均衡理性最优解，还是多人非零和博弈算法更强大？

游戏强化学习 meta 模型算法

大数据文摘转载自AI科技大本营编译 & 整理：杨阳记得豆瓣高分电影《美丽心灵》中的约翰·纳什吗？作为获得诺贝尔经济学奖的数学家，纳什在博弈论、微分几何学，以及偏微分方程等各个领域都作出卓越贡献。为表彰他在非合作博弈理论中对均衡（纳什均衡）的开创性分析，1994年瑞典中央银行授予纳什诺贝尔经济学奖。纳什均衡在社科中的应用可谓成功，而在科技领域中，也经常引用博弈论的逻辑来进行技术实现，比如，通过密码学和博弈论的结合实现大数据安全。当下，这一逻辑也开始应用在AI的算法上。 DeepNash——Deep

大数据文摘

2023/04/10

4390

DeepMind VS Meta：实现纳什均衡理性最优解，还是多人非零和博弈算法更强大？

编程算法游戏强化学习

DeepMind被谷歌收购之后，一直开启着“败家烧”的模式。不过也着实“烧”出了不少成果。曾经大火的AlphaGo，编程机器人系统Alpha Code，智能体Gato……都是让业界认可的手笔。不过，尽管在AI技术上全面开花，DeepMind仍没有放弃曾经的看家本领——AI棋牌竞技。随着DeepNash的推出，棋牌界出现又一乱入者，因为它超越人类专业棋手的技能，登上了近期的《Nature》杂志。

AI科技大本营

2022/12/10

5000

高斯消去法的算法改进

编程算法

其中括号内的数字表示对该行处理的次数，比如第三列，该列中的第一个元素没有变化，第二个元素处理了一次，第三个元素处理了两次，处理的过程为

fem178

2019/06/11

9470

最优子集回归算法详解

编程算法

最优子集回归是多元线性回归方程的自变量选择的一类方法。从全部自变量所有可能的自变量组合的子集回归方程中挑选最优者。如m个自变量会拟合2m-1个子集回归方程,然后用回归方程的统计量作准则(如交叉验证误差、Cp、BIC、调整R2等指标)从中挑选。

ruochen

2022/01/05

4.1K0

时间衰减流的改进算法

时序数据库 CTSDB

作者：Vladimir Braverman,Harry Lang,Enayat Ullah,Samson Zhou

罗大琦

2019/07/18

1.4K0

粒子群算法及其改进算法

编程算法 https 网络安全

粒子群优化（PSO）算法是Kennedy和Eberhart受鸟群群体运动的启发于1995年提出的一种新的群智能优化算法[1]。大概的意思就是一片森林里有一群鸟在找一块食物，它们不知道食物具体在哪，但是可以通过感官（例如嗅觉）去察觉到自己当前位置距离食物的远近。鸟可以记住自己走过的位置并且知道自己做过的最优位置。这一群鸟的运动都是随机的，这类似于一种穷举法。

全栈程序员站长

2022/08/31

1.3K0

最优化算法之粒子群算法（PSO）

编程算法 https 网络安全 java html

粒子群优化算法(PSO：Particle swarm optimization) 是一种进化计算技术（evolutionary computation）。源于对鸟群捕食的行为研究。粒子群优化算法的基本思想：是通过群体中个体之间的协作和信息共享来寻找最优解． PSO的优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。

全栈程序员站长

2022/06/28

2.6K0

【编程之美】最优排序算法

其他

寻找最大的K个数从n个数中寻找最大的K个数。 01 class 两种思路： 1 保存目前找到的最大k个数，每访问一个数，就与这k个数中的最小值比较，决定是否更新这k个数。储存k个数的数据结构可采用：败者树、二叉查找树、最小堆。 C++ STL提供了multiset和priority_queue容器，另外还提供了make_heap，push_heap，pop_heap方便手动构建堆结构。（测试发现，手工建堆的效率最高，当n和k增大到一定值时，采用红黑树的multiset的效率极差。手动建堆的效率相比prio

程序员互动联盟

2018/03/15

1.2K0

博弈之最大-最小搜索算法

其他

最近正在做一个人工智能的中国象棋，所以不可避免的接触到了博弈论，因为考虑到以后还会有所涉及 (alpha-beta search)，所以写成了一片文章

racaljk

2018/08/31

2K0

机器学习中的最优化算法总结

机器学习编程算法监督学习无监督学习

对于几乎所有机器学习算法，无论是有监督学习、无监督学习，还是强化学习，最后一般都归结为求解最优化问题。因此，最优化方法在机器学习算法的推导与实现中占据中心地位。在这篇文章中，SIGAI将对机器学习中所使用的优化算法做一个全面的总结，并理清它们直接的脉络关系，帮你从全局的高度来理解这一部分知识。

SIGAI学习与实践平台

2018/08/24

6.5K0

相似问题

盈亏博弈中最优期望金额的算法

Hangman博弈机制问题

在博弈中建立最优塔位算法的尝试

硬币博弈的最优策略

JavaScript Hangman博弈中的排序猜测

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问改进的Hangman博弈，最优算法
EN