CS 105:	Modules	Calendar	Office Hours	Syllabus	ML	Coding Style	Coding Rubric

Rules and moves

Pick up the last stick

The game starts with N sticks on a table. Players take turns. When it’s your turn, you must pick up 1, 2, or 3 sticks. The player who picks up the last stick wins.

Function Move.parse must accept, at mininum, strings "1", "2", and "3".

Take the last coin

The game starts with a mix of coins on the table: quarters, dimes, and nickels. The game starts with 4 quarters, 10 dimes, and 7 nickels, so if you want to play, you’ll need $2.35.

Players X and O take turns.

When it’s your turn, you take coins. You must take at least one coin, and you may take as many coins as you like, provided they are all the same denomination. That is, you must take only quarters, or only dimes, or only nickels.

The player who takes the last coin wins.

Function Move.parse must accept strings like the following:

"1 dime"
"3 quarters"
"5 nickels"

It is OK if Move.parse is very permissive in what it accepts.

Tic-Tac-Toe

This is an adversary game played by two persons using a 3x3 square board. The players (traditionally called X and O) take turns in placing X’s or O’s in the empty squares on the board (player X places only X’s and O only O’s). In the initial configuration, the board is empty.

The first player who managed to obtain a full line, column or diagonal marked with his name is the winner. The game can also end in a tie. In the picture below the first configuration is a win for O, the next two are wins for X and the last one is a tie.

  -------------    -------------    -------------    -------------
  | X |   | X |    |   |   | X |    | X | O |   |    | O | O | X |
  -------------    -------------    -------------    -------------
  |   | X |   |    | O | X | O |    | X | O |   |    | X | X | O |
  -------------    -------------    -------------    -------------
  | O | O | O |    | X |   | O |    | X |   | O |    | O | X | O |
  -------------    -------------    -------------    -------------

In Britain, this game is called “noughts and crosses.” No matter what you call it, a player who plays perfectly cannot lose. All your base are belong to the AGS. You can play /comp/105/bin/ttt.

Function Move.parse must accept the following full names:

 upper left  | upper middle  |   upper right
-------------+---------------+---------------
middle left  |    middle     |  middle right
-------------+---------------+---------------
 lower left  | lower middle  |   lower right

Function Move.visualize must also use these names. If you wish, Move.parse may recognize additional abbreviations such as ul, um, ur, ml, m, mr, ll, lm, and lr.

Detailed guidance

Implement “pick up the last stick”

Put your implementation into a file called sticks.sml, which should be organized according to the following template:

functor SticksFun(val N : int) :> GAME = struct
  ...
  type state = ...   (* or possibly    datatype state = ... *)

  val invariant : state -> bool = ...
  (* abstraction function: ... *)

  ...
  structure Move = struct
     (* pick one of these two ways to define type `move` *)
     datatype move ...    
     type move = ...
     ...
  end
  ...
end

To create an actual game, you’ll instantiate the functor:

structure TestSticks = SticksFun(val N = 14)

Complete the implementation by following these step-by-step instructions for implementing two-player games:

Choose how you will represent the state of the game (i.e., define type state). This step is crucial because it determines how complex your implementation will be. You want a representation that will make it easy to implement makemove, legalmoves, and outcome.

In “pick up the last stick,” there’s an obvious choice: a pair containing the player who’s turn it is and the number of sticks on the table. For a more ambitious game, like Hexapawn or tic-tac-toe, the representation is less obvious. I myself have implemented tic-tac-toe using two different representations, one of which is four times faster than the other.

The AGS and the computer opponent cannot possibly depend on your choice of representation (the ML module system guarantees it), so you are free to choose whatever representation you like. Even more important, you can change your representation at any time, and no code outside your own module will be affected. If you have any difficulty implementing the functions in the GAME interface, you should change your representation—or at least think about it.

You might be tempted to use mutable data to represent a game state. Don’t! The contract of the GAME interface requires that any value of type state be available to the AGS indefinitely. Mutating a state is not safe.

Document your representation by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto the basic concepts of the game, interface, including players and sticks.
- Write the invariant in an ML function named invariant, which takes a value of type state and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to.
Choose a representation for moves. You have fewer interesting choices here.

For “pick up the last stick”, there are two good choices: you could pick type int, in which case you’d have to enforce a representation invariant, or you could define an enumeration type such as
```
datatype move = ONE | TWO | THREE
```
The choice is yours.

Document this representation also by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto the number of sticks picked up.
- Write the invariant in an ML function named invariant, which takes a value of your chosen representation and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to. Depending on your choice of representation invariant might always return true.
Define the exception Move.
Define function initial.
Define function whoseturn.
Define function makemove. Its contract requires it to be Curried.
Define function outcome. If nobody has won, the outcome should be NONE for a non-final state and SOME Player.TIE for a final state.

Hints for “pick up the last stick”:
- There are no ties.
- The game is over only if there are no sticks left on the table.
- If there are no sticks left, the player whose turn it is loses.
Define function isOver. This function should return true if somebody has won or if no move is possible (everybody is stuck).
Define function legalmoves. This function must return a list of permissible moves. Order doesn’t matter, but the list should have no duplicates. If the game is over, no further moves are possible, and legalmoves must return the empty list. (In this case, according to contract, isOver must return true.)
Define function Move.visualize. This function must return a string like “Player X takes 3 dimes” or “Player O moves to the middle square.” The string must not contain a newline. You can build your strings using concatenation (^) and exported functions from other modules (e.g. Player.unparse). To convert integer values to strings you can use the function Int.toString.
Define function visualize, which returns a simple ASCII representation of the game’s state. The value should end in a newline. Remember to include the player whose turn it is to move.
Define function Move.prompt. It takes the player whose turn it is to move, and it returns a prompt message (without newline) asking the specified player to give a move.
Define function Move.parse. This function should take a string (which is probably the reply given after a call to Move.prompt), and it should return the move corresponding to that string. If there is no such move, it should raise an exception.

Function Move.parse accepts only finitely many strings. When you need to match a finite set of strings, you can recognize them using pattern matching on string literals, or you can put the strings into a data structure, like an association list or an environment. A nested sequence of if expressions is not acceptable.

So that we can test your code, please ensure that Move.parse accepts either the strings "1", "2", and "3" or the strings "one", "two", and "three".

It is OK if Move.parse is very permissive in what it accepts.
For testing, you can use the Unit signature from /comp/105/lib; the compile105-sml script should import it for you. No testing is required; at this point, you have enough ML experience to know how much effort you want to put into testing and how much value you can expect to get out.

Two-player games offer substantial scope for property-based testing. You might wish to test such properties as these:
- The initial player takes the first turn.
- Players take turns (not true of every game, but true of this one).
- If the game is over, no moves are possible.
- If a player has won, the game is over.
- If the game is not over, the outcome is NONE.
- The visualization of each state ends in a newline.
Such properties are best expressed as functions: usually a function from state to bool. Once you’ve written the function, you can test it using checkAssert with many different states.

Here’s an example function for “players take turns” (code not compiled or tested):
```
fun take_turns state =
  let val current = G.whoseturn state
      fun nextplayer  move = G.whoseturn (G.makemove state move)
      fun nextChanges move = nextplayer move <> current
  in  List.all nextChanges (G.legalmoves state)
  end
```
If I had any concerns about correctness, I would focus on testing properties to ensure that legalmoves, isOver, and outcome are all consistent.

What to watch out for. The main thing we’ll look for in testing is to be sure that your observers provide a consistent picture of a game’s state. For example, if your implementation says that player X won, it had better also say that the game is over.

Related reading: The lengthy description of the GAME signature, and the section on ML modules in the ML learning guide.

Implement “take the last coin”

Put your implementation into a file called coins.sml, which should be organized according to the following template:

structure Coins :> GAME = struct
  ...
  type state = ...   (* or possibly    datatype state = ... *)

  val invariant : state -> bool = ...
  (* abstraction function: ... *)

  ...
  structure Move = struct
     (* pick one of these two ways to define type `move` *)
     datatype move ...    
     type move = ...
     ...
  end
  ...
end

Complete the implementation by following these step-by-step instructions for implementing two-player games:

Choose how you will represent the state of the game (i.e., define type state). This step is crucial because it determines how complex your implementation will be. You want a representation that will make it easy to implement makemove, legalmoves, and outcome.

For the coins game, your representation should include both the player whose turn it is and some representation of the coins on the table. For the coines, you have a number of reasonable choices:
- A simple list of coins. This representation is faithful to the statement of the problem, and it requires a trivial abstraction function and representation invariant.
- A record or tuple giving the number of coins of each denomination.
- An association list giving the number of coins of each denomination.
The latter two choices require more thought to the abstraction function and representation invariant.

The AGS and the computer opponent cannot possibly depend on your choice of representation (the ML module system guarantees it), so you are free to choose whatever representation you like. Even more important, you can change your representation at any time, and no code outside your own module will be affected. If you have any difficulty implementing the functions in the GAME interface, you should change your representation—or at least think about it.

You might be tempted to use mutable data to represent a game state. Don’t! The contract of the GAME interface requires that any value of type state be available to the AGS indefinitely. Mutating a state is not safe.

Document your representation by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto the basic concepts of the game, interface, including players, coins, and denominations.
- Write the invariant in an ML function named invariant, which takes a value of type state and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to.
Choose a representation for moves. You have fewer interesting choices here.

Document this representation also by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto a denomination and a number of coins.
- Write the invariant in an ML function named invariant, which takes a value of your chosen representation and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to.
Define the exception Move.
Define function initial.
Define function whoseturn.
Define function makemove. Its contract requires it to be Curried.
Define function outcome. If nobody has won, the outcome should be NONE for a non-final state and SOME Player.TIE for a final state.

Hints for “take the last coin”:
- There are no ties.
- The game is over only if there are no coins left on the table.
- If there are no coins left, the player whose turn it is loses.
Define function isOver. This function should return true if somebody has won or if no move is possible (everybody is stuck).
Define function legalmoves. This function must return a list of permissible moves. Order doesn’t matter, but the list should have no duplicates. If the game is over, no further moves are possible, and legalmoves must return the empty list. (In this case, according to contract, isOver must return true.)

For the “take the last coin” game, this function is one of the more difficult ones to implement. I commend to you the following definitions:
```
  (* val downto : int * int -> int list *)
  (*    list of numbers in the given range, inclusive *)
  infix 9 downto
  fun n downto i = if n < i then []
                   else n :: (n - 1) downto i
```
Define function Move.visualize. This function must return a string like “Player X takes 3 dimes” or “Player O moves to the middle square.” The string must not contain a newline. You can build your strings using concatenation (^) and exported functions from other modules (e.g. Player.unparse). To convert integer values to strings you can use the function Int.toString.
Define function visualize, which returns a simple ASCII representation of the game’s state. The value should end in a newline. Remember to include the player whose turn it is to move.
Define function Move.prompt. It takes the player whose turn it is to move, and it returns a prompt message (without newline) asking the specified player to give a move.
Define function Move.parse. This function should take a string (which is probably the reply given after a call to Move.prompt), and it should return the move corresponding to that string. If there is no such move, it should raise an exception.

So that we can test your code, please ensure that Move.parse accepts strings like the following:
```
"1 dime"
"3 quarters"
"5 nickels"
```
It is OK if Move.parse is very permissive in what it accepts.

To help you write Move.parse, here are a couple of useful string-processing functions. The details of their contracts are left to you to work out.
```
(*val findName : string -> string option *)
fun findName s =
  List.find (fn name => String.isSubstring name s) 
            ["quarter", "dime", "nickel"]

(*val findNumber : string -> int option *)
val findNumber =
  Int.fromString o implode o List.filter Char.isDigit o explode
```
I commend to you expressions of the form
```
case (findName s, findNumber s) of ...
```
For testing, you can use the Unit signature from /comp/105/lib; the compile105-sml script should import it for you. No testing is required; at this point, you have enough ML experience to know how much effort you want to put into testing and how much value you can expect to get out.

Two-player games offer substantial scope for property-based testing. You might wish to test such properties as these:
- The initial player takes the first turn.
- Players take turns (not true of every game, but true of this one).
- If the game is over, no moves are possible.
- If a player has won, the game is over.
- If the game is not over, the outcome is NONE.
- The visualization of each state ends in a newline.
Such properties are best expressed as functions: usually a function from state to bool. Once you’ve written the function, you can test it using checkAssert with many different states.

Here’s an example function for “players take turns” (code not compiled or tested):
```
fun take_turns state =
  let val current = G.whoseturn state
      fun nextplayer  move = G.whoseturn (G.makemove state move)
      fun nextChanges move = nextplayer move <> current
  in  List.all nextChanges (G.legalmoves state)
  end
```
If I had any concerns about correctness, I would focus on testing properties to ensure that legalmoves, isOver, and outcome are all consistent.

Related reading: The lengthy description of the GAME signature, and the section on ML modules in the ML learning guide.

Implement tic-tac-toe

Put your implementation into a file called ttt.sml, which should be organized according to the following template:

structure TTT :> GAME = struct
  ...
  type state = ...   (* or possibly    datatype state = ... *)

  val invariant : state -> bool = ...
  (* abstraction function: ... *)

  ...
  structure Move = struct
     (* pick one of these two ways to define type `move` *)
     datatype move ...    
     type move = ...
     ...
  end
  ...
end

Complete the implementation by following these step-by-step instructions for implementing two-player games:

Choose how you will represent the state of the game (i.e., define type state). This step is crucial because it determines how complex your implementation will be. You want a representation that will make it easy to implement makemove, legalmoves, and outcome.

The AGS and the computer opponent cannot possibly depend on your choice of representation (the ML module system guarantees it), so you are free to choose whatever representation you like. Even more important, you can change your representation at any time, and no code outside your own module will be affected. If you have any difficulty implementing the functions in the GAME interface, you should change your representation—or at least think about it.

You might be tempted to use mutable data to represent a game state. Don’t! The contract of the GAME interface requires that any value of type state be available to the AGS indefinitely. Mutating a state is not safe.

If you think you might want immutable arrays, check out the Vector structure (see the ML supplement). (You can find out what’s in any ML structure by typing, e.g., open Vector at the interactive prompt, or you can consult the Standard Basis documentation. You can also use Moscow ML’s help system, e.g,
```
      - help "Vector";
```
If you get interested in vectors, don’t overlook the function Vector.tabulate.)

One more thing. You may be tempted to start out by representing the contents of a square using 0 and 1 or other arbitrary values. If you go this route, why not use Player.player option? It will make your code elegant and easy to understand.

Hint: You may find it useful to define a structure Grid that you can use to represent a square or rectangular array of values of type 'a. Defining suitable analogs of map and fold on the grid will help, as will functions to extract sub-grids (rows and columns).

Document your representation by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto the basic concepts of the game, interface, including the players and the game grid.
- Write the invariant in an ML function named invariant, which takes a value of type state and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to.
Choose a representation for moves. You have fewer interesting choices here.

Document this representation also by giving a representation invariant and an abstraction function.
- Write the abstraction function in a comment. We recommend using informal English to specify a function that maps your chosen representation onto a square.
- Write the invariant in an ML function named invariant, which takes a value of your chosen representation and returns a Boolean. This function must typecheck. You may call it and unit-test it if you wish, but you don’t have to. Depending on your choice of representation invariant might always return true.
Define the exception Move.
Define function initial.
Define function whoseturn.
Define function makemove. Its contract requires it to be Curried.
Define function outcome. If nobody has won, the outcome should be NONE for a non-final state and SOME Player.TIE for a final state.

Hints for Tic-Tac-Toe:
- You could write a function which checks lines, another that checks columns and finally one that checks diagonals. Then outcome could call these functions with the right parameters.
- If you are using lists in your representation, you can use pattern matching.
Define function isOver. This function should return true if somebody has won or if no move is possible (everybody is stuck).
Define function legalmoves. This function must return a list of permissible moves. Order doesn’t matter, but the list should have no duplicates. If the game is over, no further moves are possible, and legalmoves must return the empty list. (In this case, according to contract, isOver must return true.)

If you want to be clever, you can exploit rotation and reflection symmetries to prune the list returned by legalmoves. You may be surprised how much difference this trick makes to performance.
Before you start on the functions that convert between moves and strings, I recommend that you create a data structure that associates each move a representation of that move as a string. This data structure will be a single point of truth, and it will help you guarantee that Move.parse and Move.visualize are consistent, even if you make some other mistake in their implementations.
Using your data structure from the previous step, define function Move.visualize. This function must return a string like “Player X takes 3 dimes” or “Player O moves to the middle square.” The string must not contain a newline. You can build your strings using concatenation (^) and exported functions from other modules (e.g. Player.unparse). To convert integer values to strings you can use the function Int.toString.
Define function visualize, which returns a simple ASCII representation of the game’s state. The value should end in a newline. Remember to include the player whose turn it is to move.

Give us more than a simple list of numbers. You can print a nice little “ASCII graphics” layout using only a few characters. To get you started, here is some untested sample code to print a row; it has type player option list -> string:
```
local
  fun boxString (SOME p) = Player.visualize p
    | boxString (NONE  ) = " " 
in
  fun rowString []             = "|\n"
    | rowString (box :: boxes) = "| " ^ boxString box ^ " " ^ rowString boxes
end
```
The better your output, the more fun it will be to play. You can see a simple sample by running /comp/105/bin/ttt.
Define function Move.prompt. It takes the player whose turn it is to move, and it returns a prompt message (without newline) asking the specified player to give a move.
Define function Move.parse. This function should take a string (which is probably the reply given after a call to Move.prompt), and it should return the move corresponding to that string. If there is no such move, it should raise an exception.

Function Move.parse accepts only finitely many strings. When you need to match a finite set of strings, you can recognize them using pattern matching on string literals, or you can put the strings into a data structure, like an association list or an environment. A nested sequence of if expressions is not acceptable.

So that we can test your code, please ensure that Move.parse accepts "upper left", "upper middle", and all the other similar names listed above.

It is OK if Move.parse is very permissive in what it accepts.

Define Move.parse in such a way that Move.parse and Move.visualize cannot possibly be inconsistent, even if you make a mistake. Because we give you a lot of freedom, it is hard to specify precisely what it means to be consistent, but here is a rough specification:

For any move m, there should be an i and n such that m is equal to Move.parse (String.extract (Move.visualize m, i, SOME n)).

Be sure to unit-test your functions on simple states.
For testing, you can use the Unit signature from /comp/105/lib; the compile105-sml script should import it for you. No testing is required; at this point, you have enough ML experience to know how much effort you want to put into testing and how much value you can expect to get out.

Two-player games offer substantial scope for property-based testing. You might wish to test such properties as these:
- The initial player takes the first turn.
- Players take turns (not true of every game, but true of this one).
- If the game is over, no moves are possible.
- If a player has won, the game is over.
- If the game is not over, the outcome is NONE.
- The visualization of each state ends in a newline.
Such properties are best expressed as functions: usually a function from state to bool. Once you’ve written the function, you can test it using checkAssert with many different states.

Here’s an example function for “players take turns” (code not compiled or tested):
```
fun take_turns state =
  let val current = G.whoseturn state
      fun nextplayer  move = G.whoseturn (G.makemove state move)
      fun nextChanges move = nextplayer move <> current
  in  List.all nextChanges (G.legalmoves state)
  end
```
If I had any concerns about correctness, I would focus on testing properties to ensure that legalmoves, isOver, and outcome are all consistent.

Related reading: The lengthy description of the GAME signature, and the section on ML modules in the ML learning guide.

One more two-player game

The game below is available only for extra credit.

Connect 4

This is an adversary game played by two persons using 6 rods and 36 balls. Imagine the rods standing vertically, and each ball has a hole in it, so you can drop a ball onto a rod. The balls are divided in two equal groups marked X and O. The players take turns in making moves. A move for a player consists in sliding one of its own balls down a rod which is not full (the capacity of a rod is 6). The purpose is to obtain 4 balls of the same type adjacent on a horizontal, vertical or diagonal line. The game ends in a tie when all the rods are full and no player has won. We represent below the initial configuration of the game and a final state where X has won.

     | | | | | |                  | | | | | |
     | | | | | |                  | | | | | |
     | | | | | |                  | | | | | |
     | | | | | |                  O | | | | |
     | | | | | |                  O | O | | |
     | | | | | |                  O X X X X |
     -----------                  -----------

Our version uses 5 rods and connects 3, because otherwise the AGS takes too long. You can play /comp/105/bin/four.