Essay about Mancala - Artificial Intelligence, past present future PDF

Preview

Summary

Take home assignment ...

Description

Mancala Artificial Intelligence at play

Yves van Engelen Willem Gelderblom Julienne Keim

Mancala Artificial Intelligence at play

Yves van Engelen Willem Gelderblom Julienne Keim

Date: Professor: Course:

40127539 40123878 40125130

23 November 2019 Dr. Chee Wei Tan GE2340 Artificial Intelligence: Past, Presence, Future

Preface In this paper the Mancala game will be extensively explained through examples and descriptions of one of the oldest game known to date. This will be done by means of Artificial Intelligence principles. An attempt is being made to better understand the game by investigating three different strategies that can be implied to the game: MiniMax, Greedy and Alpha Beta Pruning MiniMax. Each strategy will be described and this description will hopefully result in understanding and determining the next possible move for a specific player. We want to thank our professor, Dr. Chee Wei Tan, who guided us through the study material needed to understand some principles and subjects about world of Artificial Intelligence. This made it possible to write this paper and to implement our amassed knowledge about AI into our specific subject of this paper: The Mancala Game.

Yves van Engelen Willem Gelderblom Julienne Keim Hong Kong, 23 November 2019

ii

Contents 1 Introduction

1

2 Rules and game play

2

3 Strategies

4

3.1 General game strategies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Algorithms 4.1 MiniMax Algorithm . . . . . . 4.1.1 Greedy . . . . . . . . . 4.2 Alpha-Beta Pruning MiniMax . 4.3 Example of Mancala gametree

4

5 . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5 Conclusion

8

Bibliography

9

iii

5 6 6 7

1

Introduction

Mancala (or Awari) is one of the oldest games known in our current society. Research shows that it’s probably originated from different parts in Africa[1]. The game exists of a similar, two-sided board which can differ in size. Every side of the board contains a specific amount of pits and a player’s ‘Mancala’. The Mancala is basically the collecting pit where you need to collect as much stones in as possible. The pits contain a predetermined amount of stones which are the same for every pit on the play board. The total of stones in each pit can reach up to a maximum of 1000, which gives the game an endless amount of moves, solutions and player outcomes. Each player makes consecutive moves until one player is not able to make a valid move. A player cannot make a valid move if he or she does not have any stones left on his or her side of the board. This results in the fact that the player is not able to move a stone to another pit on their side of the board, which results in an immediate end of the game. Another way in which the Mancala game can end is when a player has the majority of stones in his or her Mancala before the other player runs out of stones. The Mancala game that is investigated in this paper has a size of two rows of six pits. In the starting configuration each pit contains four stones. In the next chapter there will be an explanation of the possible moves, and an explanation of how a game can end up in the different situations. This research has the goal not only to briefly explain the working of the game, but also to find the possible way to enable Artificial Intelligence into the strategy behind the game [2].

Figure 1.1: Mancala Start Position

1

2

Rules and game play

This part will briefly explain the rules of the game and the way the game can be played by showing examples. In this part the rules of the game and the way the game can be played will be explained by showing examples. The game is be played by two players. They each sit on the opposite side of the symmetric board. The game starts with the first player who chooses a pit. The player picks all the stones from this particular pit and divides them as follows: starting with the first pit on the right of the chosen pit (so counterclockwise), every pit gets added one stone until the player runs out of the stones he or she picked up. In the specific case where the Mancala of the opponent is reached, it will be skipped. This way, you stack the stones that pass your Mancala to try and get as many stones. Let’s explain this with two examples:

Figure 2.1: Example 1

If the player on the bottom side of the board starts by emptying the pit with the blue square, the last stone will end up in the pit with the red square. This move will also add one point to the Mancala of this player, because it passes its own Mancala with the four stones it picked up.

Figure 2.2: Example 2

2

3

Suppose that it is the same players turn (bottom) and he empties the pit with the blue square, but the square does not contain four stones as before, but it contains a total of nine stones. This way, the stones pass his or her own Mancala, which gives them one extra point, but it also passes the opponents Mancala. The opponents Mancala needs to be skipped, and the last stone will eventually end up in the pit with the red square. A player is also able to make more than one move in a turn. This is possible because of the following rule: When the last stone out of the chosen pit ends in your own Mancala, this player is allowed to choose another pit to empty and divide over new pits. We can also easily explain this rule with another example:

Figure 2.3: Example 3

If the player on the bottom side starts by emptying the pit with the blue square, which contains four stones, the last stone ends up in his or her own Mancala (shown by the red rectangle). This means that he or she is allowed to make another move, for example emptying the pit with the green square and dividing the stones that contain this pit (also four in this example). The next rule of the game is as follows: If your last stone ends up in an empty pit on your side of the board, your Mancala receives all the stones from the pit on the opposite side of the one stone pit and the stone that landed in the empty pit. You basically steal stones from the other players side and immediately add them, and the other stone to your Mancala. In practice, it looks like this:

Figure 2.4: Example 4

If the player on the bottom side of the board picks up the stones from the pit with the blue square, the last stone ends up in the empty pit with the red square. This means that the player is allowed to add all the stones from the opposite opponents pit and the stone that landed in the empty pit to his own Mancala. In this situation, this means that the player can add the two stones from the pit with the green square and red square into his Mancala, which results in a total of sixteen points. This rule is called stealing and can be optional as a game rule [2].

3

Strategies

If the player is familiar with the rules and possible plays of the game, several strategies can be applied to maximize the chance of winning from the opponent. In this chapter some general game strategies are described.

3.1. General game strategies This version of Mancala is a ‘solved game’, which means that the first player can always win, if applying the right strategy (also known as a ‘perfect play’). If it’s the first player’s move, the best opening would be to begin with the third hole from the left. As explained in 2. the player will get another move as the last stone ends in the Mancala zone. In general, any move that will give the player another turn is desirable. If the first player played the beginning move as the third hole from the left, the optimal move on the second turn would be either the right-most or the second right-most pit. This move will prevent the opponent to play the same move as the first player’s first move, so the opponent cannot make a move which will give him/her two moves. A more general strategy is to make sure to empty the right-most pit as early as possible. As this pit is direct next to the Mancala zone, it will often lead to a point and an extra turn if there is a single stone in this pit. In this Mancala variant, the capture rule is implied. This will lead to another strategy to try to make your own pits empty, as dropping the last stone in an empty pit will give you the opponents stones from the opposite pit. A side note to this strategy is that in the end, if all the players pits are empty from one player, the other player can keep the remaining stones in his/her pits. If the capture rule is not implied (which is not the case in this paper, but is still worth mentioning), the following strategy can be used to try and win the Mancala game: At the beginning of the game, pick a pit from your side of the board and never take any stones from that pit. This will increase the chance that the other player runs out of stones first, which results in you winning the game. A player should also be aware of empty or almost empty pits at the opponent’s side, as this may result in the opponent capturing the other player’s stones. If a situation like this occurs, the player should try to fill the empty or almost empty pit with their next move. This is also called a ‘defensive move’. A last general strategy is try to look two or three steps ahead, like in chess.

4

4 Algorithms To enable Artificial Intelligence in the Mancala game, there needs to be an algorithm to make sure the computer knows what moves to play in any given situation. Within the Mancala game, there is one algorithm that can be applied, the ’MiniMax algorithm’. Within the MiniMax algorithm there are different types and techniques that can be used. A type of the MiniMax algorithm is the ’Greedy algorithm’. A technique that can be used is the ‘Alpha Beta Pruning MiniMax’. In the next section the main algorithm and its types and techniques will be explained.

4.1. MiniMax Algorithm The MiniMax algorithm is used for teaching AI how to play turn-based strategy games. With this algorithm all possible moves from the player will be taken into account. This will result into an attempt to minimize the advantage of the opponent and maximize its own [? ], as the name of the algorithm implies. To start using the MiniMax algorithm, there needs to be a gametree to explore all possible moves. As our Mancala variant has six pits at each side, the first layer of nodes (under the root node) will consist of six different nodes in the beginning of the game. This is also described as the width of the gametree. Another variable is the depth of the gametree, the number of nodes in one threat including the last node, the leaf node. In this algorithm there will be a fixed number of nodes assigned as the depth, also known as the ’cutoff’ depth. As Mancala is a sequence game, two-player game, both players have a different tactic. Each layer in the gametree is either a move from the first player or the second player. The first player would make a move as the root node of the game three. The second player has a different response move for each first move, resulting in the second layer of the gametree. As stated before a player wants to minimize the advantage of the opponent and maximize it’s own. As the first player makes the first move, the root node will be a ’maximize’ decision. This will assign the ’minimize’ decision to the second player. As in figure 4.1 (just a random example of a gametree) the first player will maximize the outcome of the decision, which will lead to the value of 6 (as 6 is higher than 3 and 5). This outcome was established by what the second player will do in the second layer of nodes. The second layer of nodes will minimize the value, for example the node with value 3 can choose from a child node (a node in the layer under the node) either value 5 or 3, so the second player will choose the option with value 3. This algorithm will go on until the last layer is reached, the leafs layer. The number of layers will be equal to the value set as the ’cut-off’ depth. 5

6

4. Algorithms

Figure 4.1: Gametree [? ]

4.1.1. Greedy Greedy is a simplified variant of the MiniMax algorithm. The depth, as defined in 4.1, is set at 1. This leads to a shortened calculation time, which for a large gametree can save a lot of time.

4.2. Alpha-Beta Pruning MiniMax Alpha-Beta Pruning is another variant of the MiniMax algorithm. In contrast to the greedy algorithm, the alpha-beta pruning algorithm does not lead to a less evaluated result. It will return the same result as MiniMax, but it does do more efficiently. This is because it ’prunes’ certain branches of the gametree that are not necessary to calculate. This is done by adding two variables to the code. Namely, alpha and beta. Alpha is the least best outcome for player 1 and beta the worst outcome for player 2. These get updated throughout the tree. When alpha is smaller than beta, it means there was a better option earlier in the tree and that branch can be pruned. An example of a code implementing alpha beta pruning is shown in figure 4.2. In the first line the function MiniMax is created with the code. The variables used are: position, depth, alpha, beta and maximizingPlayer.

Position Depth Alpha Beta maximizingPlayer

Current position in the tree Layers of the gametree Least best outcome for player one Least best outcome for player two If player 1 (white), which is the maximizing player, is playing, the value for maximizingPlayer will be true. If the player 2 (black), which is the minimizing player, is playing, the value of maximizingPlayer will be false.

The initial call as in figure 4.2 is provides the start values for the function. The depth, and thus the layers of the gametree, is three. The worst possible outcome for the maximizing players is minus infinity and for the minimizing player plus infinity. Player one is the maximizing player and thus the value for maximizingPlayer is true. Since maximizingPlayer is true, the part inside the if condition will be run for this move. In this part alpha is set as the greatest value of either alpha or eval. Eval is the value of the children, which are located at depth - 1. In other words eval is the outcome of the evaluation done before this move by player 2. If beta is then smaller then alpha it means that player 1 had a better option earlier in the game and that branch can be pruned and therefor the break condition is carried out.

4.3. Example of Mancala gametree

7

Figure 4.2: Alpha Beta Pruning [4]

4.3. Example of Mancala gametree In figure 4.4 an example of a Mancala gametree is shown. This is the gametree corresponding to the board shown in figure 4.3. The root (value at the top) is the outcome. The rectangle boxes below show how many stones would be added to the Mancala. For example, if pit 1 (shown third layer of the tree) would be chosen, 5 stones would be added to the Mancala, because the stones from pit 10 would be captured 1 . This is one component of the whole gametree, only for one decision by one of the players. For every turn a new gametree is made, resulting in a lot of gametrees in total. However, the other player has limited options to play, so the number of gametrees in total is limited as well. To implement these algorithms in the Mancala game (to enable Artificial Intelligence) all possible gametrees should be known.

Figure 4.3: State of Mancala board [5]

Figure 4.4: Corresponding gametree to 4.3 [5]

1 There is one mistake in this figure. The second layer of the most right branch should have a value of 1 and not 0.

5

Conclusion

Mancala (or Awari) is one of the oldest games known in our current society. Every side of the board contains a specific amount of pits and a player’s ‘Mancala’. The Mancala is the collecting pit where you need to collect as much stones as possible. The pits contain a predetermined amount of stones which are the same for every pit on the playboard. Each player makes consecutive moves until one player is not able to make a valid move. A player can’t make a valid move if he or she does not have any stones left on his or her side of the board. This results in the fact that the player is not able to move a stone to another pit on their side of the board, which results in an immediate end of the game. The version of Mancala we investigated (two rows of six pits) is a ‘solved game’, which means that the first player can always win, if applying the right strategy (also known as a ‘perfect play’). There are some strategies a player can apply to increase the winning chance. If it is the first player’s move, the best opening would be to begin with the third hole from the left as it will lead to a second turn. A general strategy is to make sure to empty the right-most pit as early as possible, as it will often lead to a point and an extra turn if there is a single stone in this pit. Because the capture rule is implied, trying to make your own pits empty is another strategy, as dropping the last stone in an empty pit will give you the opponents stones from the opposite pit. This strategy needs to be applied carefully as in the end, if all the players pits are empty from one player, the other player can keep the remaining stones in his/her pits. A player should also be aware of empty or almost empty pits at the opponent’s side, as this may result in the opponent capturing the other player’s stones. If a situation like this occurs, the player should try to fill the empty or almost empty pit with their next move. This is also called a ‘defensive move’. A last general strategy is try to look two or three steps ahead, like in chess. Artificial Intelligence can be applied in the Mancala game with the use of various algorithms. The MiniMax algorithm is used for teaching AI how to play turn-based strategy games. With this algorithm all possible moves from the player will be taken into account. This will result into an attempt to minimize the advantage of the opponent and maximize it’s own [3]. The MiniMax algorithm makes use of a so called gametree, to explore all possible moves. Using this gametree, an AI-player can optimize its chances of winning from a human-player. One simple type of the MiniMax algorithm is the Greedy algorithm, where the depth of the gametree is one. The Greedy algorithm shortens the calculation time. However, the Greedy algorithm will lead to a less evaluated result. Another variant that shortens the calculation time but gives the same result as the MiniMax algorithm is the Alpha-Beta Pruning MiniMax, where branches of the gametree that are not necessary to calculate are pruned (cut-off ). In contrast to the Greedy algorithm, the Alpha-Beta Pruning MiniMax gives the same result as the normal MiniMax, only with less calculations needed. To conclude, Mancala is a very interesting game with a lot more theories and strategies behind it than initially thought. To get the best result, when implementing Artificial Intelligence through algorithms one should make use of the MiniMax algorithm with the Alpha-Beta Pruning method instead of the Greedy variant to get the best res...