CMPU-365, Spring 2013 Asmt. 5 ==> DUE: Monday, April 8 @ 3:00 p.m. There are three LISP files provided for this assignment: "a5.lisp" contains an implementation of the basics of a game of chess. It implements all of the basic moves, but does not implement the following somewhat more esoteric kinds of moves: "castling", "en passant" or "queening a pawn". It considers the game to be over only when a player's king has been captured. It does not consider the notions of being in "check" or "checkmate". It does not look at "stalemates" or any other kind of draws. "a5-plus.lisp" is a file into which you will put all the functions you need to define for this assignment (e.g., COMPUTE-MIN, COMPUTE-MAX, EVAL-FUNC). "a5-test.lisp" defines a function, called BUILD, for automating compiling, loading and testing. Begin by creating an asmt5 directory in your own account area. Download the three files listed above from the asmt5 website. CD into your asmt5 directory; open up aclemacs; start up a lisp session and then: (load "a5-test") (build "a5-plus") ;; <---- notice the string used here! no LISP extension! You're ready to go! -------------------------------------- Using the Chess Implementation -------------------------------------- You can use the implementation to play a game of chess with two people as follows. First, use an expression such as (setf g (init-game)) to create and initialize a new CHESS struct representing a new game of chess: CL-USER(37): (setf g (init-game)) 0 1 2 3 4 5 6 7 ------------------- 7: r n b q k b n r 6: p p p p p p p p 5: - - - - - - - - 4: - - - - - - - - 3: - - - - - - - - 2: - - - - - - - - 1: P P P P P P P P 0: R N B Q K B N R ------------------- White deadwood: NIL Black deadwood: NIL It is white's turn! Notice that each square is identified by its ROW and COLUMN. The "white" pieces are indicated by capital letters in rows 0 and 1. The "black" pieces are indicated by lower-case letters in rows 6 and 7. "Deadwood" refers to pieces that have already been captured. Moves are performed using the DO-MOVE! function. It takes the following inputs: GAME, CHECK-LEGAL?, R1, C1, R2 and C2. GAME is a CHESS struct (such as the one created above). CHECK-LEGAL? is a boolean flag which should be T when people are manually entering moves in the Interactions Window. (It should be NIL when performing moves during Minimax Search.) (R1,C1) specifies the starting square; (R2,C2) specifies the ending square. If there is a piece of the right color on the starting square and it is legal to move that piece to the ending square, then DO-MOVE! will do that move, destructively modifying the CHESS struct. Here are some sample calls to the DO-MOVE! function: (do-move! g t 1 4 3 4) (do-move! g t 6 4 4 4) (do-move! g t 0 6 2 5) After these three moves, the chess game looks like this: 0 1 2 3 4 5 6 7 ------------------- 7: r n b q k b n r 6: p p p p - p p p 5: - - - - - - - - 4: - - - - p - - - 3: - - - - P - - - 2: - - - - - N - - 1: P P P P - P P P 0: R N B Q K B - R ------------------- White deadwood: NIL Black deadwood: NIL It is black's turn! Note that the DO-MOVE! function pushes each move---represented as a list of the form (r1 c1 r2 c2 destn)---onto a "move history" (a field in the CHESS struct). This facilitates the "undoing" of moves using the UNDO-MOVE! function. The UNDO-MOVE! function takes a CHESS struct as its only input; it undoes the most recent move on its move history. Other functions that can be used by people playing the game include: LEGAL-MOVE? -- returns T if the specified move is legal LEGAL-MOVES -- returns a list of all the legal moves from the current game-state COMPUTE-MOVE -- returns a randomly selected legal move (this function is defined in "a5-plus.lisp".) Further implementation details follow the rest of these instructions. ------------------------------------------------- Implementing a better COMPUTE-MOVE function! ------------------------------------------------- Your job for this assignment is to implement a COMPUTE-MOVE function based on the techniques learned in class. In particular, it should carry out MINIMAX search with ALPHA-BETA pruning based on a STATIC-EVALUATION FUNCTION. ==> Your function definitions (e.g., COMPUTE-MOVE, EVAL-FUNC, etc.) will go into the file named "a5-plus.lisp". ==> Change the name of this file to something short that includes your initials. For example, mine might be "a5-plus-lh.lisp" since my initials are LH. You will need to use this filename when calling the BUILD function. For example, I would call BUILD like this: (build "a5-plus-lh"). Your compute-move function should return the best move it finds, but should also print out the root node's ALPHA value, as well as the number of moves it considered (i.e., the number of times it called DO-MOVE!). You can implement two helper functions, COMPUTE-MAX and COMPUTE-MIN, that handle the jobs of processing MAX and MIN nodes, respectively. Your functions should include a CURR-DEPTH input that indicates the current depth of the search. ==> You should include a GLOBAL parameter called *cutoff-depth* that specifies the depth at which the static evaluation function should be used to cut off further search. This global parameter will be used by the testing functions; so be sure you call it *cutoff-depth*. Your static evaluation function should be called EVAL-FUNC (in lower-case). ------------------------------ COMPUTE-MAX and COMPUTE-MIN ------------------------------ Pseudo code for COMPUTE-MAX is roughly: If the game is over, then return an appropriate NUMERICAL value (for "I won!" or "I lost!"). If you're at the cutoff depth, then use the static-evaluation function to determine the current node's NUMERICAL value. Otherwise, use LEGAL-MOVES to fetch a list of legal moves. For each move in that *list*, do the move, make a recursive call to COMPUTE-MIN (with appropriate inputs, of course), undo the move, see if alpha/beta values need to be updated, and see if pruning is possible. ==> Each "move" in the list of legal moves should be a 4-element list of the form (r1 c1 r2 c2) representing a move from the square (r1,c1) to the square (r2,c2). If MV is such a 4-element list, you can "do" the move using an expression such as (apply #'do-move! g nil mv). Notice that the CHECK-LEGAL? flag is given a value of NIL since we assume that moves returned by LEGAL-MOVES are indeed legal. ==> Note that COMPUTE-MAX is generally responsible for returning its ALPHA value. However, when the current depth is 0, COMPUTE-MAX is supposed to return the BEST MOVE FOUND SO FAR. How you distinguish these two behaviors is up to you. ==> In case of pruning, you may wish to use the RETURN-FROM special form. For example, (return-from compute-max 55) would immediately terminate the COMPUTE-MAX function call returning the value 55. The pseudo code for COMPUTE-MIN is similar except that it does not need to worry about the "best move found so far". -- HINT: Be sure that each call to DO-MOVE! has a matching call to UNDO-MOVE! Otherwise, they may get out of synch. For example: FOR EACH LEGAL MOVE...... DO that move! Call either COMPUTE-MIN or COMPUTE-MAX, as appropriate UNDO that move! ------------------------------- STATIC EVALUATION FUNCTION ------------------------------- Your static evaluation function should be called EVAL-FUNC (in lower case). It should be based on the following values of the different kinds of chess pieces. pawn: 100, knight: 300, bishop: 350, rook: 500, queen: 975, king: 100000 In case of a win or loss, use values such as 100000 and -100000. Make sure that these values are smaller in magnitude than your initial alpha/beta values. For example, you might use 10000000 and -10000000 as surrogates for infinity and negative infinity, respectively. ==> A straightforward way of implementing the EVAL-FUNC is to run through the list of *live* pieces for each player (i.e., the pieces that are still on the board), using positive values for the current player and negative values for the other player. However, this is not terribly efficient. A better way is to proceed as follows: *** Note: these changes should be made to the a5.lisp file *** Augment the PIECE struct to include a VALUE field. This field can be initialized when the PIECE is created. (See CREATE-SET-NEW-PIECE.) Augment the CHESS struct to include an EVAL-SUBTOTALS field (which is a vector containing two entries, one for white, one for black). The entries in this vector should both initially be 0. Whenever a piece is REMOVED from the board (i.e., during a *capture* move), decrement the corresponding EVAL-SUBTOTAL to reflect the removal of that piece. Whenever a piece is ADDED to the board (e.g., during initialization or during an UNDOING of a *capture* move), increment the corresponding EVAL-SUBTOTAL by the same amount. Fortunately for you, PUT-PIECE! and PULL-PIECE! are the only two functions that actually put a piece onto the board or pull a piece off of the board. Thus, you can do the needed incremental computations in their small bodies. With these changes in place, the body of EVAL-FUNC can be quite simple. (Remember that it matters whose turn it is!) ==> Any changes you make to a5.lisp should be *described* in comments near the top of your a5-plus.lisp file. --------------------------------- Testing --------------------------------- A good way to test your COMPUTE-MOVE function is to create a board situation where it is pretty obvious what one of the players should do. You can do this by using INIT-GAME to create a new game, and then make a few calls to DO-MOVE! where one player makes good moves and the other makes really bad moves. A call to compute-move (on behalf of the good player) should recommend taking advantage of the imbalance (e.g., by taking a piece). This is automated by the TEST-CHESS function defined in "a5-test.lisp". It takes a list of "moves" as its only input. It applies those moves to a new game of chess and then calls COMPUTE-MOVE on the resulting game state. See the functions, TEST-ONE, TEST-TWO and TEST-THREE, also in "a5-test.lisp". You should be able to comfortably play a game against your chess program using a depth of 6 or, if you are quite patient, a depth of 8. If you leave pieces hanging (i.e., unprotected) then your computer opponent should take advantage. ===> Note: Because we don't implement end-of-game issues well, some surprises can occur when there are only a few pieces on the board. But your computer should find a checkmate, even if it is not the *fastest* route to a win. ===> INTERACTIONS FILE: Start up a fresh lisp session. The compile and load your files using the BUILD function. The run the following expressions: (test-one) (test-two) (test-three) ============================= TO SUBMIT ============================= ELECTRONICALLY --> Directory containing all lisp files. An INTERACTIONS file as described above. PRINTOUTS --> (1) your "a5-plus.lisp" file (whose name includes your initials). (2) your INTERACTIONS file, as described above. ===> Do NOT turn in printouts of the a5.lisp or a5-test.lisp files!!! ------------------------------------------------------------------------------ Further details on the chess implementation (see comments in "a5.lisp" too) ------------------------------------------------------------------------------ ------------------------------------------------------------------ Global constants (e.g., for the players, piece types and so on) ------------------------------------------------------------------ ==> You probably won't need to use these directly. ------------------------------------------------------------------ Structs ------------------------------------------------------------------ PIECE .. represents a chess piece. Fields include: owner, type, row, col, live? CHESS .. represents a game of chess. Fields include: board, pieces, whose-turn?, move-history ------------------------------------------------------------------ Functions ------------------------------------------------------------------ INIT-GAME: Creates and initializes a CHESS struct corresponding to a new game of chess. Uses a helper, CREATE-SET-NEW-PIECE! PUT-PIECE!: Puts given piece onto the board. PULL-PIECE!: Takes given piece off of the board. TOGGLE-TURN!: Toggles the value of the WHOSE-TURN? field in the given CHESS struct. DO-MOVE!: Destructively performs the given move. Also, pushes move onto the MOVE-HISTORY (to facilitate undoing). UNDO-MOVE!: Destructively undoes the most recent move on the move history. LEGAL-MOVE?: Returns T if given move is legal. (Only used to check legality of moves entered by PEOPLE!) Uses PATH-CLEAR? helper function. GAME-OVER?: Returns T if the game is over. Only checks whether the current player's king is no longer on the board -- presumably because it was just captured on the most recent move. LEGAL-MOVES: Returns a list of all the legal moves for the current state of the chess game. Each move is represented as a 4-element list of the form, (r1 c1 r2 c2), representing a move from (R1,C1) to (R2,C2) on the board. COMPUTE-MOVE: Returns a move for the current player. As given, it simply returns a randomly selected legal move. (Not ideal!)