Your project is to write a command-line solver for a two-player game of perfect information. The game cannot contain randomness (via dice or card draws), or information that that is known to only one player. You may not use games of severely bounded depth, such as Tic-Tac-Toe. You may consider generalizations of those games, such as Connect 4. The following list contains examples. Game not from this list must be approved, to make sure they are suitable.
Github Classroom Link
Friday 11/12 - Milestone One deadline.
Monday 11/22 - Milestone Two deadline.
Tuesday 12/7 - Milestone Three deadline.
The project is divided into three milestones. There will be a pause after each milestone to provide feedback. Objectives for the project include:
Functionality: your code should work, and satisfy the specification for each milestone.
Communicating computation: working in a group requires that you be able to communicate computational concepts. You should ensure everyone in the group understands the code well enough to work on it.
Abstraction and decomposition: you must decide how to decompose your problem, how to represent your data, what functions to define, and what types to give those functions. “It works” is a poor justification for such a decision. You should divide your types and functions on logical lines that naturally fit the structure of the problem you are solving. Towards the second milestone you should consider dividing the project into separate modules.
For this milestone, 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. I suggest data types (or possibly type aliases) to represent:
The state of the board game, including both tangible and intangible components.
Tangible components 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.
I suggest functions that compute:
The winner of a game state.
The result of making a move on a game state.
What moves are legal for a game state.
A pretty show function for a game state, to ease debugging.
Full Credit: 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.
For this milestone, you will solve games by determining the optimal move for a player for a game state. Given a game state, search for 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 will involve recursively searching through the game states that result from that move. I suggest:
Refactoring an Outcome type that represents a win or tie
Have your "who has won" function returns a Maybe Outcome:
Write a function "who will win" that returns an Outcome
This function should considers every valid move, the resulting game state, and chooses the move with the best outcome. Think Scavenge!
Write a function that takes a game and return the best Move
Further, you will implement a simple interface. You will need to build three I/O actions: one each to read and write game states from a file, and one that computes and prints the winning move. The input format should describe the board game in progress, and be designed to be simple for your program to read. 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 the following IO functions:
readGame :: String -> Game
showGame :: Game -> String
writeGame :: Game -> FilePath -> IO ()
loadGame :: FilePath -> IO Game
putWinner :: Game -> IO ()
Then implement a simple command-line interface. Your input will be the name of a file describing the board game in progress, and the output will be the best move the current player can make.
Full Credit: All of these functions should consider possible errors or edge cases. Return a Maybe Move or Maybe Game as appropriate.
For this milestone, you will implement a cut-off depth in your search. After searching through a certain number of consecutive moves, you will evaluate the board state and determine how good it is. Your evaluation function should return a positive value if the board is good for player 1, and a negative value if the board is good for player 2. Make sure that ‘winning the game’ is the best possible board state, and ‘losing the game’ is the worst. You may want to find a way to stop searching when you find the best state (winning) for the current player. You will then search for a move that forces the game to the best board state within the cut-off depth.
Further, you will have to implement a command-line interface, supporting the following flags. For full credit, use GetOpt.
Default Input: A file describing the board game in progress.
Default Output: A good move. By default, use a reasonable cutoff depth between 3 and 8, and output just the move.
Full-Credit Flags:
-h, --help Print out a help message and quit the program.
-w, --winner Print out the best move, using an exhaustive search (no cut-off depth).
-d num, --depth num Use <num> as a cutoff depth, instead of your default.
-v, --verbose Output both the move and a description of how good it is: win, lose, tie, or a rating.
Braggadocios Flags:
-i, --interactive Start a new game and play against the computer. Make sure this is compatible with the -d
flag.
-m move, --move move Make <move> and print out the resulting board, in the input format, to stdout. The move
should be 1-indexed. If a move requires multiple values, the move will be a tuple of
numbers separated by a comma with no space.