CS 2360 Fall 1995 Homework Assignments 6 and 7 Assignment 6 is due no later than 8:00am, Monday, November 13, 1995 Assignment 7 is due no later than 8:00am, Monday, November 20, 1995 Modern seega is a variant of a board game which has been played in Egypt for centuries. Here are the rules: Modern seega is played on a 3 x 3 chessboard. The two players face each other across the board. Each player begins with three pieces, placed one to a square in each of the three squares nearest that player. One player has white pieces, while the other player has black pieces. The player with the white pieces makes the first move. A player may choose to move one of his or her pieces according to the following constraints: A piece may be moved one or two squares in any direction so long as the piece does not pass over or stop on an occupied square. A piece's direction must not change in mid-move. The players alternate moving pieces until one of the players wins. A player wins when: All three of the player's pieces are lined up in a single row, column, or diagonal with no intervening spaces. However, the line cannot be on the row on which those pieces were placed at the beginning of the game. Modern seega is intended to be played with only six pieces on a 3 x 3 board. Now, however, we are extending the definition of modern seega to include any similar game involving n white pieces, n black pieces, and a n x n board (where n is greater than or equal to three). A player then wins when all n of his or her pieces are lined up in a straight line, on any row, column, or diagonal other than the row on which those pieces began the game. Over the next two weeks, you are to construct a Common LISP function which takes as input a representation of the state of a modern seega game (i.e., a board position), an indication as to which player is to move next, and an integer representing the number of moves to look ahead. (There's one other parameter too; see below.) This function returns as output the best next move that the designated player can make from that given board position. The output should be represented as a modern seega board position in the same format that was used for the input board position. Your function must select the best next move by using MiniMax search. The use of Alpha-Beta pruning is optional. You will need to devise a static board evaluation function; feel free to use the one that was given in class or supply a better or more interesting one. Your function should also be able to print a trace of its behavior as it carries out the search. This trace should show at the very least what boards or nodes are being searched and what values are being propagated upwards. You should be able to turn this printing on or off via an additional parameter to the function. Assume for now that the name of your top-level function is "seega-geek". (Please use a different name; be creative.) Your function must then be ready to accept exactly four parameters when called. The sample function call explains what goes where in the argument list: (seega-geek '((w w w)(nil nil nil)(b b b)) 'w 2 nil) ^ ^ ^ ^ | | | | The first argument is an n-element list, | | | and each of these elements represents | | | a row of the board. The first element | | | is the first or "top" row, the second | | | element is the next row, and so on. | | | Each of these elements is itself an | | | n-element list. The elements of these | | | lists are either w to indicate a white | | | piece on that square, b to indicate a | | | black piece, or nil to indiate an empty | | | square. The leftmost element in one of | | | these nested lists represents the leftmost | | | square in the row represented by that | | | list, and so on. | | | | | | The second argument will always be '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 color of pieces. | | | | 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 and last argument is the flag to turn + the trace function off or on. Nil means don't print the trace, and a non-nil value here means that the trace should be displayed. This function should then return the next best move, according to your search function and static board evaluator. So, in this case, the function might return: ((w nil w)(nil w nil)(b b b)) or some other board in this same format. The deliverables for this assignment are due in two parts. First, we'd like to see your static board evaluation function by 8:00am, Monday, November 13. You can make upgrades to it after that, but you must turn in a credible working version by 8:00am, November 13. The board evaluation function takes as input a board and returns a numeric value indicating the "goodness" of the board. This function will probably also want to know which side of the board your program is playing ('b or 'w -- for example, if you pass 'b here, then you're playing the side of the black pieces and the higher numbers should correspond to boards that are favorable to black) and which side is supposed to move next. Then, by 8:00am, Monday, November 20, we'd like to see your entire seega program -- move generation, minimax, alpha-beta pruning if you want, and your possibly new, improved secret weapon static board evaluator, all merged into one lean, mean seega machine. Some extra notes: 1) We may need to modify the specifications a bit here or there in case we forgot something. Try to be flexible. Don't whine. 2) A static board evaluation function is exactly that -- static. It doesn't search ahead. Ever. 3) You can convert our board representation to anything you want, just as long as when we talk to your functions or they talk to us, those functions are using our representation. Thus the interface to your board evaluator must be in terms of our board representation, and the interface to your top level function must be in terms of our board representation. 4) We are not asking you to write the human-computer interface so that your program can play against a human. You can if you want to, just for fun, but we don't want to see it. We have written a driver program that will allow your function to play against the functions written by your classmates. Your function will be loaded alongside your opponent's functions. Yes, two functions, trying to do exactly the same thing, sharing the same space...yikes! The potential for disaster is tremendous, because you're now programming in a very communal environment. Practice safe programming. 5) Do not redefine existing LISP functions. Before you "invent" a function name, make sure that LISP doesn't already use that name. 6) 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 the search control structure (i.e., everything else) working, then go back and tune your evaluator. -- Kurt Eiselt Assistant Dean, Student Services College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 http://www.cc.gatech.edu/aimosaic/faculty/eiselt.html