algorithm - 人工智能 : How to find an evaluation function in this game (minimax algo)?

Question

我正在考虑我可以实现的游戏 AI。我的问题是关于为这个游戏找到一个评估函数，以便应用带有 alpha/beta 切割的 minimax 算法。 https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning让我先描述一下游戏，解释一下我打算用我的 AI 实现什么，然后解决问题。

游戏:

A 2-player turn-by-turn game.
Goal is to kill opponent or have more life points at the end.
In comparison with Magic: The Gathering, you both have monsters to attack the opponent. The number is fixed, let’s say 5 each.
A monster has a fight ability (let's say between 1 and 10), and a damage ability (let's say between 1 and 5).

Each turn:
- Active player declares to his opponent which monster (he owns) engages the current fight.
- He secretly sets multipliers face down (let’s see that in next paragraph).
- Opponent declares which monster (he owns) fights against the first one, while setting multipliers the same way.
- Fight: fight ability * multipliers = final attack. Biggest attack wins and inflicts damage ability to opponent.
- Next turn, active player switch

About multipliers: you have 4 cards in hand that can double your attack (and many empty cards, so that you put 4 cards each turn on the table, and the opponent does not know if you multiplied by 1, 2, 4, 8 or 16).
Just in case: let's say we have a rule for draws to be solved.

我对 AI 的期望:能够说一个完美的球员是否应该在给定的位置上获胜。这意味着，对于一个可取胜的位置，AI 应该告诉你有一种通向胜利的方法，并给出步骤(见下面的例子)。对于对手可以获胜的位置，我还没有决定，对于在所有情况下都不会导致相同获胜者的位置(它们存在；D)。

** 一个例子:**

2 rounds left to go. I have
- Monster A: fight: 5, damage: 2
- Monster B: fight: 3, damage: 4
- life: 5, 1 multiplier left, my turn to begin
My opponent has
- Monster C: fight: 2, damage: 6
- Monster D: fight: 8, damage: 1
-life: 5, 1 multiplier left

In that case, if you think about it, you win if you play well.
Solution:
You can see that if monster C wins, he inflicts 6 and I lost.
But if he loses, one my monsters will inflict at least 2, and even if monster D wins (before or after),
I won't die and I will have more life that my opponent. Victory.
That's an example of what I want the AI to find.

当然，我简化了示例。也许它会更棘手。这就是我的问题所在。

我们可以在心理上看到，当我们还剩 2 轮时，计算所有可能的决斗很简单(最后一轮不需要计算:如果双方都玩完最后的乘数，它是确定性的)。正如我们所说，我们还有 5 轮比赛要进行。但我的观点是我们可以有 20 个，计算所有内容变得很长(就像在第一轮中试图找到最佳着法)。事实上，我们不会尝试计算它。例如，在国际象棋中，位置太多会导致无法计算所有可能性。

但是，如果你跟我学，国际象棋中有一个解决方案——我们可以实现一个评估函数。我们怎么知道前进 10 步，这一步会导致更好的位置？因为我们评估这个职位。我们声称，如果一个位置是将死，或者如果你有更多的棋子，或者如果你控制中心等等，那么这个位置会更好......

那么，我的问题是:

如何评估我提出的游戏中的位置？

我的意思是，第一轮，如果我能计算出接下来两轮的可能走法，我就会得出第三轮或第四轮的所有可能位置。但在我看来这似乎没有帮助。你可以拥有更好的生活点数、更好的牌、更多的左乘数，这一切都取决于接下来会发生什么。我没有看到在一般情况下符合要求的优势。你呢？

N.B.1 我希望它是清楚的，我简化了游戏规则，当然我们可以添加规则(如果连续 2 轮获胜，则组合，适用于伤害能力的乘数......)

N.B.2 我想到了一个神经网络，但这个问题对我来说仍然很有趣。而且神经网络似乎很难解决，因为多轮(我的知识比了解神经网络中任何具有追溯作用的模型要局限得多)。

N.B.3 我认为如果我仍然进行完整的计算分析，minimax 和 alpha/beta 切割会有所帮助，但我担心的是计算时间，这就是我在这里问这个问题的原因。是的，我可能可以从最后 2 轮位置的完整计算开始。

感谢阅读，我希望你和我一样觉得这个问题很刺激!

Answer 1

在任何游戏中评估位置的一种方法是尝试了解被认为是游戏专家的玩家的思维过程。所以你可以在这个游戏中找到专家，并向他们询问在游戏过程中决定他们决定的因素。或者，您可以通过研究游戏并经常玩来使自己成为专家。仅通过查看游戏规则很难得出一个好的评估函数。

我没玩过这个游戏，但从一些简单的启发式开始可能是有意义的，它是决定游戏状态的变量的线性组合(你的主要角色的生命值，你拥有的乘数，总战斗力/你所有怪物的伤害能力，你任何怪物的最大战斗/伤害能力，剩余回合数等)。考虑到你对手的相应值，你将得到这样的 eval 函数:a1*(my_hp - opp_hp) + a2*(my_monsters_total_fight - opp_monsters_total_fight) + a3*(my_monsters_total_damage - opp_monsters_total_damage) + a4*(my_number_of_multipliers - opp_number_of_multipliers) + ... , 其中系数 a1,a2,..可正可负取决于相应变量的影响(例如hp变量a1的系数为正等)

现在，此功能可能有效也可能无效，但至少它会为您提供一个起点，您可以从中尝试改进它，或者如果它惨败则完全放弃。您可以尝试通过调整系数来改进此评估函数，添加一些非线性项以在变量(乘法、幂、对数等)之间产生更复杂的关系，并查看它如何影响性能。您还可以尝试使用遗传算法和差异进化等优化技术来自动化调整过程。一般来说，提出一个好的启发式方法与其说是一门科学，不如说是一门艺术(毕竟，它被称为启发式方法是有原因的)。从反复试验开始，看看结果如何。