Project 5:
Games of Perfect Information

Due Wednesday, Nov 13th

For this sprint, you will need to be able to represent the board game in Haskell, make moves on the board game, and tell if a player has won the board game. You should have a variable defined that represents the initial game state. I should be able to play the game by loading your code in GHCI and calling functions you have defined.

This sprint should implement the following stories, each of which should be implemented on one or more branches. In total, you will add 6 stories (pieces of functionality) to your list of tasks to be finished by the sprint, called the backlog. I have included an Estimate of the relative difficulty of each story,  selected from the range 1,2,3,5,8. The Estimate considers the amount of work required, the logical difficulty of the story, and how much the story will effect the rest of the code base.  The difficulty of stories 2, 3, and 4 stories can vary significantly from game to game.

Story 1: Define data types or type aliases for a player, game state, move, and winner.  I suggest data types (or possibly type aliases) to represent:

• • • The state of the board Game, including both tangible and intangible components.

      • Tangible componentdris includes pieces and their locations. 

      • Intangible components may include whose turn it is, what the current bet in, or any other information not represented on the game board, but critical to game play.

    • A Move on the game board.

    • The Winner of a game.

    • You may have subtypes for these types as well. Be careful of using strings or integers where enumerated types would have more fidelity.

1. • Estimate: 8.
     
     

Story 2: Check who has won the game state, if anyone, with a function of type  Game -> Winner.

1. • Estimate: 5 requires story 1.
     
     

Story 3: Compute the result of making a legal move in a game state, with a function of type Game -> Move -> Game.

1. • Estimate: 2 requires story 1.
     
     

Story 4: Compute the legal moves from a game state, with a function of type Game -> [Move].

1. • Estimate: 3 requires story 1.
     
     

Story 5: Pretty-print a game into a string, with a function of type Game -> String. You should not override the Show typeclass. This is primarily for debugging purposes.

1. • Estimate: 2, requires story 1,  lower priority.
     
     

Story 6: All of these functions should consider possible errors or edge cases: what if there no winner, what if the move is not legal for the current game, etc. Use Maybe's or Either's appropriately.

1. • Estimate: 2, requires stories 1-4, for full credit.

Due Friday, Nov 22nd

There are two components for this sprint. In total, you will add 10 stories (pieces of functionality) to your list of tasks to be finished by the sprint, called the backlog. For this sprint, You can add these stories to the Issues tab on your GitHub page if you like.  Many of these stories include specific function names and type signatures: this is usually bad practice, but is useful for this course.

First, you will solve games by determining the optimal move for a player for a game state. We will add the following stories for solving the game to our backlog:

Story 7: If necessary, ensure that your game has bounded depth. For games that can cycle, such as checkers and chess, add a turn counter and tie the game when it hits zero.

• 1. • • Estimate: 2
         
         

Story 8: Refactor a Winner or Outcome type that represents a win or tie (but not an ongoing game).

• 1. • Have your "check who has won" function, from story 2, be of type  Game -> Maybe Winner.

       • Estimate: 1
         
         

Story 9: Write  a function whoWillWin :: Game -> Winner. 

• 1. • Considers every valid move, the resulting game state, and chooses the move with the best outcome for the current player. This will involve recursively searching through the game states that result from that move.  Think Scavenge!

       • Estimate: 8, requires story 8.
         
         

Story 10: Write a function bestMove :: Game -> Move that takes a Game and return the best Move. 

• 1. • Given a game state, you should  return a move that can force a win for the current player. Failing that, return a move that can force a tie for the current player. 

     • This is very similar to whoWillWin, but keeps track of what the first move was that could force that outcome. That means you should not use this function to write whoWillWin.

       • Estimate: 5, requires story 9.
         
         

Second, you will implement a simple interface. Your program should read a file name from standard input or an argument, solve the game, and print the winning move. This can be broken down into the following stories, which we will add to our backlog.

Story 11: Design simple text format that is easy for your program to read and write. It should probably be different  your "pretty show" from the first sprint.

• 1. • The input format should describe the board game in progress, and can look very similar to your internal representation. 

     • For instance, each square is a 0 for blank, 1 for player 1, or 2 for player 2. The current turn or other intangible components are given in the first (or last) few lines.

     • I suggest you use newlines, spaces, or other delimiters that afford the use of lines, words, and splitOn.

       • Estimate: 1
         
         

Story 12: Define a function readGame :: String -> Game that takes a string in your text format and returns the corresponding game.

• 1. • • You should design your format in story 5. to make this as easy as possible.

       • Estimate: 2, requires story 11
         
         

Story 13: Define a function showGame :: Game -> String that takes a game and turns it into a string in your text format.

• 1. • Ensure that readGame (showGame game) works for a variety of inputs!

       • Estimate: 1, requires story 11
         
         

Story 14: Define a series of IO actions to wrap around these functions, as well as bestMove, and define a main IO action. You will need to build four I/O actions: one each to read and write game states from a file, one that computes and prints the winning move, and a simple main action. 

• 1. • At least some of these actions will need to be in a Main module that imports your other module(s).

     • writeGame :: Game -> FilePath -> IO ()

     • loadGame :: FilePath -> IO Game 

     • putBestMove :: Game -> IO () that computes the best move and prints it to standard output. For full credit, also print the outcome that moves forces.

     • main :: IO (), which reads a file name from standard input or the arguments, loads the game, and prints the best move.

       • Estimate: 3, requires stories 10, 11, 12, and 13
         
         

Story 15: Define at least four files that can be read in by loadGame, representing games in various states of play. To be good test cases, you should have at least two games that are a maximum of three or four moves from the end, which that can be won or lost based on different choices. 

• Estimate: 1, requires story 11
  
  

There are also a couple of stories related to testing and error handling. In proper software development, these would be part of every story. For this course, we have split them into their own. Note story 6 is extended here.

Story 16: Define several test cases for each function: games to compute valid moves, who has won, who will win, and the best move from; games that should result from making moves on those games; and strings to convert to and from games. 

• 1. • You will need games that are only a few moves from the end. I suggest at least one each that is finished, one move, two moves, and four moves from the end.

     • Caveat: In this context, "from the end" means "worst case number of moves, no matter how either player plays." Even if there is a way to win in one move, you might end up searching every other move first - and taking those all the way to the end of the game.

       • Estimate: 3, lower priority.
         
         

Story 6: All functions should consider possible errors or edge cases. Return a Maybe Move, Maybe Game,  etc. as appropriate. 

• 1. • • Estimate: 2-5, depending on game, which functions needs to change, and familiarity with Maybe and do blocks. For full credit.