In article <47n0o2$dfo@pravda.cc.gatech.edu>, Kurt Eiselt wrote: >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. A few addtions.... To make this easier to grade. The above function must be called BOARD-EVALUATOR . e.g. (board-evaluator '( _ _ _ ) ( w w w ) ( b b b ) 'w 'b ) ==> 100 (board-evaluator '( _ _ _ ) ( w w w ) ( b b b ) 'b 'b ) ==> -100 In addition you are required to write the following two functions. ( you need them anyway, but with prescribed names means the test harness can grab them.. ) You should DOCUMENT what the range of values your function returns. The example above ranges from 100 to -100. Where 100 is a win and -100 is a lose. 1. BOARD-CONVERT This function should take a board in the "universal" format and translate to your chosen internal format. e.g. (board-convert '( _ _ _ ) ( w w w ) ( b b b ) ) ==> ( .... whatever seems best .... ) [ Note: if your format is the universal format you will still need this function... it becomes very simple though... Additionally you will probably need another function BOARD-UNCONVERT ] 2. GAME-OVER-P This function should return W or B iff the game is over. Otherwise NIL. [ The example below assumes that the internal format is the input format. ] (game-over-p '( _ _ _ ) ( w w w ) ( b b b ) ) ==> W (game-over-p '( w w w ) ( _ _ _ ) ( b b b ) ) ==> NIL [ You may also find useful a function that takes a board , a position from and to. and determines whether this will result in a winning board. ] Hint: a board ADT might encode more info than just the position of the pieces. NOTE: minmax search do NOT progress though board in which the game is over. Additionally, you program should depend on three defconstants. (defconstant *white* 'w ) (defconstant *black* 'b ) (defconstnat *blank* '_ ) NOTE: by the completion of assignment 6 you should have completed a a working board ADT. You code text should contain a description of what the interface to this ADT looks like. And any other ADT and/or abstractions you develop. >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 ^^^^^^^^^^^^^^^^^^ Alpha-beta pruning is NOT required. Make a working version WITHOUT alphah-beta pruning and then put it in if you wish. [ This might require trashing you minimax functions, but the board stuff all stays the same. ] "Premature optimization is the root of all evil." > >2) A static board evaluation function is exactly that -- static. It > doesn't search ahead. Ever. Your static board evaluation function can recognize patterns other than win/lose. Such as almost a win and almost a lose. Patterns such as m in a row on a nxn board. Like there may be an advantage to making a defensive move as opposed to an offensive move. for instance _ _ W _ W W _ W B _ B _ _ B _ B And it is black's move. At this point stopping White might be more important than getting closer to a win. Hence there is value is playing defense ... one of the many nuances involved in a good evaluation function. >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. The conversion functions outlined earlier allows you to abstract away your internal representation. You evaluator may operate on your internal representation. Meaning that the conversion routine can be called pre and post entering your code.... ( defun seega-geek ( universal-board ... ) (board-unconvert ( .... (board-convert universal-board ) ... ))) > >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. Avoiding this name collision is precisely what packages are for..... Let me ponder this and I'll get back to you folks soon.... rather than having to prefix each and every one of your functions with a something.. >5) Do not redefine existing LISP functions. Before you "invent" a > function name, make sure that LISP doesn't already use that name. packages help save you from this too... :-) >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. Getting a passible board evaluator is easy. Getting a finely tuned one working is harder. Make it work. Then optimize it. You'll encode better hueristics if you play the game a bit... Store your passible one somewhere... then go on. It you totally ruin it making it better turn in the passible one for part I. You can either optimize it using minimax tress on paper. Or you can optimize by plugging it into your minimax function. -- Lyman S. Taylor "We are Microsoft. (lyman@cc.gatech.edu) all other products are irrelevant. resistance is futile. Prepare to be assimilated." .sig seen while netsurfing the Internet. In article <47oo5b$8i6@pravda.cc.gatech.edu>, Lyman S. Taylor wrote: > > A few addtions.... Oooops one more addition 4. BOARD-PRINT Although, I might give a first cut this function away for free.... ( it will presume some board ADT functions. ) -- Lyman S. Taylor "We are Microsoft. (lyman@cc.gatech.edu) all other products are irrelevant. resistance is futile. Prepare to be assimilated." .sig seen while netsurfing the Internet.