## Homework 3

### Introduction

Mancala (Read about it on wikipedia or try to play it on cool math games) is normally played on a "two sided" board where each player has six pits on their side of the board with a seventh "well" or "Mancala" on the right end of the board:

During the study of the minimax algorithm I several times referenced variations of a game called Nim.

This assignment is a made up game that combines Nim with the game of Mancala.

### How to Play

Consider a game consisting of M pits and N tokens.  At the start of the game all N tokens are located in the leftmost/"first" marked space.

For example, a game consisting of 4 marked "pits" and 5 tokens would start like this:

When it is your turn you may pick up any number of tokens (from 1 to all of them) from any SINGLE one of the M marked pits and distribute those tokens one each to the pits to the right.  Thus, on the opening move of the game, player 1 can pick up anywhere from 1 to 5 of the tokens in area 1.

Suppose that player 1 picks up 3 tokens.  This would mean that the player places 1 each in pit 2, 3, and 4. After the player is done the board would look like this:

From this new board, player two has five different moves possible:

 One token from pit one Two tokens from pit one One token from pit two One token from pit three One token from pit four

If there are tokens left over when you reach the last pit these tokens are removed from play. Thus, if player one had picked up all five tokens from pit one at the start of the game, player two would have been faced with the following board.

Play continues until all the tokens have been removed from the board. The winner is the player who removed the last token from the game.

This means that the SHORTEST game possible for the game shown above is four moves and the game would be won by player 2.

• Player one picks up all five tokens from pit one.
• Player two picks up the only token from pit two.
• Player one picks up both tokens from pit three.
• Player two picks up both tokens from pit four.

The LONGEST game playable would take M*N moves or, in the example we have been working with, 20 moves. I leave it to you to figure out how that game would work (or prove me wrong).

### Base Requirements (25 of 30 points)

For this homework you should write a program that fits the following base requirements:

• Your code should ask the user for a comma separated set of integers to indicate the current state of the board.
• The very top board would be:   5,0,0,0
• The second board would be:    2,1,1,1
• IN THEORY, your program should work with any number of stones in any number of pits and should not be hardcoded to 5 stones in 4 pits as I have used in my example (see note below)
• You should use minimax to pick the "optimal" move.  In this case, since the game is only a win game or a lose game you may use a Utility Function of 1 if max wins and 0 if min wins.
• Your code should print the results of the minimax algorithm including:
• From what pit you should pick up the tokens [Number the pits 1 through 4]
• How many of the tokens in that pit should be picked up
• Whether that is expected to lead to a win or  lose.
NOTE: The board described above has too much repetition (rechecking things it's already checked) with base minimax and may take several minutes to solve. So instead of 5 stones in 4 pits you can use 4 stones in 4 pits to check this out. But again, your code should be able to handle ANY values I put in and should not be hardcoded.

### Additional Functionality

You may add in EITHER or BOTH of these extensions for additional points. The first one you successfully add will be worth five points. The second one you successfully add will be worth three additional points

Extension A:

Given the choice we would prefer to win as quickly as possible (or delay losing as long as possible).

• The only way to achieve this is to modify the game from a 1 vs. -1 outcome to something where the length of the game is part of the score.
• To achieve this you should use a utility function consisting of:
• (100 - #ofTotalMoves)*1 if player one wins
• (100 - #ofTotalMoves)*-1 if player two wins
• [Note: that 100 was selected to be sufficiently large enough to cover a wide variety of games that you might test]
• This would mean that
• a game won by player two in the minimum # of moves would have a score of (100-4)*(-1) = -96
• a game won by player one after 7 moves would have a score of (100 - 7)*(1) = 93
• a game won by player two after 20 moves would have a score of (100 - 20)*(-1) = -80

Extension B:

Notice that there are at least two different ways to arrive at the following board:

First, Max could pick up all four stones from pit one and distribute them appropriately. This means Min would arrive at the board shown.

But also notice that Max could pick up three stones from pit one and get to:

Then Min and Max could alternate picking up that one stone left in pit one and they could "walk it" down the board and remove it.

In other words it would be Min's turn and she would be faced with:

In both of these situations the MiniMax algorithm would have to continue to search for the expected value for this board even though both situations are Min's choice.

One way that we can speed up the algorithm (at the expense of increased memory utilization) is to store every board we have encountered along with the expected utility function is for that board. But note, this also requires us to store not only the board but whose turn it is, because Min and Max have different goals for this board.

In this extension you should add in a lookup table that records every board encountered along with whose turn it is, and then the expected outcome of that board. As minimax runs it should check this lookup table BEFORE entering a recursive call. If it finds it in the table it can simply use that score rather than repeating the potentially long calculation.

### Suggestions:

1. Begin with a simple board with a known solution. For example, consider 0,0,0,2. You know that if you pick up both stones from pit 4 then you will win the game. If you only pick up one of the stones than your opponent will win on the next move.

Similarly, 1 from space 4 would lead to a win.  But 1 from space 3 would lead to a lose.

1. Follow your finished program all the way from start state to end state.  For example, my program told me that the optimal opening move was:

At this point I should have player 1 make that move and then run my program to see what player 2 should do:

Confirm the results of your program.  If player 1 was expected to win if he/she made that move, then player 2 better be expected to lose no matter what.  But then make THAT move:

Keep tracing to make sure your game plays "correctly."

### Submitting Your Work

Prior to the deadline, use the homework submission system

to upload any files you have produced.

You should bundle all of your files (including your readme.txt) into a zip file.

In addition to online copies, please submit hard copies of this lab at the start of class on the day this lab is due.