CS 32 Project 3

This is the most fun I have had on a CS project to date. The assignment was to create a mancala board, with an option to play against a computer player. (If you don't know what mancala is you can find the rules and play the game here.) Creating the board was easy enough; I just needed to print some text that would be the "board", track each player's score, and update as moves were made. The tricky part was the code for the computer player. The specs for this project required that the computer player would make "good" decisions. Meaning, when my code was tested for grading, the graders set up boards so that there was one choice that was the best choice.

In order to do this, I decided to use the minimax algorithm. This algorithm "plays" all the possible moves, then calls the minimax function again, but allowing the other player to play this time. This function is called recursively until all possibilities have been run, or until the timer runs out. Then, each outcome is assigned a score. Positive means the computer is winning, negative means the human player is winning, and 0 signifies a tie. This sounds a little confusing, but an illustration might make it more clear.

This board has two holes per side. I made the board really small on purpose because drawing a tree for a board with more than two holes per player is extremely tedious. Let's say we want to use the minimax algorithm when the board is in a state like the top node. What the algorithm should do is play until there is a result and assign each move a score.

There are many ways to implement this function, but I chose to do it like this: For every hole that is not empty is chooseMove(), the function creates a temporary Board and makes a move at the hole with the temporary board, and passes this board to miniMax(). miniMax() is called recursively and assumes that the opponent player plays at their best. Then, miniMax() returns how “good” each move is based on the evaluate() function. evaluate() returns 0 if there is a tie, 10000 if the player wins, and -10000 is the player loses. If the game is not over, the board returns a middle value. If the player is winning but hasn’t won (the player has more beans in their pot than the opponent), the board is evaluated at 5000, if it’s the other way around, -5000 is returned.

Here's my pseudocode:

int miniMax() 
 
evaluate the function to how “good” of a state it is in and to see if the game is over 
if the game is over or time is out 
 return the the evaluation of the board 
if looking for the maximum 
 for every hole that is not empty 
  make a move 
  use minimax algorithm to determine how good of a move that was 
  if that move was better for the player than before set best as that move 
otherwise if looking for the minimum 
 for every hole that is not empty 
  make a move 
  use minimax algorithm to determine how good that move was 
  if move was worse for the player (therefore better for the opponent) than before set it as the best move 
 
return best 

To keep track of the holes and beans in Board, I used two dynamically allocated arrays, one for the north player, and one for the south player. There are several helper functions that I created in Player, Game, and Board. I created these helper functions to make the code easier to read and less messy. For example, in sow(), the function is really long and I found that while I was writing the function, I would often look back and forth between the beginning and middle of the if statement that I was writing to see what side I was writing for. As I was checking my code, it was confusing to read NORTH and SOUTH, and I was often unsure of what a section of code was meant to be doing. By using the functions determineOppSide() and switchSide() my code was cleaner and easier to read. Additionally, I found that myself rewriting a lot of code, that was tweaked just a bit every time, so it seemed more efficient and less cluttered to just create a function for the repeating bits of code.

See my full code here.