Contents
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 and developed by Kristian Čurla.
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.
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.
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:
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!
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!
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 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:
private enum locations { NoLocation, Palace, Library, Garden, Temple, Stronghold };
strategyType represents the objective or the ability written at the top right of the card. For this, I used the following enum:
private enum strategies
{ EachComb, All, Majority, Ties, DontHave,
OneCardMajority, DoubleAmount, SingleCard };
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);
}
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;
}
The function uses a bool array named viz which holds the value true for the cards that are already in the ShuffledDeck. 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;
}
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.
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!
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.
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 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".
- 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, All, Majority, DontHave, while bearing in mind the "Win all ties" card if the player has it. - 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;
CountSymbols(botCardsSymbols, botChosenCards);
CountSymbols(userCardsSymbols, userChosenCards);
bool botHasWinAllTiesCard = HasCard(botChosenCards, (int)strategies.Ties);
bool userHasWinAllTiesCard = HasCard(userChosenCards, (int)strategies.Ties);
botScore += OneCardMajority(botChosenCards, botCardsSymbols,
userCardsSymbols, ref maxPointsBot, botHasWinAllTiesCard);
userScore += OneCardMajority(userChosenCards, userCardsSymbols,
botCardsSymbols, ref maxPointsUser, userHasWinAllTiesCard);
DoubleAmountCard(botChosenCards, botCardsSymbols);
DoubleAmountCard(userChosenCards, userCardsSymbols);
botScore += NoPoints(botChosenCards, userChosenCards,
botCardsSymbols, userCardsSymbols,
ref maxPointsBot, botHasWinAllTiesCard);
userScore += NoPoints(userChosenCards, botChosenCards, userCardsSymbols,
botCardsSymbols, ref maxPointsUser, userHasWinAllTiesCard);
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:
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 goes through all the cards a player has and updates an array called cardsSymbols. 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 array will have the following values: [1,1,1,1,1,0]. While the bot's cardsSymbol 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.
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.
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;
}
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 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 1st 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.
Step 4
public static void DoubleAmountCard(ArrayList chosenCards, int[] cardsSymbols)
{
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 entries, except the 1st 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.
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:
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;
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:
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. The player has 2 libraries and 1 garden in his kingdom. So cardsSymbols[(int)locations.Library] is 2, while cardsSymbols[(int)locations.Garden] 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 (the number of combinations for which he will get points from this card) is 1. In conclusion, this card will get him 1*5 points.
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.
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?
The answer: player A gains 5 points and player B gains 6 points.
- If we encounter an
(int)strategies.All card:
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 array will look like this: [0,1,1,1,1,1].
- If we encounter an
(int)strategies.Majority card:
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;
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 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:
- 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.
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
In conclusion, player A will gain 14 points from the cards that belong to this case.
- Player B has the "For majority in Libraries gain 7 points" card, but unfortunately he has no Libraries.
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.
In conclusion, player B will gain 0 points from the cards that belong to this case.
- If we encounter an
(int)strategies.DontHave card:
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;
For this, we check all the values, except the first one, stored by the cardsSymbols 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.
In the example, player B has this card. His cardsSymbol array looks like this: [0,1,0,1,1,2]. As the 1st 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!
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 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 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 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.
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!
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 1st 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!
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.
- The user (red) has the following cards in hand [A1, A2, A3].
- The bot (blue) has the following cards in hand [B1, B2, B3].
Bearing this in mind, we can construct the following game tree:
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!
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
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. 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, ArrayLists 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.
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.
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 1st child, that can bring him 19 points instead of 15. So on and so forth.
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;
}
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!
The 1st 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: cardsLeft. 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]++;
}
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.
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:
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
This is very important for understanding the Minimax with Alpha Beta Pruning Algorithm!
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 abovebeta 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 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!
After going through A, B, E, K, L, we know that Min can gain 3 when he is in B by choosing E. Beta has the value 3 in B.
Then, we visit F and M and we learn that MAX can gain 5 points while in F by choosing M. Right now, alpha has the value 5 in F. But beta has the value 3 in F. This means that the Min 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:
- 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.
- 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.
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.
In conlusion, Minimax with alpha beta pruning is a faster algorithm than the Minimax one!
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.
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 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.
