问题标签 [game-theory]

看完《黑暗骑士》后，我对囚徒困境的概念非常着迷。必须有一种算法可以在特定情况下最大化自己的收益。

对于那些发现这个外国的人：http ://en.wikipedia.org/wiki/Prisoner%27s_dilemma

非常非常有趣的东西。

编辑：问题是，如果有的话，囚徒困境最有效的算法是什么？

我最近在与一位非编码人员讨论国际象棋计算机的可能性。我对理论并不精通，但我认为我知道的足够多。

我认为，不可能存在一个总是在国际象棋中获胜或陷入僵局的确定性图灵机。我认为，即使您搜索 player1/2 动作的所有组合的整个空间，计算机在每一步中决定的单个动作也是基于启发式的。基于启发式，它不一定能击败对手可以做的所有动作。

相反，我的朋友认为，如果计算机从不犯“错误”举动，那么它总是会赢或打平（但是您如何定义？）。但是，作为一个学过 CS 的程序员，我知道即使是你的好选择——给定一个聪明的对手——最终也会迫使你做出“错误”的举动。即使你什么都知道，你的下一步行动是贪婪地匹配一个启发式。

大多数国际象棋计算机试图将可能的最终游戏与正在进行的游戏相匹配，这本质上是一种动态编程回溯。再一次，有问题的残局是可以避免的。

编辑：嗯......看起来我在这里激怒了一些羽毛。那挺好的。

再想一想，解决像国际象棋这样的有限游戏似乎没有理论上的问题。我认为国际象棋比跳棋要复杂一点，因为获胜不一定是通过棋子的数字耗尽，而是通过队友。我最初的断言可能是错误的，但话又说回来，我想我已经指出了一些尚未得到令人满意的证明（正式）的东西。

我想我的思想实验是，每当树中的一个分支被取走时，算法（或记忆的路径）必须为对手移动的任何可能分支找到一条通向配偶的路径（而不是交配）。讨论后，我会购买，因为内存比我们想象的要多，所有这些路径都可以找到。

我正在寻找一个好的算法推荐。

我有用户和成就。用户创建成就，然后将其提供给其他用户。与每个成就相关联的是用户指定的点值。一个用户的总分是他们所有成就的总和。

基本上：

好的，所以这个系统显然非常适合游戏。您可以创建许多帐户并互相取得大量成就。我试图通过将点值缩放到与用户指定的不同的值来减少一点。

1. 假设所有用户都是诚实的，但他们只是很难以不同的方式衡量。我应该如何标准化点值？AKA 一个用户为每个简单的成就给出 5 分，另一个给出 10 分，我怎样才能将它们标准化为一个值。目标是分数与难度成正比的分布。
2. 如果一个用户不擅长判断分值，我如何根据获得成就的用户数来判断难度？
3. 假设用户可以大部分被划分为不相交的组，其中一个用户将成就授予一整套其他用户。这对前两种算法有帮助吗？例如，用户 A 仅向以奇数结尾的用户授予成就，而用户 B 仅向以偶数结尾的用户授予成就。
4. 如果每个人都是恶意的，我能离让用户无法过度夸大他们的积分值还有多远？

注意：给予用户的质量与他获得的成就没有任何关系。许多给予者只是机器人，它们自己没有收到任何东西，但会自动奖励用户的某些行为。

我目前的计划是这样的。我有一个从我那里获得成就的人分配 10 分。如果我总共给 55 人发放了 10 个成就，我的分配是 550。然后根据获得它的人数分配给每个成就。如果分布是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]获得每项成就的人，那么点值将是[50, 25, 16.6, 12.5, 10, 8.3, 7.1, 6.25, 5.5, 5]。

欢迎和赞赏我的方法和替代建议的任何问题。另外，发布您能想到的我错过的其他案例，我会将它们添加到列表中。谢谢！

我有时会编写程序来玩棋盘游戏。基本策略是标准的 alpha-beta 修剪或类似搜索，有时会通过通常的残局或开局方法来增强。我主要玩国际象棋变体，所以当需要选择我的评估函数时，我使用基本的国际象棋评估函数。

但是，现在我正在编写一个程序来玩一个全新的棋盘游戏。如何选择一个好的甚至像样的评估函数？

主要挑战是相同的棋子总是在棋盘上，所以通常的材质函数不会因位置而改变，而且游戏已经玩了不到一千次左右，所以人类不一定会玩够还没有给出见解。（PS。我考虑过 MoGo 方法，但随机游戏不太可能终止。）

游戏详情：游戏在 10×10 棋盘上进行，每边固定 6 个棋子。这些棋子有一定的运动规则，并以一定的方式相互作用，但从来没有一个棋子被捕获。游戏的目标是在棋盘上的某些特殊方格中有足够的棋子。计算机程序的目标是提供与当前人类玩家竞争或更好的玩家。

这本身不是一个编程问题，尽管最终目标是设计一种算法。我正在寻找参考资料或至少是一种游戏的名称。它在电视游戏节目中非常普遍。游戏如下：

您有许多插槽，每个插槽都包含一个您不知道的项目（来自某个有限集合）。您必须猜测每个插槽包含什么。您将您的猜测告诉法官（他知道每个插槽包含什么），他会告诉您有多少猜测是正确的，而不会告诉您哪个。当您成功猜出所有项目时，游戏结束。

我会对有关此类游戏的任何信息感兴趣，包括对以尽可能少的猜测进行求解的算法的引用等。只是名称，以便我可以在谷歌上搜索它也可以。

谢谢！

这将是一个很长的帖子，只是为了好玩，所以如果你没有太多时间最好去帮助人们解决更重要的问题:)

最近在 Xbox 上发布了一款名为“Tower Bloxx”的游戏。游戏的一部分是以最佳方式在场地上放置不同颜色的塔，以最大限度地增加最有价值的塔的数量。我写了一个算法，可以确定最有效的塔放置，但它不是很有效，几乎只是暴力强制所有可能的组合。对于具有 4 种塔型的 4x4 场，它在大约 1 小时内解决，5 种塔型大约需要 40 小时，这太多了。

规则如下： 场地上可以放置 5 种类型的塔。有几种类型的字段，最简单的一种只是 4x4 矩阵，其他字段有一些您无法构建的“空白”。您的目标是在场地上放置尽可能多的最有价值的塔，以最大化场地上的总塔价值（假设所有塔是一次建造的，没有转弯）。

塔类型（按从低到高的顺序排列）：

• 蓝色 - 可以放在任何地方，值 = 10
• 红色 - 只能放置在蓝色之外，值 = 20
• 绿色 - 放置在红色和蓝色之外，值 = 30
• 黄色 - 除了绿色、红色和蓝色，值 = 40
• 白色 - 除了黄色、绿色、红色和蓝色之外，值 = 100

这意味着例如绿色塔应该在北、南、西或东相邻单元格中至少有 1 个红色和 1 个蓝色塔（对角线不计算在内）。白塔应该被所有其他颜色包围。

这是我在 4x4 场上的 4 个塔的算法：

1. 组合总数 = 4^16
2. 循环 [1..4^16] 并将每个数字转换为 base4 字符串以编码塔的位置，因此 4^16 = "3333 3333 3333 3333" 表示我们的塔类型（0=蓝色，...， 3=黄色）
3. 将塔放置字符串转换为矩阵。
4. 对于矩阵中的每个塔，检查其邻居，如果任何要求失败，则整个组合失败。
5. 将所有正确的组合放入一个数组中，然后将该数组按字典顺序排序为字符串，以找到可能的最佳组合（首先需要对字符串中的字符进行排序）。

我想出的唯一优化是跳过不包含任何最有价值的塔的组合。它跳过了一些处理，但我仍然循环遍历所有 4^16 个组合。

有没有想过如何改进？如果在 java 或 php 中，代码示例会很有帮助。

- - - -更新 - - - -

添加更多非法状态后（黄色不能建在角落，白色不能建在角落和边缘，场应至少包含每种类型的塔），意识到在4x4场上只能建造1个白塔并优化 Java 代码，总时间从 40 小时减少到约 16 小时。也许线程会将其缩短到 10 小时，但这可能是蛮力限制。

我没有学过博弈论，但它让我着迷。我的直觉是大多数“企业应用程序”开发人员都没有使用它。但是，它显然与大型在线网站（例如推荐系统）相关，并且对 SO 影响巨大。

您是否在日常项目中应用了任何博弈论原理？如果有，有哪些原则？

支持我们有一个 n * m 表，两个玩家玩这个游戏。他们依次排除细胞。玩家可以选择一个单元格（i，j）并排除从（i，j）到（n，m）的所有单元格，排除最后一个单元格的人输掉游戏。

例如，在一个 3*5 的棋盘上，玩家 1 排除单元格 (3,3) 到 (3,5)，玩家 2 排除单元格 (2,5) 到 (3,5)，当前棋盘是这样的： （O 表示不排除该单元格，而 x 表示排除该单元格）

在玩家 1 排除从 (2,1) 到 (3,5) 的单元格后，棋盘变为

现在玩家 2 排除了从 (1,2) 到 (3,5) 的单元格，只剩下 (1,1) 干净：

所以玩家 1 必须排除唯一的 (1,1) 单元格，因为一名玩家必须在一个回合中至少排除一个单元格，并且他输掉了游戏。

很明显，在 n*n、1*n 和 2*n (n >= 2) 的情况下，先玩的人获胜。

我的问题是，有没有什么策略可以让玩家在所有情况下都赢得比赛？他应该先上场吗？

附言

我认为它与动态规划或分而治之等策略有关，但尚未形成想法。所以我把它贴在这里。

答案

感谢sdcwc 的链接。对于大于 1*1 的牌桌，第一个玩家将获胜。证明如下：（借自维基页面）

事实证明，对于任何大于 1 × 1 的矩形起始位置，第一个玩家都可以获胜。这可以用一个策略窃取论点来证明：假设第二个玩家有一个获胜的策略来对抗任何最初的第一个玩家动作。假设第一个玩家只占据右下角的方格。根据我们的假设，第二名玩家对此有反应，这将迫使胜利。但是，如果存在这样的获胜反应，那么第一个玩家可以将其作为他的第一步，从而迫使胜利。因此，第 2 名玩家无法制定获胜策略。

而策梅洛定理保证了这种制胜策略的存在。

在《缺陷预防实用指南》中，作者提到提高软件开发生产力的一种创造性方法是实施“生产力游戏”，让员工以类似于在 Stack Overflow 上获得声誉和徽章的方式相互竞争。

他们给出的一个例子是微软的“Vista Internal Beta 1 Game”，其中要求团队成员执行任务，让他们得到一个拼写“beta 1”的字母。他们通过以下方式收到这些信件：

• b：安装 beta 1 版本
• e：对 beta 1 版本进行投票
• t：通宵运行
• a：安装 3 个连续的 beta 1 版本
• 1：通宵跑3次

他们有一个网站可以跟踪每周的排行榜。作者描述了结果：

Beta 2 游戏扩展了这一概念，并为测试活动奖励积分。有多个级别的奖品和随机抽奖，玩家可以根据参与获得腕带。在某些情况下，腕带成为会议和走廊上刺激竞争的象征。

这些游戏最终在全公司范围内发行的发行游戏中达到高潮。奖品是根据完成安装和某些测试活动的人的随机图纸。再一次，结果是惊人的，大多数公司都参与了测试 Windows Vista 的最后几天。

有没有人在贵公司实施或参与过类似的事情？过得怎么样？什么进展顺利，什么不成功？

PS 请不要对 Vista 发表刻薄的评论，因为它仍然是 Windows 7 的主要核心，我认为游戏理念有一些优点。

更新：增加赏金以获得更多想法。赏金周结束后，我会接受最有趣的一个。我正在寻找可以由 20 多人的开发团队完成的实用想法。

更新 2：看起来 Facebook 有一个“推送业力”的元游戏来确定谁的提交通常是好的。

《接近》是一款类似于奥赛罗、围棋和冒险的领土统治策略游戏。两名玩家，使用 10x12 六角网格。Brian Cable于 2007 年发明的游戏。

似乎是一个值得讨论的游戏a）最佳算法然后b）如何构建人工智能。
由于随机因素和疯狂的分支因素 (20^120)，策略将基于概率或启发式。所以很难客观地比较。 每轮最多 5 秒的计算时间限制似乎是合理的 => 这排除了所有蛮力尝试。（在专家级别上玩游戏的 AI 来感受一下——基于一些简单的启发式，它做得非常好）

游戏：此处为 Flash 版本，此处为iPhone版本iProximity以及网络上其他地方的许多副本规则：此处

目的：在放置所有瓷砖后控制最多的军队。你从一个空的六角板开始。每回合你都会收到一个随机编号的瓷砖（数值在 1 到 20 支军队之间），可以放置在任何空置的棋盘空间上。如果此图块与任何 ALLY 图块相邻，它将增强每个图块的防御 +1（最大值为 20）。如果它与任何 ENEMY 瓷砖相邻，如果其数量高于敌人瓷砖上的数量，它将控制它们。

关于策略的思考：这里有一些初步的想法；将计算机 AI 设置为专家可能会学到很多东西：

1. 最小化你的周长似乎是一个好策略，以防止翻转并最大限度地减少最坏情况下的损坏
2. 就像围棋一样，在你的阵型中留下洞是致命的，只有六角网格更是如此，因为你可以在一次移动中失去多达 6 个方格的军队
3. 低编号的瓷砖是一种负担，因此请将它们远离您的主要区域，靠近棋盘边缘并分散。您还可以使用低编号的瓷砖来填补阵型中的漏洞，或者在对手不会打扰进攻的外围获得小幅收益。
4. 三块的三角形结构很牢固，因为它们相互加强，也减少了周长
5. 每个图块最多可以翻转 6 次，即当它的相邻图块被占用时。对编队的控制可以来回流动。有时您会丢失部分阵型并堵塞任何孔以使该部分板“死”并锁定您的领土/防止进一步损失。
6. 低编号的牌是显而易见的但价值较低的负债，但如果高编号的牌被翻转（这更难），它们可能会成为更大的负债。一个 20 军队的棋子的幸运游戏可以导致 200 的摆动（从 +100 到 -100 军队）。所以瓷砖的放置会有进攻和防守的考虑。

评论 1,2,4 似乎类似于极小极大策略，其中我们最小化最大预期可能损失（通过对对手可以从 1..20 获得的值 ß 的一些概率考虑进行修改，即只能被 ß 翻转的结构=20 瓷砖“几乎坚不可摧”。）我不清楚评论 3、5、6 对最佳策略的影响。对围棋、国际象棋或奥赛罗棋手的评论感兴趣。

（XBox Live 的续集ProximityHD 允许 4 人合作或竞争性本地多人游戏增加了分支因素，因为您现在在任何给定时间都有 5 个牌，其中您只能玩一个。加强盟友牌是每个盟友增加到 +2。）