Homework 3

Playing a made up game called "Nimcala"


Due: Friday, October 13th, 10:00 AM


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.

 

 

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:

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

 

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

https://www.cs.uni.edu/~schafer/submit/which_course.cgi

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.