问题标签 [minimax]

So I was looking up Mini-max for a Tic-Tac-Toe Game, but couldn't understand how the recursion worked? Okay, so basically here are my questions:

1. How does minimax know whose turn is it? Whats the best way to indicate the player whose turn it is generating?
2. How do you generate possible moves?
3. How do you know when you are at a terminal node, and how do you generate the terminal nodes?

For example in this Pseudo-code

A node is a board correct? And is the depth how many plies the code has to go down in recursion? Also what is the max function and where are the nodes being generated from?

Now, so far I have this code for creating a board:

But how would I know whose turn is it? And how do I generate the child nodes for the board?

我正在尝试为井字游戏实现极小极大算法，其中两个玩家都是人类，并且每次计算机都使用极小极大算法建议最佳移动。但它并不是每次都给出正确的建议。例如：它没有为以下场景提供正确的建议：玩家 X：1 玩家 O：2 玩家 X：5。这是我的代码：

我正在制作一个用于练习制作课程的 tictactoe 板，但我的算法遇到了问题。它似乎在返回最好的移动进攻，但它并没有起到防守作用。我不知道我在哪里搞砸了，似乎找不到它。我在这里查看了很多关于它的东西，并将它与类似的项目进行了比较，但似乎仍然无法理解。这是我的代码。

所有的类都在底部。提前感谢您的任何帮助和更正。:)

我在下面的代码中使它递归，虽然我仍然无法计算得分.. 如果值为 1、0 或 -1，那么如果有多个具有相同值的移动，它将只取第一个可能不是最好的举动“阻止。

测试结果如下

测试 1

测试 2

我已经实现了 Negamax，因为它可以在wikipedia上找到，其中包括 alpha/beta 修剪。

然而，它似乎有利于失败的举动，据我所知，这是一个无效的结果。

游戏是井字游戏，我已经抽象了大部分游戏玩法，因此应该很容易在算法中发现错误。

给出这个输入：

算法选择将棋子放置在 0、1 处，造成一定的损失，对这个陷阱执行此操作（没有任何事情可以赢得或以平局告终）：

我很确定游戏实现是正确的，但算法也应该是正确的。

编辑：更新evaluate和nextMove.

EDIT2：修复了第一个问题，但似乎仍然存在错误

我想使用极小极大搜索（带有 alpha-beta 修剪），或者更确切地说是负极大搜索，让计算机程序玩纸牌游戏。

纸牌游戏实际上由 4 名玩家组成。因此，为了能够使用极小极大等，我将游戏简化为“我”对抗“他人”。在每一次“移动”之后，你都可以从游戏本身客观地读出当前状态的评价。当所有 4 名玩家都放置了卡片时，最高的玩家将赢得所有玩家 - 卡片的价值计算在内。

由于您不知道其他 3 名玩家之间的卡牌分布究竟如何，我认为您必须使用不属于您的卡牌模拟所有可能的分布（“世界”）。你有 12 张牌，其他 3 名玩家总共有 36 张牌。

所以我的方法是这个算法，其中player1 到 3 之间的数字表示程序可能需要为其寻找动作的三个计算机玩家。并-player代表对手，即所有其他三名球员。

这似乎工作正常，但是对于 1 ( depthLeft=1) 的深度，程序已经需要平均计算 50,000 次移动（放置的牌）。当然，这太过分了！

所以我的问题是：

1. 实施是否正确？你能模拟这样的游戏吗？关于不完善的信息，尤其是？
2. 如何在速度和工作量方面改进算法？
3. 例如，我可以将可能的移动集减少到 50% 的随机集以提高速度，同时保持良好的结果吗？
4. 我发现UCT 算法是一个很好的解决方案（也许）。你知道这个算法吗？你能帮我实现它吗？

我想开发一个信息不完全的两人游戏——“Stratego”。

这场比赛“有点”像国际象棋，但最初我们对对手棋子的排名一无所知。当一个棋子攻击或被某个对手的棋子攻击时，他们的等级被揭示并且更高等级的棋子杀死/捕获更低等级的棋子。可以在此处找到有关游戏的更多详细信息。

我做了一点研究。我读了 JA Stankiewicz 的“Stratego 中的对手建模”。但是我找不到有关如何开发游戏的完整教程。我曾成功开发过一款两人游戏——“黑白棋”，又名黑白棋，我熟悉 MINIMAX 算法和 alpha-beta 修剪。

我在某处发现蒙特卡洛树搜索也用于开发零和二人游戏。它可以用于像战略这样的游戏吗？我可以获得相同的完整教程吗？

任何其他不涉及蒙特卡洛树搜索的教程也很有用:)

我正在编写一个 tictactoe 程序，但它不是你传统的 tictactoe

首先，棋盘是 4x4，获胜的方法是在一行、一列或对角线上获得 3 个同类和 1 个对手。因此，通过第一列，以下将是“O”的胜利：

我正在尝试实现一个极小极大算法，以便为程序提供一个无法击败的“硬”模式。

我的问题是我不能希望创建一个包含所有可能游戏状态的树，因此我必须想出某种函数来评估我可以生成的游戏状态。

我想我的问题是，我怎么能想出这样的功能？

在我弄清楚了一些事情之后，这个问题和我的另一个问题合二为一，所以我修改了这个问题。

下面概述了我试图用我的功能完成的事情。

1. 遍历所有的点。如果它是开放的，请选择带有当前玩家符号的位置。
2. 如果这一举动导致游戏获胜并且轮到计算机玩家，则将点的键值对（整数）和点的分数（整数，在本例中为 1）添加到scored-spots哈希图中。
3. 递归并调用这个相同的函数，传递给它新 scored-spots的哈希映射、刚刚移除的棋盘、相同的玩家和相同的符号。
4. 但是，如果游戏没有获胜，请继续下一个条件语句并检查它。
5. 以相同的方式继续下一个条件语句，只是分数不同（轮到计算机获胜为 1，轮到人类获胜为 -1，平局为 0）。
6. 如果没有条件语句评估为真，则无论如何都要递归（scored-spots在这种情况下哈希映射不会有任何不同）。

这是我尝试过的代码，但这并没有返回我期望的值。

注意：
board是这样的散列图：（{0 "0", 1 "1", 2 "2"}点位置 - 点值）
sym是一个符号，如“X”或“O”
current-player是关键字，如:computer或是:human
scored-spots这样的散列图：{}

我期望的返回值是一个散列图，每个开放点都得分。例如，{1 0, 4 1, 5 -1, 6 -1, 8 0}。

相反，如果我通过这个 board:
{1 "X" 2 "X" 3 "O" 4 "4" 5 "5" 6 "6" 7 "7" 8 "X" 9 "O"}，
我会得到一个带有大量list哈希映射的返回值。

我知道如何使用 minimax 之类的算法来玩完美的游戏（在这种情况下，我正在寻找类似于井字游戏的游戏）

但是，我想知道如何创建一个不完美的算法，或不同“技能水平”（简单、中等、困难等）的人工智能，人类玩家实际上有机会击败。

我目前正在尝试实现一个Minimax algorithmfor Tic Tac Toe。在当前版本中，在某些情况下，计算机会出现问题，我不太清楚为什么。例如，如果我（作为人类玩家）从左上角的 x 开始，计算机的反应是左下角的 ao（当然，这等于他输了）整个程序在MVC-Design.

问题：我是否正确纠正了 Minimax 算法，或者（如果没有）是什么导致了“坏”动作？

这是代码：（我省略了一些我测试正确的方法的代码）

游戏类表示 Cell[][] 数组中的字段（与 AIMinimax 相同）并创建 AIMinimax 的实例并在此调用 nextMove，以生成计算机做出的下一个移动。默认情况下，人类玩家总是启动。

先感谢您！