The purpose of this assignment is to offer you the first experience with Python, which supports the Object-Oriented programming paradigm. Our main focuses are Dynamic Typing and Duck Typing. Please use Python 3.6 to finish this assignment.

The assignment consists of 4 tasks.

• You need to implement a famous board game called Six Mens Morris in Python.
• You are asked to demonstrate the advantages/disadvantages of dynamic typing through some example code, which could be taken from any code you write for this assignment.
• We give you the Java source code of a game called Save The Tribe. You need to reimplement the game in Python to make the code cleaner with the help of Duck Typing.
• Additional features and mechanisms are introduced to the Save The Tribe game. You need to implement the enhanced game in both Java and Python.

After completing the 4 tasks, you need to write a report elaborating on Dynamic Typing and Duck Typing.

NOTES: all your codes will be graded on the Linux machines in the Department. You are welcome to develop your codes on any platform, but please remember to test them on Department machines.

2 Task 1: Six Mens Morris

This is a programming exercise for you to get familiar with Python, which is a dynamically typed language. In this task, you have to strictly follow our proposed OO design and the game rules for the 2-player Six Mens Morris game stated in this section.

Six Mens Morris is a popular game in Italy, France and England during the Middle Ages but was obsolete by 1600. You can have a try to play this game in https://www.novelgames.com/ en/sixmensmorris.

For simplicity, we want you to implement a watered-down version of Six Mens Morris. The detailed specification or game rules are described as follows.

2.1 Description

The game board consists of a grid with 16 intersections or points as shown in Figure 1. Each player has six pieces, or men, coloured black or white. Players try to form mills three of their men lined up horizontally or verticallyallowing a player to remove the opponents man from the game board. For simplicity, Player 1 always uses the white pieces and Player 2 uses the black ones.

The game proceeds in the following two phases.

1. Placing the pieces. The game begins with an empty board. Player 1 first starts to play and the two players take turns placing their men, one per turn on empty points. This phase will last for 6 rounds since each player has only 6 men. Note that a player forming a mill can remove one of the opponents pieces from the board. However, no one can win during Phase 1. After all men are placed, Phase 2 begins.

Figure 1: Game board for Six Mens Morris.

2. Moving the pieces. Players again alternate moves, this time moving a man to an adjacent and unoccupied point. A piece may not jump over another piece. Players continue to try to form mills and remove their opponents pieces as in Phase 1. Note that a player can break a mill by moving one of his pieces out of an existing mill, then moving it back to form the same mill a second time (or any number of times), each time removing one of his opponents men.

Game goal or winning conditions. A player wins by reducing the opponent to two men (where the opponent could no longer form mills and thus be unable to win), or by leaving the opponent with no legal moves. Note that this game will never end in a tie.

As shown in Figure 2, on the left-hand side, Player 1 loses the game because (s)he has only two pieces left. On the right-hand side, Player 1 also loses the game because (s)he cannot move any one of the white pieces.

Figure 2: Winning conditions of Six Mens Morris. A player wins by reducing the opponent to two pieces or by leaving them without a legal move.

Mill examples. As shown in Figure 3, the left board forms a mill since three black pieces are lined up horizontally. The right board forms no mill because there are no lines between the lower two pieces.

Figure 3: Visualization of a mill. Mill is formed when three men of the same color are lined up horizontally or vertically.

2.2 Problem Specification

This section describes the requirements, program design, function decomposition, game flow, etc.

2.2.1 Game Board Representation

There are 16 possible points on a board. Therefore, we use letters a,b,c,,p to denote these board positions, as illustrated in Figure 4.

Figure 4: Board positions specification.

To encode the whole game board, we use an array of 16 characters. Each character in the array is either . (Empty point), # (Player 1), or @ (Player 2). Using this representation, the initial board is encoded as an array of 16 . characters.

2.2.2 Input/Output Specification

Types of Player. Users can choose Player 1 and Player 2 to be either human- or computercontrolled. You have to use the command line to request the types of the two players before starting the game (as shown in Figure 5).

Figure 5: Setting for the type of players.

Board. Once the players are chosen, the empty board is outputted first. Note that we always output two views of the board at the same time. The left view represents the current board state and the right one shows the board positions map (where the letters a,b,c,,p denote the positions on the board) as shown in Figure 6 because the board is not rectangular. You do not need to worry about the boards visualization because we have implemented the printing function in the provided code. Do not modify the printing function, or you will lose marks.

Figure 6: Empty board.

Every time a player does a legal movement on the board, the program will output the current state of the board.

Movements. This program requires decisions of the following three operations from the human or computer players.

• PUT(pos): In Phase 1 of this game, the players put pieces in turn on the board. It takes an input of one letter as the position of the piece. If it is an illegal movement or input, the program will output a warning message Invalid Put-Movement. and request for input again. The input messages format for players is like Player 1 [Put] (pos): and it takes a input of one letter.
• MOVE(s, t): In Phase 2 of this game, the players move the existing pieces on the board and the input takes 2 letters: source position and target position. If it is an illegal movement or input, the program will output a warning message Invalid Move-Movement. and request for input again. The input messages format for players is like Player 1 [Move] (from to): and it takes an input of two letters separated by a space.
• REMOVE(pos): In either phase of the game, once a player forms a mill on the board, the player can do an extra movement, which removes an opponents piece. In this movement, it takes an input of one letter position. If it is an illegal removal or input, the program will output a warning message Invalid Remove-Movement. and request for input again. The input messages format for players is like Player 1 [Remove] (pos): and it takes a input of one letter.

A computer player always makes valid operations. The program should print out the input message of the corresponding operations and the decision by the computer player same as the message for human player.

Overall Interface. As shown in Figure 7, this is basically the whole interface of our game. The board will be displayed after every movement or play and each player has to make his decision for the requested movement. Although a computer player does not request for input, it outputs the decision in the same format as the human player does.

After the game ends, it will output a winning message for the winner like Congratulation to the winner: Player 1!.

2.3 Required Classes and Functions

To let you get familar with OO-design, we provide an OO class design framework for this game. You should follow this OO-design and must not modify the prototypes of any of these classes and functions. You can design extra functions if you find it necessary.

class SixMensMorris

This class controls the overall game process, including phases 1 and 2 in Six Mens Morris, and the starting and ending of the game.

board = Board()

This is a variable representing the game board.

players = [Player(1), Player(2)]

This is an array with two variables representing the players.

num play = 0

This is a variable representing the number of total plays (one play denotes one movement by a player.). Each time a player does a movement, this variable is incremented by 1. We note that 1 round is equivalent to 2 plays.

next player(self)

This function returns the current player in this round.

Figure 7: The interface.

opponent(self, player)

This function returns the opponent of the player. If the argument is Player 1, then it will return Player 2, and vice versa.

check win(self, player)

This function returns a Boolean variable representing whether the player wins the game. It calls board.check win() in fact.

start game(self)

This function controls the overall logic of the game.

class Board

This class defines the game board and its properties such as the connected edges and all possible mills on the board, as well as a series of movements and legal movement checks on the board. The state of the board is controlled by the players.

state

This is the representation of the state of the game board, which stores an array of size 16.

mills

This variable pre-defines all possible mill configurations, each of which is represented as a 3-tuple on the board.

edges

This variable pre-defines all possible edges, each of which is represented as a 2-tuple on the board.

print board(self)

This function prints the current stored board state. It would print two views one shows the board state and the other one shows the reference board positions for the players. Please refer to the visualization of the board in Figure 7.

check put(self, pos)

This function checks whether the PUT-movement is legal. The argument is the putting position. The output is a Boolean variable.

check move(self, s, t, player)

This function checks whether the MOVE-movement is legal. The arguments are the source position, the target position, and the player. The output is a Boolean variable.

check remove(self, pos, player)

This function checks whether the REMOVE-movement is legal for the player. The arguments are the position on which the piece is expected to be removed and the player. The output is a Boolean variable.

• put piece(self, pos, player)

This function does the PUT-movement on the board without checking.

• move piece(self, s, t, player)

This function does the MOVE-movement on the board without checking.

• remove piece(self, pos, player)

This function does the REMOVE-movement on the board without checking.

form mill(self, pos, player)

This function returns a Boolean variable representing whether it forms a mill at this position for the player.

check win(self, player, opponent)

This function returns a Boolean variable representing whether the current player wins. If the current player wins the game, then it returns True. Otherwise, it returns False. Please refer to the winning conditions.

class Player

This class defines the behaviors of players. The player can put pieces, move pieces and remove pieces on the board.

• id

Players id. It is an integer 0 or 1.

• symbol

Players symbol. Player 1 uses # but Player 2 uses @.

• board

This is the game board for the player.

next put(self)

This function defines a PUT-movement for the player. It should be implemented by the Human and Computer classes. It returns the position to which the piece is put because it might trigger the formation of a mill.

next move(self)

This function defines a MOVE-movement for the player. It should be implemented by the Human and Computer classes. It returns the position to which the piece moves because it might trigger the formation of a mill.

next remove(self, opponent) This function defines a REMOVE-movement for the player. It should be implemented by the Human and Computer classes.

class Human

This class extends the superclass Player to play the game, where the players movements are from the input of the user.

next put(self)

This function outputs a prompt and takes a single location input for a PUT-movement. Specifically, the input messages format is like Player 1 [Put] (pos): and it takes an input of one letter. It keeps checking whether it is a legal PUT-movement until the input is legal. After getting the correct input, it then does the movement on the board (by calling board.put piece()). It returns the position where the piece to put because it might trigger the formation of a mill. When there is an error input, it will output a warning message Invalid Put-Movement..

next move(self)

This function outputs a prompt and takes two location inputs (s, t) for a MOVEmovement. Specifically, the input messages format for players is like Player 1 [Move] (from to): and it takes an input of two letters separated by a space. It keeps checking whether it is a legal MOVE-movement until the input is legal. After getting the correct input, it then does the movement on the board (by calling board.move piece()). It returns the position to which the piece moves because it might trigger the formation of a mill. When there is an error input, it will output a warning message Invalid Move-Movement..

next remove(self, opponent)

This function outputs a prompt and takes a location input for a REMOVE-movement. Specifically, The input messages format for players is like Player 1 [Remove] (pos): and it takes a input of one letter. It keeps checking whether it is a legal REMOVEmovement until the input is legal. After getting the correct input, it then does REMOVEmovement on the board (by calling board.remove piece()). It returns nothing. When there is an error input, it will output a warning message Invalid Remove-Movement..

class Computer

This class extends the superclass Player to play the game, where the players movement is generated by the computer.

next put(self)

This function randomly generates a legal PUT-movement and does the movement on the board (by calling board.put piece()). It outputs the same message like Player 1 [Put] (pos): and one letter representing his decision. It returns the position where the piece locates because it might trigger the formation of a mill. Note that the computer only generates a legal movement and thus print no warning message.

next move(self)

This function randomly generates a legal MOVE-movement (s,t) and then does the movement on the board (by calling board.move piece()). It outputs the same message as the human player: Player 1 [Move] (from to): and two letters representing his decision. It returns the position to which the piece moves because it might trigger the formation of a mill. Note that the computer only generates a legal movement and thus print no warning message.

next remove(self, opponent)

This function randomly generates a legal REMOVE-movement and does REMOVEmovement on the board (by calling board.remove piece()). It outputs the same message like Player 1 [REMOVE] (pos): and one letter representing his decision. It returns nothing. Note that the computer only generates a legal movement and thus print no warning message.

2.4 Your programming task

Overall there are six source files, one for each defined class and additional tools file: Board.py, Computer.py, Human.py, Player.py, SixMensMorris.py, utils.py. The files are templates. Your task is to complete the missing parts of the code which are marked by TODO. The programming environment is Python3 (Python3.5+) only.

1. Complete your name and student ID in every file.
2. Based on the above problem specification, complete the game program by implementing the above member functions.
3. The program starts by running python3 SixMensMorris.py. You should design enough corner cases to test your program.

Things to note:

1. Apart from completing these member functions, Do Not change any other parts of our provided source code.
2. Please strictly follow the Input/Output specification in Subsection 2.2.2. You might easily get the I/O details by directly going through the provided code. Otherwise, your marks can be deducted.
3. For better visualization, we added color in the output and you can find the color functions in the file utils.py. You should not change the color or its uses in the source code. Otherwise, it might cause errors when we are comparing the output content by machines.
4. In Python, there is a library that you can use to debug the code, e., ipython. You can simply insert from IPython import embed; embed() and run the program. Then you can debug your program like checking the variable values or debugging the code you write while the code is running.

3 Task 2: Demonstrating Advantages and Disadvantages of Dynamic Typing

These are commonly-claimed advantages and disadvantages of Dynamic Typing:

1. Advantages
   • More generic code can be written. In other words, functions can be defined to apply on arguments of different types.
   • Possibilities of mixed type collection data structures.
2. Disadvantage
   • Loss of type checking at compile time.

Please provide concise example codes designed by yourself or extracted from any code you write for this assignment to demonstrate the advantages and disadvantage of Dynamic Typing mentioned above. You are welcome to provide other advantages or disadvantages along with code fragment for extra bonus points.

4 Task 3: Save The Tribe

This task is to build a game in Python. A Java implementation of the game is given. You need to understand its behavior and re-implement it with Python. After finishing this task, you will have experienced a special feature of Python called Duck Typing, which is possible only in a dynamically typed language. And you will see a difference between the Java and Python implementations, the former of which does not support Duck Typing.

4.1 Duck Typing

The following synopsis of Duck Typing is summarized from:

http://en.wikipedia.org/wiki/Ducktyping

http://www.sitepoint.com/making-ruby-quack-why-we-love-duck-typing

In standard statically-typed object-oriented languages, objects classes (which determine an object characteristics and behavior) are essentially interpreted as the objects types. Duck Typing is a new typing paradigm in dynamically-typed (late binding) languages that allows us to dissociate typing from objects characteristics. It can be summarized by the following motto by the late poet James Whitcombe Riley:

When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.

The basic premise of Duck Typing is simple. If an entity looks, walks, and quacks like a duck, for all intents and purposes it is fair to assume that one is dealing with a member of the species anas platyrhynchos. In practical Python terms, this means that it is possible to try calling any method on any object, regardless of its class.

An important advantage of Duck Typing is that we can enjoy polymorphism without inheritance. An immediate consequence is that we can write more generic codes, which are cleaner and more concise.

4.2 Background

In Ancient Rome, a tribe is attacked by alien invaders. The only way to wipe out these invaders is to seek an artifact from a desert nearby. However, the desert is very dangerous with many monsters residing there.

With the mission to save the tribe, a soldier (the player) comes to the desert and starts his journey to seek the artifact. Each monster in the desert lives in its own cave and the artifact is taken by one of the monsters. The soldier has to enter the cave and kill the monster in a topological order so that (s)he could get the keys to enter other caves. Figure 8 illustrates the pre-defined topological order, where each node represents a cave. If the soldier wants to enter cave 2, (s)he has to kill the monster inside cave 5 or cave 1 first to get the key for cave 2. The monster inside cave 7 keeps the artifact that the soldier wants to collect.

Figure 8: Topological order to kill the monsters.

4.3 Task Description

At the beginning, there are 7 monsters and a spring in the desert. All of them are distributed in different positions, as illustrated in Figure 9. The health capacity of the soldier is 100, the health capacity of the monsters is a random number in the range of 3070, which must be in multiples of 10. The soldier can drink the spring water to recover fully his health. Before exploring the desert, the soldier is equipped with 2 elixirs to increase his health during fight, as well as the keys to enter cave 5 and cave 1.

Figure 9: Map of the desert. Symbols of M, S and @ represent the monsters, soldier and spring respectively.

• At each iteration, the soldier can move to the next grid cell in the desert.

When meeting a cave, the monster inside will check whether the soldier has the key to enter or not.

• If yes, the soldier will fight with the monster in a round-based manner. In each round, the soldier has three options:
  1. Attack: The health of the monster will be damaged by 10. If the monster is still alive, the health of the soldier will also be damaged by 10. Enter next round. Note that the soldier always attacks first.
  2. Escape: The soldier escapes and the health of monster will be recovered to its health capacity automatically. The fight is over.
  3. Use Elixir: The soldier uses elixir, which could increase her/his health by 15 to 20 randomly. Enter next round.

If the soldier successfully kills the monster (health of monster is reduced to 0 or less), (s)he will get the dropped item(s) from the monster. Otherwise, when the health of the soldier is reduced to 0 or less, the soldier is dead and the game is over.

• If no, the monster will tell the soldier where (s)he can collect the key to enter this cave.

When meeting the spring, the soldier will drink the water and recover his health to 100.

The soldier can only the water for one time.

• When the soldier gets the artifact from the monsters, the game will be over.

You should read and execute the given Java program to understand its behavior and design. Then please replicate all the behavior of the given Java Program in Python with Duck Typing, following the same class design. You should not introduce extra instance variables or instance methods. You program should run by calling python3 SaveTheTribe.py. You will also be evaluated on your programming style.

5 Task 4: Strengthen Yourself

A merchant comes to the desert. The soldier could buy shield or elixir with coins to strengthen himself, which enables him to kill the monster more easily. After killing each monster, the soldier could get one coin.

5.1 New Game Elements

At the beginning, there are 7 monsters (M), a merchant ($), and a spring (@) in the desert. The merchant is located at (7,7) on the map. Note that the soldier has no coins initially.

• At each iteration, the soldier can move to the next grid cell in the desert.

When meeting a cave, the monster inside will check whether the soldier has the key to enter or not.

• If yes, the soldier will fight with the monster in a round-based manner. In each round, the soldier has three options:
  1. Attack: The health of the monster will be damaged by 10. If the monster is still alive, the health of the soldier will also be damaged by 10 his defence value, but the damage value is no less than zero. Enter next round. Note that the soldier always attacks first.
  2. Escape: The soldier escapes and the health of monster will be recovered to its health capacity automatically. The fight is over.
  3. Use Elixir: The soldier uses elixir, which could increase her/his health by 15 to 20 randomly. Enter next round.

If the soldier successfully kills the monster (health of monster is reduced to 0 or less), he will get the dropped item(s) and one coin from the monster. Otherwise, when the health of the soldier is reduced to 0 or less, the soldier is dead and the game is over.

• If no, the monster will tell the soldier where (s)he can collect the key to enter this cave.

When meeting the spring, the soldier will drink the water and recover his health to 100.

When meeting the merchant, the soldier has three options:

1. The soldier can buy an elixir with one coin.
2. The soldier can buy a shield with two coins. Each shield can improve the defence value of the soldier by 5.
3. (Note that the soldier will also automatically leave if (s)he doesnt have enough money to buy what (s)he chooses to buy).

• When the soldier gets the artifact from the monsters, the game will be over.

5.2 Program Enhancement

You are now required to enhance both the Java and Python implementations of Task 3, according to the requirements below:

1. You need to add a Merchant A Java template is provided for your reference.
2. You need to make appropriate modifications to the Soldier and Monster classes, for which you need to use the power of inheritance as much as possible. For example, for the modification of the Soldier class, you need to add a subclass of the Soldier class, and name it as Task4Soldier class, instead of modifying the Soldier class directly. But please note that you are allowed to modify the instance variable health in Soldier class into a protected variable.
3. You need to make appropriate modifications to the SaveTheTribe and Map classes in Java, but only need to modify SaveTheTribe class in Python, due to the usage of Duck Typing. For the changes on these two classes, you are allowed to modify the original class design of Task 3.
4. You are required to name each class that you have modified or added for Task 4 as Task4xxx. For example, if you modify the SaveTheTribe class, please name it as Task4SaveTheTribe, and name the corresponding file as Task4SaveTheTribe.py or Task4SaveTheTribe.java.
5. You are required to display all the attributes of the soldier in each iteration, as illustrated in Figure 10.
6. Your program should be run by calling python3 Task4SaveTheTribe.py and javac Task4SaveTheTribe.java.

Figure 10: Displayed information in each iteration.

6 Report

Your simple report should answer the following questions within TWO A4 pages.

1. Providing example code and necessary elaborations for demonstrating advantages and disadvantages of Dynamic Typing as specified in Task 2.
2. Using codes for Task 3, give two scenarios in which the Python implementation is better than the Java implementation. Given reasons.
3. Using codes for Task 4, illustrate further advantages of Duck Typing.