时间僵尸和游戏浪潮– Minimax的应用(带有Alpha Beta修剪)（译文）

原文地址：https://www.codeproject.com/Articles/1272876/Tides-of-Time-Bot-and-Game-Application-of-Minimax

原文作者：Oana Mancu

译文由本站 robot-v1.0 翻译

前言

Any deterministic game can be broken down to its core functionalities. By understanding them, one can implement fundamental algorithms such as Minimax (with alpha beta pruning), thus paving the way towards a better AI opponent.

任何确定性游戏都可以细分为其核心功能.通过了解它们,可以实现诸如Minimax(带有alpha beta修剪)的基本算法,从而为更好的AI对手铺平了道路.

• 下载源代码2.1 MB(Download source code - 2.1 MB)

内容(Contents)

• 介绍(Introduction)

• 规则(Rules)

• 将游戏机制纳入代码(Putting the Game Mechanics Into Code)

  • 存放卡(Storing the Cards)
  • 卡洗牌(Card Shuffling)
  • 重要的提醒(Important Notice)
  • 用户选择卡片时(When a Card Is Chosen by the User)

• 计分比赛(Scoring the Game)

• Minimax算法(The Minimax Algorithm)

• 带有Alpha Beta修剪的Minimax(Minimax With Alpha Beta Pruning)

• 结论(Conclusion)

• 最终通知(Final Notice)

介绍(Introduction)

另一个Minimax理论介绍？没有!尽管本文着重于构建使用该算法的机器人,但它也包含了用C#编写游戏机制的所有必要细节,因此最终您将拥有一个真正的游戏!可以用Minimax算法解决的又一经典游戏吗？没有!关于这些标题的文章已经很多.那么,这实际上是关于什么的？这是关于为现代纸牌游戏建立明智的对手.一款从未出于学术目的进行过分析的游戏.从来没有关于它及其机制的文章被撰写过.惊人的(Yet another Minimax theoretical presentation? No! Though this paper focuses on building a bot that uses the algorithm, it also contains all the necessary details for writing the mechanics of the game in C#, so that in the end, you will have an actual game! Yet another classical game that can be solved with the Minimax algorithm? No! An abundance of articles were already written on those titles. So, what is this actually about? It is about building an intelligent opponent for a modern card game. A game which was never before analyzed for academic purposes. Never before has an article been written about it and its mechanics. The amazing) 时间潮(Tides of Time) 由出版(is published by) 门户游戏(Portal Games) 由KristianČurla开发.(and developed by Kristian Čurla.)

人工智能就是创造力.通常,在组织数据之后,您可以从Minimax之类的经典算法开始,然后添加和探索新事物,从而使您的程序越来越好.希望本文将提供您将继续开发的基本bot,使其变得更聪明,直到被击败为止!另外,我希望它能给您启发,探索传统界外AI的美好世界!(Artificial intelligence is all about creativity. Usually, after you organize your data, you can start with a classical algorithm like Minimax and then add and explore new things, making your program better and better. Hopefully, this article will provide a basic bot that you will continue to develop, making it even smarter, until it cannot be beaten! Also, I hope that it will give you the inspiration to explore the wonderful world of AI outside its traditional boundaries!)

如果我还没有说服您阅读本文,请看看(If I haven’t convinced you to read this article yet, just have a look) 这里(here) ,在这里您可以玩实际的游戏并测试遵循本教程后将拥有的超棒机器人.让我们从规则开始.(, where you can play the actual game and test the awesome bot you’ll have after following this tutorial. Let’s start with the rules.)

规则(Rules)

时间的潮汐是基于回合的策略纸牌游戏.其目标是通过选择最适合您的王国的牌来积累胜利点,同时关注对手的选择.每张卡都有一定的能力或目标,如果满足,将为您提供许多胜利点.尽管该游戏由三回合组成,但由于其重复性,本文将仅探讨第一回合的机制.(Tides of Time is a turn-based strategy card game. Its goal is to amass Victory Points, by choosing the most suitable cards for your kingdom, while keeping an eye on your opponent’s choices. Each card has a certain ability or an objective which, if fulfilled, grants you a number of Victory Points. Though the game is comprised of three separate rounds, the present article will be exploring the mechanics of only the first one, due to its repetitive nature.)

游戏由18张扑克牌组成.他们中的15个在底部都有一个名称,在顶部是一个目标,在右侧是一个得分指示器,在左侧是一个套件.其他三个只有名称和能力.游戏中有五个套件,每个套件三张卡:(The game consists of 18 playing cards. 15 of them each have a name at the bottom, an objective at the top, a scoring indicator on the right, and a suite on the left. The other three only have a name and an ability. There are five suites in the game and three cards of each suite:)

宫 -(Palace -)

图书馆 -(Library -)

花园-(Garden -)

庙-(Temple -)

要塞-(Stronghold -)

这些功能也很容易理解,因为它们做了卡片上写的:(The abilities are also very easy to understand as they do what is written on the cards:)

例如,古代分水卡有皇宫套间,如果您在本回合结束时拥有的要塞套间比对手多,将给您七个胜利点.如果您和您的对手都拥有一个"要塞"套件,那么目标就无法实现.另一方面,Kings Nest卡可以赢得所有关系.因此,在这种情况下,这两张牌的组合为玩家提供了7个胜利点.(For example, The Ancient Divide card has the Palace suite and will grant you seven Victory Points if at the end of the round you possess more Stronghold suites than your opponent. If both you and your opponent have one Stronghold suite, the objective is not fulfilled. On the other hand, The Kings Nest card grants the ability to win all ties. Thus, in this scenario, these two cards combined grant the player 7 Victory Points.)

游戏的设置阶段始于洗牌.每个玩家被发五张牌.其他的则面朝下放在堆栈中.因此,在游戏开始时,两个玩家仅知道各自的五张牌.(The Setup phase of the game begins with the shuffling of the cards. Each player is dealt five cards. The others are placed face down in a stack. Thus, at the beginning of the game, both players only know their respective five cards.)

然后,每个玩家从他的手中选择一张牌并将其面朝下放在桌子上.两位玩家同时将卡面朝上.这是他们各自王国的第一部分.他们俩此时都无法改变主意.在游戏期间,两张牌都将保持正面朝上.(Then each player chooses a card from his hand and places it face down on the table. Both players simultaneously turn the card face up. This is the first part of their respective kingdoms. Neither of them can change their minds at this point. Both cards will remain face up for the duration of the game.)

接下来,玩家交换手中的所有卡.因此,每个玩家现在将拥有各自对手开始使用的四张牌.游戏继续进行.玩家拿起一张牌,同时将其正面朝上.那张卡现在是他们王国的一部分.(Next, players exchange all the cards in their hand. Thus, each player will now have four of the cards that their respective opponent started with. The game proceeds as before. Players pick a card and simultaneously turn it face up. That card is now part of their kingdom.)

交换继续进行,直到没有玩家剩余纸牌为止.通过检查每个能力或目标及其各自的收益来计算分数.(The exchanges continue until none of the players has no more cards remaining. The score is calculated by examining each ability or objective and their respective yields.)

现在,您可以通过实际玩游戏来充分利用这些规则(Now you can make good use of these rules by actually playing the game) 这里(here) !(!)

将游戏机制纳入代码(Putting the Game Mechanics Into Code)

现在是时候深入研究代码了!首先,除非我们在程序中实现了卡片,实际规则以及计算得分的功能,否则我们就无法制定机器人的策略.因此,让我们创建一个让我们的智能机器人震撼的设置!(Now it’s time to dive into the code! First of all, we cannot have a strategy for our bot until we implemented in our program the cards, the actual rules, and a function that calculates us the score. So let’s create the setting where our clever bot will rock!)

存放卡(Storing the Cards)

在现实世界中,卡是对象.因此,我们应该有一个名为(In the real world, a card is an Object. Thus we should have a class named) Card 具有以下属性:(with the following properties:)

public int picNo;
public int locationType { get; set; }
public int strategyType { get; set; }
public ArrayList strategyLocations { get; set; }
public int points { get; set; }

哪里:(where:)

• picNo 这将帮助我们检索特定卡的相应图片,并在我们的静态卡组中找到它.(will help us retrieve the corresponding picture for a certain card and to find it in our static deck of cards.)
• locationType 代表卡片左上角的符号或套件.它可以采用以下值:卡上没有符号时为0,宫殿为1,图书馆为2,花园为3,寺庙为4,堡垒为5.为了提高可读性,我使用了(represents the symbol or suite from top left corner of the card. It can take the following values: 0 when the card has no symbol on it, 1 for Palace, 2 for Library, 3 for Garden, 4 for Temple and 5 for Stronghold. To improve readability, I used an) enum 数据类型:(data type:)
• strategyType 表示写在卡片右上方的目标或能力.为此,我使用了以下内容(represents the objective or the ability written at the top right of the card. For this, I used the following) enum :(:)哪里:(where:)

EachComb 指这些卡:(refers to these cards:)

All 指:(refers to:)

Majority 指:(refers to:)

Ties 指:(refers to:)

DontHave 指:(refers to:)

OneCardMajority 指:(refers to:)

DoubleAmount 指:(refers to:)

SingleCard 指:(refers to:)

• strategyLocation 是一个(is an) ArrayList 指出适合的西装类型(which indicates the types of suits to which the) strategyType 参考.它是(refers. It is) null ,如果卡上未指定此类位置.(, if there is no such place specified on the card.)例如,对于以下卡片,我的这些条目中有(For example, for the following card, I have these entries in my) ArrayList :(:) (int)locations.Palace ,(,) (int)locations.Stronghold, (int)locations.Temple

• points 是代表您达到卡上所写目标的点数的属性.例如,对于价值超过(is the property that represents the number of points you gain if you fulfill the objective written on the card. For example, for the card above the value of) points 是(is) 9 .(.) 的(The) Card 类也有一个构造函数:(class also has a constructor:)

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;
        }

将所有卡置于静态时使用(which is used when putting all the cards in the static) Card 命名数组(array named) deck 通过调用(by calling the) Init() 功能:(function:)

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);
        }

卡洗牌(Card Shuffling)

既然我们在游戏中实际上已经拥有一副纸牌了,是时候编写一个函数以便在每次新游戏前都可以将纸牌洗牌了:(Now that we actually have a deck of cards in our game, it is time to write a function so that the cards can be shuffled before every new game:)

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;
        }

该函数使用名为bool的数组(The function uses a bool array named) viz 对于已存在的卡,该值保持为true(which holds the value true for the cards that are already in the) ShuffledDeck .会生成1到18范围内的随机数,直到将所有卡都放入(. Random numbers from the range 1 to 18 are being generated until all the cards are being put into the) ShuffledDeck 堆栈.(stack.)

洗牌后,我们可以通过调用以下函数将其分发给玩家:(Once the cards are shuffled, we can deal them to the players by calling the following function:)

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张牌为止.最后,将机器人的卡片放置在(The function imitates exactly the manner in which real people deal cards when they play: a card is pulled from the stack and given to a player until both players have 5 cards each. In the end, the bot’s cards are placed in the) cardsInGame_Bot 会话变量,而用户的卡放置在(session variable, while the user’s cards are placed in the) cardsInGame_User 会话变量.(session variable.)

重要的提醒(Important Notice)

现在,别忘了上述所有函数都是在首次加载页面时调用的:(Now, don’t forget that all of the above functions are called just when the page is loaded for the first time:)

if (!Page.IsPostBack)
        {
            Session["subround"] = 1;
            GameMechanics.Init();
            Session["shuffledDeck"] = GameMechanics.Shuffle();
            GameMechanics.DistributeCards();
        }

或当"(or when the “)新游戏(New Game)单击按钮!(” button is clicked!)

用户选择卡片时(When a Card Is Chosen by the User)

用户选择卡后,将发生以下情况:(After a card is chosen by the user, the following things happen:)

• 用户选择的卡已添加到(The card chosen by the user is added to the) userChosenCards 会话变量,这是一个(session variable, which is an) ArrayList 持有用户在游戏中选择的所有卡牌.(that holds all the cards that have been chosen by the user along the game.)
• 用户选择的卡将从(The card chosen by the user is deleted from the) cardsInGame_User 会话变量.(session variable.)
• 机器人选择的卡也会发生同样的情况.(The same happens for the card chosen by the bot.)
• 之后,玩家交换剩余的卡,这些卡保留在(After that, the players exchange the remaining cards, which are held in the) cardsInGame_User 用户的会话变量(session variable for the user and in the) cardsInGame_Bot 机器人的会话变量.(session variable for the bot.)
• 如果是最后一轮,将计算分数并将其打印出来.(If it’s the last round, the score is calculated and printed out.)

计分比赛(Scoring the Game)

评分功能对于Minimax算法至关重要.这就是为什么它应该拥有自己的一章.(The function for scoring is crucial for the Minimax algorithm. That’s why it deserves a chapter of its own.)

在深入研究代码细节之前,我不得不提到,我们拿牌来计算得分的顺序非常重要.让我们看下面的例子:(Before diving into the details of the code, I have to mention that the order in which we take the cards to calculate the score is very important. Let’s look at the following example:)

在这里,根据(Here, according to the) 观看播放(Watch It Played) YouTube视频频道,我们首先应该检查播放器是否仅用一张卡就可以解决每套诉讼中的大部分问题.在这种情况下,他获得8分.然后,我们应使用"将您最多套西装数量加倍"的卡片.在这里,玩家有3种花色,每种花色1张.因此,我们必须将所有这些都加倍.最后,他将拥有:2个宫殿,2个图书馆和2个寺庙.在那之后,我们可以考虑其他卡片,他将从中得到6点图书馆积分和6点宫殿积分.(YouTube video channel, we should first check if the player has the majority of each suit in question with only one card. If this is the case, he receives 8 points. Then, we should apply the card “Double the amount of your most numerous suit(s)”. Here, the player has 3 kinds of suits and one card of each. So, we have to double all of them. In the end, he will have: 2 Palaces, 2 Libraries, and 2 Temples. After that, we can take into consideration the other cards from which he will gain 6 points for the Libraries and 6 points for the Palaces.)

分数将通过以下步骤计算:(The score will be calculated by following these steps:)

• 计算球员有多少种不同类型的衣服.(Count how many suits of all types the players have.)
• 检查播放器是否具有"赢得所有平局卡".(Check if the player has the “Win all ties card”.)
• 如果玩家拥有,则套用"对于多数只穿一张牌可获得8分的西装".(Apply the “For majority in suits with only one card gain 8 points” if the player has it.)
• 检查牌手是否持有"将最多套西服的数量加倍"的牌,如果有,则套用它.(Check if the player has the card “Double the amount of your most numerous suit(s)” and apply it if he does.)
• 用以下策略计算卡片给出的积分:(Calculate the points given by the cards with the following strategies:) EachComb , 一种(, A) ll ,(,) Majority, DontHave ,同时请记住如果玩家拥有"赢得一切平局"卡.(, while bearing in mind the “Win all ties” card if the player has it.)
• 如果玩家拥有该卡,则套用"单张卡可获得最高得分8分"的卡.(Apply the card “For scoring the highest with a single card gain 8 points” if the player has it.) 主要的(The main) Score 函数将如下所示:(function will look like this:)

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);

            //Stept 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);

        }

如您所见,我们必须多次检查玩家是否有某些卡牌.因为在我们的代码中有多余的地方不好,所以最好有一个函数.此功能应接收玩家的牌和我们正在寻找的策略作为参数.它只是遍历所有卡片并返回(As you can see, we have to check quite a few times if the player has certain cards. As it is not good to have redundancies in our code, it is better to have a function for that. This function should receive the player’s cards and the strategy we are searching for as arguments. It simply goes through all the cards and returns) true 如果找到匹配项或(if it finds a match or) false 如果不:(if not:)

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;
        }

在进入每个步骤的细节之前,值得一提的是,每次计算每张卡的得分时,我都会更新一张卡的最高得分.这将被存储在(Before jumping into each step’s details, it is worth mentioning that I will update the highest score gained with a single card every time I calculate the score gained for each card. This will be memorized in the) maxPointsBot 机器人的变量和(variable for the bot and in the) maxPointsUser 用户的变量.它们的值将设置为(variable for the user. Their values will be set to) 0 在开始时,它们将继续引用所有相关功能.通常,它们可以在名称下找到(at the beginning and they will be passed on with references to all the functions in question. Usually, they can be found under the name) maxPoints 这些功能中.(inside these functions.)

为了更好地理解,我将使用以下示例:(For a better understanding, I will use the following example:)

第1步(Step 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]++;
           }

       }

如您所见,该函数(As you can see, the function) CountSymbols 遍历玩家拥有的所有牌并更新名为c的数组(goes through all the cards a player has and updates an array called c) ardsSymbols .该数组为游戏中的每种花色设置了一个条目:0对应于没有花色的牌,1表示宫殿,2表示图书馆,3表示花园,4表示圣殿,5表示要塞.其目的是跟踪玩家每种类型的西装的数量.在上面的示例中,玩家A拥有1张不带西装的牌,1个宫殿,1个花园,1个图书馆,1个神殿且没有要塞.所以用户的(. This array has an entry for each kind of suit in the game: 0 corresponds to the cards with no suit, 1 for Palace, 2 for Library, 3 for Garden, 4 for Temple, 5 for Stronghold. Its purpose is to keep track of how many suits of each type the player has. In the example above, player A has 1 card with no suit on it, 1 Palace, 1 Garden, 1 Library, 1 Temple and no Strongholds. So the user’s) cardsSymbol 数组将具有以下值:[1,1,1,1,1,0].当机器人的(array will have the following values: [1,1,1,1,1,0]. While the bot’s) cardsSymbol 数组看起来像这样:[0,1,0,1,1,2],因为他有0张不带西装的牌,1个宫殿,0个图书馆,1个花园,1个神庙和2个要塞.(array will look like this: [0,1,0,1,1,2] as he has 0 cards with no suit, 1 Palace, 0 Libraries, 1 Garden, 1 Temple and 2 Strongholds.)

第2步(Step 2)

bool botHasWinAllTiesCard = HasCard(botChosenCards, (int)strategies.Ties);
bool userHasWinAllTiesCard = HasCard(userChosenCards, (int)strategies.Ties);

我们只是使用以下命令检查用户或漫游器是否具有"赢得所有关系卡"(We just check if the user or the bot have the “Win all ties card” using the) HasCard 功能.结果保存在(function. The result is kept in the) botHasWinAllTiesCard 机器人的变量和(variable for the bot and in the) userHasWinAllTiesCard 用户的变量.(variable for the user.)

在示例中,玩家A拥有这张卡.所以(In the example, player A has this card. So) userHasWinAllTiesCard 保持值为真,而(holds the value true, while) botHasWinAllTiesCard 是(is) false .(.)

第三步(Step 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;
       }

该功能通过调用以下命令来检查玩家是否具有"对于多数只穿一张牌可获得8分的西装"(The function checks if the player has the “For majority in suits with only one card gain 8 points” by calling the) HasCard 功能.如果找到这样的卡,它将遍历(function. If it finds such a card, it goes through all the entries from the) cardsSymbols 数组和(array and the) opponentCardsSymbols 数组,在步骤1中进行填充.然后计算每个玩家仅持有一张卡的西装数量.如果有一项(除1(array, which were populated in Step 1. Then it counts how many suits with only one card each player holds. If an entry (except the 1)圣(st)一个)提到的数组的值为1,那么我们只有一张牌就适合.如果玩家拥有"对于只有一张牌的多数服可以获得8分"的牌,且此类服比对手多,则其得分加8分.如果他拥有该卡并且与他的对手拥有相同数量的西服以及"赢得所有领带"卡,他也可以获得8分.(one) of the arrays mentioned has the value 1, then we have a suit with only one card. If the player has the “For majority in suits with only one card gain 8 points” card and more such suits than the opponent, 8 points are added to his score. He can also gain 8 points if he has the card and the same number of such suits as his opponent along with the “Win all ties” card.)

在此示例中,没有玩家拥有这张卡.因此,没有添加点.(In this example, none of the players has this card. So, no points are added.)

第4步(Step 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;
           }
       }

此功能检查播放器是否具有"将您最多套衣服的数量加倍"卡.如果玩家拥有:(This function checks if the player has the “Double the amount of your most numerous suit(s)” card. If the player has it:)

• 它会检查所有同类型西装的最大数量(It checks what is the maximum number of suits of the same type, by going through all the) cardsSymbols 条目,除了1(entries, except the 1)圣(st)一,然后选择其最大值.此值保存在(one, and choosing its maximum value. This value is kept in the) max 变量.(variable.)
• 它将来自(It doubles the values from the) cardsSymbols 等于的数组(array which are equal to) max .(.) 在最后一个示例中,没有玩家拥有这张卡.因此,不添加任何点.(In the last example, no player has this card. Thus, no points are added.)

第5步(Step 5)

现在,我们必须遍历所有用户的卡片,看看他是否具有以下策略之一:(Now we have to go through all the user’s cards and see if he has one of the following strategies:) (int)strategies.EachComb ,(,) (int)strategies.All ,(,) (int)strategies.Majority ,(,) (int)strategies.DontHave .(.)

• 如果我们遇到(If we encounter an) (int)strategies.EachComb 卡:(card:)我们会验证玩家在卡片上写过西服或西服组合的次数.答案是由(We verify how many times the player has the suit or the combination of suits written on the card. The answer is given by) min{ cardsSymbols[x] | x in card.strategyLocations} .分数是通过将该数字乘以卡片为西装或目标中所写西装的分数得出的分数得出的.(. The score is calculated by multiplying this number with the number of points the card gives for the suit or the combination of suits written in the objective.)

让我们研究以下示例:(Let’s examine the following example:)

玩家拥有一张卡,每张卡可为他带来5分,其中包括一个图书馆和一个花园.所以(The player has the card that brings him 5 points for each set which consists of a Library and a Garden. So) x 将采用以下值:(will take the values:) (int)locations.Library 和(and) (int)locations.Garden .玩家在他的王国中有2个图书馆和1个花园.所以(. The player has 2 libraries and 1 garden in his kingdom. So) cardsSymbols[(int)locations.Library] 是2,而(is 2, while) cardsSymbols[(int)locations.Garden] 是1.它们之间的最小值是1.尽管他有2个图书馆,但由于他只有1个花园,因此他只能进行1个组合.从而,(is 1. The minimum value between them is 1. Although he has 2 libraries, he can only make 1 combination because he only has 1 Garden. Thus,) noSets (他可以从这张卡中获得积分的组合数量)为1.总之,这张卡将为他获得1 * 5积分.((the number of combinations for which he will get points from this card) is 1. In conclusion, this card will get him 15 points.*)

从每种类型的每套西装得3分的卡中获得的分数数量甚至更容易计算,但是这种方法更为通用,适用于所有具有"(The amount of points scored from the cards that give 3 points for each suit of a certain type is even easier to calculate, but this method is more general and works for all the cards that have the strategy “) EachComb “,包括它们.(”, including them.)

现在,让我们回到玩家A和B.您能计算出他们从拥有(Now, let’s get back to player A and B. Can you calculate how many points they will gain from the cards that have the) EachComb 战略？(strategy?)

答案:玩家A获得5分,玩家B获得6分.(The answer: player A gains 5 points and player B gains 6 points.)

• 如果我们遇到(If we encounter an) (int)strategies.All 卡:(card:)这种情况与第一种情况几乎相同.除了游戏结束时,每个玩家都有5张卡.因此,如果达到了这张卡的目的,则由于游戏中有五种花色,每张卡上都有不同的符号.所以(This case is pretty much the same as the first one. Except that at the end of the game, every player has 5 cards. Thus, if the objective of this card is fulfilled, each card has a different symbol on it as there are 5 types of suits in the game. So the) cardsSymbols 数组将如下所示:[0,1,1,1,1,1,1].(array will look like this: [0,1,1,1,1,1].)

• 如果我们遇到(If we encounter an) (int)strategies.Majority 卡:(card:)我们检查玩家在问题类型上是否比对手更多.这是通过使用(We check if the player has more suits of the type in questions than the opponent has. This is done by using the values from the) cardsSymbols 和(and the) opponentCardsSymbols 与卡片上指定的西服类型相对应的数组.如果玩家拥有与对手相同的花色,只要他也具有"赢得所有平局卡”,该玩家也可以获得7分.(arrays that correspond to the type of suits specified on the card. The player can also gain 7 points if he has the same number of suits as his opponent as long as he also has the “Win all ties card”.)

在示例中:(In the example:)

- 玩家A拥有"在宫殿中占多数可获得7点"的牌.玩家A有1个宫殿,玩家B也有1个宫殿.尽管这是平局,但玩家A仍然获得7分,因为他还拥有"赢得所有平局"卡.(*Player A has the "For majority in Palaces gain 7 points" card. Player A has 1 Palace and player B has 1 Palace too. Although it's a tie, player A still gets his 7 points because he also has the "Win all ties" card.*)玩家A还拥有"让寺庙中的大多数人获得7分"卡,他发现自己处在与上述相同的情况下,获得了7分(*Player A also has the "For majority in Temples gain 7 points" card and he finds himself in the same situation as above, gaining 7 points*)

总之,玩家A从属于这种情况的牌中获得14分.(In conclusion, player A will gain 14 points from the cards that belong to this case.)

- 玩家B拥有"对于大多数图书馆来说,可以获得7分"卡,但是不幸的是,他没有图书馆.(*Player B has the "For majority in Libraries gain 7 points" card, but unfortunately he has no Libraries.*)玩家B还拥有"在花园中占多数可获7分"卡.玩家B有1个花园,而玩家A也有1个花园.不幸的是,他没有"赢得所有领带"卡,并且从该卡中也获得了0分.(*Player B also has the "For majority in Gardens gain 7 points" card. Player B has 1 garden, while player A also has 1. Unfortunately, he doesn't have the "Win all ties" card and he gains 0 points from this card also.*)

总之,玩家B从属于这种情况的牌中获得0分.(In conclusion, player B will gain 0 points from the cards that belong to this case.)

• 如果我们遇到(If we encounter an) (int)strategies.DontHave 卡:(card:)为此,我们检查除第一个值外的所有值(For this, we check all the values, except the first one, stored by the) cardsSymbols 数组,并且每次找到0时,我们会将玩家的得分加3分.这是因为他没有与该条目相对应的任何类型的西装.(array and each time we find a 0, we add 3 points to the player’s score. This is because he doesn’t have any suit of the type that corresponds to the entry.)

在示例中,玩家B拥有这张卡.他的(In the example, player B has this card. His) cardsSymbol 数组看起来像这样:[0,1,0,1,1,2].作为1(array looks like this: [0,1,0,1,1,2]. As the 1)圣(st)值对应于没有套色的牌,则不会考虑.因此,玩家B除一种以外具有所有西服类型.确实,他没有任何花园!(value corresponds to the cards that do not have a suit on them, it will not be taken into consideration. Thus, player B has all suit types but one. Indeed, he doesn’t have any gardens!)

第6步(Step 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;
        }

正如我所提到的以及在代码中所见,我更新了(As I’ve mentioned and as seen in the code, I updated the) maxPointsBot 和(and) maxPointsUser 计算每张卡给出的分数后的变量.现在,剩下要做的就是检查玩家是否具有"对于单张卡可获得最高分获得8分"的功能,并比较他的(variables after calculating the score given by each card. Now, all that it remains is to check whether or not the player has the “For scoring the highest with a single card gain 8 points” or not and to compare his) maxPoints' 单张牌获得的对手最大积分的价值.不要忘记考虑"赢得一切关系"卡.(value to the opponent’s maximum points gained with a single card. Don’t forget to take the “Win all ties” card into consideration.)

在这个例子中(In the example,) maxPointsUser 从以下一张牌中获得的值为7:“对于宫殿中的大多数,获得7分”,“对于寺庙中的大多数,获得7分"和(has the value 7 from one of the following cards: “For majority in Palaces gain 7 points”, “For majority in Temples gain 7 points” and) maxPointsBot 从"对于每个要塞获得3点"获得值6.用户拥有一张卡"单张卡可获得最高8分”.他实现了目标,因此用户获得了8分.(has the value 6 from the “For each Stronghold gain 3 points”. The user has the card “For scoring the highest with a single card gain 8 points”. He fulfills the objective, thus the user gains 8 points.)

最后,在此示例中,用户获得27分,而机器人仅获得9分.但是请等到我们为我们的机器人加油!(In the end, in this example, the user has 27 points, while the bot has just 9. But wait until we put some brains in our bot!)

Minimax算法(The Minimax Algorithm)

在两个玩家都选择了他们的第一张卡之后,他们交换了各自剩余的卡.此时,玩家知道所有正在使用的牌.他们确切地知道对手的可能性.这使我们能够创建一个游戏树,其中考虑到玩家各自选择所决定的所有可能的纸牌组合.因此,我们可以说游戏是确定性游戏,除了1(After both players have chosen their first card, they exchange their respective remaining cards. At this point, the players know all the cards that are in play. They know exactly what their opponent’s possibilities are. This enables us to create a game tree that takes into consideration all the possible combinations of cards determined by the players' respective choices. Thus, we can state that the game is a deterministic one, except for the 1)圣(st)回合.该游戏的图形表示很难创建,因此,为了便于说明,让我们更改游戏规则!(round. A graphical representation for this game is rather difficult to create, so just for the sake of an easier explanation, let’s change the rules of the game!)

假设两个玩家每人仅以三张牌开始,并且他们已经知道对手的牌是什么.这样,我们可以更深入地研究Minimax理论的实际应用.总结一下:(Let’s assume that both players only start with three cards each and that they already know what their opponent cards are. This way, we can dive deeper into the practical applications of the Minimax theory. To summarize:)

• 机器人将开始游戏.因此,蓝色节点对应于机器人的选择,红色节点对应于玩家的动作.(The Bot will start the game. Thus, the blue nodes correspond to the bot’s turn to choose and the red nodes, to the player’s actions.)
• 每个玩家有三张牌.在此示例中,他们将在每次选择后交换他们的卡.(Each player has three cards. They will exchange their cards after each choice in this example.)
• 用户(红色)手中有以下卡牌[A1,A2,A3].(The user (red) has the following cards in hand [A1, A2, A3].)
• 机器人(蓝色)手中有以下卡片[B1,B2,B3].(The bot (blue) has the following cards in hand [B1, B2, B3].) 牢记这一点,我们可以构建以下游戏树:(Bearing this in mind, we can construct the following game tree:)

我们从左侧的第一个蓝色节点开始.机器人可以从他的直系子孙中选择任何一张卡:B1,B2,B3.假设该机器人选择了B3卡.因此,我们前进到B3红色节点及其自身的路径.轮到用户了.现在,他可以在[A1,A2,A3]卡之间进行选择.假设他选择了A2卡.到目前为止,我们的组合是B3A2.(We start at the first blue node on the left. The bot can pick any card from his direct children: B1, B2, B3. Let’s say the bot picks the B3 card. Thus, we advance to the B3 red node and its own path. It is the user’s turn. Now he can choose between the [A1, A2, A3] cards. Let’s say he picks the A2 card. Our combination so far is B3A2.)

在两个玩家选择了一张牌之后,即每两层树之后,回合便发生变化.更确切地说,每个级别之后都带有红色节点.请记住,每轮比赛结束后,玩家之间的纸牌会互换!(The round changes after both the players chose a card, that means after every 2 levels of the tree. More precisely, after each level with red nodes. Remember that after each round the cards are changed between the players!)

然后,该机器人又来了.结果选项如下:它将选择A1或A3卡.因此,从现在开始,我们有4种可能的情况:(Then is the bot’s turn again. The resulting options are the following: it will either pick the A1 or the A3 card. Thus from this point on, we have 4 possible scenarios:)

B3A2 A1B1 

B3A2 A1B2

B3A2 A3B1

B3A2 A3B2

因此,机器人选择了一张卡后,用户也会选择一张.因此,我将执行2个功能.每个玩家1个.我将它们称为Bot的Max和User的Min.他们会这样互相呼唤:(So after the bot chooses a card, the user will also choose one. So I will make 2 functions. 1 for each player. I will call them Max for the Bot and Min for the User. They will call one another like this:)

看起来像是一个无限循环,但是我们将很快弄清楚如何停止递归.(It looks like an infinite loop, but we will figure out how to stop the recursion in a bit.)

首先,让我们看看这些函数需要哪些变量作为参数.我们只需要我们要选择的卡:(First of all, let’s see what variables these functions need as arguments. We just need the cards we are going to choose from:) botCardsToChooseFrom ,(,) userCardsToChooseFrom 以及我们已经选择的卡片,以便我们可以针对每种配置计算机器人的最终分数:(and the cards we have already chosen so we can calculate the bot’s final score for each configuration:) botChosenCards .此外,我们需要为决定为机器人选择的卡设置一个out变量:(. Also, we need an out variable for the card we decide to choose for the bot:) cardNo .(.)

现在,对于每个蓝色节点,我们将遍历所有(Now, for every blue node, we will go through all the cards from) botCardsToChooseFrom 对于每张单独的卡,我们将复制该阵列的副本,从中取出卡,并将另一副本复制到(and for each separate card, we will make a copy of this array from which we take the card and another copy to the) botChosenCards 我们向其中添加卡.然后,我们称(to which we add the card. Then, we call the) Min 这些副本的功能.我们创建副本是因为我们需要下一张卡片需要使用的原件(function with these copies. We create copies because we need the originals for the next cards we will choose from) botCardsToChooseFrom 而且,如您所知,(and, as you know,) ArrayList s通过引用传递.(s are passed by reference.)

现在,(Right now, the) Max 函数将如下所示:(function will look like this:)

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);

        }

现在,该看看如何停止无限循环了.您已经猜到了,我们可以在(Now, it’s time to see how to stop the infinite loop. As you have already guessed, we can stop when) botCardsToChoose 只剩下一张卡,因为除了选择一张特定的卡外别无选择.在这一点上,我们不称呼(has just one card left because it has no other option than choosing a specific card. At this point, we do not call the) Min 之所以能够正常运行,是因为我们真的不在乎用户的最终卡.在图形表示中,这些最终的卡片用黑色上色.当我们到达它们时,由于已经选择了所有卡,因此我们可以计算机器人的最终分数.在从根到叶的路径上可以找到的卡片构成了卡片的唯一最终状态组合.当我们将其转换为代码时,我们有:(function anymore because we really don’t care about the user’s final card. In the graphical representation, these final cards are colored in black. When we reach them, we can calculate the bot’s final score as all the cards are already chosen. The cards that can be found along the path from the root to a leaf form a unique final state combination of cards. When we transform this into code, we have this:)

if (botCardsToChooseFrom.Count == 1)
            {
                int userScore, botScore;
                botChosenCards.Add(botCardsToChooseFrom[0]);
                GameMechanics.Score(out botScore, out userScore, botChosenCards, userChosenCards);
                return botScore;
            }

之后,我们可以更改(After this, we can change the) void 为了(for the) Max 发挥作用(function to) int 因为它返回了一些东西.(as it returns something.)

到目前为止,我们的机器人知道如何计算它具有的所有可能性以及每个结果分数.不幸的是,它没有关于如何选择正确方案的线索.当然,它想选择一个得分最高的!但是这里是用户的输入.机器人的最佳卡片路径可能会因用户的选择而挫败.这就是为什么我们应该考虑最坏的情况.我们应该假设用户将始终选择将机器人得分最小的卡,而机器人将尝试使其得分最大化.这就是为什么叫用户(Until now, our bot knows to calculate all the possibilities it has and each of the resulting scores. Unfortunately, it doesn’t have a clue about how to choose the right scenario. Of course, it would like to choose the one that will lead to the best score! But here comes the user’s input. The perfect card path for the bot might be foiled by the user’s choices. That’s why we should think of the worst case scenario. We should assume that the user will always choose the card that will minimize the bot’s score, while the bot will try to maximize its score. This is why the user is called) Min ,而机器人被称为(, while the bot is called) Max .(.)

这是与上述游戏树相对应的Minimax树.使用从树的叶子到根的返回值填充该树.(This is the Minimax tree that corresponds to the game tree presented above. This tree is populated from the leaves to the root using the returned values by the) Min 和(and) Max 功能.(functions.)

一片叶子简单地返回沿着其到根的路径的那组纸牌的分数.(A leaf simply returns the score for the set of cards which are along its path to the root.) cardNo 接收与叶子相对应的卡.(receives the card that corresponds to the leaf.)

我们将从树叶到根,而不是相反地分析这棵树,因为我们知道每条单独路径的确切分数.(We will be analyzing this tree from leaf to root and not the other way around because we know the exact scores of each separate path.)

在第三轮中,每个玩家可以选择2张卡.红色(最小)查看孩子的分数,并选择为蓝色(最大)带来最小分数的卡片.如果red的孩子的值分别为19和22,他将选择第一个孩子返回的卡.换句话说,他将竭尽全力阻止Blue的最佳道路.然后,Blue还会查看他的孩子的价值观,并在他试图最大化自己的得分时,选择与他可以获得的最大得分相对应的卡片.例如,如果他的孩子的值分别为19和15,则他选择由他的1提供的卡(In the third round, each player can choose between 2 cards. Red (Min) looks at his children’s score and chooses the card that bring the smallest score possible for the Blue (Max). If red’s children have the values 19 and 22, he will choose the card returned by the first child. In other words, he will do his best to hinder Blue’s best path. Then, Blue also looks at his children’s values and, as he tries to maximize his score, he chooses the card that corresponds to the maximum score he can gain. For example, if his children have the values 19 and 15, he chooses the card provided by his 1)圣(st)这个孩子可以给他带来19分而不是15分.依此类推.(child, that can bring him 19 points instead of 15. So on and so forth.)

让我们检查一下根:根具有以下子代:Child1:{值:15,卡:B3},Child2:{值:15,卡:B2}.子3:{值:12,卡:B1}.它的孩子的最大价值为15.在这种情况下,机器人将选择Child1或Child2提供的卡.这意味着,如果他在回合1中选择卡B3或B2,他将获得至少15点的积分,前提是他将继续在下一回合中应用此算法.(Let’s examine the root: The root has the following children: Child1: {value: 15, card: B3}, Child2: {value: 15, card: B2}. Child3: {value: 12, card: B1}. The maximum value of its children is 15. In this situation, the bot will choose the card provided by Child1 or Child2. This means that if it chooses card B3 or B2 in Round1 he will gain at least 15 points, based on the assumption that he will continue to apply this algorithm for the next rounds.)

这是上述功能的最终代码:(Here is the final code for the functions mentioned above:)

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函数.这是因为实际上,除了最能使机器人得分最小化的选择之外,用户还可以做出其他选择.该算法假设最坏的情况将会发生,如果不这样做,机器人可以简单地获得更多积分!(It’s worth mentioning that the Minimax functions are called during each round of the game. This is because in reality, the user can make other choices than the ones that are best for minimizing the bot’s score. The algorithm assumes that worst case scenario is going to happen and if it doesn’t the bot can simply gain even more points!)

另外,请记住,这是运气的游戏.在给定条件下,算法会尽力为机器人获取尽可能多的分数.但是通过技巧和运气的结合,用户仍然可以获得比机器人可以获得的最高分数更高的分数.如果我们的机器人很完美,那么没人会玩这个游戏!(Also, bear in mind that this is a game of luck. The algorithm does its best to gain as many points as possible for the bot in the given conditions. But the user can still score better than the maximum points the bot can gain, through a combination of skill and luck. If our bot would be perfect, no one would want to play the game!)

带有Alpha Beta修剪的Minimax(Minimax With Alpha Beta Pruning)

1(The 1)圣(st)回合本质上不是确定性的,因为我们无法知道比赛中的所有牌.机器人只知道他的5张牌.对手可以从其他13张牌中任意组合5张牌:c(round is not deterministic in nature as we cannot know all the cards that are in the play. The bot just knows his 5 cards. The opponent can have any 5 card combination from the other 13 cards: c) ardsLeft .因此,有1287种可能的组合!机器人无法知道他可以选择的绝对最佳卡,但是我们仍然可以为其实施一种策略. AI的美丽来了!由于没有完美的解决方案,我们可以发挥创造力!这是一种可能的策略:(. Thus, there 1287 possible combinations! The bot cannot know the absolute best card he can choose, but we can still implement a kind of strategy for it. Here comes the beauty of AI! As there isn’t any perfect solution for this problem, we can use our creativity! This is a possible strategy:)

我们可以使用众所周知的回溯算法生成所有这些组合:(We can generate all these combinations with the well known backtracking algorithm:)

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算法.考虑到一张卡可能是组合的最佳选择,但不一定适合其他组合,因此这将为我们提供许多不同的解决方案.一种选择是选择代表大多数可能组合的最佳选择的卡.每张卡被选择的次数保留在(We can apply the Minimax algorithm for each combination we find. Given the fact that a card may be the best for a combination but not necessarily good for the others, this will give us a lot of different solutions. An option is to choose the card that represents the best choice for most of the possible combinations. The number of times each card was chosen is kept in the) timesChosen 数组.该数组的最大值将指出机器人将在第一轮中选择的卡.(array. The maximum value of this array will point out the card that the bot will choose for the 1st round.)

不幸的是,这花费了相当长的时间,并且用户会感到无聊.我们必须找到减少它的方法!幸运的是,有一个更好的Minimax算法版本,称为Minimax,带有alpha beta修剪功能.它使用的想法是相同的,但是并没有遍历整个游戏树.由于我们的新朋友,这是可能的(Unfortunately, this takes quite some time and the user will get bored. We have to find a way to reduce it! Luckily, there is a better version of the Minimax algorithm called Minimax with alpha beta pruning. The idea it uses is the same but it doesn’t traverse all the entire game tree. This is possible due to our new friends) alpha 和(and) beta !(!)

让我们以下面的游戏树为例:(Let’s take the following game tree as an example:)

当我们应用Minimax算法时,将按以下顺序访问节点:(When we apply the Minimax algorithm, the nodes are visited in this order:)

B,E,K,L,F,M,N,C,G,O,P,H,Q,R,D,I,S,T,J,U,V(B, E, K, L, F, M, N, C, G, O, P, H, Q, R, D, I, S, T, J, U, V)

这对于理解带有Alpha Beta修剪算法的Minimax非常重要!(This is very important for understanding the Minimax with Alpha Beta Pruning Algorithm!)

另外,假定它具有以下Minimax树:(Also, assume that it has the following Minimax tree:)

现在该开会了(Now it’s time to meet) alpha 和(and) beta .你准备好了吗？(. Are you ready?)

• alpha 是最大化器当前可以在该级别或更高级别上保证的最佳值(is the best value that the maximizer can currently guarantee at that level or above)
• beta 是最小化器当前可以保证在该级别或更高级别的最佳值(is the best value that the minimizer can currently guarantee at that level or above) 这就是我们更新的方式(This is how we update) alpha 对于最大用户:(for the Max user:)

bestScore = -INF

for each child node:

    value = AlphaBetaMin(child,alpha,beta)

    bestScore = max(bestScore,value)

    alpha = max(alpha,bestScore)


return bestScore

对于最小用户,我们有(And for the Min user we have) beta :(:)

bestScore = INF 

for each child node:

         value = AlphaBetaMax(child,alpha,beta)

         bestScore = min(bestScore,value)

         beta = min(beta,bestScore)

return bestScore

这就是(This is how) alpha 和(and) beta 在Minimax期间使用alpha beta修剪算法进行更新:(are updated during the Minimax with alpha beta pruning algorithm:)

到目前为止,我们拥有与以前相同的算法,除了(So far, we have the same algorithm as before except for) alpha 和(and) beta .尚无优化.耐心一点!(. There is no optimization yet. Just be patient!)

经过A,B,E,K,L之后,我们知道Min可以通过选择E在B中获得3.(After going through A, B, E, K, L, we know that Min can gain 3 when he is in B by choosing E.) Beta 在B中的值为3.(has the value 3 in B.)

然后,我们访问F和M,我们了解到通过选择M,MAX在F中可以获得5分.(Then, we visit F and M and we learn that MAX can gain 5 points while in F by choosing M. Right now,) alpha 在F中的值为5.但是(has the value 5 in F. But) beta 在F中的值为3.这意味着(has the value 3 in F. This means that the) Min 玩家已经有一个选择(E)可以给对手带来少于5分,因此,他永远不会选择F.等待!我们没有从N计算值!让我们看看这个值会发生什么:(player already has a choice (E) that can bring less than 5 points to his opponent, thus, he will never choose F instead. Wait! We didn’t calculate the value from N! Let’s see what can happen with this value:)

• 如果N的值大于M的值,则意味着通过选择N而不是M可以使Max拥有更多的点.对于他来说,不幸的是,Red已经有了选择,可以使Blue的点数少于N或M.给他机会在这两个之间进行选择.(If the value of N is greater than the value of M, it means that Max can have more points by choosing N instead of M. Unfortunately for him, Red already has a choice that brings Blue less points than N or M and that will not give him the opportunity to choose between these 2.)
• 如果N的值小于M的值,则表示Max将选择M.但是Red再次具有一个选项,它将迫使Blue获得少于M的点,甚至少于N.(If the value of N is lesser than the value M, it means that Max will choose M. But again Red already has an option that will force Blue to gain less points than M and even less than N.) 总之,无论N的值是多少,Red都会始终选择E而不是F!这意味着我们不必浪费时间来计算N的值!每次都会发生(In conclusion, Red will always choose E instead of F, no matter the value of N! This means that we don’t have to waste time to calculate the value of N! This will happen every time) beta 小于或等于(is less or equal to) alpha .在这种情况下,我们应该停止寻找可以从我们所在节点的子级获得的其他值,因为玩家实际上将永远不会获得进入该节点的机会.(. In this case, we should stop looking for other values that can be gained from the children of the node in which we are, as the player will never actually get the chance to be in that node.)

通过将其添加到我们的代码中,我们可以:(By adding this to our code, we have:)

//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

最后,该算法使用的树将如下所示:(Finally, the tree used by the algorithm will look like this:)

在此图片中,黑色节点表示从未访问过它们,甚至从未创建过它们.(In this picture, the black nodes indicate that they were never visited or even created.)

总之,带有alpha beta修剪功能的Minimax是比Minimax更快的算法!(In conlusion, Minimax with alpha beta pruning is a faster algorithm than the Minimax one!)

结论(Conclusion)

综上所述,现在我们有一个实际的游戏,其中包含所有机制的实现和解释.此外,我们还设计了一个功能强大的机器人,考虑到游戏也具有不确定的部分,从而尽力而为.它的策略基于Minimax和带有Alpha Beta Pruning算法的Minimax.最令人惊奇的是,没有任何其他源代码或文章专注于该游戏的实现或为它创建机器人!(To sum up, now we have an actual game with all its mechanics implemented and explained. Furthermore, we also designed a functional bot that does its best taking into consideration that the game also has a nondeterministic part. Its strategy is based on the Minimax and the Minimax with Alpha Beta Pruning algorithms. And the most amazing part of this is that there aren’t any other source codes or articles focusing on the implementation of this game or on creating a bot for it!)

机器人可以在线测试(The bot can be tested online) 这里(here) 完整的源代码(包括前端)可以从本文顶部下载.(and the full source code, with the front end included, can be downloaded from the top of the article.)

该机器人非常棒,足以说明一切!而且,如果您按照本篇较长的教程进行操作,则意味着您也很棒!希望这表明您可以通过简单的算法,一点点的想象力,工作和耐心来实现很多伟大的事情.(The bot is so awesome that it speaks for himself! And if you followed this rather long tutorial, it means that you are awesome too! Hope that this showed you that a lot of great things can be achieved with simple algorithms, a bit of imagination, work, and patience.)

最终通知(Final Notice)

与"时间的潮汐"棋盘游戏有关的所有内容都仅用于学术目的.创建了一篇科学文章,旨在进入(Any and all content pertaining to the “Tides of Time” boardgame has been utilized for academic purposes only. A scientific article was created for the purpose of entering the) AI TensorFlow挑战(AI TensorFlow Challenge) 竞争.尚未将受版权保护的材料用于商业用途.游戏产生的所有权利均保留给设计师,艺术家和制作人.(competition. No commercial use of the copyrighted material has been pursued. All rights emanating from the game are reserved to its designer, artists, and producers.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。