Description
Part 1: The Game
Crusher is played on a hexagonal board with N hexes to a side. Each player starts with
2N‐1 pieces arranged in two rows at opposite ends of the board. Here’s an example of an
initial Crusher board where N = 3:
W W W
W W
B B
B B B
White always begins at the top of the board, and white always makes the first move.
In Crusher, players alternate moves and try to win by obliterating the other player’s pieces.
A piece can move in one of two ways:
First, a piece can slide to any one of six adjacent spaces so long as the adjacent space is
empty. So in the diagram below, the black piece can slide to any of the spaces indicated by
a “*”:
W W W
* *
* B *
* *
B B B
The other type of movement is a leap. A piece can leap over an adjacent piece of the same
color in any of six directions. The space that the piece leaps to may be empty, or it may be
occupied by an opponent’s piece. If the space is occupied by an opponent’s piece, that piece
is removed from the game. Thus leaping is not only a means of movement, but it’s the only
means of capturing an opponent’s piece. Also, note that a player must line up two pieces in
order to capture an opponent’s piece. Here’s an example of leaping. Let’s say the board
looks like this:
W W
W
B
B B
If it’s now black’s turn, black has two possible leaps available (in addition to several slides).
Black could leap like this and crush the white piece (hence the name Crusher):
W W
B
B
B
This would seem to be a pretty good move for black, as it results in a win for black. The
other possible leap shows black running away for no obvious reason:
W W
W
B B
B
Note that a piece may not leap over more than one piece. Oh, there’s one more constraint
on movement. No player may make a move that results in a board configuration that has
occurred previously in the game. This constraint prevents the “infinite cha‐cha” where one
player moves forward, the other player moves forward, the first player moves back, the
other player moves back, the first player moves forward, and so on. It will be easy for you
to prevent this sort of annoying behavior by checking the history list of moves that will be
passed to your program.
There are two ways for a player to win this game (the only ways for the game to end):
1. a player wins when he or she has removed N (i.e., more than half) of the opponent’s
pieces from the board.
2. A player wins if it’s the opponent’s turn and the opponent can’t make a legal move.
Part 2: Your Task
You are to construct a Haskell function called “crusher” (along with all the necessary
supporting functions) which takes as input 1) a representation of the state of a Crusher
game (i.e., a board position), 2) an indication as to which player is to move next, and 3) an
integer representing the number of moves to look ahead, (As you read on, you’ll find that
the current board position is actually the first element on a list containing all the boards or
states that the game has passed through, from the initial board to the most recent board.)
4) an integer representing N (the number of hexes or spaces along one side of the board).
This function determines the next best move that the designated player can make from that
given board position. That move should be represented as a Crusher board position in the
same format that was used for the input board position. That new board position is then
cons’ed onto the history list of boards that was passed as an argument to your function, and
that updated list is the value returned by the function.
Your function must select the next best move by using MiniMax search (Tuesday, Nov 24th
lecture). You will need to devise a static board evaluation function to embody the strategy
you want your Crusher program to employ, and you’ll need to construct the necessary
move generation capability.
Here’s an example of how your Crusher function will be called. Assume that we want your
function to make the very first move in a game of Crusher, and that N is set to 3. As we
noted above, that beginning board would look like this:
W W W
W W
B B
B B B
Your Crusher function must then be ready to accept exactly four parameters when called.
The sample function call explains what goes where in the argument list:
*Main> crusher [“WWWWWBBBBB”] ‘W’ 2 3
^ ^ ^ ^
| | | |
The first argument is a list of strings. | | |
That list represents a history of the | | |
game, board by board. The first string | | |
on this list will be the most recent board. | | |
The last element of the list will be the | | |
initial board before either player has | | |
moved. This history list is initialized | | |
as shown above. Each sublist is a list | | |
of characters which can be either ‘W’, ‘B’, | | |
or ‘’. Each of these elements represents | | |
a space on the board. The first n elements | | |
are the first or “top” row (left to | | |
right), the next n+1 elements are the | | |
second row, and so on. (The number of | | |
spaces or hexes in each row increases | | |
by 1 to a maximum of 2n1 and then | | |
decreases by 1 in each of the following | | |
rows until the bottom row, which contains | | |
n hexes or spaces. | | |
| | |
The second argument is always ‘W’ or ‘B’, + | |
to indicate whether your function is playing | |
the side of the white pieces or the side of | |
the black pieces. There will never be any | |
other colour used. | |
| |
The third argument is an integer to indicate + |
how many moves ahead your minimax search is to |
look ahead. Your function had better not look |
any further than that. |
|
The fourth argument is an integer representing +
N, the dimensions of the board. The value 3
passed here says that this board has 3 spaces or hexes
along each of its six sides.
This function should then return the next best move, according to your search function and
static board evaluator, cons’ed to the front of the list of game boards that was originally
passed to your function as the first argumment. So, in this case, the function might return:
[“WWWWWBBBBB”, “WWWWWBBBBB”]
(or some other board in this same format). The new first element of this history list
represents the game board immediately after the function moves a piece. That game board
corresponds to the following diagram:
W W
W W
W
B B
B B B
Final Notes:
1) A static board evaluation function is exactly that ‐‐ static. It doesn’t search ahead. Ever.
2) You can convert our board representation to anything you want, just as long as when we
talk to your function or it talks to us, your function communicates with us using our
representation.
3) Program early and often. The board evaluator is easy. The rest is much more difficult.
Get the board evaluator out of the way in a hurry, then start working on the rest of it as
soon as you can. Get everything else working, then go back and tune your evaluator.
4) Before writing any code, play the game a few times.
5) If you are in a one or two person group, the rest of this document does not apply to you.
Do not try to implement the interactive part ‐‐ there is no bonus in doing extra work. You
can do so regardless, but if you’re not a 3‐person group only your crusher function will be
graded.
Part 3: HumanComputer Interface (for three person groups only)
[This section requires that you know about performing I/O actions in Haskell. Read
Chapter 8 for this topic or lecture slides from Thursday Nov 26th (to be uploaded)]
After implementing the crusher function described above, you need to implement the
interactive interface with the human player.
The user will initiate the game by calling a function called “main”. This function will read
from the user a number N and a player (‘W’ or ‘B’) which the user would like to play and
initiate the board with the given size. Assume White always plays first (whether it’s the
user or the computer).
Your program needs to be able to read the user’s moves from input, test them for legality
and apply them. A simple way to do this would be to number each place according to their
order in the board representation (as passed to the crusher function). The user will then
give two consecutive numbers, n1 and n2, which will translate to: move the piece in n1 to
n2. If the move is not legal your program should produce an error and prompt the user
again, until a legal move is given. The legality of the move should be decided based on the
constraints explained in Part 1 of this document. Once a move is accepted, your program
should apply it to the board and print out the new board configuration. After a move by
either player the new board should be printed.
Your program should also declare when the game is over and who the winner is.
Here’s a sample interaction at the beginning of the game (your program doesn’t have to
produce the exact same messages as this one):
ghci> main
N is:
3 (entered by the user)
Colour is:
W (entered by the user)
Initial board:
W W W
W W
B B
B B B
Enter next move:
from: 5 (entered by the user)
to: 10 (entered by the user)
The result:
W W W
W
W
B B
B B B
my move:
W W W
W
B
B B
B B
Enter next move:
…
And when the game is over:
my move:
B B
B
B
Game Over: Black is the Winner!
You can change or simply this interaction however you wish as long as it is possible for the
user to easily follow the flow of the game.
To sum up, these are the main components you will need to implement for this part:
0. Top‐level initiation.
1. An interactive loop. You can read section 8.6 of your textbook, p. 191, for inspiration.
2. Conversion of board between the human readable format (exactly as shown in examples,
using 3 blank spaces between consecutive pieces and one line break between two rows)
and the machine readable string representation (the one used by the crusher function)
3. Conversion of the user’s input values into usable parameters for your program as well as
validating them.
4. Miscellaneous tasks related to communication with the user, such as: printing messages
to the user and reading her inputs, handling error cases, handling the end of the game.
Note 1: It’s okay to hard‐code the value of the third argument of Crusher when working in
the interactive mode. You can also choose to read it from the user’s input at the time of
initialization.
Note 2: To test your full program you may find it easier to compile your program and run it
independently, as opposed to running it interactively in GHCi. If you’d like to do so, first,
make sure your top level function is called main and is an IO type and your module is called
‘Main’ (or don’t have a module name declaration at all); then simply compile and run as
explained in this guide:
https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/using‐ghc.html#idp85
50064