Assignment 2

Consider the two-player game altNim in which one is initially given a pile of matchsticks and players alternately remove some number of matchsticks from the pile until one of the players wins. The number of matchsticks that can be removed by each player alternates in a repeating block of four moves dictated by Boolean variable startOdd and integer variable actionState as follows:

Player #	actionState	startOdd = True	startOdd = False
1	0	[-1, -3]	[-2, -4]
2	1	[-2, -4]	[-1, -3]
1	2	[-2, -4]	[-1, -3]
2	3	[-1, -3]	[-2, -4]

A player loses if there is exactly one matchstick left in the pile at the beginning of their turn or any matchstick-removal move they can make results in zero or a negative number of matchsticks in the pile. A player wins if the opponent player loses.

Write and document a Python program that uses the MiniMax algorithm to evaluate a specified state in the altNim game tree. You have been given Python files myAltNimClasses.py and testAltNim.py and you need to fill in the function definitions in file myAltNimFunctions.template according to the specified algorithms given in Lecture #9 to create a file myAltNimFunctions.py such that testAltNim.py (when run using python3 on the CS departmental LabNet systems) can exactly reproduce the outputs in script file out.script.

You are not allowed to modify any of the code in provided files testAltNim.py and myAltNimClasses.py. When modifying file myAltNimFunctions.template to create myAltNimFunctions.py, you cannot:

• modify the lone import statement;
• add other import statements (this includes import statements added automatically by IDEs such as PyCharm);
• add, modify, or remove function definitions or modify given comments associated with those functions;
• add new class definitions or global variables (use the provided classes in file mySearchClasses.py); or
• access any provided class attributes directly (use provided attribute access functions in file mySearchClasses.py).

Violations of any of these constraints will result in severe mark deductions (see assignment evaluation scheme below).

Hints

You may find it useful to progress through the given tests in the given order when debugging your code.

A leaf in the altNim game tree is any state with less than or equal to one matchstick remaining.

When function eval() in myAltNimFunctions.py is evaluating a leaf node in the altNim game tree, -1000 is returned if the min player wins (i.e., isMax = True and there is one matchstick remaining) or the max player loses (i.e., isMax = False and there are less less than or equal to zero matchsticks remaining), 1000 is returned if the max player wins (i.e., isMax = True and there are less than or equal to zero matchsticks remaining) or the min player loses (i.e., isMax = False and there is one matchstick remaining), and the number of matchsticks remaining is returned otherwise.

You may find it useful in understanding how the MiniMax function works to look at how this function is used in playing a game of altNim; to this end, a Python program (altNim.py) that allows a human to play altNim against a computer using the classes and functions in this assignment has been provided (see here for a script file of three altNim games).

Assignment Submission

Please submit your program file myAltNimFunctions.py through the course D2L / Brightspace shell by 11:59pm on the assignment due date. Note that each program file must have the following comment block at the top, where the X's are replaced with the appropriate information. For example, my Python file for this assignment would begin with the following comment block:

#########################################################
##  CS 3200 (Fall 2024), Assignment #2                 ##
##   Script File Name: myAltNimFunctions.py            ##
##       Student Name: Todd Wareham                    ##
##         Login Name: harold                          ##
##              MUN #: 8008765                         ##
#########################################################

You do not have to develop your code on our CS departmental LabNet systems. However, as your code will be tested on our CS departmental LabNet systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• August 15, 2024
  Assignment #2 posted.

Created: August 15, 2024
Last Modified: October 3, 2024