Tides of Time Bot 和游戏 - Minimax 的应用（带 Alpha Beta 剪枝）
5.00/5 (10投票s)
任何确定性游戏都可以分解为其核心功能。通过理解这些功能，可以实现诸如 Minimax（带 alpha-beta 剪枝）等基本算法，从而为更好的 AI 对手铺平道路。
目录
引言
又是 Minimax 的理论演示？不！尽管本文专注于构建一个使用该算法的机器人，但它也包含了用 C# 编写游戏机制所需的所有必要细节，这样最终你将拥有一个真正的游戏！又是一个可以用 Minimax 算法解决的经典游戏？不！关于这些游戏已经有大量的文章了。那么，这到底讲的是什么呢？它是关于为一款现代卡牌游戏构建一个智能对手。一款从未被学术目的分析过的游戏。以前从未有文章写过它及其机制。这款由 Portal Games 出版，Kristian Čurla 开发的精彩游戏是 时光之潮。
人工智能就是关于创造力。通常，在组织好数据后，你可以从 Minimax 等经典算法开始，然后添加和探索新事物，使你的程序越来越好。希望本文能提供一个基本的机器人，你将继续开发它，使其变得更智能，直到它无法被击败！此外，我也希望它能给你灵感，让你在传统边界之外探索人工智能的奇妙世界！
如果我还没有说服你阅读本文，只需点击这里，你可以玩实际游戏并测试你按照本教程制作的超棒机器人。让我们从规则开始。
规则
《时光之潮》是一款回合制策略卡牌游戏。它的目标是通过为你的王国选择最合适的卡牌来积累胜利点数，同时密切关注对手的选择。每张卡牌都有一定的能力或目标，如果实现，将为你带来一定数量的胜利点数。尽管游戏由三个独立的回合组成，但由于其重复性，本文将仅探讨第一个回合的机制。
游戏由 18 张牌组成。其中 15 张牌底部有名称，顶部有目标，右侧有得分指示器，左侧有花色。另外三张牌只有名称和能力。游戏中有五种花色，每种花色有三张牌。
宫殿 - 
图书馆 - 
花园 - 
寺庙 - 
要塞 - 
这些能力也非常容易理解，因为它们就是卡牌上所写的功能。
例如，古老的分界线牌（Ancient Divide card）有宫殿花色，如果在回合结束时你拥有比对手更多的要塞花色，它将为你带来七点胜利点数。如果你和你的对手都拥有一张要塞花色，则目标未达成。另一方面，王者之巢牌（The Kings Nest card）赋予赢得所有平局的能力。因此，在这种情况下，这两张牌结合起来为玩家带来 7 点胜利点数。
游戏的设置阶段从洗牌开始。每位玩家发五张牌。其余的牌面朝下放在一叠中。因此，在游戏开始时，两位玩家只知道各自的五张牌。
然后每位玩家从手中选择一张牌，面朝下放在桌子上。两位玩家同时翻开这张牌。这是他们各自王国的第一部分。此时他们都不能改变主意。这两张牌在游戏期间都将面朝上。
接下来，玩家交换手中所有卡牌。因此，每位玩家现在将拥有对手最初拥有的四张卡牌。游戏照常进行。玩家选择一张卡牌并同时翻开。该卡牌现在是其王国的一部分。
交换继续进行，直到所有玩家手中都没有牌为止。通过检查每项能力或目标及其各自的收益来计算得分。
现在你可以在这里实际玩游戏，好好利用这些规则！
将游戏机制转化为代码
现在是时候深入研究代码了！首先，在我们程序中实现卡牌、实际规则以及一个计算分数的函数之前，我们无法为我们的机器人制定策略。所以让我们来创建我们的聪明机器人将大放异彩的环境！
存储卡牌
在现实世界中，卡牌是一个对象。因此我们应该有一个名为 `Card` 的类，具有以下属性：
public int picNo;
public int locationType { get; set; }
public int strategyType { get; set; }
public ArrayList strategyLocations { get; set; }
public int points { get; set; }
其中
- `picNo` 将帮助我们检索特定卡牌的对应图片，并在我们的静态牌组中找到它。
- `locationType` 表示卡牌左上角的符号或花色。它可以取以下值：0 表示卡牌上没有符号，1 表示 `Palace`（宫殿），2 表示 `Library`（图书馆），3 表示 `Garden`（花园），4 表示 `Temple`（寺庙），5 表示 `Stronghold`（要塞）。为了提高可读性，我使用了 `enum` 数据类型。
private enum locations { NoLocation, Palace, Library, Garden, Temple, Stronghold }; - `strategyType` 代表卡牌右上角写的目标或能力。为此，我使用了以下 `enum`：
private enum strategies { EachComb, All, Majority, Ties, DontHave, OneCardMajority, DoubleAmount, SingleCard };其中
`EachComb` 指的是这些牌：
`All` 指的是：
`Majority` 指的是：
`Ties` 指的是：
`DontHave` 指的是：
`OneCardMajority` 指的是：
`DoubleAmount` 指的是：
`SingleCard` 指的是：
- `strategyLocation` 是一个 `ArrayList`，它指示 `strategyType` 所引用的花色类型。如果卡牌上没有指定此类位置，则为 `null`。
例如，对于以下卡片，我的 `ArrayList` 中有这些条目：`(int)locations.Palace`、`(int)locations.Stronghold`、`(int)locations.Temple`。
- `points` 属性表示如果你实现了卡牌上写的目标，你将获得的积分数。例如，对于上面的卡牌，`points` 的值为 `9`。
`Card` 类也有一个构造函数：
public Card(int picNo, int locationType, int strategyType,
ArrayList strategyLocations, int points)
{
this.picNo = picNo;
this.locationType = locationType;
this.strategyType = strategyType;
this.strategyLocations = strategyLocations;
this.points = points;
}
它在通过调用 `Init()` 函数将所有卡牌放入名为 `deck` 的静态 `Card` 数组时使用。
public static void Init()
{
deck = new Card[19];
deck[1] = new Card(1, (int)locations.Stronghold,
(int)strategies.EachComb,
new ArrayList() { (int)locations.Temple }, 3);
deck[2] = new Card(2, (int)locations.Palace,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Library }, 3);
deck[3] = new Card(3, (int)locations.Library,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Garden }, 3);
deck[4] = new Card(4, (int)locations.Temple,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Palace }, 3);
deck[5] = new Card(5, (int)locations.Garden,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Stronghold }, 3);
deck[6] = new Card(6, (int)locations.Garden,
(int)strategies.Majority, new ArrayList()
{ (int)locations.Palace }, 7);
deck[7] = new Card(7, (int)locations.Temple,
(int)strategies.Majority, new ArrayList()
{ (int)locations.Garden }, 7);
deck[8] = new Card(8, (int)locations.Stronghold,
(int)strategies.Majority, new ArrayList()
{ (int)locations.Library }, 7);
deck[9] = new Card(9, (int)locations.Palace,
(int)strategies.Majority, new ArrayList()
{ (int)locations.Stronghold }, 7);
deck[10] = new Card(10, (int)locations.Library,
(int)strategies.Majority, new ArrayList()
{ (int)locations.Temple }, 7);
deck[11] = new Card(11, (int)locations.Temple,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Library, (int)locations.Garden }, 5);
deck[12] = new Card(12, (int)locations.Library,
(int)strategies.EachComb, new ArrayList()
{ (int)locations.Palace,
(int)locations.Stronghold, (int)locations.Temple }, 9);
deck[13] = new Card(13, (int)locations.Garden,
(int)strategies.All, null, 13);
deck[14] = new Card(14, (int)locations.Stronghold,
(int)strategies.DontHave, null, 3);
deck[15] = new Card(15, (int)locations.Palace,
(int)strategies.Ties, null, 0);
deck[16] = new Card(16, (int)locations.NoLocation,
(int)strategies.OneCardMajority, null, 8);
deck[17] = new Card(17, (int)locations.NoLocation,
(int)strategies.DoubleAmount, null, 0);
deck[18] = new Card(18, (int)locations.NoLocation,
(int)strategies.SingleCard, null, 8);
}
洗牌
现在我们的游戏中已经有了一副牌，是时候编写一个函数，以便在每局新游戏开始前洗牌了。
public static Stack<Card> Shuffle()
{
bool[] viz = new bool[19];
Stack<Card> shuffledDeck = new Stack<Card>();
var random = new Random((int)DateTime.UtcNow.Ticks);
int randomVal;
bool ok;
for (int i = 1; i <= 18; i++)
{
ok = false;
do
{
randomVal = random.Next(1, 19);
if (viz[randomVal] == false)
{
ok = true;
viz[randomVal] = true;
shuffledDeck.Push(deck[randomVal]);
}
} while (ok == false);
}
return shuffledDeck;
}
该函数使用一个名为 `viz` 的 `bool` 数组，对于已经放入 `ShuffledDeck` 中的卡牌，其值为 true。随机生成 1 到 18 范围内的数字，直到所有卡牌都被放入 `ShuffledDeck` 栈中。
洗牌完成后，我们可以调用以下函数将它们发给玩家：
public static void DistributeCards()
{
ArrayList cardsInGame_Bot = new ArrayList(),
cardsInGame_Human = new ArrayList();
Stack<Card> shuffledDeck =
(Stack<Card>)HttpContext.Current.Session["shuffledDeck"];
int noCards = 5 - (int)HttpContext.Current.Session["subround"] + 1;
for (int i = 1; i <= noCards; i++)
{
cardsInGame_Bot.Add(shuffledDeck.Pop());
cardsInGame_Human.Add(shuffledDeck.Pop());
}
HttpContext.Current.Session["cardsInGame_Bot"] = cardsInGame_Bot;
HttpContext.Current.Session["cardsInGame_User"] = cardsInGame_Human;
}
该函数精确模拟了真人发牌的方式：从牌堆中抽出一张牌并交给一名玩家，直到两名玩家每人都有 5 张牌。最后，机器人的牌放在 `cardsInGame_Bot` 会话变量中，而用户的牌放在 `cardsInGame_User` 会话变量中。
重要提示
现在，别忘了以上所有函数只在页面首次加载时调用。
if (!Page.IsPostBack)
{
Session["subround"] = 1;
GameMechanics.Init();
Session["shuffledDeck"] = GameMechanics.Shuffle();
GameMechanics.DistributeCards();
}
或者点击“**新游戏**”按钮时！
当用户选择一张牌时
用户选择卡片后，会发生以下事情：
- 用户选择的卡牌被添加到 `userChosenCards` 会话变量中，这是一个 `ArrayList`，它存储了用户在游戏过程中选择的所有卡牌。
- 用户选择的卡牌从 `cardsInGame_User` 会话变量中删除。
- 机器人选择的卡牌也同样处理。
- 之后，玩家交换剩余的卡牌，这些卡牌存储在用户的 `cardsInGame_User` 会话变量和机器人的 `cardsInGame_Bot` 会话变量中。
- 如果这是最后一轮，则计算并打印分数。
游戏计分
计分功能对 Minimax 算法至关重要。这就是为什么它值得单独一章。
在深入了解代码细节之前，我必须提及我们计算分数时卡牌的顺序非常重要。让我们看下面的例子：
在这里，根据 Watch It Played YouTube 视频频道，我们应该首先检查玩家是否仅凭一张牌就拥有每个相关花色的多数。如果情况属实，他将获得 8 分。然后，我们应该应用“将你数量最多的花色翻倍”的牌。这里，玩家拥有 3 种花色，每种花色一张牌。所以，我们必须将它们全部翻倍。最终，他将拥有：2 个宫殿，2 个图书馆和 2 个寺庙。之后，我们可以考虑其他卡牌，他将从图书馆获得 6 分，从宫殿获得 6 分。
分数将按照以下步骤计算：
- 计算玩家拥有所有类型花色的数量。
- 检查玩家是否拥有“赢得所有平局”的牌。
- 如果玩家拥有“仅凭一张牌在花色中占多数获得 8 分”的牌，则应用它。
- 检查玩家是否拥有“将你数量最多的花色数量翻倍”的牌，如果拥有则应用它。
- 计算具有以下策略的牌所给出的分数：`EachComb`、`All`、`Majority`、`DontHave`，同时如果玩家拥有“赢得所有平局”的牌，也要将其考虑在内。
- 如果玩家拥有“单张牌得分最高获得 8 分”的牌，则应用它。
主 `Score` 函数将如下所示：
public static void Score(out int botScore, out int userScore,
ArrayList botChosenCards, ArrayList userChosenCards)
{
int noCards = botChosenCards.Count;
int[] botCardsSymbols = new int[6], userCardsSymbols = new int[6];
botScore = 0; userScore = 0;
int maxPointsUser = 0, maxPointsBot = 0;
//Step 1
CountSymbols(botCardsSymbols, botChosenCards);
CountSymbols(userCardsSymbols, userChosenCards);
//Step 2
bool botHasWinAllTiesCard = HasCard(botChosenCards, (int)strategies.Ties);
bool userHasWinAllTiesCard = HasCard(userChosenCards, (int)strategies.Ties);
//Step 3 - if player has the card
//"For majority in suits with only one card gain 8 VPs"
botScore += OneCardMajority(botChosenCards, botCardsSymbols,
userCardsSymbols, ref maxPointsBot, botHasWinAllTiesCard);
userScore += OneCardMajority(userChosenCards, userCardsSymbols,
botCardsSymbols, ref maxPointsUser, userHasWinAllTiesCard);
//Step 4
DoubleAmountCard(botChosenCards, botCardsSymbols);
DoubleAmountCard(userChosenCards, userCardsSymbols);
//Stept 5
botScore += NoPoints(botChosenCards, userChosenCards,
botCardsSymbols, userCardsSymbols,
ref maxPointsBot, botHasWinAllTiesCard);
userScore += NoPoints(userChosenCards, botChosenCards, userCardsSymbols,
botCardsSymbols, ref maxPointsUser, userHasWinAllTiesCard);
//Stept 6 - check for the card
//"For scoring the highest with a single card gain 8 VPs
botScore += SingleCardHighestScore(botChosenCards, maxPointsBot,
maxPointsUser, botHasWinAllTiesCard);
userScore += SingleCardHighestScore(userChosenCards, maxPointsUser,
maxPointsBot, userHasWinAllTiesCard);
}
如你所见，我们需要检查玩家是否拥有某些卡牌很多次。由于代码中存在冗余不好，最好为此设置一个函数。这个函数应该接收玩家的卡牌和我们正在寻找的策略作为参数。它只是遍历所有卡牌，如果找到匹配项则返回 `true`，否则返回 `false`。
public static bool HasCard(ArrayList chosenCards, int strategy)
{
bool hasCard = false;
for (int i = 0; i < chosenCards.Count; i++)
{
Card card = (Card)chosenCards[i];
if (card.strategyType == strategy)
{
hasCard = true;
break;
}
}
return hasCard;
}
在深入探讨每个步骤的细节之前，值得一提的是，每次我计算每张牌获得的分数时，我都会更新单张牌获得的最高分数。对于机器人，这将存储在 `maxPointsBot` 变量中，对于用户，将存储在 `maxPointsUser` 变量中。它们的初始值将设置为 `0`，并将通过引用传递给所有相关函数。通常，它们可以在这些函数中以 `maxPoints` 的名称找到。
为了更好地理解，我将使用以下示例：
步骤 1
public static void CountSymbols(int[] cardsSymbols, ArrayList chosenCards)
{
for (int i = 0; i < chosenCards.Count; i++)
{
Card card = (Card)chosenCards[i];
cardsSymbols[(int)card.locationType]++;
}
}
如您所见，`CountSymbols` 函数会遍历玩家拥有的所有牌，并更新一个名为 `cardsSymbols` 的数组。该数组为游戏中每种花色类型设置一个条目：0 代表没有花色的牌，1 代表 `Palace`，2 代表 `Library`，3 代表 `Garden`，4 代表 `Temple`，5 代表 `Stronghold`。其目的是跟踪玩家拥有每种花色的数量。在上面的示例中，玩家 A 有 1 张没有花色的牌，1 张 `Palace`，1 张 `Garden`，1 张 `Library`，1 张 `Temple`，并且没有 `Strongholds`。因此，用户的 `cardsSymbol` 数组将具有以下值：[1,1,1,1,1,0]。而机器人的 `cardsSymbol` 数组将如下所示：[0,1,0,1,1,2]，因为它有 0 张没有花色的牌，1 张 `Palace`，0 张 `Libraries`，1 张 `Garden`，1 张 `Temple` 和 2 张 `Strongholds`。
第二步
bool botHasWinAllTiesCard = HasCard(botChosenCards, (int)strategies.Ties);
bool userHasWinAllTiesCard = HasCard(userChosenCards, (int)strategies.Ties);
我们只需使用 `HasCard` 函数检查用户或机器人是否拥有“赢得所有平局”的牌。结果分别保存在机器人的 `botHasWinAllTiesCard` 变量和用户的 `userHasWinAllTiesCard` 变量中。
在这个例子中，玩家 A 拥有这张牌。所以 `userHasWinAllTiesCard` 的值为 true，而 `botHasWinAllTiesCard` 为 `false`。
步骤 3
public static int OneCardMajority(ArrayList chosenCards,
int[] cardsSymbols, int[] opponentCardsSymbols,
ref int maxPoints, bool hasWinAllTiesCard)
{
int points = 0;
bool hasCard = HasCard(chosenCards, (int)strategies.OneCardMajority);
if (hasCard == true)
{
int noCardsOneSuit = 0, opponentNoCardsOneSuit = 0;
for (int j = 1; j <= noPlacesTypes; j++)
{
if (cardsSymbols[j] == 1) noCardsOneSuit++;
if (opponentCardsSymbols[j] == 1) opponentNoCardsOneSuit++;
}
if ((noCardsOneSuit > opponentNoCardsOneSuit) ||
(noCardsOneSuit == opponentNoCardsOneSuit &&
hasWinAllTiesCard == true)) points += 8;
}
if (points > maxPoints) maxPoints = points;
return points;
}
该函数通过调用 `HasCard` 函数来检查玩家是否拥有“仅凭一张牌在花色中占多数获得 8 分”的牌。如果找到这样一张牌，它会遍历在步骤 1 中填充的 `cardsSymbols` 数组和 `opponentCardsSymbols` 数组中的所有条目。然后它计算每个玩家拥有多少张只有一张牌的花色。如果上述数组的某个条目（除了第一个）的值为 1，那么我们就有一张只有一张牌的花色。如果玩家拥有“仅凭一张牌在花色中占多数获得 8 分”的牌并且比对手拥有更多这样的花色，则将 8 分添加到他的分数中。如果他拥有这张牌并且与对手拥有相同数量的此类花色，并且拥有“赢得所有平局”的牌，他也可以获得 8 分。
在此示例中，两位玩家都没有这张牌。因此，未添加任何点数。
步骤 4
public static void DoubleAmountCard(ArrayList chosenCards, int[] cardsSymbols)
{
//verify if the user has the card
bool hasCard = HasCard(chosenCards, (int)strategies.DoubleAmount);
int max = 0;
if (hasCard == true)
{
for (int i = 1; i <= noPlacesTypes; i++)
if (cardsSymbols[i] > max) max = cardsSymbols[i];
for (int i = 1; i <= noPlacesTypes; i++)
if (cardsSymbols[i] == max) cardsSymbols[i] = max * 2;
}
}
此功能检查玩家是否拥有“将你最多数花色数量翻倍”的牌。如果玩家拥有它：
- 它通过遍历 `cardsSymbols` 数组中除第一个之外的所有条目，并选择其最大值，来检查相同类型花色的最大数量。该值保存在 `max` 变量中。
- 它将 `cardsSymbols` 数组中等于 `max` 的值翻倍。
在最后一个例子中，没有玩家拥有这张牌。因此，没有加分。
步骤 5
现在我们必须遍历用户的所有牌，看看他是否拥有以下策略之一：`(int)strategies.EachComb`、`(int)strategies.All`、`(int)strategies.Majority`、`(int)strategies.DontHave`。
- 如果我们遇到一张 `(int)strategies.EachComb` 牌：
case ((int)strategies.EachComb): int noSets = 100; for (int j = 0; j < (int)card.strategyLocations.Count; j++) { int loc = (int)card.strategyLocations[j]; if (cardsSymbols[loc] < noSets) noSets = cardsSymbols[loc]; } auxPoints = card.points * noSets; points = points + auxPoints; if (auxPoints > maxPoints) maxPoints = auxPoints; break;我们验证玩家拥有卡牌上写明的花色或花色组合的次数。答案由 `min{ cardsSymbols[x] | x in card.strategyLocations}` 给出。分数通过将此数字乘以卡牌为目标中写明的花色或花色组合提供的点数来计算。
让我们看下面的例子：
玩家拥有这样一张牌：每拥有一个由图书馆和花园组成的组合，就能获得 5 分。因此 `x` 将取值：`(int)locations.Library` 和 `(int)locations.Garden`。玩家的王国中有 2 个图书馆和 1 个花园。所以 `cardsSymbols[(int)locations.Library]` 是 2，而 `cardsSymbols[(int)locations.Garden]` 是 1。它们之间的最小值为 1。尽管他有 2 个图书馆，但他只能组成 1 个组合，因为他只有 1 个 `Garden`。因此，`noSets`（他将从这张牌中获得积分的组合数量）是 1。综上所述，这张牌将为他带来 1*5 分。
从每种特定类型的花色获得 3 分的牌的分数计算起来甚至更容易，但这种方法更通用，适用于所有具有“`EachComb`”策略的牌，包括它们。
现在，我们回到玩家 A 和 B。你能计算出他们将从拥有 `EachComb` 策略的牌中获得多少分数吗？
答案：玩家 A 获得 5 分，玩家 B 获得 6 分。
- 如果我们遇到一张 `(int)strategies.All` 牌：
这种情况与第一种情况非常相似。不同的是，在游戏结束时，每个玩家都有 5 张牌。因此，如果这张牌的目标达成，每张牌上都有不同的符号，因为游戏中有 5 种花色。所以 `cardsSymbols` 数组将是这样的：[0,1,1,1,1,1]。
- 如果我们遇到一张 `(int)strategies.Majority` 牌：
case ((int)strategies.Majority): int place = (int)card.strategyLocations[0]; if (cardsSymbols[place] > opponentCardsSymbols[place] || (cardsSymbols[place] == opponentCardsSymbols[place] && hasWinAllTiesCard)) { points += card.points; if (card.points > maxPoints) maxPoints = card.points; } break;我们检查玩家在相关花色类型上的数量是否多于对手。这通过使用 `cardsSymbols` 和 `opponentCardsSymbols` 数组中与卡牌上指定的花色类型对应的值来完成。如果玩家与对手拥有相同数量的花色，并且也拥有“赢得所有平局”的卡牌，他也可以获得 7 分。
在这个例子中：
- 玩家 A 拥有“宫殿多数获得 7 分”的牌。玩家 A 有 1 座宫殿，玩家 B 也有 1 座宫殿。尽管是平局，但玩家 A 仍然获得了 7 分，因为他也拥有“赢得所有平局”的牌。
玩家 A 还拥有“寺庙多数获得 7 分”的牌，他发现自己与上述情况相同，获得了 7 分。
综上所述，玩家 A 将从属于这种情况的牌中获得 14 分。
- 玩家 B 拥有“图书馆多数获得 7 分”的牌，但不幸的是他没有图书馆。
玩家 B 也有“花园多数获得 7 分”的牌。玩家 B 有 1 个花园，而玩家 A 也有 1 个。不幸的是，他没有“赢得所有平局”的牌，所以他从这张牌中也获得了 0 分。
综上所述，玩家 B 将从属于这种情况的牌中获得 0 分。
- 玩家 A 拥有“宫殿多数获得 7 分”的牌。玩家 A 有 1 座宫殿，玩家 B 也有 1 座宫殿。尽管是平局，但玩家 A 仍然获得了 7 分，因为他也拥有“赢得所有平局”的牌。
- 如果我们遇到一张 `(int)strategies.DontHave` 牌：
case ((int)strategies.DontHave): auxPoints = 0; for (int j = 1; j <= noPlacesTypes; j++) if (cardsSymbols[j] == 0) auxPoints += card.points; points += auxPoints; if (auxPoints > maxPoints) maxPoints = auxPoints; break;为此，我们检查 `cardsSymbols` 数组中存储的所有值（除了第一个），每次找到 0 时，就给玩家的分数加上 3 分。这是因为他没有任何对应于该条目类型的花色。
在这个例子中，玩家 B 拥有这张牌。他的 `cardsSymbol` 数组看起来像这样：[0,1,0,1,1,2]。由于第一个值对应于没有花色的牌，它将不被考虑在内。因此，玩家 B 拥有所有花色类型，除了一个。确实，他没有任何花园！
步骤 6
public static int SingleCardHighestScore
(ArrayList chosenCards, int maxPoints, int opponentMaxPoints, bool hasWinAllTiesCard)
{
bool hasSingleCardHighestScore = HasCard(chosenCards,
(int)strategies.SingleCard);
if (hasSingleCardHighestScore)
{
if (maxPoints > opponentMaxPoints ||
(maxPoints == opponentMaxPoints &&
hasSingleCardHighestScore == true))
return deck[18].points;
}
return 0;
}
正如我所提到的，也如代码所示，我在计算每张牌获得的分数后更新了 `maxPointsBot` 和 `maxPointsUser` 变量。现在，剩下的就是检查玩家是否拥有“单张牌得分最高获得 8 分”的牌，并将他的 `maxPoints` 值与对手单张牌获得的最高分数进行比较。别忘了将“赢得所有平局”的牌考虑在内。
在这个例子中，`maxPointsUser` 从“宫殿多数获得 7 分”或“寺庙多数获得 7 分”的牌中获得 7 分，而 `maxPointsBot` 从“每个要塞获得 3 分”的牌中获得 6 分。用户拥有“单张牌得分最高获得 8 分”的牌。他完成了目标，因此用户获得 8 分。
最后，在这个例子中，用户有 27 分，而机器人只有 9 分。但等我们给机器人一些智慧！
Minimax 算法
两位玩家都选完第一张牌后，他们交换各自剩余的牌。此时，玩家知道所有在场的牌。他们清楚地知道对手的所有可能性。这使得我们能够创建一个游戏树，它考虑了由玩家各自选择决定的所有可能的卡牌组合。因此，我们可以说这款游戏是确定性的，除了第一轮。为这款游戏创建图形表示相当困难，所以为了更简单的解释，我们来改变游戏规则！
我们假设两位玩家都只用三张牌开始，并且他们已经知道对手的牌是什么。这样，我们可以更深入地探讨 Minimax 理论的实际应用。总结一下：
- 机器人将开始游戏。因此，蓝色节点对应于机器人的选择回合，红色节点对应于玩家的行动。
- 每位玩家有三张牌。在这个例子中，他们将在每次选择后交换牌。
- 用户（红色）手中有以下牌 [A1, A2, A3]。
- 机器人（蓝色）手中有以下牌 [B1, B2, B3]。
考虑到这一点，我们可以构建以下博弈树：
我们从左边第一个蓝色节点开始。机器人可以从其直接子节点中选择任意一张牌：B1、B2、B3。假设机器人选择了 B3 牌。因此，我们前进到 B3 红色节点及其自己的路径。现在轮到用户了。他可以在 [A1, A2, A3] 牌中进行选择。假设他选择了 A2 牌。我们到目前为止的组合是 B3A2。
当两位玩家都选择一张牌后，即树的每两个级别（更准确地说，每个红色节点级别）之后，回合都会改变。请记住，每回合之后，牌都会在玩家之间交换！
然后又轮到机器人了。剩下的选项是：它将选择 A1 或 A3 牌。因此，从这一点开始，我们有 4 种可能的情况：
B3A2 A1B1
B3A2 A1B2
B3A2 A3B1
B3A2 A3B2
因此，在机器人选择一张牌后，用户也将选择一张。所以我将制作 2 个函数。每个玩家一个。我将它们命名为 Max (机器人) 和 Min (用户)。它们将像这样互相调用：
这看起来像一个无限循环，但我们很快就会找出如何停止递归。
首先，让我们看看这些函数需要哪些变量作为参数。我们只需要我们将要从中选择的牌：`botCardsToChooseFrom`、`userCardsToChooseFrom` 以及我们已经选择的牌，以便我们可以计算每种配置下机器人的最终分数：`botChosenCards`。此外，我们还需要一个输出变量，用于我们决定为机器人选择的牌：`cardNo`。
现在，对于每个蓝色节点，我们将遍历 `botCardsToChooseFrom` 中的所有牌，对于每张单独的牌，我们将复制此数组，从中取出该牌，并创建另一个副本到 `botChosenCards`，并将该牌添加进去。然后，我们用这些副本调用 `Min` 函数。我们创建副本是因为我们需要原始数组来处理 `botCardsToChooseFrom` 中我们将选择的下一张牌，而且，如您所知，`ArrayList` 是按引用传递的。
目前，`Max` 函数将如下所示：
public static void Max(ArrayList botCardsToChooseFrom, ArrayList botChosenCards,
ArrayList userCardsToChooseFrom, ArrayList userChosenCards, out int cardNo)
{
for (int i = 0; i < botCardsToChooseFrom.Count; i++)
{
Card card = (Card)botCardsToChooseFrom[i];
ArrayList auxBotCardsToChooseFrom = new ArrayList(botCardsToChooseFrom);
auxBotCardsToChooseFrom.RemoveAt(i);
ArrayList auxBotChosenCards = new ArrayList(botChosenCards);
auxBotChosenCards.Add(card);
Min(auxBotCardsToChooseFrom, auxBotChosenCards,
new ArrayList(userCardsToChooseFrom),
new ArrayList(userChosenCards), out auxCardNo);
}
现在，是时候看看如何停止无限循环了。正如你已经猜到的，当 `botCardsToChoose` 只剩下一张牌时，我们可以停止，因为它别无选择，只能选择一张特定的牌。此时，我们不再调用 `Min` 函数，因为我们真的不在乎用户的最后一张牌。在图形表示中，这些最终的牌用黑色着色。当我们到达它们时，我们可以计算机器人的最终分数，因为所有牌都已选择。沿从根到叶的路径上找到的牌形成了一个独特的最终状态组合。当我们将其转化为代码时，我们得到：
if (botCardsToChooseFrom.Count == 1)
{
int userScore, botScore;
botChosenCards.Add(botCardsToChooseFrom[0]);
GameMechanics.Score(out botScore, out userScore,
botChosenCards, userChosenCards);
return botScore;
}
之后，我们可以将 `Max` 函数的 `void` 改为 `int`，因为它会返回一个值。
到目前为止，我们的机器人知道如何计算所有可能性以及由此产生的每个分数。不幸的是，它不知道如何选择正确的方案。当然，它会选择能带来最佳分数的方案！但用户的输入来了。机器人完美的卡牌路径可能会被用户的选择挫败。这就是为什么我们应该考虑最坏的情况。我们应该假设用户总是会选择最小化机器人分数的卡牌，而机器人会尝试最大化自己的分数。这就是为什么用户被称为 `Min`，而机器人被称为 `Max`。
这是与上面呈现的博弈树对应的 Minimax 树。这棵树是根据 `Min` 和 `Max` 函数的返回值从叶子到根填充的。
叶子简单地返回沿着其到根的路径上卡牌集合的分数。`cardNo` 接收对应于叶子的卡牌。
我们将从叶到根分析这棵树，而不是反过来，因为我们知道每条单独路径的精确分数。
在第三回合，每个玩家可以在 2 张牌中选择。红色（Min）查看其子节点的分数，并选择能为蓝色（Max）带来最小分数的牌。如果红色子节点的值为 19 和 22，他将选择第一个子节点返回的牌。换句话说，他会尽力阻碍蓝色最好的路径。然后，蓝色也查看其子节点的值，由于他试图最大化自己的分数，他会选择对应于他能获得的最大分数的牌。例如，如果其子节点的值为 19 和 15，他会选择其第一个子节点提供的牌，这能给他带来 19 分而不是 15 分。依此类推。
我们来分析一下根节点：根节点有以下子节点：`Child1`：{值：15，牌：B3}，`Child2`：{值：15，牌：B2}。`Child3`：{值：12，牌：B1}。其子节点的最大值为 15。在这种情况下，机器人将选择由 `Child1` 或 `Child2` 提供的牌。这意味着如果在第一轮中它选择 B3 或 B2 牌，它将至少获得 15 分，前提是它将在接下来的回合中继续应用此算法。
这是上面提到的函数的最终代码：
const int INF = 10000;
public static int Max(ArrayList botCardsToChooseFrom, ArrayList botChosenCards,
ArrayList userCardsToChooseFrom, ArrayList userChosenCards, out int cardNo)
{
int maxScore = -INF;
cardNo = 0;
if (botCardsToChooseFrom.Count == 1)
{
int userScore, botScore;
botChosenCards.Add(botCardsToChooseFrom[0]);
GameMechanics.Score(out botScore, out userScore,
botChosenCards, userChosenCards);
return botScore;
}
for (int i = 0; i < botCardsToChooseFrom.Count; i++)
{
Card card = (Card)botCardsToChooseFrom[i];
ArrayList auxBotCardsToChooseFrom = new ArrayList(botCardsToChooseFrom);
auxBotCardsToChooseFrom.RemoveAt(i);
ArrayList auxBotChosenCards = new ArrayList(botChosenCards);
auxBotChosenCards.Add(card);
int auxCardNo;
int score = Min(auxBotCardsToChooseFrom, auxBotChosenCards,
new ArrayList(userCardsToChooseFrom),
new ArrayList(userChosenCards), out auxCardNo);
if (score > maxScore)
{
maxScore = score;
cardNo = i;
}
}
return maxScore;
}
public static int Min(ArrayList botCardsToChooseFrom, ArrayList botChosenCards,
ArrayList userCardsToChooseFrom,
ArrayList userChosenCards, out int cardNo)
{
int minScore = INF;
cardNo = 0;
for (int i = 0; i < userCardsToChooseFrom.Count; i++)
{
Card card = (Card)userCardsToChooseFrom[i];
ArrayList auxUserCardsToChooseFrom =
new ArrayList(userCardsToChooseFrom);
auxUserCardsToChooseFrom.RemoveAt(i);
ArrayList auxUserChosenCards = new ArrayList(userChosenCards);
auxUserChosenCards.Add(card);
int auxCardNo;
int score = Max(auxUserCardsToChooseFrom, new ArrayList(botChosenCards),
new ArrayList(botCardsToChooseFrom),
auxUserChosenCards, out auxCardNo);
if (score < minScore)
{
minScore = score;
cardNo = i;
}
}
return minScore;
}
值得一提的是，`Minimax` 函数在游戏的每一轮中都会被调用。这是因为在现实中，用户可以做出不同于最小化机器人分数的最佳选择。该算法假设最坏情况会发生，如果没发生，机器人甚至可以获得更多分数！
另外，请记住这是一款运气游戏。该算法尽力在给定条件下为机器人争取尽可能多的分数。但用户仍然可以通过技能和运气的结合，比机器人能获得的最大分数还要高。如果我们的机器人是完美的，就没有人愿意玩这个游戏了！
带 Alpha Beta 剪枝的 Minimax
第一轮本质上不是确定性的，因为我们无法知道所有在玩中的牌。机器人只知道自己的 5 张牌。对手可以从其他 13 张牌中拥有任意 5 张牌的组合：`cardsLeft`。因此，有 1287 种可能的组合！机器人无法知道它能选择的绝对最佳牌，但我们仍然可以为它实现一种策略。这就是人工智能的美妙之处！由于这个问题没有完美的解决方案，我们可以发挥我们的创造力！这是一种可能的策略：
我们可以用众所周知的回溯算法生成所有这些组合。
public static void Back(int where, int k, int n, int[] comb, int[] cardsLeft,
ArrayList botCardsInGame, int[] timesChosen)
{
if (where == k + 1) Sol(k, comb, cardsLeft, botCardsInGame, timesChosen);
else
{
for (int i = comb[where - 1] + 1; i <= n; i++)
{
comb[where] = i;
Back(where + 1, k, n, comb, cardsLeft, botCardsInGame, timesChosen);
}
}
}
public static void Sol(int k, int[] comb, int[] cardsLeft,
ArrayList botCardsInGame, int[] timesChosen)
{
ArrayList userCardsToChooseFrom = new ArrayList();
for (int i = 1; i <= 5; i++)
userCardsToChooseFrom.Add(GameMechanics.deck[cardsLeft[comb[i]]]);
int cardNo;
int score = AlphaBetaMax(botCardsInGame, new ArrayList(),
userCardsToChooseFrom, new ArrayList(), out cardNo, -INF, INF);
if (score > 0)
timesChosen[cardNo]++;
}
我们可以对我们找到的每个组合应用 `Minimax` 算法。鉴于一张牌可能对某个组合是最好的，但不一定对其他组合也很好，这将给我们带来许多不同的解决方案。一种选择是选择对大多数可能组合来说是最佳选择的牌。每张牌被选择的次数保存在 `timesChosen` 数组中。这个数组的最大值将指出机器人将在第一轮中选择的牌。
不幸的是，这需要相当长的时间，用户会感到厌烦。我们必须找到一种方法来减少它！幸运的是，Minimax 算法有一个更好的版本，叫做带 Alpha Beta 剪枝的 Minimax。它使用的思想是相同的，但它不会遍历整个博弈树。这得益于我们的新朋友 `alpha` 和 `beta`！
我们以以下博弈树为例：
当我们应用 `Minimax` 算法时，节点按此顺序访问：
B, E, K, L, F, M, N, C, G, O, P, H, Q, R, D, I, S, T, J, U, V
这对于理解带 Alpha Beta 剪枝的 Minimax 算法非常重要！
另外，假设它有以下 Minimax 树：
现在是时候认识 `alpha` 和 `beta` 了。你准备好了吗？
- `alpha` 是最大化玩家在当前级别或更高级别可以保证的最佳值。
- `beta` 是最小化玩家在当前级别或更高级别可以保证的最佳值。
这就是我们为 `Max` 用户更新 `alpha` 的方式：
bestScore = -INF
for each child node:
value = AlphaBetaMin(child,alpha,beta)
bestScore = max(bestScore,value)
alpha = max(alpha,bestScore)
return bestScore
对于 Min 用户，我们有 `beta`：
bestScore = INF
for each child node:
value = AlphaBetaMax(child,alpha,beta)
bestScore = min(bestScore,value)
beta = min(beta,bestScore)
return bestScore
这就是在带 alpha-beta 剪枝的 Minimax 算法中 `alpha` 和 `beta` 的更新方式：
到目前为止，除了 `alpha` 和 `beta`，我们拥有与之前相同的算法。还没有优化。请耐心等待！
经过 A、B、E、K、L 后，我们知道 Min 在 B 中通过选择 E 可以获得 3。此时 B 中的 `Beta` 值为 3。
然后，我们访问 F 和 M，得知 Max 在 F 中通过选择 M 可以获得 5 分。目前，F 中的 `alpha` 值为 5。但 F 中的 `beta` 值为 3。这意味着 Min 玩家已经有一个选择 (E) 可以为他的对手带来少于 5 分，因此，他绝不会选择 F。等等！我们还没有计算 N 的值！我们来看看这个值会发生什么：
- 如果 N 的值大于 M 的值，则意味着 Max 通过选择 N 而不是 M 可以获得更多分数。不幸的是，红色玩家已经有了一个选择，它将迫使蓝色玩家获得比 N 或 M 更少的分数，并且不会给他机会在这两者之间进行选择。
- 如果 N 的值小于 M 的值，则意味着 Max 将选择 M。但红色玩家已经有了一个选项，它将迫使蓝色玩家获得比 M 甚至比 N 更少的分数。
总之，无论 N 的值是多少，红色玩家总是会选择 E 而不是 F！这意味着我们不必浪费时间去计算 N 的值！每当 `beta` 小于或等于 `alpha` 时，就会发生这种情况。在这种情况下，我们应该停止寻找可以从我们所在节点的子节点获得的其它值，因为玩家实际上永远不会有机会到达那个节点。
将此添加到我们的代码中，我们得到：
//for MAX
bestScore = -INF
for each child node:
value = AlphaBetaMin(child,alpha,beta)
bestScore = max(bestScore,value)
alpha = max(alpha,bestScore)
if(beta<=alpha)
break;
return bestScore
//for MIN
bestScore = INF
for each child node:
value = AlphaBetaMax(child,alpha,beta)
bestScore = min(bestScore,value)
beta = min(beta,bestScore)
if(beta<=alpha)
break
return bestScore
最后，算法使用的树将如下所示：
在这张图片中，黑色节点表示它们从未被访问过甚至创建过。
总而言之，带 alpha-beta 剪枝的 Minimax 比 Minimax 算法更快！
结论
总而言之，现在我们有了一个实际的游戏，其所有机制都已实现和解释。此外，我们还设计了一个功能性机器人，它在考虑到游戏也具有非确定性部分的情况下尽力而为。其策略基于 Minimax 和带 Alpha Beta 剪枝的 Minimax 算法。最令人惊叹的部分是，目前还没有其他源代码或文章专注于此游戏的实现或为其创建机器人！
该机器人可以在此处在线测试，包括前端在内的完整源代码可以从文章顶部下载。
这个机器人太棒了，它会替自己说话！如果你坚持读完了这篇相当长的教程，那也说明你很棒！希望这向你展示了通过简单的算法、一点点想象力、努力和耐心，可以实现许多伟大的事情。
最后通知
所有与“时光之潮”棋盘游戏相关的内容仅用于学术目的。创建了一篇科学文章，旨在参加AI TensorFlow 挑战赛。未对受版权保护的材料进行任何商业用途。游戏产生的所有权利均保留给其设计师、艺术家和制作人。