问题标签 [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.

0 投票
2 回答
2903 浏览

java - 跳棋的 MinMax AI

我用 minmax AI 用 Ja​​va 创建了简单的 Checkers 游戏,但我不工作。我使用 minmax 的递归版本,但它一定有问题,因为它返回的移动不是最好的,但可能是第一次生成的。

如果我用 depth = 1 调用 minmax 它应该“返回 7 个值(有 7 个可能的移动),但如果我从 2,4 移动到 3,3,它只返回 1 ...但是当我尝试调试它时,ArrayList move 有正确的大小。所以我不知道它有什么问题。:(

编辑: “返回”我错误地表示第一个条件(当深度为 0 或移动为空时)只发生一次,但如果它是正确的,它应该发生 7 次。对不起,我的英语不好。

你知道一些网站,哪里有正确的 minmax 递归伪代码(最好使用 alpha/beta,因为我需要扩展它)或者你能帮我解决这个问题吗?应该只是小事。谢谢!

0 投票
1 回答
2121 浏览

algorithm - Minimax 和井字游戏 - 我的算法正确吗?

我为 TTT 实现了一个极小极大算法。当我让 AI 玩家迈出第一步时,它会将所有可能移动的极小最大值评估为 0。这意味着它可以选择网格上的任何方格作为第一步。但是,任何井字游戏指南都会告诉您,在迈出第一步时选择角落或中心方块是更好的选择,因为获胜的机会更高。

为什么我的算法没有反映这一点?

编辑:澄清一下,我想问的是:这是极小极大算法的限制还是我的实现不正确?

0 投票
0 回答
1523 浏览

java - Java MiniMax TicTacToe AI vs AI 不会进行防守

我一直在尝试通过使用井字游戏来学习 MiniMax,因为这似乎是最常用的示例之一。我从不修剪开始尝试掌握它。我有 2 个 AI 互相对抗,但 X 总是获胜。我认为问题在于他们没有进行防守,我不太确定如何实施。下面是代码,我还有一些其他的类文件,但我认为除非有要求,否则不需要它们。非常感谢。

0 投票
2 回答
14186 浏览

java - MiniMax 实现

我正在尝试用 Java 编写一个小型 AI 算法来实现 miniMax 算法。

以此为基础的游戏是两人游戏,其中两名玩家每回合移动一次,每个棋盘位置导致每个玩家得分。玩家 X 的位置的“质量”是通过从玩家 X 在该位置的得分中减去对手的得分来评估的。每一步都用一个整数表示(即输入 1 移动一,输入 2 移动二等)

我知道 miniMax 应该使用递归来实现。目前我有:

一种evaluate()方法,它将表示棋盘状态的对象(即“BoardState”对象和称为“max”的布尔值(签名将是evaluate(BoardState myBoard, boolean max))作为参数。

轮到玩家 X 时 max 为真。给定一个棋盘位置,它将评估所有可能的移动并返回对玩家 X 最有利的移动。如果轮到对手,max 将为 false,该方法将返回对玩家 X 最不利的移动(即:对玩家 y 最有利)

但是,我在编写实际miniMax方法时遇到了困难。我的一般结构是这样的:

因此我提交了初始的游戏状态和我希望它研究的“深度”。

然后我会有类似的东西:

这听起来像是一个合理的实现吗?有什么建议么?:)

谢谢!

0 投票
1 回答
1986 浏览

minimax - alpha beta search iterative deepening refutation table

I've implemented an alpha beta search with iterative deepening and i've read several techniques to further optimize the algorithm by searching for the best move first that came up from previous depth search.

as far as i understand, can i just store the principal variation from the previous depth search in dynamic length list? for example, suppose i have searched until depth 4 with PV : [1, 0, 2, 3] means that at depth 1, choose move number 1, at depth 2 choose move number 0, at depth 3 choose move number 2 , etc..., and then for depth 5 search, the algorithm will first search the child of the node from that previous depth PV.

is that what you call the refutation tables?

description of refutation table from this link : For each iteration, the search yields a path for each move from the root to a leaf node that results in either the correct minimax score or an upper bound on its value. This path from the d - 1 ply search can be used as the basis for the search to d ply. Often, searching the previous iteration’s path or refutation for a move as the initial path examined for the current iteration will prove sufficient to refute the move one ply deeper.

if it's not the same, can you explain what is refutation table really is(because to me, both seems equal, but im not sure) and what is the advantage of using the refutation tables instead of the way i mentioned first?

0 投票
1 回答
651 浏览

r - Finding a boundary in a density plot

I am very new to machine learning so I am open to suggestions as well. I read something called minimax risk today and I was wondering if this is possible in my case.

I have two datasets and am interested in finding a line (or a boundary to be more precise) such that the area under the left curve to the right of the vertical line is equal to the area under the right curve to the left of the vertical line. Is there a way this can be done in R i.e., find out the exact location to draw the vertical line?

I put up some sample data here that can be used to plot the following graph: https://gist.github.com/Legend/2f299c3b9ba94b9328b2

enter image description here

0 投票
1 回答
63 浏览

artificial-intelligence - 人工玩家评价

我对正在创建的棋盘游戏有疑问。我计划使用 MiniMax 和 AlphaBeta 修剪为游戏制作人工玩家,但我不确定如何评估玩家是否擅长游戏。由于这是一款新游戏,因此我无法找到一个很好的玩家来提供反馈。所以我想知道是否有任何技术可以客观地确定人造球员是否真的很好。先感谢您。

0 投票
3 回答
1717 浏览

algorithm - Minimax 树,玩家可以连续移动多次

在玩过使用 Minimax 和 Alpha-Beta Pruining 的回合制游戏之后,如果满足某些条件,如何处理同一玩家可以连续多次移动的游戏?

0 投票
2 回答
2829 浏览

algorithm - 如何调整我的 Minimax 搜索树来处理没有基于术语的游戏?

我必须做一个项目,我们需要实现 mancala 棋盘游戏,然后还为它实现 AI。

我们被告知,我们需要修改或更改极小极大树以能够与 mancala 一起使用,因为在游戏中玩家可以连续进行多个回合。

我已经实现了我的游戏逻辑和 GUI,但现在在我开始使用 AI 之前,我想尝试了解它背后的理论。我在网上搜索了基于非回合的迷你最大树,但我似乎找不到任何东西。但是我看到很多人在谈论使用 minimax 做 mancala。

现在我了解了正常的极小极大树以及每个级别如何在最小节点和最大节点之间交替。有了我现在需要的树,我会说: min > max > max > min > max如果第二个玩家有两个回合?

我们还需要能够指定 Minimax 树的给定层深度。我们还需要进行 alpha beta 修剪,但那是稍后,一旦我真的有一棵树。

0 投票
0 回答
722 浏览

javascript - 极小极大/计算机移动选择(井字游戏/Javascript)的错误?

我正在尝试实现一个单人井字游戏,其中计算机玩家永远不会输(每次都强制平局或获胜)。在四处搜索之后,似乎使用极小极大策略是相当标准的,但我似乎无法让我的算法正常工作,这导致计算机选择了一个非常糟糕的举动。谁能帮我找出我的代码哪里出错了?

“O”是用户(最大),“X”是计算机(最小)

编辑:我重新发布了我的代码,我已经修复了 getComputerNextMove 中的一些东西和一些小错误......现在我的代码正在寻找更好的分数,但如果有人获胜,它并不总是会出现(这些功能似乎是好吧,我想我只是没有检查正确的位置)。它也没有选择最好的举动。底部有一些测试器功能可以查看极小极大如何工作/测试游戏状态(获胜者/平局)。

tictactoe.js:

索引.html:

CSS: