Description
In this homework, you will write a program to determine the next move for a player in the
Mancala game using Greedy, Minimax, and Alpha-Beta pruning algorithm. The rules of the
Mancala game can be found at https://en.wikipedia.org/wiki/Mancala [1] and you can also try
playing it online at http://play-mancala.com/ [2] to get a better understanding of the game.
Introduction to Mancala:
Mancala is a two-player game from Africa in which players moves stones around a board
(shown above), trying to capture as many as possible. In the board above, player 1 owns the
bottom row of stones and player 2 owns the top row. There are also two special pits on the
board, called Mancalas, in which each player accumulates his or her captured stones (player 1’s
Mancala is on the right and player 2’s Mancala is on the left).
On a player’s turn, he or she chooses one of the pits on his or her side of the board (not the
Mancala) and removes all of the stones from that pit. The player then places one stone in each
pit, moving counterclockwise around the board, starting with the pit immediately next to the
chosen pit, including his or her Mancala but NOT his or her opponents Mancala, until he or she
has run out of stones. If the player’s last stone ends in his or her own Mancala, the player gets
another turn. If the player’s last stone ends in an empty pit on his or her own side, the player
captures all of the stones in the pit directly across the board from where the last stone was
placed (the opponents stones are removed from the pit and placed in the player’s Mancala) as
well as the last stone placed (the one placed in the empty pit). The game ends when one player
cannot move on his or her turn, at which time the other player captures all of the stones
remaining on his or her side of the board.
Tasks:
In this assignment, you will write a program to determine the next move by implementing the
following algorithms:
x Greedy
x Minimax
x Alpha-Beta
Legal moves:
Assume that the current board position is as shown in the image above and the current turn is
Player-1’s. Blocks B2-B7 are Player-1’s pits, blocks A2-A7 are Player-2’s pits, B8 is Player-1’s
Mancala and A1 is Player-2’s Mancala. We define a move for any player as to pick a pit (except
Mancala) from which the stones are removed and placed in other pits as explained above. So
for the current board position, Player-1’s legal moves are pits B2, B3, B4, B5, B6, or B7. The
image below shows the board position if Player-1 picks B5 as his/her move. Any player cannot
choose an empty pit as a move, i.e. empty pits are illegal moves.
Note that a player can make more than one move during his/her turn as per the rules. For
example, Player-1 can pick pit B4 and then pick any other pit (except for B4 as it will be empty)
for his turn for the starting board position shown above. So keep that in mind while making
decisions for any of the tasks. YOU HAVE TO MAKE A LEGAL MOVE IF ONE IS AVAILABLE.
End game:
If a player cannot make any valid move, i.e. all of his pits (except Mancala) are empty, the game
ends and the remaining stones are moved to the other player’s Mancala.
Evaluation function:
The goal of the game is to collect maximum number of stones by the end of the game and to
win the game; you need to collect more stones than your opponent. So, the evaluation function
for any legal move is computed as the difference between the numbers of stones in both
players’ Mancala if that move is chosen.
E(p) = #Stones_player – #Stones_opponent
For example, for the current board position shown above, if Player-1 chooses pit B5 as his/her
move, then the value of the evaluation function would E(B5) = (1-0) = 1. Note: You can hence
assume that your agent is always the “max” player. Similarly, E(B2) = (0-0) = 0.
Tie breaking and Expand order:
Ties between pits are broken by selecting the node that is first in the position order on the
figure above. For example, if all legal moves for Player-1 (B2, B3, B4, B5, B5, B6, and B7) have
the same evaluated values, the program must pick B2 according to tie breaker rule. Same rule
applies for Player-2.
Your traverse order must be in the positional order also. For example, your program will
traverse on B2, B3, B4, B5, B6, and B7 branch in order.
Board size:
The board size will be 2xN along with a mancala for each player, where N represents the
number of pits for a player and 3≤N≤10. The board size for the mancala board shown above
would be 2×6. The initial number of stones in each pit can be maximum 1000.
Pseudo code:
Greedy: It is a special case of Minimax. The cut-off depth is always 1. Thus, the algorithm is very
simple. You only need to pick the action which has the highest evaluation value.
Minimax: AIMA Figure 5.3 (Minimax without cut-off) and section 5.4.2 (Explanation of Cutting
off search)
Alpha-Beta: AIMA Figure 5.3 (Alpha-Beta without cut-off) and section 5.4.2 (Explanation of
Cutting off search)
Input:
You are provided with a file input.txt that describes the current state of the game.