home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / xlisp / ufg.arc / GAME.LSP < prev    next >
Text File  |  1987-06-02  |  44KB  |  890 lines
  1. ;;;;
  2. ;;;;    UFG Version 1.1, Copyright (c) 1987, by Hans DeHartog.
  3. ;;;;    Distribution granted for non-commercial use.
  4. ;;;;
  5. ;;;;    Universal Functions for Game-playing
  6. ;;;;    ------------------------------------
  7. ;;;;
  8. ;;;    UFG consist of a set of Lisp-functions, which can play games.
  9. ;;;
  10. ;;;    Universality:    Any 2-person game can be implemented by adding
  11. ;;;            a small set of clearly specified functions (see
  12. ;;;            below).
  13. ;;;
  14. ;;;    Goals:        Robustness, portability, functionality, size
  15. ;;;            (small games should run on small systems).
  16. ;;;
  17. ;;;    Non-goals:    Speed (should be taken care of by selecting
  18. ;;;            the right hardware, now or in the future).
  19. ;;;            Fancy screen-i/o (makes you highly non-portable).
  20. ;;;
  21. ;;;    Implementation:    Written in elementary Common Lisp. Somewhat
  22. ;;;            consideration has been given to write things
  23. ;;;            in a clear and portable way without using the
  24. ;;;            more exotic features of Common Lisp, probably
  25. ;;;            at the cost of speed.
  26. ;;;
  27. ;;;    Algorithm:    Minimax algorithm, Alpha-Beta-cut-offs,
  28. ;;;            progressive deepening and feed-over.
  29. ;;;
  30. ;;;    Features:    Theory handling (book of openings), showing
  31. ;;;            evaluations, advise on next move, escape to
  32. ;;;            Lisp, role-switching, save/restore situations,
  33. ;;;            strength-control with respect to time or depth,
  34. ;;;            taking back moves, recognition of repetition of
  35. ;;;            moves.
  36. ;;;
  37. ;;;    Any two-person game can be played by this program. The functions in
  38. ;;;    this file provide a general game-playing function with the features
  39. ;;;    mentioned above. Game-specific functionality should be provided by
  40. ;;;    the user with a set of functions with the following specifications:
  41. ;;;
  42. ;;;    Function    Argument(s)    Return-type
  43. ;;;    -------------------------------------------------
  44. ;;;    INITIALIZE    (none)        BOARD
  45. ;;;    PRINT-BOARD    BOARD        (not used)
  46. ;;;    GENERATE-MOVES    list of BOARDs    list of MOVEs
  47. ;;;    MAKE-MOVE    MOVE, BOARD    new BOARD
  48. ;;;    EVALUATE    list of BOARDs    NUMBER
  49. ;;;    CURRENT-PLAYER    BOARD        SYMBOL or STRING
  50. ;;;
  51. ;;;    The types BOARD and MOVE can be any data-structure that can be
  52. ;;;    bound to a variable by SETQ, compared for equality by EQUAL,
  53. ;;;    printed by PPRINT and after that succesfully read in again by
  54. ;;;    the standard function READ.
  55. ;;;    List of BOARDs actually means the history of all BOARDS (the CAR
  56. ;;;    being the most recent). This can be used for doing special things
  57. ;;;    when repetition of moves occurs.
  58. ;;;    Furthermore, the user should provide two global variables called
  59. ;;;    *INFINITE*, which contains the highest value that EVALUATE can
  60. ;;;    return, and NAME-OF-THE-GAME (a string that is the name of the
  61. ;;;    game (e.g. "Chess", "GO" or "Kalah").
  62. ;;;    If (EVALUATE BOARDs) returns *INFINITE*, it is assumed that the
  63. ;;;    current player has won the game (minus *INFINITE* means loss).
  64. ;;;    Note also that EVALUATE should always consider the situation from
  65. ;;;    the current player (who's turn it is).
  66. ;;;    Finally, the user should supply a file in the working directory,
  67. ;;;    that contains a short (preferably not more than 20 lines) text,
  68. ;;;    describing the rules of the game. The file-name should be a con-
  69. ;;;    catenation of the name of the game and ".rls" (e.g. "chess.rls").
  70. ;;;    It is recommended that the data-structure for a MOVE is kept quite
  71. ;;;    simple because the user has to type it in when he types a move.
  72. ;;;    Experiences so far indicate that even a dotted pair, .e.g (E2 . E4),
  73. ;;;    is too difficult for some people. You better convert vice versa to
  74. ;;;    a symbol: E2-E4 or E2E4.
  75. ;;;    For more information, see the description of the global variables.
  76.  
  77. ;;;;
  78. ;;;;    Globals
  79. ;;;;    =======
  80. ;;;;    Here are the global variables for this program. Note that the user
  81. ;;;;    who supplies the game-specific functions does not need any of those.
  82. ;;;;    All the information he needs is given by arguments to his functions.
  83. ;;;;
  84. ;;;    First the board and the history. Typically, BOARD always points to
  85. ;;;    the CAR of HISTORY. Because it is frequently used, we've created a
  86. ;;;    special variable for it instead of taken the CAR every time.
  87. ;;;    BOARD is initialized by the user-routine INITIALZE. Initially,
  88. ;;;    HISTORY is set to the the list of one BOARD.
  89. (DEFVAR BOARD (INITIALIZE))
  90. (DEFVAR HISTORY (LIST BOARD))
  91.  
  92. ;;;    BOARDS-TO-KEEP determines how long we keep the old situations.
  93. ;;;    If non-negative, it determines the number of situations that will
  94. ;;;    be kept in HISTORY. This can be set by the "keep"-command. So, KEEP 1
  95. ;;;    means: 1 board will be saved (this could be done for 'irreversible'
  96. ;;;    games like kalah or go). Note that this nullifies the possibility
  97. ;;;    of the "undo"-command and the possibility to recognize repetition
  98. ;;;    of moves throughout the history.
  99. ;;;    As 0 is a useless value in this case, it means: save everything.
  100. ;;;    Negative values are not used. However, a negative value (-n) to the
  101. ;;;    "keep"-command means a one-time-only cut-off of the history to the
  102. ;;;    length n. This can be usefull after captures, which normally mean
  103. ;;;    that previous situations can not occur anymore.
  104. (DEFVAR BOARDS-TO-KEEP 0)
  105.  
  106. ;;;    LIST-OF-MOVES always contains the list of moves that are possible
  107. ;;;    in the current situation (indicated by BOARD). When the program
  108. ;;;    has to figure out a move, this list is reordered by trying to have
  109. ;;;    the best move in front of the list.
  110. ;;;    This list is also used to check if the user gave a legal move (i.e.
  111. ;;;    if his ANSWER is a member of this list). Any heuristics in the user
  112. ;;;    supplied functions with respect to move-generation should not omit
  113. ;;;    legal but worthless moves from the list but put them at the end of
  114. ;;;    the list. On the other hand, it is occasionally allowed to enter an
  115. ;;;    illegal move in the list for the only reason that it would take too
  116. ;;;    much time to check for legality of that move.
  117. (DEFVAR LIST-OF-MOVES)
  118.  
  119. ;;;    SHOW-EVALUATIONS-P is a toggle-switch (T or NIL) which determines if
  120. ;;;    we are showing evaluations of moves while thinking. This switch will
  121. ;;;    be flipped by the "eval"-command.
  122. (DEFVAR SHOW-EVALUATIONS-P T)
  123.  
  124. ;;;    BELL-P controls ringing the bell when user has to type a command or
  125. ;;;    a move. Initially it is on (T), but can be switched off by the
  126. ;;;    "bell"-command.
  127. (DEFVAR BELL-P T)
  128.  
  129. ;;;    The players. They are supposed to have names, e.g. BLACK and WHITE,
  130. ;;;    A and B, NORTH and SOUTH. The way to find out the name of the cur-
  131. ;;;    rent player, is by the user-supplied function with the same name.
  132. ;;;    BOARD contains the initial situation, so PLAYER1 will be the first
  133. ;;;    player to move.
  134. (DEFVAR PLAYER1 (CURRENT-PLAYER BOARD))
  135.  
  136. ;;;    Its more difficult to find out the name of the other player because
  137. ;;;    it is not his turn, so no function will give us directly his name.
  138. ;;;    So, what we have to do is the following: generate the moves from the
  139. ;;;    initial situation, take the first one, make that move and finally
  140. ;;;    call the function CURRENT-PLAYER. This should be the name of the
  141. ;;;    second player. While we're doing this, we also bind LIST-OF-MOVES.
  142. ;;;    Note that after this, we've already used most of the user-supplied
  143. ;;;    functions. Therefore, any severe errors by the user are likely to
  144. ;;;    show up immediately.
  145. (DEFVAR PLAYER2
  146.   (CURRENT-PLAYER
  147.    (MAKE-MOVE (CAR (SETQ LIST-OF-MOVES (GENERATE-MOVES HISTORY))) BOARD)))
  148.  
  149. ;;;    Next two variables are for keeping the times that were used by both
  150. ;;;    players. Units of measurement are seconds. These are not used for
  151. ;;;    determining if somebody looses because he used too much time.
  152. ;;;    They are used for strength-control (if not controlled by depth) and
  153. ;;;    they will be shown after every PRINT-BOARD. There values are com-
  154. ;;;    pletely irrelevant after an "undo"-command and strength-control
  155. ;;;    should be by means of depth-restriction (if any).
  156. (DEFVAR PLAYER1-TIME 0)
  157. (DEFVAR PLAYER2-TIME 0)
  158.  
  159. ;;;    The MOVE-COUNTER is not only an administrative variable. It is also
  160. ;;;    used for strength control (by time). MOVE-COUNTER is incremented
  161. ;;;    after a move by the second player, so it always denotes the move
  162. ;;;    that has to be done. After the "undo"-command, the value of this
  163. ;;;    variable is probably of no use anymore to control the strength by
  164. ;;;    time-constraints.
  165. (DEFVAR MOVE-COUNTER 1)
  166.  
  167. ;;;    Strength-control is done by one single variable: TIME-OR-DEPTH-LIMIT.
  168. ;;;    It can be changed by the human player with the "sets"-command.
  169. ;;;    If TIME-OR-DEPTH-LIMIT is negative (e.g. -6), the strength of this
  170. ;;;    program is simply 'brute-force with depth 6'. So, negative values
  171. ;;;    simply set depth-limits. As depth 1 is not usefull, setting the
  172. ;;;    strength to -1 has the special effect of 'infinite' depth, i.e. the
  173. ;;;    programs 'thinks' until the end of the game has been reached...
  174. ;;;    With positive values, the strength is dependent on the value AND the
  175. ;;;    amount of time that is used by the opponent. If TIME-OR-DEPTH-LIMIT
  176. ;;;    is 20, it means that this program tries to do one move in every 20
  177. ;;;    seconds. However, if the opponent uses more time, the program will
  178. ;;;    do the same. The formula used to determine the amount of time that
  179. ;;;    is available for a move can be found at the start of function THINK.
  180. ;;;    The initial value of zero means "blitz-game", i.e. the program tries
  181. ;;;    to use less time than his opponent. However, for non-negative values
  182. ;;;    of this variable, there exists always a chance that the program will
  183. ;;;    exceed the expected time because of the "feed-over"-feature.
  184. (DEFVAR TIME-OR-DEPTH-LIMIT 0)
  185.  
  186. ;;;    BOTTOM-OF-TREE-P is a simple variable to check within the function
  187. ;;;    THINK, if we reached the bottom of the search-tree (i.e. if we have
  188. ;;;    reached the end of the game. It is initialized and checked in THINK
  189. ;;;    and possibly changed in the function ANALYZE.
  190. (DEFVAR BOTTOM-OF-TREE-P)
  191.  
  192. ;;;    The next global variable determines the role of this program in the
  193. ;;;    game. If NIL, the program does not participate in the game but keeps
  194. ;;;    checking and registrating alternate moves and does all the necessary
  195. ;;;    house-keeping. When changed to the name of one of the players (by the
  196. ;;;    "play"-command), the program will play the role of that player until
  197. ;;;    another "play"-command is given (which means: "exchanging chairs") or
  198. ;;;    until the "stop"-command is given.
  199. (DEFVAR COMPUTER-ROLE NIL)
  200.  
  201. ;;;    THEORY is a list of situations (BOARDs) and (ideally) the best move
  202. ;;;    in those situations. The format is simply as follows:
  203. ;;;    ((BOARD1 MOVE1) (BOARD2 MOVE2) ... (BOARDn MOVEn))
  204. ;;;    THEORY can be read in from a file by the "book"-command, it can be
  205. ;;;    modified by the "tell"-command and it can be written out to a file
  206. ;;;    by the "book"-command (got that?).
  207. (DEFVAR THEORY NIL)
  208.  
  209. ;;;    Together with THEORY, there is a flag (THEORY-UPDATED-P) which
  210. ;;;    determines if the THEORY has been stored in a file, or not.
  211. ;;;    This flag is cleared, when the THEORY is read or written and set
  212. ;;;    when the theory changes by the "tell"-command.
  213. ;;;    It is used to warn the user when the program is about to exit
  214. ;;;    while maybe there exists new theory that he might want to be saved.
  215. (DEFVAR THEORY-UPDATED-P NIL)
  216.  
  217. ;;;    START-TIME is a variable for the time-accounting. It contains the
  218. ;;;    time when a player starts to think about a move. For its initiali-
  219. ;;;    zation (and time-accounting in general) we use the (probably non-
  220. ;;;    standard) function CLOCK with no arguments which is supposed to
  221. ;;;    return the time (i.e. wall-clock-time, NO cpu-time) since some
  222. ;;;    fixed point in the past.
  223. ;;;    For Unix-systems, use the return-value of the system-call TIME.
  224. ;;;    For systems that provide you (lucky) with full-blown Common Lisp,
  225. ;;;    you can define CLOCK as follows:
  226. ;;;    (DEFUN CLOCK ()
  227. ;;;           (ROUND (GET-INTERNAL-REAL-TIME)
  228. ;;;              (INTERNAL-TIME-UNITS-PER-SECOND)))
  229. (DEFVAR START-TIME (CLOCK))
  230.  
  231. ;;;    AUTO-MOVE-P is a toggle-switch which (if ON) make this program to
  232. ;;;    continue automatically for either player whenever (s)he has just
  233. ;;;    one move to choose from. Handy for games where a player has to
  234. ;;;    skip a move (in which case his only move should be 'SKIP' or so).
  235. (DEFVAR AUTO-MOVE-P T)
  236.  
  237. ;;;;
  238. ;;;; M A I N   F U N C T I O N 
  239. ;;;;
  240. (DEFUN GAME (&AUX TMP ANSWER)
  241.   ;; This is the main-function that should be loaded after the user
  242.   ;; supplied functions. It is just one 'endless' loop from which there
  243.   ;; are three escapes: first by giving the "exit"-command, second exit
  244.   ;; is 'the normal way-out' when the game is over (no moves are generated)
  245.   ;; and third is the escape to Lisp (by the "lisp"-command). This function
  246.   ;; is called dynamically at the beginning (lexically at the end).
  247.   ;; Intially, welcome the user and print the situation.
  248.   (TERPRI)
  249.   (PRINC "Welcome to the game of ")
  250.   (PRINC NAME-OF-THE-GAME)
  251.   (PRINC "!")
  252.   (TERPRI)
  253.   (PRINC "For help, type HELP or RULES")
  254.   (TERPRI)
  255.   (PRINT-SITUATION)
  256.   ;; Here's the 'endless' loop:
  257.   (DO    ()
  258.     ;; Next are the criteria for exiting this loop (and program).
  259.     ;; Generate moves from the current situation if necessary. If there
  260.     ;; are no moves, do the epilog (tell who wins/looses and exit).
  261.     ((AND (NULL LIST-OF-MOVES)
  262.           (NULL (SETQ LIST-OF-MOVES (GENERATE-MOVES HISTORY))))
  263.      (EPILOG T (EVALUATE HISTORY)))
  264.     
  265.     ;; If there is only one possible move, and AUTO-MOVE-P is ON, just do
  266.     ;; that move (whoever's turn it is). Otherwise, ask for a command or
  267.     ;; move unless its my turn to play. In that case, "think" returns my
  268.     ;; best move which is handled as if it had been typed in.
  269.     (SETQ ANSWER (COND ((AND AUTO-MOVE-P (= (LENGTH LIST-OF-MOVES) 1))
  270.                 (CAR LIST-OF-MOVES))
  271.                ((EQUAL COMPUTER-ROLE (CURRENT-PLAYER BOARD))
  272.                 (THINK))
  273.                (T (IF BELL-P (PRINC ""))
  274.                   (PRINT 'COMMAND/MOVE) (READ))))
  275.     
  276.     ;; Do time-accounting unless the "play"-command was given (i.e. we
  277.     ;; are switching roles).
  278.     (IF (NOT (EQL ANSWER 'PLAY))
  279.         (IF    (EQUAL (CURRENT-PLAYER BOARD) PLAYER1)
  280.         (SETQ PLAYER1-TIME (+ PLAYER1-TIME (- (CLOCK) START-TIME)))
  281.         (SETQ PLAYER2-TIME (+ PLAYER2-TIME (- (CLOCK) START-TIME)))))
  282.     (SETQ START-TIME (CLOCK))
  283.     
  284.     ;; Check if he typed a move or a command. If its a move, it must be
  285.     ;; in the list of moves that had been generated at the start of the
  286.     ;; main loop.
  287.     (COND ((MEMBER ANSWER LIST-OF-MOVES :TEST #'EQUAL) (TERPRI)
  288.            
  289.            ;; If so, do the move and do the necessary house-keeping.
  290.            ;; Note, that a provision has been build in to handle the
  291.            ;; case that an illegal move occurs in the list of moves.
  292.            ;; In that case the function "make-move" should return NIL
  293.            ;; in stead of a new situation. This is done because for
  294.            ;; some games it is necessary to almost do the move before
  295.            ;; you can see if it was a legal move or not (eg the suicide-
  296.            ;; rule in GO).
  297.            (COND ((SETQ TMP (MAKE-MOVE ANSWER BOARD))
  298.               (PRINC MOVE-COUNTER) (PRINC ". ")
  299.               (SETQ HISTORY (CONS (SETQ BOARD TMP) HISTORY))
  300.               ;; Keep history at desired length (if any).
  301.               (IF (AND (> BOARDS-TO-KEEP 0)
  302.                    (> (LENGTH HISTORY) BOARDS-TO-KEEP))
  303.               (SETQ HISTORY (REVERSE
  304.                      (NTHCDR (- (LENGTH HISTORY)
  305.                             BOARDS-TO-KEEP)
  306.                          (REVERSE HISTORY)))))
  307.               (SETQ LIST-OF-MOVES NIL)
  308.               (COND  ((EQUAL (CURRENT-PLAYER BOARD) PLAYER1)
  309.                   ;; update move-counter every 2 plies
  310.                   (SETQ MOVE-COUNTER (1+ MOVE-COUNTER))
  311.                   (PRINC "... ")))
  312.               (PRINC ANSWER))
  313.              (T (PRINC "Illegal move")))
  314.            (PRINT-SITUATION))
  315.           
  316.           ;; Next is the dispatch-table for all the possible commands.
  317.           ;; We end up here if something had been typed in that was not
  318.           ;; member of LIST-OF-MOVES.
  319.           ;; Note that in most cases, abbreviated commands are possible.
  320.           (T (CASE ANSWER
  321.                
  322.                ;; The first command is the "auto"-command which toggles
  323.                ;; the switch for doing moves automatically when there
  324.                ;; is only one possible move.
  325.                ((AUTO AUT AU A) (SETQ AUTO-MOVE-P (NOT AUTO-MOVE-P)))
  326.  
  327.                ;; The second command is the "bell"-command which flips
  328.                ;; a toggle-switch that controls ringing the bell when
  329.                ;; the user is expected to type in a command or move.
  330.                ((BELL BEL BE) (SETQ BELL-P (NOT BELL-P)))
  331.                
  332.                ;; Read or write the opening-book, depending on the fact
  333.                ;; that the theory (i.e. a list of conses, thar car de-
  334.                ;; noting the situation and the cdr the corresponding
  335.                ;; move) is empty or not. Note that the theory can be
  336.                ;; non-empty for two reasons: it has been read in
  337.                ;; before or new situations have been added by the
  338.                ;; "tell"-command.
  339.                ((BOOK BOO BO)
  340.             (IF THEORY
  341.                 ;; Here we're writing the theory.
  342.                 (COND ((NULL (SETQ ANSWER (OPENO (READ))))
  343.                    (PRINC "Can't open output-file"))
  344.                   (T (PPRINT THEORY ANSWER)
  345.                      (CLOSE ANSWER)
  346.                      (SETQ THEORY-UPDATED-P NIL)))
  347.                 ;; Here we're reading the theory.
  348.                 (COND ((NULL (SETQ ANSWER (OPENI (READ))))
  349.                    (PRINC "Can't open input-file"))
  350.                   (T (SETQ THEORY (READ ANSWER))
  351.                      (CLOSE ANSWER)
  352.                      (SETQ THEORY-UPDATED-P NIL)))))
  353.                
  354.                ;; Next handles the exit-command.
  355.                ((EXIT EXI EX) (EPILOG T))
  356.                
  357.                ;; Next is the "eval"-command which simply flips a
  358.                ;; predicate.
  359.                ;; The user can find out the current setting by giving
  360.                ;; the "help"-command (or any other non-existing com-
  361.                ;; mand or move).
  362.                ((EVAL EVA EV)
  363.             (SETQ SHOW-EVALUATIONS-P (NOT SHOW-EVALUATIONS-P)))
  364.                
  365.                ;; The "hint"-command simply acts as if it is my turn to
  366.                ;; move. Note however, that the strength-setting is in
  367.                ;; effect! So, in the case of time-related strength,
  368.                ;; this program will use almost all the time that is
  369.                ;; available for the user. If time is no issue, the
  370.                ;; "hint"-command can be used for really deep analysis
  371.                ;; of the current situation by setting any depth (by
  372.                ;; the "sets"-command) before giving this "hint"-command.
  373.                ;; Although the implementation is simple, it has some
  374.                ;; side-effect: while 'thinking', the list of currently
  375.                ;; legal moves is reordered by the progressive deepening
  376.                ;; strategy. Therefore, if the "play"-command is given
  377.                ;; after the "hint"-command, the machine can figure out
  378.                ;; the best move in less time due to the alpha-beta-cut-
  379.                ;; offs.
  380.                ((HINT HIN) (IF (= (LENGTH LIST-OF-MOVES) 1)
  381.                        (PRINT (CAR LIST-OF-MOVES))
  382.                        (PRINT (THINK))))
  383.                
  384.                ;; The "hist"-command simply prints all the boards in the
  385.                ;; history (oldest first).
  386.                ((HIST HIS)
  387.             (DOLIST (TMP (REVERSE HISTORY)) (PRINT-BOARD TMP)))
  388.                
  389.                ;; The "keep"-command can be used to save some space at
  390.                ;; the cost of loosing historical data and decreasing
  391.                ;; the number of moves you can go back with the "undo"-
  392.                ;; command.
  393.                ((KEEP KEE KE K)
  394.             (COND ((NUMBERP (SETQ TMP (READ)))
  395.                    (COND ((>= TMP 0)
  396.                       (SETQ BOARDS-TO-KEEP TMP)
  397.                       (SETQ TMP (- TMP))))
  398.                    (IF (> (+ TMP (LENGTH HISTORY)) 0)
  399.                    (SETQ HISTORY
  400.                      (REVERSE (NTHCDR (+ TMP
  401.                                  (LENGTH HISTORY))
  402.                               (REVERSE HISTORY))))))
  403.                   (T (INFORMATION))))
  404.                
  405.                ;; The "lisp"-command takes you back to Lisp by a simple
  406.                ;; return from this main loop. For non-lisping players
  407.                ;; you might consider to remove this feature...
  408.                ;; To continue with the game (if possible after you
  409.                ;; lisping), simply call the main function again: (game)
  410.                (LISP (RETURN))
  411.                
  412.                ;; The "list"-command simply gives a list of all possible
  413.                ;; moves in the current situation.
  414.                (LIST (DOLIST (M LIST-OF-MOVES) (PRINC " ") (PRINC M)))
  415.                
  416.                ;; The "play"-command instructs this program to do the
  417.                ;; next move. By repeatedly giving this command, this
  418.                ;; program plays "against" itself. Although it would
  419.                ;; have been easy to implement a command that does this
  420.                ;; automatically, it was deliberately not done, because
  421.                ;; stopping the program in that case would probably
  422.                ;; require some implementation-dependent code (for
  423.                ;; trapping Control-C or so).
  424.                ;; Note that this "play"-command can not be abbreviated
  425.                ;; for two reasons: firstly, it has a major impact on
  426.                ;; the flow of the program (and the game) and secondly,
  427.                ;; in the start of this main loop is another test to see
  428.                ;; if the "play"-command had been given in order to see
  429.                ;; if time-accounting has to be done.
  430.                (PLAY (SETQ COMPUTER-ROLE (CURRENT-PLAYER BOARD)))
  431.                
  432.                ;; Here are the "rest" and "save" commands to restore and
  433.                ;; save situations from/to a file. If you type the file-
  434.                ;; name without quotes, any lowercase characters are
  435.                ;; converted to uppercase by most Lisp-implementations.
  436.                ;; This is probably not what you want as a Unix-user.
  437.                ((REST RES RE)
  438.             (COND ((NULL (SETQ ANSWER (OPENI (READ))))
  439.                    (PRINC "Can't open input-file"))
  440.                   (T (SETQ SHOW-EVALUATIONS-P (READ ANSWER))
  441.                  (SETQ TIME-OR-DEPTH-LIMIT (READ ANSWER))
  442.                  ;; Note that we also save my role. There is no
  443.                  ;; danger for this program to immediately going
  444.                  ;; to "think" after restoring because the
  445.                  ;; "save"-command only could have been given
  446.                  ;; when it was not my turn (unless somebody
  447.                  ;; fiddled with the file...)
  448.                  (SETQ COMPUTER-ROLE (READ ANSWER))
  449.                  (SETQ PLAYER1-TIME (READ ANSWER))
  450.                  (SETQ PLAYER2-TIME (READ ANSWER))
  451.                  (SETQ MOVE-COUNTER (READ ANSWER))
  452.                  (SETQ BOARDS-TO-KEEP (READ ANSWER))
  453.                  (SETQ HISTORY (READ ANSWER))
  454.                  (SETQ LIST-OF-MOVES NIL)
  455.                  (SETQ BOARD (CAR HISTORY))
  456.                  (CLOSE ANSWER)
  457.                  (PRINT-SITUATION))))
  458.                ((SAVE SAV SA)
  459.             (COND ((NULL (SETQ ANSWER (OPENO (READ))))
  460.                    (PRINC "Can't open output-file"))
  461.                   (T (PRINT SHOW-EVALUATIONS-P ANSWER)
  462.                  (PRINC "; show-evaluations-p" ANSWER)
  463.                  (PRINT TIME-OR-DEPTH-LIMIT ANSWER)
  464.                  (PRINC "; time-or-depth-limit" ANSWER)
  465.                  (PRINT COMPUTER-ROLE ANSWER)
  466.                  (PRINC "; computer-role" ANSWER)
  467.                  (PRINT PLAYER1-TIME ANSWER)
  468.                  (PRINC "; player1-time" ANSWER)
  469.                  (PRINT PLAYER2-TIME ANSWER)
  470.                  (PRINC "; player2-time" ANSWER)
  471.                  (PRINT MOVE-COUNTER ANSWER)
  472.                  (PRINC "; move-counter" ANSWER)
  473.                  (PRINT BOARDS-TO-KEEP ANSWER)
  474.                  (PRINC "; boards-to-keep" ANSWER)
  475.                  (PPRINT HISTORY ANSWER)
  476.                  (CLOSE ANSWER))))
  477.                
  478.                ;; The "rules"-command explains the rules of the game.
  479.                ;; It depends on the existence of a file supplied by the
  480.                ;; creator of the game. It simply copies that file. Note
  481.                ;; that we use READLN here, which is exactly the same as
  482.                ;; READ-LINE in most Lisp-implementations; however, in
  483.                ;; Common Lisp you have to explicitly specify a NIL-
  484.                ;; result when EOF is reached. So, for Common Lisp you
  485.                ;; have to define READLN as follows:
  486.                ;;(DEFUN READLN (&OPTIONAL STREAM)
  487.                ;;       (IF STREAM (READ-LINE STREAM NIL)
  488.                ;;        (READ-LINE *STANDARD-INPUT* NIL)))
  489.                ((RULES RULE RUL RU)
  490.             (SETQ ANSWER (STRCAT NAME-OF-THE-GAME ".rls"))
  491.             (COND  ((SETQ TMP (OPENI ANSWER))
  492.                 (DO ((L (READLN TMP) (READLN TMP)))
  493.                     ((NULL L)) (PRINC L) (TERPRI))
  494.                 (CLOSE TMP))
  495.                    (T (PRINC "Sorry, can't find file ")
  496.                   (PRINC ANSWER))))
  497.                
  498.                ;; The "sets"-command controls the strength of this
  499.                ;; program in playing the game. Generally, its imple-
  500.                ;; mentation is a brute force technique (i.e. when given
  501.                ;; enough time, it will always find the best move). Any
  502.                ;; heuristics should be provided by the user-functions
  503.                ;; because they are game-dependent. You can think of
  504.                ;; building something non-algorithmic in the evalua-
  505.                ;; tion-function or 'pre-order' the list of generated
  506.                ;; moves.
  507.                ((SETS SET SE) (IF (NUMBERP (SETQ ANSWER (READ)))
  508.                       (SETQ TIME-OR-DEPTH-LIMIT ANSWER)
  509.                       (INFORMATION)))
  510.                
  511.                ;; The "show"-command has been implemented for the simple
  512.                ;; reason that the situation can be scrolled of you
  513.                ;; screen after giving other commands.
  514.                ((SHOW SHO SH) (PRINT-SITUATION))
  515.                
  516.                ;; The "stop"-command switches back to the initial state
  517.                ;; in which this program simply checks and registrates
  518.                ;; the moves of both players but doesn't do any thinking.
  519.                ;; It only works after the "play"-command has been given.
  520.                ((STOP STO ST)
  521.             (IF COMPUTER-ROLE (SETQ COMPUTER-ROLE NIL)
  522.                 (INFORMATION)))
  523.                
  524.                ;; The "tell"-command adds the current situation and the
  525.                ;; given move to the theory.
  526.                ((TELL TEL TE) (ADD-TO-THEORY (READ)))
  527.                
  528.                ;; The "undo"-command backs up in history until it finds
  529.                ;; a situation where the same player has to move again
  530.                ;; and has at least a choice of moves (otherwise, the
  531.                ;; program would do that only move right away for him).
  532.                ;; Note, that some administrative chaos can result from
  533.                ;; this feature, because we don't save the times and
  534.                ;; move-counters separate for every situation in history.
  535.                ;; However, one normally is not concerned about those
  536.                ;; things when you allow people to take back their moves.
  537.                ((UNDO UND UN U)
  538.             (DOLIST (B (CDR HISTORY))
  539.                 (COND ((EQUAL (CURRENT-PLAYER BOARD)
  540.                           (CURRENT-PLAYER B))
  541.                        (SETQ TMP
  542.                          (MEMBER B HISTORY :TEST #'EQUAL))
  543.                        (COND ((> (LENGTH
  544.                           (GENERATE-MOVES TMP)) 1)
  545.                           (SETQ MOVE-COUNTER
  546.                             (- MOVE-COUNTER
  547.                                (DIVIDE
  548.                             (- (LENGTH HISTORY)
  549.                                (LENGTH TMP)) 2)))
  550.                           (SETQ LIST-OF-MOVES NIL)
  551.                           (SETQ HISTORY TMP)
  552.                           (SETQ BOARD (CAR HISTORY))
  553.                           (PRINT-SITUATION) (RETURN)))))))
  554.                
  555.                ;; Finally in this dispatch-table, if no legal command
  556.                ;; was given and no legal move was typed, tell the user
  557.                ;; about the possibilities. This is also the end of the
  558.                ;; main loop and main function.
  559.                (T (INFORMATION)))))))
  560.  
  561. ;;; ADD-TO-THEORY adds a situation and a corresponding move to the theory.
  562. ;;; First, the move is checked for its legality. Second, if the given situation
  563. ;;; already exists in the theory, it is removed (and the user is informed about
  564. ;;; the move being replaced). Finally, the board and move are CONS'ed to THEORY
  565. (DEFUN ADD-TO-THEORY (MOVE &AUX TMP)
  566.   (COND    ((AND    (MEMBER MOVE LIST-OF-MOVES :TEST #'EQUAL)
  567.         (MAKE-MOVE MOVE BOARD))
  568.      (COND    ((SETQ TMP (ASSOC BOARD THEORY :TEST #'EQUAL))
  569.          (SETQ THEORY (REMOVE TMP THEORY :TEST #'EQUAL))
  570.          (IF (NOT (EQUAL MOVE (CDR TMP)))
  571.              (PRINT `(REPLACED ,(CDR TMP))))))
  572.      (SETQ THEORY-UPDATED-P T)
  573.      (SETQ THEORY (CONS (CONS BOARD MOVE) THEORY)))
  574.     (T (PRINC "Illegal move"))))
  575.  
  576. ;;; PRINT-SITUATION first calls the user-supplied function PRINT-BOARD and
  577. ;;; after that, it gives some additional information. It tells who's turn it
  578. ;;; is and reports about the time used by both players. Finally, it checks
  579. ;;; for repetition of moves.
  580. (DEFUN PRINT-SITUATION ()
  581.   ;; Although BOARD is a global variable, we have to pass it explicitly
  582.   ;; to the function PRINT-BOARD.
  583.   (PRINT-BOARD BOARD)
  584.   ;; In general we distinguish two cases here: the case that the program
  585.   ;; plays a role in the game (in which the information can be somewhat
  586.   ;; more 'personal') and the case that the program is 'passive' (in
  587.   ;; which case we give 'neutral' information by mentioning the players
  588.   ;; by their 'official' names).
  589.   (COND (COMPUTER-ROLE
  590.      (IF (EQUAL COMPUTER-ROLE (CURRENT-PLAYER BOARD))
  591.          (PRINC "My") (PRINC "Your"))
  592.      ;; In the informal case, it is sometimes necessary to be
  593.      ;; able to see what pieces belong to which player (just in
  594.      ;; case that PRINT-BOARD isn't too informative about that).
  595.      (PRINC " turn with ") (PRINC (CURRENT-PLAYER BOARD))
  596.      ;; Only give the times when they are used to control strength.
  597.      (COND ((>= TIME-OR-DEPTH-LIMIT 0)
  598.         (PRINC ", ")
  599.         (PRINC (IF (EQUAL COMPUTER-ROLE PLAYER1) 'I "you"))
  600.         (PRINC " used ") (PRIT PLAYER1-TIME) (PRINC ", ")
  601.         (PRINC (IF (EQUAL COMPUTER-ROLE PLAYER2) 'I "you"))
  602.         (PRINC " used ") (PRIT PLAYER2-TIME))))
  603.     (T (PRINC (CURRENT-PLAYER BOARD)) (PRINC "'s turn")
  604.        (COND ((>= TIME-OR-DEPTH-LIMIT 0)
  605.           (PRINC ", ") (PRINC PLAYER1) (PRINC " used ")
  606.           (PRIT PLAYER1-TIME) (PRINC ", ") (PRINC PLAYER2)
  607.           (PRINC " used ") (PRIT PLAYER2-TIME)))))
  608.   (IF (MEMBER BOARD (CDR HISTORY) :TEST #'EQUAL)
  609.       (PRINC ", repetition of moves...")))
  610.  
  611. ;;; The function PRIT prints a time, given as a number of seconds, in the
  612. ;;; format hh:mm:ss. It is assumed that no game-player will need 60 hours or
  613. ;;; more for his game. If so, the next routine will do funny things, but for
  614. ;;; compensation you can apply for an entry in the Guinness Book of Records.
  615. ;;; The function DIVIDE in PRIT is a normal integer-divide (as in Fortran),
  616. ;;; so in simple Lisp-implementations you can replace DIVIDE by /. In pure
  617. ;;; Common Lisp however, it should be defined as (or replaced by)
  618. ;;; (DEFUN DIVIDE (X Y) (FLOOR X Y)), otherwise you will suffer from ratio's.
  619. (DEFUN PRIT (TIME)
  620.   (COND ((< TIME 60) (PRINC TIME))
  621.     (T (PRIT (DIVIDE TIME 60)) (PRINC ":")
  622.        (IF (< (REM TIME 60) 10) (PRINC 0))
  623.        (PRINC (REM TIME 60)))))
  624.  
  625. ;;; Function INFORMATION is called whenever the user did something wrong
  626. ;;; (typed an illegal move or an unknown or not uniquely abbreviated command).
  627. ;;; This function gives the user all the possible information within the
  628. ;;; realm of a general game-playing program. The first line deliberately
  629. ;;; contains an example of a move (in case the move-syntax isn't clear).
  630. ;;; For all user-modifiable variables/switches, the current value is given.
  631. ;;; Information is adapted to the current situation (e.g. the "play"- and
  632. ;;; "stop"-command). Note also that some options are mentioned only when
  633. ;;; appropiate (e.g. STOP). As this function mainly prints readable output,
  634. ;;; it is 'self-documenting'.
  635. (DEFUN INFORMATION ()
  636.   (PRINC "Type a move, e.g. ")
  637.   (PRINC (CAR LIST-OF-MOVES))
  638.   (PRINC ", or one of the following:")
  639.   (PRINT 'AUTO) (PRINC "    Toggle-switch for 'auto-move' when there")
  640.   (PRINC " is only 1 move") (CURRENT-VALUE AUTO-MOVE-P)
  641.   (PRINT 'BELL) (PRINC "    Toggle-switch for ringing the bell when it is")
  642.   (PRINC " your turn") (CURRENT-VALUE BELL-P)
  643.   (PRINT 'BOOK) (PRINC "f    Reads/writes theory from/to file f, if up-to")
  644.   (PRINC "-date read, else write")
  645.   (PRINT 'EVAL) (PRINC "    Toggle-switch for showing evaluations")
  646.   (CURRENT-VALUE SHOW-EVALUATIONS-P)
  647.   (PRINT 'EXIT) (PRINC "    Back to your favourite operating system")
  648.   (PRINT 'HINT) (PRINC "    Gives suggestion for your next move (uses all")
  649.   (PRINC " your time!)")
  650.   (PRINT 'HIST) (PRINC "    Prints the history of boards (oldest first)")
  651.   (PRINT 'KEEP) (PRINC "n    Keeps history-size to n boards (n>0), n=0 ")
  652.   (PRINC "means infinite,") (TERPRI) (PRINC "    n<0 cuts history-size to -n")
  653.   (CURRENT-VALUE BOARDS-TO-KEEP)
  654.   (PRINT 'LISP) (PRINC "    Back to Lisp (continue with '(GAME)')")
  655.   (PRINT 'LIST) (PRINC "    Lists possible moves in current situation")
  656.   (PRINT 'PLAY) (PRINC "    Makes me play ")
  657.   (PRINC (CURRENT-PLAYER BOARD)) (PRINC "'s role")
  658.   (PRINT 'REST) (PRINC "f    Restores situation from file f")
  659.   (PRINT 'RULES) (PRINC "    Explains the rules of the game")
  660.   (PRINT 'SAVE) (PRINC "f    Saves current situation to file f")
  661.   (PRINT 'SETS) (PRINC "n    Sets strength to n seconds/ply (n >= 0)")
  662.   (PRINC " or depth to -n (n < -1)") (TERPRI)
  663.   (PRINC "    -1 means depth='infinite'")
  664.   (CURRENT-VALUE TIME-OR-DEPTH-LIMIT)
  665.   (PRINT 'SHOW) (PRINC "    Shows board (default after every move)")
  666.   (COND (COMPUTER-ROLE (PRINT 'STOP) (PRINC "    Stops me playing ")
  667.                (PRINC COMPUTER-ROLE) (PRINC "'s role")))
  668.   (PRINT 'TELL) (PRINC "m    Adds to theory that m is the best move now")
  669.   (PRINT 'UNDO) (PRINC "    Back to your previous move (if possible)"))
  670.  
  671. ;;; The function CURRENT-VALUE is only used by PRINT-SITUATION an prints the
  672. ;;; current value of something, converting T an NIL to ON and OFF respectivily.
  673. (DEFUN CURRENT-VALUE (VALUE)
  674.   (PRINC ", currently ")
  675.   (PRINC (COND ((NULL VALUE) 'OFF)
  676.            ((EQ VALUE T) 'ON)
  677.            (T VALUE))))
  678.  
  679. ;;; The function ANALYZE is the heart of the 'thinking-mechanism' of this
  680. ;;; program. It is only called by the more general function THINK.
  681. (DEFUN ANALYZE (DEPTH ALFA BETA HISTORY &AUX MOVES VALUE)
  682.   ;; First, check if we reached the maximum depth. If so, set the global
  683.   ;; variable BOTTOM-OF-TREE-P to NIL to inform the function THINK that
  684.   ;; we did not yet reach 'end-of-game' and after that, use the 'static'
  685.   ;; game-specific evaluation-function supplied by the user and return
  686.   ;; its value.
  687.   (COND ((ZEROP DEPTH)
  688.      (SETQ BOTTOM-OF-TREE-P NIL)
  689.      (EVALUATE HISTORY))
  690.     ;; Second, check if we got a NIL-situation. This is only possible
  691.     ;; when an illegal move was member of the LIST-OF-MOVES. If so,
  692.     ;; return *INFINITE*. The rationale behind this is as follows: in
  693.     ;; most games, it is a rule that if somebody makes an illegal move,
  694.     ;; his opponent wins the game. If this program is the opponent in
  695.     ;; this case, it won't further consider this move.
  696.     ((NULL (CAR HISTORY)) *INFINITE*)
  697.     ;; Third, if there are no moves generated in the current situation,
  698.     ;; the game is probably finished and we use the 'static' evaluation
  699.     ;; again (typically, this will be plus or minus *INFINITE* or zero).
  700.     ((NULL (SETQ MOVES (GENERATE-MOVES HISTORY))) (EVALUATE HISTORY))
  701.     ;; If none of the things above was true, we really have to think,
  702.     ;; i.e. for all the possible moves, do the move and use this function
  703.     ;; recursively with depth one less and alfa and beta reversed and
  704.     ;; switched, thereby implementing alfa-beta-cut-offs.
  705.     (T (DOLIST (MOVE MOVES ALFA)
  706.            (SETQ VALUE (- (ANALYZE (1- DEPTH) (- BETA) (- ALFA)
  707.                        (CONS (MAKE-MOVE MOVE (CAR HISTORY))
  708.                          HISTORY))))
  709.            ;; Now check if the value returned is greater than alfa.
  710.            (AND (> VALUE ALFA)
  711.             ;; If so, and it is greater or equal than beta we can
  712.             ;; skip the rest of the moves.
  713.             (>= (SETQ ALFA VALUE) BETA)
  714.             (RETURN ALFA))))))
  715.  
  716. ;;; Function THINK does all the difficult stuff in this program. It is called
  717. ;;; when this program has to figure out its move or when the user wants some
  718. ;;; advise for his move (i.e. when gave the "hint"-command). This function
  719. ;;; will not be called when there is just one possible move.
  720. (DEFUN THINK (&AUX VALUE ALARM ALFA QUIET)
  721.   ;; First, lets hope for some help by the theory. If the current situation
  722.   ;; exists in the theory, just return what the theory suggests.
  723.   (COND    ((SETQ VALUE (ASSOC BOARD THEORY :TEST #'EQUAL)) (CDR VALUE))
  724.     ;; Second, compute the time we've left to figure out a move. This is
  725.     ;; done by setting the local variable ALARM to a value that is not to
  726.     ;; be exceeded by the wall-clock. So in the sequel we can simply check
  727.     ;; for (CLOCK) being greater than ALARM (in which case we better hurry,
  728.     ;; or ...?). In the next formula we take into account the number of
  729.     ;; seconds per move (i.e. the value of TIME-OR-DEPTH-LIMIT). If this
  730.     ;; value is negative - in which case depth is the only restriction -
  731.     ;; the value of ALARM is not relevant and not used. We also use the
  732.     ;; time consumed by our opponent (if that is more than he should with
  733.     ;; respect to TIME-OR-DEPTH-LIMIT, we also can safely use some more
  734.     ;; time). Finally, the amount of time is multiplied by a factor (L-1)/L
  735.     ;; (where L is the number of possible moves in this sitation) in order
  736.     ;; to anticipate possible combinatory explosions...
  737.   (T (SETQ ALARM
  738.        (+ START-TIME
  739.           (/ (* (1- (LENGTH LIST-OF-MOVES))
  740.             (IF (EQUAL (CURRENT-PLAYER BOARD) PLAYER1)
  741.             (- (MAX (* MOVE-COUNTER TIME-OR-DEPTH-LIMIT)
  742.                 PLAYER2-TIME)
  743.                PLAYER1-TIME)
  744.             (- (MAX (* MOVE-COUNTER TIME-OR-DEPTH-LIMIT)
  745.                 PLAYER1-TIME)
  746.                PLAYER2-TIME)))
  747.          (LENGTH LIST-OF-MOVES))))
  748.      ;; The outer loop implements progressive deepening and feed-over's.
  749.      ;; It 'endlessly' increments the depth and sets the local variable
  750.      ;; QUIESCENCE to QUIET (initially NIL). QUIET is set in the innner
  751.      ;; loop. Tests for leaving this outer loop are at its end.
  752.      (DO ((DEPTH 2 (1+ DEPTH)) (QUIESCENCE NIL QUIET)) ()
  753.      ;; Setting BOTTOM-OF-TREE-P true and find it still to be true at the
  754.      ;; end of the the loop (i.e. the function ANALYZE didn't set it to
  755.      ;; NIL), means that we can leave this loop because we've reached the
  756.      ;; end of the game.
  757.      (SETQ BOTTOM-OF-TREE-P T)
  758.      ;; Start with alfa being minus infinite. Note that in this function
  759.      ;; we use alfa-only-cut-offs because we stay at the top-level of the
  760.      ;; search-tree.
  761.      (SETQ ALFA (- *INFINITE*))
  762.      ;; Here is the inner loop which simply goes over all the moves. Note
  763.      ;; that we can not use the DOLIST-construct here because the list is
  764.      ;; reordered within this loop!
  765.      (DO* ((I 0 (1+ I)) (MOVE (CAR LIST-OF-MOVES) (NTH I LIST-OF-MOVES)))
  766.           ;; We can exit from this loop when there are no more moves (yes,
  767.           ;; now we have to check that explicitly) or when alfa has reached
  768.           ;; infinity (which means we have won!)
  769.           ((OR (NULL MOVE) (= ALFA *INFINITE*)))
  770.           ;; First check if we've run out of time and the situation is
  771.           ;; quiet. If so, clobber the value of DEPTH to make the outer
  772.           ;; loop believe he has to return also.
  773.           (COND ((AND (>= TIME-OR-DEPTH-LIMIT 0)
  774.               (> (CLOCK) ALARM)
  775.               QUIESCENCE)
  776.              (SETQ DEPTH (- TIME-OR-DEPTH-LIMIT))
  777.              (RETURN)))
  778.           ;; If time left or 'condition red', let ANALYZE do its work. Note
  779.           ;; that beta is always inifinite here at the top-level.
  780.           (SETQ VALUE (- (ANALYZE (1- DEPTH) (- *INFINITE*) (- ALFA)
  781.                       (CONS (MAKE-MOVE MOVE BOARD) HISTORY))))
  782.           ;; If the user wants to see the evaluations, show him now.
  783.           ;; Note that, due to alfa-beta-cut-offs, less valuable moves
  784.           ;; are shown with value 'not less' (i.e. equal to) than the
  785.           ;; value of the best move so far.
  786.           (COND (SHOW-EVALUATIONS-P
  787.              (COND  ((ZEROP I) (TERPRI)
  788.                  (PRINC "Depth=") (PRINC DEPTH)))
  789.              (PRINC " ") (PRINC MOVE)
  790.              (PRINC "=") (PRINC VALUE)))
  791.           ;; If this move is better than the previous 'best' move, put
  792.           ;; it in front of the list (and save this value in alfa for
  793.           ;; future comparisons).
  794.           (COND ((> VALUE ALFA) (SETQ ALFA VALUE)
  795.              (SETQ LIST-OF-MOVES
  796.                (NCONC (LIST MOVE)
  797.                   (DELETE MOVE LIST-OF-MOVES :TEST #'EQUAL)))
  798.              ;; Ideally, the best move is in front of the list, so if
  799.              ;; I equals zero (we were evaluating the first move) it
  800.              ;; is normal to find a value greater than minus infinity.
  801.              ;; However, if I is not zero, we've found a better move
  802.              ;; that was not the first one in the list. This is an in-
  803.              ;; dication that we are not in a quiet situation (so set
  804.              ;; QUIET to NIL, which will be used in the outer loop).
  805.              (SETQ QUIET (= I 0)))))
  806.      ;; This is the end of the inner loop.
  807.      ;; Here are the tests for leaving the outer loop. There can be three
  808.      ;; reasons for leaving. First, we've reached the end of the game
  809.      ;; (which actually means that the function ANALYZE never got a depth-
  810.      ;; value of zero). Second, the winner is known (which means that alfa
  811.         ;; is plus or minus infinite). In these first two cases we can inform
  812.      ;; the user what we found out by the function EPILOG but without
  813.      ;; exiting the game. Third and last reason: we've simply reached the
  814.      ;; depth-limit set by the user (with the "sets"-command). Note that
  815.      ;; this last reason can never happen when he set TIME-OR-DEPTH-LIMIT
  816.      ;; to -1 because this loops starts with DEPTH=2!!! However, the value
  817.      ;; of DEPTH can be set to (- TIME-OR-DEPTH-LIMIT) by the inner-loop
  818.      ;; in order to return when time forces us to do so.
  819.      (IF (OR (ZEROP (+ TIME-OR-DEPTH-LIMIT DEPTH))
  820.          (AND (OR BOTTOM-OF-TREE-P (= (ABS ALFA) *INFINITE*))
  821.               (EPILOG NIL ALFA)))
  822.          (RETURN (CAR LIST-OF-MOVES)))))))
  823.  
  824. ;;; EPILOG is used to inform the user about the end of the game. It is used
  825. ;;; in the function THINK (in which the first argument is NIL, meaning: only
  826. ;;; inform, but do not exit the program). It is really used to exit the pro-
  827. ;;; gram (after giving the information) when there are no more moves generated
  828. ;;; in the main-function GAME.
  829. (DEFUN EPILOG (FINISH &OPTIONAL VALUE)
  830.   ;; First check if any evaluation is wanted.
  831.   (COND (VALUE
  832.      (TERPRI)
  833.      ;; Second, check if we have to report the result and there is a winner.
  834.      (COND    ((= VALUE *INFINITE*)
  835.          ;; If so, we distinguish again between the 'personal' approach
  836.          ;; and the formal (as we did in the function PRINT-SITUATION).
  837.          (COND    ((EQUAL (CURRENT-PLAYER BOARD) COMPUTER-ROLE)
  838.              (PRINC "I win"))
  839.             (COMPUTER-ROLE (PRINC "You win"))
  840.             (T (PRINC (CURRENT-PLAYER BOARD)) (PRINC " wins"))))
  841.         ;; If no winner, than maybe there is a looser.
  842.         ((= VALUE (- *INFINITE*))
  843.          (COND    ((EQUAL (CURRENT-PLAYER BOARD) COMPUTER-ROLE)
  844.              (PRINC "I loose"))
  845.             (COMPUTER-ROLE (PRINC "You loose"))
  846.             (T (PRINC (CURRENT-PLAYER BOARD)) (PRINC " looses"))))
  847.         ;; If the evaluation is zero, then we drew.
  848.         ((ZEROP VALUE) (PRINC "Draw"))
  849.         ;; Finally, if none of the above is true, the game is undecided
  850.         ;; but over anyway.
  851.         (T (PRINC "Game over")))
  852.      (PRINC "!") (TERPRI)))
  853.   ;; Ask if theory has to be saved (when appropiate).
  854.   (DO (F) ((NOT (AND FINISH THEORY-UPDATED-P)))
  855.       (TERPRI)
  856.       (PRINC "Save the theory? (NIL if no, filename if yes) ")
  857.       (COND ((SETQ F (READ))
  858.          (COND ((SETF F (OPENO F))
  859.             (PPRINT THEORY F) (CLOSE F)
  860.             (SETQ THEORY-UPDATED-P NIL))
  861.            (T (PRINC "Can't open output-file"))))
  862.         (T (SETQ THEORY-UPDATED-P NIL))))
  863.   (IF FINISH (EXIT) T))
  864.  
  865. ;;; Now you've read all this, let's do it!
  866. (GAME)
  867.  
  868. ;;;    Things to be done:
  869. ;;;    ------------------
  870. ;;;    More sophisticated handling of theory (hashing BOARD into database).
  871. ;;;    Use opponent's time to set up search-tree and start evaluations.
  872. ;;;    Create validation-suite (or reproducible covering test-set).
  873.  
  874. ;;;    Modification history
  875. ;;;    --------------------
  876. ;;;
  877. ;;;    april 1987, initial version 1.0
  878. ;;;
  879. ;;;    may 1987, removed "learn"-option in which every move was added
  880. ;;;        to the theory (as with most 'learning' systems, you don't
  881. ;;;        have control over whatever is learned and it finally kills
  882. ;;;        your application because it suffers from all 'knowledge'
  883. ;;;        it has to carry). To build a good theory, you have to use
  884. ;;;        the "tell"-command selectivily.
  885. ;;;        Added "auto"-command to toggle between automatically move
  886. ;;;        (or not) when there is only 1 move.
  887. ;;;        Changed the function INFORMATION accordingly.
  888. ;;;        Made this version 1.1.
  889.  
  890.