Checkers Assignment (cpsc449 Fall 2021)
Due: 29th October (Moves and applying moves) 5th November (ai)
English draughts

English draughts or checkers is described here it is played on an 8 x 8 checkered board starting with the "player" (who starts) having 12 black "men" (or "pawns") at his end of the board and the "opponent" having 12 red "men" at his end.  The game is played on the "black" squares of the checkered board with alternating moves.  "Men" can only move diagonally forward.  When "men" are crowned -- achieved by reaching the other end of the board -- they become "kings".  "Kings" can move diagonally forward and backward.  A simple move is a single step diagonally by one piece (man or king) provided the position moved into is vacant.  A capture or jump move is when a player (resp. opponent) piece is diagonally adjacent to an opponent (resp. player) piece and the position diagonally behind the opponent (resp. player) piece is vacant: a jump move removes the opponent (resp. player) piece from the board (a capture) and occupies the vacant position behind the piece.  Both players must do a jump move if one is available.  Furthermore once a piece makes a jump it must completely exhaust all the jumps available to it: this may involve multiple jumps (which are allowed to change diagonal directions).

PLEASE NOTE: We are using a (Calgary) variant of the English rules which allows a pawn, which reaches the end row to become a king, to continue jumping (in the same turn) as a king.  Furthermore, to stop endless games a player cannot make a move which would repeat a state.   This last is a hard rule for human players to keep track of .... but is easily checked by computer: although it is somewhat challenging  to program it (see below in implementation notes) ...

The objective of the game -- that is the winning conditions -- is to arrange that there is no move available to the opponent.  This can be achieved either by capturing all opponent pieces or by blocking every possible move that the opponent can make.  So for example, the most subtle case is a player winning by ensuring the only moves available would cause a repeated state ....

The assignment is to:
  1. Write a program to check for all the legal moves a player can make (we will test this).
  2. Create an AI which can play the game!  It probably will be possible to create one which beats most human players! (Bonus point available for this)

These tasks are broken down for you below.

There is a very simple front-end which should work in all Haskell implementations in Main.hs.  There is also a fancy front-end using "brick", "stack", and "cabal" developed by Ben MacAdam which is available here (superseded version here) -- only if you are very keen/know what you are doing should you consider download this (it needs a unix platform).  Niran Pon has cloned the repository here:  he has removed the dependency on the Haskell version  (this involves changing " base >=4.13 && < 4.14" to " base" everywhere in the cabal files) and has some work arounds for windows users ( for the Windows users, checkers-brick depends on VTE a Unix library, thus this dependency must be removed). 

Once you have a frontend (and survived these operating system level dependencies if you go for the fancy frontend), you need the datatype for a game state in Types.hs:

data GameState =
  GameState { blackPieces :: [Coord]
                     , redPieces :: [Coord]
                     , blackKings :: [Coord]
                     , redKings :: [Coord]
                     , status :: Status
                     , message :: String
                     , history :: Moves }

The "status" field tells you whether it is red or black to play, while the "message" field allows you to display information to the user(s) -- the "message" field is very useful while debugging!  The pieces (or pawns) and the kings positions are indicated by two dimensional coordinates starting at zero: the first coordinate counts across the board from left to right, the second coordinate counts down the board.  The red player starts at the bottom of the board (moving up) while the black player starts at the top of the board (moving down).

The initial game state has all the pieces in their home position and red gets first move.  There are four ways provided to play the game:

  1. Human (red) versus human (black): this is useful at the stage when you are sorting how to determine legal moves. 
  2. Human (red) versus ai (black): this is useful for determining whether your ai is any good!  With a bit of luck you should be able to surprise yourself.
  3. Ai (red) versus Human (black).
  4. Ai (red) versus ai (black): this is useful for tournament and comparing designs of the ai (and in particular the heuristic functions).
You must modify "main.hs" to create your checkers player.   (If you download the front end you should get a folder "src": in this case "main.hs" is in the "src" folder.)  To developing your program and test it you will need "Types.hs": it contains all the (basic) datatypes you will need ...

Below is a description of the steps you have to go through to develop a checkers program ...

==================================================================

Finding legal moves

Your first job is to, given a state of the game, find all the legal moves which can be made from that state of the game.   To test this on gradescope you will need to package this into a module called "Checkers.Moves" (which will import "Checkers.Types") in the file "Moves.hs" which you can submit to gradescope.  This module should export a function:

moves::GameState -> (SMorJM [Move])

Here is the template for "Moves.hs".

This function breaks down the moves into the simple (non-jump) moves and the jump moves.  A move is specified by a list of coordinates, [PorK Coord], which indicate the sequence of places where the piece lands in its move and whether the piece is a Pawn or a King (this information is useful in checking repeated moves).

To program this one breaks the moves into two parts the "jump_moves" and the "simple_moves".    Recall that if a jump move is available then the player -- whose turn it is -- must make a jump.  Only if there are no jumps can he make a simple move.  A simple move for a piece (pawn) is a diagonal one square move forward (to an empty position) while a king can move one square backward or forward diagonally.  Thus a simple move is specified by two coordinates, [start,end].  A jump move is specified by a list of coodinates [start,landing1,landing2,...,end] where each sequential pair is a two step diagonal move which "captures" or "jumps over" a position occupied by an opponent piece which is removed from the board.  The basic jump captures only one piece: more interesting are the mutiple jump moves.  For a king these can literally go in circles as a king can jump diagonally forward or backward.  A piece (pawn), however, must always jump diagonally forward (although the direction can change).   A complication (Calgary rules) is that half way through a jump sequence a piece (or pawn) can become a king by reaching the opposite end so the jumps can then continue in any direction!

You should develop two functions:

simple_moves::GameState -> [Move]    
and jump_moves::GameState -> [Move]
which combine into 

            moves::GameState -> (SMorJM [Move])
            moves st | jumpmoves /= [] = JM (jump_moves st)
                           | simplemoves /= [] = SM (simple_moves st)
                           | otherwise = EndM

Your next task is to program the required function:

apply_move:: Move -> GameState -> GameState

I suggest you put this in a module "Checkers.ApplyMove" (in the file "ApplyMove.hs") you should import "Checkers.Moves" and "Checkers.Types" one can then see whether the move is in the set of all possible legal moves you have calculated.  If it is you can go ahead and make the move: be careful to turn pieces (pawns) into kings when they reach the far end.   If the move is not legal, you can modify the "message" field of the state to indicate that an illegal move has been made.   Don't forget you can use this field for debugging as well ...

Once you have an apply_move function you can try out the program as a human-human interaction.  It is important that you thoroughly test this stage of the development as if you get the moves wrong everything will be wonky after that!!!

You can check this on gradescope:  to do this you have to upload both "Moves.hs" and "ApplyMove.hs"
(here is a template for ApplyMove.hs).

This stage should involve about 200 lines of Haskell code. 

This stage requires some careful planning: you must be clear on how you are going to break down the various tasks before you launch into programming them!!!  It is worth discussing this in the labs ...

Programming the AI

The two basic techniques are to use a "heuristic" function and "min-max search".   Let us start with a really simple heuristic function  (see more below on this). You can package this into a module "Heuristic" if you wish.  You will need two functions:

black_heuristic:: GameState -> Int                     red_heuristic::GameState -> Int

The first gives a heuristic evaluation of the game state from the perspective of the the black player.  For example one may take the difference in the number of pieces:
#blackPieces-#redPieces+2*(#blackKings-#redKings).  
Similarly by swapping black and red one may obtain a red heuristic.  Using this you must program a min-max search.  For the tournament it will be useful to have this in a module: you could initially call  "ABsearch".  This involves "looking ahead" a number of moves by searching the (implicit) game tree formed by considering your moves, the opponent responses, your responses, etc to some specified depth (called a "ply") at which you use the heuristic function to determine how good the state reached is for the player you are representing.  One then evaluates the tree with your player trying to maximize the value of his move while the opponent tries to minimize the value of the move.  This is why the game tree is sometimes called a "min-max tree"!

A basic min-max search, however, is rather inefficient and there is a more powerful technique which uses \alpha-\beta pruning (see here and also the class notes and here for an animated version): this allows the program to avoid searching states which will not affect the outcome.   Using \alpha-\beta pruning is valuable as it increases the depth/ply you can search by about a factor of roughly two: this can dramatically improve the performance of the ai!!

It is useful to make the number of "ply" look-ahead a parameter of your program so that you can experiment with how effective and how long your ai takes given the depth of look-ahead!  A basic program should be able to look-ahead about 6 moves and take less than 10 seconds.   A technique you may want to add -- when you have a basic ai going -- is called "waiting for quiescence": the idea is that before using the heuristic one should wait for the "jump" moves to be over as these greatly effect the value of a position being evaluated.

A basic min-max search with \alpha-\beta pruning should only take only about 40 lines of code ... but the code is quite sophisticated so you must understand what it is doing!   Again test your code carefully.  Once you have a basic system you can start adding all sorts of improvements!!

Heuristics

The last step in developing an ai is to consider more sophisticated heuristics.  Something to consider is that what is important is actually different at the different  stages of the game! 

Thus it is possible to have quite sophisticated heuristics ...

!GOOD LUCK!


Stage I: calculating the possible moves

Here you need to develop the functions
moves::GameState -> SMorJM [Move]
apply_move::Move ->  GameState -> GameState
We have published some test game states to help you to determine whether you are finding all the possible moves (see below). You should also try playing some (human/human) checkers games with these functions.

Your submission for Stage I will be in two parts and to gradescope ...

(A) Calculating the legal moves:

This should be a Haskell file called Moves.hs containing the module Checkers.Moves.  You can submit this to gradescope so that we can test that you have the "moves" function  working correctly.  You should import Checkers.Types.hs.  This file must be runnable with vanilla ghci (i.e. no fancy brick interface etc.).    Make sure that you document your code.

To see some configurations being tested take a peek at testcases.pdf. 

(B) Applying legal moves

The "apply_move" function needs to be tested.  We will also set up gradescope automatic testing for this!

(All the non-bonus of the marks for the assignment are available if you reach this stage)

Stage II: Minmax search and \alpha-\beta pruning

Here you should use a very basic heuristic and implement a minmax search to a ply which you can control.
Your aim from this stage is to produce:
red_ai:: GameState -> Move
black_ai::GameState -> Move
Stage III: heuristics

Finally one can try to make your heuristic more complicated (e.g. to account for the different stages of the game).

Stage IV: creating a module

Finally you need to package up your work for the submission for part II. 

This involves creating a module containing your program: this is so we can easily use your code in the tournament and testing it.   We would like you to create a module named Checkers followed by your first and last name (so we can disambiguate the programs) which exports the basic playing components.  For example I would create:
module Checkers.RobinCockett (moves, apply_move, red_ai, black_ai)
You will need to import this module into main.   If you get to this stage you will have a tournament ready program!!

At this stage you need to decide the ply (depth of search) you are going to implement.

Tournament rules:

Each lab. section can send up TWO programs for the class competition (5 bonus marks if you get sent up: 3 bonus marks for being in the lab competition and lasting a full game  without crashing or making an illegal move).  Lab. member are allowed to tweak the program prior to the class competition.

Each competition will consist of a single game with the initial red player determined by a coin toss: 
     (1) If either ai makes an illegal move the game is immediately forfeit.
     (2) If an ai takes more than 10 seconds on two consecutive moves it will forfeit the game!
     (3) If an ai takes more than 20 seconds on any move it will forfeit the game immediately!



===================================================================================================
IMPLEMENTATION NOTES:
===================================================================================================

These are fairly detailed implementation notes for stage I:

Ultimately you need to write the program in main.hs in the src folder ... but in order to test it you may want to have a light weight version which imports the datatypes from Types.hs.
What I suggest is that you pick up the file Types.hs which contains all the datatypes needed.  You can place this in your working directory (perhaps the src directory):

For ease of debugging it may be useful to write a moves module which you can put in a file "Moves.hs" (in the same diretory).  You can load this into ghci intepreter for easy debugging.  

=============================
<Moves.hs>

module Checkers.Moves where

import Checkers.Types


-------------ADD YOUR PROGRAM FOR MOVES-------------
--------------------BELOW HERE----------------------

==============================
If you arrange things like this we can then pick up your moves file and easily test it by importing your moves module into our tests on gradescope

Moves:

As mentioned above your first aim is to get the simple moves sorted out various possibilities must be covered depending on the status of the game:

simple_moves:: GameState -> [Move]
simple_moves st
                | _status st == Red
                    = (simpleKing (redKings st))++(simplePiece (redPieces st))
                | _status st == Black
                    = (simpleKing (blackKings st))++ (simplePiece (blackPieces st))
                | otherwise = [] 
 where ...

One then has to program the simple moves in the context of the "where".  For example to get the simple moves for the pieces one might use a list comprehension roughly like (note PorK data is missing!):

    simplePiece xs =
                      [ [(x,y),(x',y')]
                      | (x,y) <- xs
                      , (x',y') <- let y'=y+dir in [(x+1,y'),(x-1,y')]
                      , notoccupied (x',y') st && onboard (x',y')]

where "dir" is the direction of the player (either Red or Black determined by (status st) ) involved.

The form of the moves function involves testing whether there are jump moves: recall if there are jump moves they must be taken: one only does a simple move when there are no jumps.  This suggests a "moves" function something like:

moves st = (simplemoves st,jumpmoves st)
 

The first challenge of this first stage is to get the jump moves programmed.  Below is an incomplete version for jumping kings (there is no PorK data).  It is very similar for pieces/pawns (recall that they can turn into kings).

     jumpKing xs = [(x,y):ys | (x,y) <- xs, ys <- jumpKing' (x,y) [] (x,y)]
     jumpKing' start rem (x,y) =
                   [ (x'',y''):ys
                   | ((x',y'),(x'',y'')) <- [((x+1,y+1),(x+2,y+2)),((x-1,y+1),(x-2,y+2)),((x+1,y-1),(x+2,y-2)),((x-1,y-1),(x-2,y-2))]
                   , not (member (x',y') rem) && opponent_occupied (x',y') st && (start==(x'',y'') & notoccupied (x'',y'') st && onboard (x'',y'')
                   , ys <- jump_over (jumpKing' start ((x',y'):rem) (x'',y'')) ]

      jump_over [] = [[]]
      jumpover z = z

The complication is that as one jumps pieces they get removed from the board and one must avoid jumping them again (otherwise you can go round in circles!).  Also your starting position is no longer occupied so it is possible to jump through that.  For this reason in defining the jumps recursively one must pass in the positions (in "rem") which have already been jumped over and the start position ("start").   This allows the appropriate checks for validity of the jump.  There is one additional subtelty: when the jumps are over one must return not just an empty list of jumps (signifying there are none) but rather a list containing the empty list in order to smoothly terminate the recursive calling of the jumps.  This is the purpose of "jump_over" function.

This should get you through generating the possible moves from a state!!!!!

Repeated states:

The wrinkle I have not addressed (this is the challenging part of the whole assignment and should get you head scratching!!!)  is using the history to tell whether one has repeated a state.  As pawn moves and jumps are irreversible the only moves one has to worry about are the simple king moves.  In this case you are looking for a repetition of the current state: this means looking back in the moves to see whether there is an earlier stage at which each piece was in exactly the same spot or, more challengingly, the black and red kings are in some permutation of their original position.  So there must have been a sequence of history moves in which, for each king, there is a series of simple king moves which take the colored kings back to the same place or (more generally) a permutation of those places.  

To determine this is one uses the history to trace where each piece came from.  To program this keep two lists -- black moves and red moves -- of "movement pairs" (a start position and a current position): these lists will initially be empty. For each move in the history update the appropriate lists by altering the start position of the piece being moved back to its earlier start position.  When the appropriate list is empty -- or the piece has not been moved before -- this will amount to adding the move itself to that appropriate list.  Note that all you need to know is the positions of the pieces as each piece (red or black) occupies a unique position and a move gives a before and after position.   Furthermore, you need not keep track of pieces which have not moved.  This means one can eliminate movement pairs that record no movement.  Furthermore you can eliminate any cycles which occur in either of these lists.  If at some stage in the history (of simple king moves) you discover each piece came from where it is currently -- which means the movement list is empty again -- you have repeated a state.   Similarly, if you reach a state in which every move (in each list) is in a cycle so can be removed then you have a repeated state.

In programming this it may be worth first not worrying initially about removing permutations from the list so that you check for non-repeating positions which allow similarly colored pieces to be permuted.   After mastering this add removing cycles ...

Apply_moves:

Your next task is to apply the moves to a state!  Again for debugging you may like to start by developing this in your "Moves" module in your working directory.  Eventually however you will want to import "Moves"  into the "ApplyMove" module.  

In order to use the front end in "Main" you must import "Moves" and "ApplyMove" and call:

main =  frontend $ GameConfig { engine = apply_move
                                                     , blackMove = Human
                                                     , redMove = Human
                                                     , state = initialGameState }

This will allow you to interactively play checkers using the arrow keys, space bar (to enter a position) and return (to return a move). 

Of course, the apply move function not only does the move but checks that it is valid.  This can be done by just checking whether it is in the list of legal moves:

apply_move mv st | inmoves mv (moves st) = ....
                              | otherwise = st{message = "Illegal move!!"}

The last is record syntax for modifying a field in a record and it produces a GameState which is the same as "st" except the message has been changed.

When the code is legal one must separate out the cases: is it a simple move or a jump move?  What are you moving?

Here a code sample for making a simple red king move:

make_simple_move [start,end] st
       | _status st == Red && member start (redKings st)
               = st{redKings = replace start end (redKings st)
                     , status = change_player st
                     , message = ""}
       | _status st == Black && member start (blackKings st)
               = ...

For jump moves the code is recursive but not very different.  Here is a code snippet  for a red king jump

make_jump_move (start:(next:rest)) st
       | _status st == Red && member start (redKings st)
                = make_jump_move (next:rest)
                            (st{blackKings = remove (jumped start next) (blackKings st)
                               , blackPieces = remove (jumped start next) (blackPieces st)
                               , redKings = next:(remove start (redKings st))
                               , message = ""})
       | _status st == Black && member start (blackKings st)
                = ...

This should allow one to get through to having an interactive board in which human can play human.

You next task is to get the "ai" to play one of the players ...


===================================================================================================
GETTING STACK:
===================================================================================================

Currently you don't need stack .... so ignore this section!!


This system does work on unix based personal computers:

(1) For the Mac system you need Xcode tools: in the command line "xcode-select --install".  To then install stack go to "haskellstack.org" and follow the unix operating system instructions.  Then go to the git repository "github.com/benjamin-macadam/Haskell-Checkers-Frontend" and download the repository.

(2) If you have a Linux/Fedora/..  system goto "haskellstack.org" and follow the unix operating system instructions. 

N.B. You may need to install the "libtinfo" (terminal info) library.  On ubuntu you say "sudo apt install libtinfo-dev".

Then go to the git repository "github.com/benjamin-macadam/Haskell-Checkers-Frontend" and download the repository.

For Windows systems:

(a) Lower than Windows 10: goto https://www.virtualbox.org/ then install VirtualBox (it is free).  Then install ubuntu under the VirtualBox environment (you are guided through the installation by VirtualBox).  Open a terminal inside ubuntu ... then proceed as for the unix system.  Make sure you have allocated enough disc space ...

(b) For Windows 10 or more you need install a unix emulator. Here is our recommendation: pick up ubuntu (for wsl2 -- Windows Subsystem for Linux) from the window app store (it is free): here is a link to how to install "https://docs.microsoft.com/en-us/windows/wsl/install-win10".

Once you have installed ubuntu, click the windows key and type "ubuntu": this should bring up a ubuntu shell.  You can now follow the instructions for unix described above, although everything now has to be done in the ubuntu shell.  Don't  forget that you need the "libtinfo" library ...

Your "normal" windows files are in /mnt/c.   You need to download the repository into /home/username ...

There is a nice editor for working with wsl called "Vscode" ....

Please note: The downloads are rather slow so this can take some time!!!