MATH20621 Programming with Python - Coursework 3: Nine Men's Morris
Coursework 3
In this coursework, worth 70% of the marks for the course, you are required to write Python functions, by filling in code into the template below. Submit your Python script on Blackboard before the deadline on Thursday, 14th December 2023 at 1pm. (I suggest aiming to submit at least hour earlier, to avoid any last-minute computer problems).
Feedback
As this is part of the course assessment, we will not be able to help you solving these problems in the lab classes or elsewhere. You will receive a feedback report with a score for each function, and some overall feedback on the code quality.
Please read the problem descriptions carefully! The problems should (hopefully) be formulated in a way that there are no doubts. In case there remains a question on a problem formulation, please post it to the Blackboard Discussion Forum and it will be answered. Errors in this document will be corrected and noted on the 'errata' list on Blackboard.
Nine Men's Morris
Nine Men's Morris is a two-player game played with counters on a board. It was popular in mediæval England, but has been played for over 2000 years. The game board consists of 16 lines, as follows:
┌──────────┬──────────┐ │ │ │ │ ┌──────┼──────┐ │ │ │ │ │ │ │ │ ┌──┴──┐ │ │ │ │ │ │ │ │ ├───┼───┤ ├───┼───┤ │ │ │ │ │ │ │ │ └──┬──┘ │ │ │ │ │ │ │ │ └──────┼──────┘ │ │ │ │ └──────────┴──────────┘
Two players can place their counters (X for player 1, and O for player 2) on each of the 24 corners or intersections of the lines (we'll call these 'points'), leading to boards in play that look like, for example,
X──────────┬──────────┐ │ │ │ │ O──────O──────O │ │ │ │ │ │ │ │ ┌──┴──┐ │ │ │ │ │ │ │ │ X───X───┤ O───┼───X │ │ │ │ │ │ │ │ └──┬──┘ │ │ │ │ │ │ │ │ └──────O──────┘ │ │ │ │ └──────────┴──────────X
The game is played in two stages:
The board starts with no counters on it, and each player starts with nine counters in their hand. Starting with player 1, they take it in turns to place their counters on unoccupied points on the board. If in placing a piece, a player manages to occupy all three points on a straight line with one of their counters (called forming a mill) then they may then remove one of their opponents counters from the board. (For example, in the diagram above, player 2, represented by
O, has such a mill, but player 1, represented byX, does not). Such removed counters play no further part in the game. This continues until both players have placed all their counters.Players continue to alternate turns. In a turn, a player moves one of their counters along a line to an adjacent unoccupied point. As before, if this move forms a mill, then the player removes one of their opponents counters from the board. A player loses if they are unable to move any of their pieces, or if they have only two counters left on the board.
Simulating the game in Python
The object of this coursework is to write a simulator for the game, which allows either two players to play each other.
The board
We'll identify points on the board with integers 0 to 23 as follows:
0──────────1──────────2 │ │ │ │ 3──────4──────5 │ │ │ │ │ │ │ │ 6──7──8 │ │ │ │ │ │ │ │ 9──10──11 12─13──14 │ │ │ │ │ │ │ │ 15─16─17 │ │ │ │ │ │ │ │ 18────19─────20 │ │ │ │ 21────────22─────────23
The game state
The game state -- that is, everything required to describe a game in play -- consists of four elements:
- The location and type of counters on the board
- The number of unplaced counters that each player has in their hand
- The player who taking a turn
We will store game state in a Python list g containing four elements,
g = [[...], p1_counters, p2_counters, active_player]
g[0]is itself a list of 24 integers, describing the board, with theith element of this list,g[0][i]describing what is present at pointion the board.g[0][i]is:- 0 if point
iis unoccupied - 1 if point
icontains a counter of player 1 - 2 if point
icontains a counter of player 2
- 0 if point
g[1]stores an integer containing the number of counters that player 1 has in hand (not yet placed on the board)g[2]stores an integer containing the number of counters that player 2 has in hand (not yet placed on the board)g[3]stores an integer, either 1 or 2, depending on whether the player currently taking their turn is player 1 or player 2, respectively.
A function draw_board() is provided that displays a board state to the console, using diagrams similar to those above. You may use this function as-is, as part of your program, or you may wish to modify it to improve the appearance of the board.
Asking the user for input
The game should interact with users only by asking for integer board locations, and a function request_location(question_str) is provided for this purpose.
This function
- displays the parameter string
question_strthat is passed to it, as a prompt to the user - waits for the user to type an integer
- either: -returns this integer, if it corresponds to a location on the board (between 0 and 23 inclusive)
- or raises a ValueError if the text typed was not an integer
- or raises a RuntimeError if the text typed was an integer, but not in the range 0 to 23 inclusive.
The request_location function is the only way in which you should ask the user for input. You must not modify this function, and you must not use the input(...) function anywhere else in your code. (The reason for this is that, when testing the code, I may modify the request_location function to automate the user input to your program). Using the input(...) function anywhere else in your code will result in the loss of marks.
The tasks:
The following tasks each ask you to write a Python function that forms some part of the game. Generally speaking, the earlier tasks are easier than the later tasks. It is expected that you will call some of the functions from earlier tasks in the later tasks. Unless otherwise specified, functions do not return a value.
- The function definitions are already defined in the template code provided. Use this template, and fill in the implementation of the functions.
- For each function, write a short docstring (~ 1-3 sentences) that explains what the function does, what parameters it takes, and what it returns (if anything).
- Document each of your functions using comments (
#) to explain what the code is doing. On average, I suggest writing one comment line for every ~5 lines of code, though this varies greatly depending on the code being written
Task 1: checking adjacency (4 marks)
Write a function is_adjacent(i, j) that takes two integers representing points on the board, and returns the Boolean value True if those two points are adjacent to one another (connected by a line without going through another point), or False otherwise. A point is not adjacent to itself. For example is_adjacent(21,22) should return True, and is_adjacent(21, 23) and is_adjacent(21,20) should both return False.
You can assume that the values of i and j provided are integers between 0 and 23 inclusive.
Task 2: setting up the game state (4 marks)
Write a function new_game() that returns the game state (the list of four elements, as described above), for a new game in which no counters have been placed.
Task 3: counting counters (4 marks)
Write a function remaining_counters(g) that takes a game state g and returns an integer containing the total number of counters that the current player (g[3]) has available. This is the sum of the number of counters the player has in hand (yet to place on the board) and the number of counters they have on the board.
Task 4: checking for mills (6 marks)
Write a function is_in_mill(g, i) that takes a game state g and an integer index of a point i. The function should return:
- -1 if
iis outside the range 0-23 inclusive, or if there is no counter at pointi - 0 if the counter at point
iis not in a mill, - 1 if the counter at point
ibelongs to player 1 and is in (one or more) mills - 2 if the counter at point
ibelongs to player 2 and is in (one or more) mills
Task 5: checking if the player can move (4 marks)
Write a function player_can_move(g) that returns True if the current player has a valid move to make, or False if they do not. A player has a valid move if they have one or more counters left in their hand, or if not, if any of their counters on the board are next to an adjacent unoccupied space.
Task 6: placing a counter (4 marks)
Write a function place_counter(g, i) that places a counter of the currently active player at point i on the board. The function should raise a RuntimeError if there is already a counter at this location decrement the number of counters that the current player has in their hand.
You can assume that i will be an integer between 0 and 23 inclusive, and that this function is only called if the active player has at least one counter in their hand.Task 7: moving a counter (4 marks)
Write a function move_counter(g, i, j) that moves a counter of the currently active player from point i on the board to the adjacent point j. The function should raise a RuntimeError if this move is not possible, namely if points i and j are not adjacent, if point i doesn't contain a counter of the current player, or if there is already a counter at point j. The function should update the game state to reflect the moved counter.
You can assume that i and j will be an integers between 0 and 23 inclusive.
Task 8: removing an opponent's counter (4 marks)
Write a function remove_opponent_counter(g, i) that takes a game state g and point i and removes the counter at point i on the board. The function succeeds if the point i is occupied by a counter of the opposing player (i.e. the player who is not the current player), and raises a RuntimeError otherwise.
Task 9: taking a turn (8 marks)
Write a function turn(g) that simulates taking a turn of the game. This function takes a game state g and should do five things in sequence:
Check whether the current player is unable to move or has otherwise lost the game, and return
Falseif so, without modifyingg.If the current player has one or more counters in hand,
- ask the player for a location to place a counter on the board using
request_location, - update the game state
gto place this counter
If the player gives an invalid location, or the placement is not possible under the rules of the game, the player should be prompted to enter the location again, until a valid placement is made.
- ask the player for a location to place a counter on the board using
otherwise, the current player has no counters in hand, so,
- ask the player for the location of a counter to move using
request_location, - ask the player for a location to move said counter to, again using
request_location. - update the game state
gto move this counter
If the player gives invalid location(s), or the move is not possible under the rules of the game, the player should be prompted to enter both the locations again, until a valid move is made.
- ask the player for the location of a counter to move using
If the play in step 2 has formed a mill, ask the player for the location of an opposing counter to be removed, and update the game state
gto remove this counter. As before, if an invalid location is given, the player should be re-prompted until a valid location of an opposing counter is provided.Update the game state to switch the current player.
Return
Trueto indicate that the game is not over yet
At appropriate points during the turn, you should display the board, using the provided draw_board() function, or otherwise.
Task 10: saving and loading a game state (8 marks)
Write a function save_state(g, filename) that saves the game state g to a text file, and a function load_state(filename) that returns a game state loaded from a text file. In both cases, the filename is given in the string filename.
Both functions should raise a RuntimeError if the file cannot be saved/loaded.
The file format for both functions is the same, so that the code
save_state(g, 'my_file.txt')
g_new = load_state('my_file.txt')
reloads the same game state that has just been saved, and g_new is equal to g.
The text file used by both functions has four lines, in the following format:
- The first line of the file contains the board state
g[0], stored as integers fromg[0][0]tog[0][23], separated by spaces and commas, as follows0, 2, 1, 0,... etc. There is no comma after the final numberg[0][23]. - The second line of the file contains a single integer, the value of g[1]
- The third line of the file contains a single integer, the value of g[2]
- The fourth line of the file contains a single integer, the value of g[3]
Task 11: playing a game
Write a simple function play_game() that creates a new game state g and repeatedly calls turn(g) to simulate an entire game. Once the game is over, display some text to congratulate the winner.
The play_game function is assessed by hand, rather than by automated testing.
How this coursework will be assessed
This coursework is worth 70 marks, and 70% of the course overall.
50 marks are for correctness of the functions defined in tasks 1-9. These will be tested in an automated way, as in the previous courseworks. The number of automatically assessed marks for each task 1-10 is shown above.
8 marks will be for the overall quality of experience of a player playing the game in Task 11. This will be assessed by humans, and will be based on:
- Correct behaviour of the
play_gamefunction - Clear display of the board at appropriate points in the game
- Clear prompts to the players throughout the game, for example when positions on the board are being requested
- Appropriate handling of errors and clear error messages when invalid input is provided
- Correct behaviour of the
12 marks will be for the quality of the code. This will be assessed by humans, and will be based on:
- Clarity and precision of docstrings for each function
- Clarity of comments elsewhere in the code that describe what the code is doing
- Code quality. Code should be clear, efficient and easy to maintain. Marks may be lost for
- Very inefficient algorithms
- Code that is unnecessarily verbose or difficult to understand
- Unnecessary duplication of code
The model answer to coursework 2, to be released during week 9, provides an example of good quality code, comments and docstrings
Before you submit...
- Re-read the instructions carefully and make sure you have not missed anything.
- Make sure you have filled out your name, student ID number, and email at the top of the code
- Be sure to submit to Blackboard just the
.pyfile containing the python code. Do not submit the code in any other format (for example, a screenshot, PDF, jupyer notebook or word document are not acceptable formats).
