问题标签 [minimax]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 极小极大评估函数
我正在使用 Unity3D 开发游戏《最终幻想 VIII》中看到的迷你游戏 Triple Triad。
基本游戏是一个 3x3 网格,玩家和 NPC 手里拿着 5 张牌。目标是在棋盘被填满时持有最多的牌。卡片的顶部、底部、左侧和右侧有 4 个数字。玩家将一张牌放在网格上,另一位玩家可以将一张牌放在它旁边,然后将比较牌上的数字(例如,如果一张牌在中间,而对手在它的左边打了一张,对手卡的右值将与已经存在的卡的左值进行比较)。如果一张牌大于另一张牌,则玩家将“拿走”对手的牌。
关于三重三合会的更多细节可以在这里看到:http: //finalfantasy.wikia.com/wiki/Triple_Triad
我目前正在为单人游戏设计 AI,以便人类可以与 NPC 对战。我已经决定开发 AI 的最佳方式是使用带有 alpha-beta 修剪的 Minimax 算法,以便轮流为 AI 找出最佳可能的移动。
我遇到的问题是,我在互联网上看到的大多数示例都显示了 tic-tac-toe 的评估器功能。这比三元组评估器要简单得多,因为该函数必须考虑卡片上的值以及正在播放的位置(例如,拿走一张敌人的卡片)。
有没有人对我如何编写这个评估器函数有任何提示?或者至少我怎样才能将这个站点的代码改编成一个可以评估我的板子的三元组?
http://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
c++ - 返回 tictactoe 的 minimax 算法中的 bestMove
我试图编写 Russel Norvig 的人工智能书中给出的井字游戏的极小极大算法。除了将 bestMove 返回给用户的方式之外,它拥有一切。我正在努力返回 bestMove,但无法决定何时选择 bestMove。帮助,有人吗?
PS:还有其他伪代码可以找到 minmax 值。但是,他们只专注于井字游戏,我正在尝试将其扩展到其他游戏。谢谢。
更新:整个代码可以在这里找到:http: //ideone.com/XPswCl
c++ - 了解 Negamax 的约束
这段代码是为计算 tictactoe 游戏中某个位置的 bestMove 而构建的。我几乎得到了代码的每一部分,除了 for 循环中的条件,它表示 minRating != LOSING_POSITION。此代码来自给定伪代码的实现。
我无法将 for 循环的第二个条件与给定的代码匹配,直到你找到一个强制获胜。我找不到这个事实和那个 minRating != LOSING_POSITION 之间的相似之处
algorithm - Alpha-beta 修剪同一玩家的连续动作
我已经为 Checkers 实现了 alpha-beta 修剪,并认为我已经让它工作了,但发现计算机不会连续进行多次跳转(当它必须时)。例如:
人工智能会:
人工智能应该这样做:
我试图通过检查 MovePiece 的返回值来修复它,它返回玩家是否完成了他的回合,这取决于移动是否是跳跃以及是否还有进一步的跳跃。根据返回值,它将再次运行 MaxValue/MinValue(取决于它第一次看到要进行进一步移动时所处的位置)或继续在树中并切换玩家。
相关代码(C# 中)如下(retVal 是包含 Value、Depth 和 Move to do 的类型):
...
然而,这导致了一些……有趣的结果(第一步除了最小的修剪之外什么都不做),尽管我认为这将是正确的改变。
用新的动作让 MaxValue/MinValue 再次调用自己是正确的做法吗?
artificial-intelligence - Alpha beta剪枝的评价函数设计
我正在设计一个国际象棋游戏,它背后的人工智能实现了一个带有 alpha-beta 修剪的搜索树。我在设计游戏的评估函数时遇到了困难。
如何为任何类型的游戏设计评估函数?
c++ - 井字游戏的 MinMax 简单演示
我一直在努力弄清楚 MinMax 算法是如何工作的,希望 alpha-beta 修剪算法能够工作。我对发生的递归感到困惑。
- 首先,每个中间板都得分吗?或仅终端游戏板。
- 其次,返回的究竟是什么?程序如何知道下一步该放在哪里?我看到我应该返回棋盘分数(在tictactoe中,-1,0,1)但是程序如何知道接下来应该播放哪个动作。
我曾尝试找到一个简单的 C 或 C++ 程序来证明这一点,但我运气不佳。我正在尝试学习这个算法,我可以为我的计算机编程课的其余部分创建一个演示文稿。
非常感谢!五
java - minimax 代码总是返回 0
我从维基百科写了一个 Alpha-Beta 修剪。我正在尝试编写一个四连接 AI。该函数应该返回列号,然后我的主函数会移动。
javascript - JavaScript FileSystem API 作为 Chess Alpha Beta 数据存储
我开始用 JavaScript 和一些 Node.JS 编写国际象棋程序,如果我发现需要让服务器参与国际象棋 AI 逻辑,至少在我可能无知的观点中,这仍然是合理的。我的问题很简单:JavaScript 的客户端 FileSystem API 是缓存极小极大结果以供将来参考的合理方法,还是生成的数据太多而无法存储在任何地方?我的想法是,它可以用作一种方式,让 AI 能够通过访问以前的决策而不是每次手动重新确定它们来适应用户并“学习”。这是一个合理的计划还是我低估了这需要的内存使用量?如果您的回答是这似乎是合理的,那么有关以这种方式存储数据的最有效方法的一些提示也会很好。
c++ - MiniMax 到 Alpha-Beta 搜索转换的问题
好的,我的问题对于玩过棋盘游戏编程的人来说应该很熟悉,所以这里是:
- 我已经实现了 MiniMax 算法的一个变体(返回移动而不是最小/最大值)。
- 我也尝试将其设置为 alpha-beta,尽管它最终完全失败了。
所以,这是我的 MiniMax 代码:
有什么想法可以调整上述内容以使其成为 Alpha-Beta 搜索吗?
这是我对 Alpha-Beta 转换的尝试(失败得很惨):
提示(避免任何误解):
该
this->eval()
函数从玩家 A 的角度返回一个分数。例如,+100 分表示该位置有利于玩家 A,而 -100 分表示该位置有利于玩家 B。MINUS_INF
并PLUS_INF
分别被定义为一些任意小的和大的值。这不像家庭作业或任何东西(如果是的话,我很可能永远不会有兴趣玩这些东西......哈哈)
Move
是一个简单的类,包含有关移动的详细信息,以及它的相应值(由eval
函数分配。HASHMAKE
并且UNHASHMAKE
只是 2 个 move-(un)making 和 move-(un)hashing 宏,应该没什么区别。MAXMOVE
定义如下:#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))
MINMOVE
定义如下:#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))