最近我和一位非编码人员就国际象棋电脑的可能性进行了讨论.我不太懂理论,但想想我已经足够了解.
我认为不存在确定性的图灵机总是在国际象棋中获胜或陷入僵局.我认为,即使你搜索了玩家1/2移动的所有组合的整个空间,计算机在每一步决定的单一动作都是基于启发式的.基于启发式,它不一定能击败对手可以做的所有动作.
相反,我的朋友认为,如果计算机永远不会做出"错误"动作,那么计算机将永远胜出或结合(但是你定义了吗？).然而,作为一名采用CS的程序员,我知道即使你的好选择 - 给予明智的对手 - 也会迫使你最终做出"错误"的动作.即使你知道所有事情,你的下一步行动也是贪婪地匹配启发式.
大多数国际象棋计算机都试图将可能的最终游戏与正在进行的游戏相匹配,这本质上是一个动态的编程追溯.同样,有问题的最后阶段是可以避免的.
编辑:嗯......看起来我在这里乱了一些羽毛.非常好.
再考虑一下,似乎解决像国际象棋这样的有限游戏没有理论上的问题.我认为国际象棋比跳棋更复杂,因为胜利不一定是数字耗尽,而是通过配偶.我最初的断言可能是错误的,但我认为我已经指出了一些尚未得到令人满意的证明(正式).
我想我的思想实验是,无论何时树中的分支被采用,那么算法(或记忆路径)必须找到对手移动的任何可能分支的配偶路径(不进行交配).在讨论之后,我会购买比我们可能梦想的更多的内存,所有这些路径都可以找到.
我有时会编写程序来玩棋盘游戏.基本策略是标准的alpha-beta修剪或类似的搜索,有时通过终结游戏或开放的常用方法来增强.我主要使用国际象棋变体,所以当需要选择我的评估功能时,我会使用基本的国际象棋评估功能.
但是,现在我正在编写一个程序来玩一个全新的棋盘游戏.我如何选择一个好的甚至是体面的评估函数？
主要的挑战是相同的棋子总是在棋盘上,因此通常的材料功能不会根据位置而改变,并且游戏的播放次数不到一千次左右,所以人类不一定玩得太多还没有给出见解.(PS.我考虑过MoGo方法,但随机游戏不太可能终止.)
游戏细节:游戏在10×10的棋盘上进行,每侧固定6个棋盘.这些作品具有一定的运动规则,并以某种方式相互作用,但没有任何一块被捕获.游戏的目标是在棋盘上的某些特殊方块中放置足够的棋子.计算机程序的目标是提供与当前人类玩家竞争或更好的玩家.
artificial-intelligence machine-learning game-theory evaluation-function alpha-beta-pruning
在"缺陷预防实用指南"中,作者提到,提高软件开发效率的一种创新方法是实施"生产力游戏",员工之间的竞争方式类似于获得Stack Overflow上的声誉和徽章.
他们给出的一个例子是微软"Vista内部Beta 1游戏",其中团队成员被要求执行任务,这将给他们写一封拼写为"beta 1"的信.他们得到这些信件:
他们有一个网站跟踪每周的排行榜.作者描述了结果:
beta 2游戏扩展了概念并为测试活动颁发了积分.有多种级别的奖品和随机图纸,玩家可以根据参与情况获得腕带.在某些情况下,腕带成为会议和走廊的象征,刺激了竞争.
这些游戏最终在公司范围内发布的发布游戏中达到高潮.奖品是基于完成安装和某些测试活动的人的随机图纸.再一次,结果是惊人的,公司的大多数人参与了测试Windows Vista的最后几天.
有没有人在贵公司实施或参与类似的事情？怎么样？什么进展顺利,什么没有成功？
PS请不要对Vista有任何讽刺性的评论,因为它仍然是Windows 7的主要核心,我认为游戏理念有一些优点.
更新:添加赏金以获得更多想法.在赏金周结束后,我会接受最有趣的一个.我正在寻找可以由20多人的开发团队完成的实用想法.
更新2:看起来Facebook有一个" 推动业力 " 的元游戏,以确定谁的提交通常是好的.
在游戏2048中,假设玩家在最佳位置进行最佳播放并平铺产卵,那么可以实现的最大平铺是什么？
天真的我会说最大可实现的瓷砖是65536 * 2 = 131072因为看起来最好的电路板如下:
4 4 8 16
256 128 64 32
512 1024 2048 4096
65536 32768 16384 8192
但我不确定是否
(对不起,如果我应该问game.stackexchange,但这更像是一个CS问题,而不是游戏中的一个)
在Hangman游戏中,贪婪的字母频率算法是否等同于最佳获胜机会算法？
为了更好地猜测正确的答案,有没有值得牺牲保留你的剩余生命的情况？
进一步澄清问题:
动机:这个问题的灵感来自http://www.datagenetics.com/blog/april12012/index.html上的有趣讨论
他们提出了一种最佳地解决单词游戏"Hangman"的算法.
他们的策略可以这样概括(编辑以供澄清):
在每一个阶段,我们都在猜测最大数量的剩余可能单词中出现的字母(以前没有猜到).
喜欢这种算法有一些动机 - 我们总是最不可能失去生命.
但是,令我感到震惊的是,这不一定是最好的解决方案:如果我们试图猜测这个词(在一定数量的生命中),那么最常见的字母是最有用的字母并不一定总是这样.区分剩余的可用单词.
不过,我不确定,因为尽可能避免失去生命似乎是恰当的.最佳策略是否会让我们牺牲生命以获得更好的获胜机会？
问题:这种贪婪算法是否等同于最佳获胜机会算法？你能证明吗？
一个示例字典+游戏将是理想的显示反证.
我最近来到了Gambit - http://www.gambit-project.org/doc/index.html--一个C++算法游戏理论API.
有人知道.NET游戏理论库吗？
我没有学过博弈论,但它让我很着迷.我的直觉是大多数"企业应用"开发人员都没有使用它.但是,它显然与大型在线网站(例如推荐系统)相关,并对SO产生巨大影响.
您是否在日常项目中应用了任何博弈论原理？如果是这样,原则是什么？
我使用 Python/Numpy 中的函数来解决组合博弈论中的问题。
\nimport numpy as np\nfrom time import time\n\ndef problem(c):\n start = time()\n N = np.array([0, 0])\n U = np.arange(c)\n \n for _ in U:\n bits = np.bitwise_xor(N[:-1], N[-2::-1])\n N = np.append(N, np.setdiff1d(U, bits).min())\n\n return len(*np.where(N==0)), time()-start \n\nproblem(10000)\n然后我用 Julia 编写它，因为我认为由于 Julia 使用即时编译，它会更快。
\nfunction problem(c)\n N = [0]\n U = Vector(0:c)\n \n for _ in U\n elems = N[1:length(N)-1]\n bits = elems .\xe2\x8a\xbb reverse(elems)\n push!(N, minimum(setdiff(U, bits))) \n end\n \n return sum(N .== 0)\nend\n\n@time problem(10000)\n …我在编程竞赛(安德鲁·斯坦克维奇竞赛21)中遇到一个关于如下游戏的问题时遇到了困难:
尼克和彼得喜欢玩以下游戏[...].他们在一张纸上绘制一个无向二分图G,并将一个标记放在其顶点之一上.之后他们轮流行动.尼克先行动.
移动包括沿着图形边缘移动令牌.之后,在移动之前令牌所在的顶点以及与其相关的所有边缘都将从图形中移除.没有有效动作的玩家输掉游戏.
给出了图表,现在的任务是找到给定的起始节点,如果两个玩家都以最佳方式玩,则起始玩家是赢还是输.总结一下
由于图表是二分图,Nick(第一个玩家)将始终从左侧移除一个节点,Peter将始终从右侧移除一个节点.
图表最多可以有1000个节点(最多500每侧)和50000个边缘,所以需要一个很好的多项式时间算法(这里的时间限制为2秒解决所有首发位置,但我认为我们可以分享很多不同起始位置之间的信息).
我很确定这可以简化为某种顶点覆盖或打包问题,因为图是二分的,但我找不到与这些相关的策略.
我知道一个特殊情况的解决方案:假设两侧分别有n 1和n 2个顶点.如果匹配大小为min(n 1,n 2)并且如果较小侧的玩家开始,则存在获胜策略:他只需跟随匹配的边缘并自动获胜.
有任何想法吗？
我们有一片生树的森林.两个玩家根据以下规则进行交替移动:一个动作是切割顶点及其所有子节点.进行最后一次移动(没有顶点)的玩家获胜.
我们如何为游戏中的位置计算Grundy函数？
假设我们有树木,我们需要说明目前的位置是赢还是输？