1 ;;; landmark.el --- neural-network robot that learns landmarks
3 ;; Copyright (C) 1996-1997, 2000-2015 Free Software Foundation, Inc.
5 ;; Author: Terrence Brannon (was: <brannon@rana.usc.edu>)
6 ;; Created: December 16, 1996 - first release to usenet
7 ;; Keywords: games, neural network, adaptive search, chemotaxis
9 ;; This file is part of GNU Emacs.
11 ;; GNU Emacs is free software: you can redistribute it and/or modify
12 ;; it under the terms of the GNU General Public License as published by
13 ;; the Free Software Foundation, either version 3 of the License, or
14 ;; (at your option) any later version.
16 ;; GNU Emacs is distributed in the hope that it will be useful,
17 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
18 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 ;; GNU General Public License for more details.
21 ;; You should have received a copy of the GNU General Public License
22 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
27 ;; To try this, just type: M-x landmark-test-run
29 ;; Landmark is a relatively non-participatory game in which a robot
30 ;; attempts to maneuver towards a tree at the center of the window
31 ;; based on unique olfactory cues from each of the 4 directions. If
32 ;; the smell of the tree increases, then the weights in the robot's
33 ;; brain are adjusted to encourage this odor-driven behavior in the
34 ;; future. If the smell of the tree decreases, the robots weights are
35 ;; adjusted to discourage a correct move.
37 ;; In laymen's terms, the search space is initially flat. The point
38 ;; of training is to "turn up the edges of the search space" so that
39 ;; the robot rolls toward the center.
41 ;; Further, do not become alarmed if the robot appears to oscillate
42 ;; back and forth between two or a few positions. This simply means
43 ;; it is currently caught in a local minimum and is doing its best to
46 ;; The version of this program as described has a small problem. a
47 ;; move in a net direction can produce gross credit assignment. for
48 ;; example, if moving south will produce positive payoff, then, if in
49 ;; a single move, one moves east,west and south, then both east and
50 ;; west will be improved when they shouldn't
52 ;; Many thanks to Yuri Pryadkin <yuri@rana.usc.edu> for this
53 ;; concise problem description.
56 (eval-when-compile (require 'cl-lib
))
62 (defgroup landmark nil
63 "Neural-network robot that learns landmarks."
69 ;; The board is a rectangular grid. We code empty squares with 0, X's with 1
70 ;; and O's with 6. The rectangle is recorded in a one dimensional vector
71 ;; containing padding squares (coded with -1). These squares allow us to
72 ;; detect when we are trying to move out of the board. We denote a square by
73 ;; its (X,Y) coords, or by the INDEX corresponding to them in the vector. The
74 ;; leftmost topmost square has coords (1,1) and index landmark-board-width + 2.
75 ;; Similarly, vectors between squares may be given by two DX, DY coords or by
76 ;; one DEPL (the difference between indexes).
78 (defvar landmark-board-width nil
79 "Number of columns on the Landmark board.")
80 (defvar landmark-board-height nil
81 "Number of lines on the Landmark board.")
83 (defvar landmark-board nil
84 "Vector recording the actual state of the Landmark board.")
86 (defvar landmark-vector-length nil
87 "Length of landmark-board vector.")
89 (defvar landmark-draw-limit nil
90 ;; This is usually set to 70% of the number of squares.
91 "After how many moves will Emacs offer a draw?")
94 "This is the x coordinate of the center of the board.")
97 "This is the y coordinate of the center of the board.")
100 "This is the x dimension of the playing board.")
103 "This is the y dimension of the playing board.")
106 (defun landmark-xy-to-index (x y
)
107 "Translate X, Y cartesian coords into the corresponding board index."
108 (+ (* y landmark-board-width
) x y
))
110 (defun landmark-index-to-x (index)
111 "Return corresponding x-coord of board INDEX."
112 (% index
(1+ landmark-board-width
)))
114 (defun landmark-index-to-y (index)
115 "Return corresponding y-coord of board INDEX."
116 (/ index
(1+ landmark-board-width
)))
118 (defun landmark-init-board ()
119 "Create the landmark-board vector and fill it with initial values."
120 (setq landmark-board
(make-vector landmark-vector-length
0))
121 ;; Every square is 0 (i.e. empty) except padding squares:
122 (let ((i 0) (ii (1- landmark-vector-length
)))
123 (while (<= i landmark-board-width
) ; The squares in [0..width] and in
124 (aset landmark-board i -
1) ; [length - width - 1..length - 1]
125 (aset landmark-board ii -
1) ; are padding squares.
129 (while (< i landmark-vector-length
)
130 (aset landmark-board i -
1) ; and also all k*(width+1)
131 (setq i
(+ i landmark-board-width
1)))))
133 ;;;_ + DISPLAYING THE BOARD.
135 ;; You may change these values if you have a small screen or if the squares
136 ;; look rectangular, but spacings SHOULD be at least 2 (MUST BE at least 1).
138 (defconst landmark-square-width
2
139 "Horizontal spacing between squares on the Landmark board.")
141 (defconst landmark-square-height
1
142 "Vertical spacing between squares on the Landmark board.")
144 (defconst landmark-x-offset
3
145 "Number of columns between the Landmark board and the side of the window.")
147 (defconst landmark-y-offset
1
148 "Number of lines between the Landmark board and the top of the window.")
151 ;;;_ + LANDMARK MODE AND KEYMAP.
153 (defcustom landmark-mode-hook nil
154 "If non-nil, its value is called on entry to Landmark mode."
158 (defvar landmark-mode-map
159 (let ((map (make-sparse-keymap)))
160 ;; Key bindings for cursor motion.
161 (define-key map
"y" 'landmark-move-nw
) ; y
162 (define-key map
"u" 'landmark-move-ne
) ; u
163 (define-key map
"b" 'landmark-move-sw
) ; b
164 (define-key map
"n" 'landmark-move-se
) ; n
165 (define-key map
"h" 'backward-char
) ; h
166 (define-key map
"l" 'forward-char
) ; l
167 (define-key map
"j" 'landmark-move-down
) ; j
168 (define-key map
"k" 'landmark-move-up
) ; k
170 (define-key map
[kp-7
] 'landmark-move-nw
)
171 (define-key map
[kp-9
] 'landmark-move-ne
)
172 (define-key map
[kp-1
] 'landmark-move-sw
)
173 (define-key map
[kp-3
] 'landmark-move-se
)
174 (define-key map
[kp-4
] 'backward-char
)
175 (define-key map
[kp-6
] 'forward-char
)
176 (define-key map
[kp-2
] 'landmark-move-down
)
177 (define-key map
[kp-8
] 'landmark-move-up
)
179 (define-key map
"\C-n" 'landmark-move-down
) ; C-n
180 (define-key map
"\C-p" 'landmark-move-up
) ; C-p
182 ;; Key bindings for entering Human moves.
183 (define-key map
"X" 'landmark-human-plays
) ; X
184 (define-key map
"x" 'landmark-human-plays
) ; x
186 (define-key map
" " 'landmark-start-robot
) ; SPC
187 (define-key map
[down-mouse-1
] 'landmark-start-robot
)
188 (define-key map
[drag-mouse-1
] 'landmark-click
)
189 (define-key map
[mouse-1
] 'landmark-click
)
190 (define-key map
[down-mouse-2
] 'landmark-click
)
191 (define-key map
[mouse-2
] 'landmark-mouse-play
)
192 (define-key map
[drag-mouse-2
] 'landmark-mouse-play
)
194 (define-key map
[remap previous-line
] 'landmark-move-up
)
195 (define-key map
[remap next-line
] 'landmark-move-down
)
196 (define-key map
[remap beginning-of-line
] 'landmark-beginning-of-line
)
197 (define-key map
[remap end-of-line
] 'landmark-end-of-line
)
198 (define-key map
[remap undo
] 'landmark-human-takes-back
)
199 (define-key map
[remap advertised-undo
] 'landmark-human-takes-back
)
201 "Local keymap to use in Landmark mode.")
205 (defvar landmark-emacs-won
()
206 "For making font-lock use the winner's face for the line.")
208 (defface landmark-font-lock-face-O
'((((class color
)) :foreground
"red")
210 "Face to use for Emacs's O."
214 (defface landmark-font-lock-face-X
'((((class color
)) :foreground
"green")
216 "Face to use for your X."
220 (defvar landmark-font-lock-keywords
221 '(("O" .
'landmark-font-lock-face-O
)
222 ("X" .
'landmark-font-lock-face-X
)
223 ("[-|/\\]" 0 (if landmark-emacs-won
224 'landmark-font-lock-face-O
225 'landmark-font-lock-face-X
)))
226 "Font lock rules for Landmark.")
228 (put 'landmark-mode
'front-sticky
229 (put 'landmark-mode
'rear-nonsticky
'(intangible)))
230 (put 'landmark-mode
'intangible
1)
231 ;; This one is for when they set view-read-only to t: Landmark cannot
232 ;; allow View Mode to be activated in its buffer.
233 (define-derived-mode landmark-mode special-mode
"Lm"
234 "Major mode for playing Lm against Emacs.
235 You and Emacs play in turn by marking a free square. You mark it with X
236 and Emacs marks it with O. The winner is the first to get five contiguous
237 marks horizontally, vertically or in diagonal.
239 You play by moving the cursor over the square you choose and hitting \\[landmark-human-plays].
241 Other useful commands:
242 \\{landmark-mode-map}
243 Entry to this mode calls the value of `landmark-mode-hook' if that value
244 is non-nil. One interesting value is `turn-on-font-lock'."
245 (landmark-display-statistics)
246 (setq-local font-lock-defaults
'(landmark-font-lock-keywords t
))
247 (setq buffer-read-only t
))
250 ;;;_ + THE SCORE TABLE.
253 ;; Every (free) square has a score associated to it, recorded in the
254 ;; LANDMARK-SCORE-TABLE vector. The program always plays in the square having
255 ;; the highest score.
257 (defvar landmark-score-table nil
258 "Vector recording the actual score of the free squares.")
261 ;; The key point point about the algorithm is that, rather than considering
262 ;; the board as just a set of squares, we prefer to see it as a "space" of
263 ;; internested 5-tuples of contiguous squares (called qtuples).
265 ;; The aim of the program is to fill one qtuple with its O's while preventing
266 ;; you from filling another one with your X's. To that effect, it computes a
267 ;; score for every qtuple, with better qtuples having better scores. Of
268 ;; course, the score of a qtuple (taken in isolation) is just determined by
269 ;; its contents as a set, i.e. not considering the order of its elements. The
270 ;; highest score is given to the "OOOO" qtuples because playing in such a
271 ;; qtuple is winning the game. Just after this comes the "XXXX" qtuple because
272 ;; not playing in it is just losing the game, and so on. Note that a
273 ;; "polluted" qtuple, i.e. one containing at least one X and at least one O,
274 ;; has score zero because there is no more any point in playing in it, from
275 ;; both an attacking and a defending point of view.
277 ;; Given the score of every qtuple, the score of a given free square on the
278 ;; board is just the sum of the scores of all the qtuples to which it belongs,
279 ;; because playing in that square is playing in all its containing qtuples at
280 ;; once. And it is that function which takes into account the internesting of
283 ;; This algorithm is rather simple but anyway it gives a not so dumb level of
284 ;; play. It easily extends to "n-dimensional Landmark", where a win should not
285 ;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !)
286 ;; should be preferred.
289 ;; Here are the scores of the nine "non-polluted" configurations. Tuning
290 ;; these values will change (hopefully improve) the strength of the program
291 ;; and may change its style (rather aggressive here).
293 (defconst landmark-nil-score
7 "Score of an empty qtuple.")
295 (defconst landmark-score-trans-table
296 (let ((Xscore 15) ; Score of a qtuple containing one X.
297 (XXscore 400) ; Score of a qtuple containing two X's.
298 (XXXscore 1800) ; Score of a qtuple containing three X's.
299 (XXXXscore 100000) ; Score of a qtuple containing four X's.
300 (Oscore 35) ; Score of a qtuple containing one O.
301 (OOscore 800) ; Score of a qtuple containing two O's.
302 (OOOscore 15000) ; Score of a qtuple containing three O's.
303 (OOOOscore 800000)) ; Score of a qtuple containing four O's.
305 ;; These values are not just random: if, given the following situation:
313 ;; you want Emacs to play in "a" and not in "b", then the parameters must
314 ;; satisfy the inequality:
316 ;; 6 * XXscore > XXXscore + XXscore
318 ;; because "a" mainly belongs to six "XX" qtuples (the others are less
319 ;; important) while "b" belongs to one "XXX" and one "XX" qtuples.
320 ;; Other conditions are required to obtain sensible moves, but the
321 ;; previous example should illustrate the point. If you manage to
322 ;; improve on these values, please send me a note. Thanks.
325 ;; As we chose values 0, 1 and 6 to denote empty, X and O squares,
326 ;; the contents of a qtuple are uniquely determined by the sum of
327 ;; its elements and we just have to set up a translation table.
328 (vector landmark-nil-score Xscore XXscore XXXscore XXXXscore
0
334 "Vector associating qtuple contents to their score.")
337 ;; If you do not modify drastically the previous constants, the only way for a
338 ;; square to have a score higher than OOOOscore is to belong to a "OOOO"
339 ;; qtuple, thus to be a winning move. Similarly, the only way for a square to
340 ;; have a score between XXXXscore and OOOOscore is to belong to a "XXXX"
341 ;; qtuple. We may use these considerations to detect when a given move is
342 ;; winning or losing.
344 (defconst landmark-winning-threshold
345 (aref landmark-score-trans-table
(+ 6 6 6 6)) ;; OOOOscore
346 "Threshold score beyond which an Emacs move is winning.")
348 (defconst landmark-losing-threshold
349 (aref landmark-score-trans-table
(+ 1 1 1 1)) ;; XXXXscore
350 "Threshold score beyond which a human move is winning.")
353 (defun landmark-strongest-square ()
354 "Compute index of free square with highest score, or nil if none."
355 ;; We just have to loop other all squares. However there are two problems:
356 ;; 1/ The SCORE-TABLE only gives correct scores to free squares. To speed
357 ;; up future searches, we set the score of padding or occupied squares
358 ;; to -1 whenever we meet them.
359 ;; 2/ We want to choose randomly between equally good moves.
361 (count 0) ; Number of equally good moves
362 (square (landmark-xy-to-index 1 1)) ; First square
363 (end (landmark-xy-to-index landmark-board-width landmark-board-height
))
365 (while (<= square end
)
367 ;; If score is lower (i.e. most of the time), skip to next:
368 ((< (aref landmark-score-table square
) score-max
))
369 ;; If score is better, beware of non free squares:
370 ((> (setq score
(aref landmark-score-table square
)) score-max
)
371 (if (zerop (aref landmark-board square
)) ; is it free ?
372 (setq count
1 ; yes: take it !
375 (aset landmark-score-table square -
1))) ; no: kill it !
376 ;; If score is equally good, choose randomly. But first check freedom:
377 ((not (zerop (aref landmark-board square
)))
378 (aset landmark-score-table square -
1))
379 ((zerop (random (setq count
(1+ count
))))
380 (setq best-square square
382 (setq square
(1+ square
))) ; try next square
385 ;;;_ - INITIALIZING THE SCORE TABLE.
387 ;; At initialization the board is empty so that every qtuple amounts for
388 ;; nil-score. Therefore, the score of any square is nil-score times the number
389 ;; of qtuples that pass through it. This number is 3 in a corner and 20 if you
390 ;; are sufficiently far from the sides. As computing the number is time
391 ;; consuming, we initialize every square with 20*nil-score and then only
392 ;; consider squares at less than 5 squares from one side. We speed this up by
393 ;; taking symmetry into account.
394 ;; Also, as it is likely that successive games will be played on a board with
395 ;; same size, it is a good idea to save the initial SCORE-TABLE configuration.
397 (defvar landmark-saved-score-table nil
398 "Recorded initial value of previous score table.")
400 (defvar landmark-saved-board-width nil
401 "Recorded value of previous board width.")
403 (defvar landmark-saved-board-height nil
404 "Recorded value of previous board height.")
407 (defun landmark-init-score-table ()
408 "Create the score table vector and fill it with initial values."
409 (if (and landmark-saved-score-table
; Has it been stored last time ?
410 (= landmark-board-width landmark-saved-board-width
)
411 (= landmark-board-height landmark-saved-board-height
))
412 (setq landmark-score-table
(copy-sequence landmark-saved-score-table
))
414 (setq landmark-score-table
415 (make-vector landmark-vector-length
(* 20 landmark-nil-score
)))
416 (let (i j maxi maxj maxi2 maxj2
)
417 (setq maxi
(/ (1+ landmark-board-width
) 2)
418 maxj
(/ (1+ landmark-board-height
) 2)
421 ;; We took symmetry into account and could use it more if the board
422 ;; would have been square and not rectangular !
423 ;; In our case we deal with all (i,j) in the set [1..maxi2]*[1..maxj] U
424 ;; [maxi2+1..maxi]*[1..maxj2]. Maxi2 and maxj2 are used because the
425 ;; board may well be less than 8 by 8 !
430 (landmark-init-square-score i j
)
436 (landmark-init-square-score i j
)
439 (setq landmark-saved-score-table
(copy-sequence landmark-score-table
)
440 landmark-saved-board-width landmark-board-width
441 landmark-saved-board-height landmark-board-height
)))
443 (defun landmark-nb-qtuples (i j
)
444 "Return the number of qtuples containing square I,J."
445 ;; This function is complicated because we have to deal
446 ;; with ugly cases like 3 by 6 boards, but it works.
447 ;; If you have a simpler (and correct) solution, send it to me. Thanks !
448 (let ((left (min 4 (1- i
)))
449 (right (min 4 (- landmark-board-width i
)))
451 (down (min 4 (- landmark-board-height j
))))
453 (min (max (+ left right
) 3) 8)
454 (min (max (+ up down
) 3) 8)
455 (min (max (+ (min left up
) (min right down
)) 3) 8)
456 (min (max (+ (min right up
) (min left down
)) 3) 8))))
458 (defun landmark-init-square-score (i j
)
459 "Give initial score to square I,J and to its mirror images."
460 (let ((ii (1+ (- landmark-board-width i
)))
461 (jj (1+ (- landmark-board-height j
)))
462 (sc (* (landmark-nb-qtuples i j
) (aref landmark-score-trans-table
0))))
463 (aset landmark-score-table
(landmark-xy-to-index i j
) sc
)
464 (aset landmark-score-table
(landmark-xy-to-index ii j
) sc
)
465 (aset landmark-score-table
(landmark-xy-to-index i jj
) sc
)
466 (aset landmark-score-table
(landmark-xy-to-index ii jj
) sc
)))
467 ;;;_ - MAINTAINING THE SCORE TABLE.
470 ;; We do not provide functions for computing the SCORE-TABLE given the
471 ;; contents of the BOARD. This would involve heavy nested loops, with time
472 ;; proportional to the size of the board. It is better to update the
473 ;; SCORE-TABLE after each move. Updating needs not modify more than 36
474 ;; squares: it is done in constant time.
476 (defun landmark-update-score-table (square dval
)
477 "Update score table after SQUARE received a DVAL increment."
478 ;; The board has already been updated when this function is called.
479 ;; Updating scores is done by looking for qtuples boundaries in all four
480 ;; directions and then calling update-score-in-direction.
481 ;; Finally all squares received the right increment, and then are up to
482 ;; date, except possibly for SQUARE itself if we are taking a move back for
483 ;; its score had been set to -1 at the time.
484 (let* ((x (landmark-index-to-x square
))
485 (y (landmark-index-to-y square
))
486 (imin (max -
4 (- 1 x
)))
487 (jmin (max -
4 (- 1 y
)))
488 (imax (min 0 (- landmark-board-width x
4)))
489 (jmax (min 0 (- landmark-board-height y
4))))
490 (landmark-update-score-in-direction imin imax
492 (landmark-update-score-in-direction jmin jmax
494 (landmark-update-score-in-direction (max imin jmin
) (min imax jmax
)
496 (landmark-update-score-in-direction (max (- 1 y
) -
4
497 (- x landmark-board-width
))
499 (- landmark-board-height y
4))
502 (defun landmark-update-score-in-direction (left right square dx dy dval
)
503 "Update scores for all squares in the qtuples in range.
504 That is, those between the LEFTth square and the RIGHTth after SQUARE,
505 along the DX, DY direction, considering that DVAL has been added on SQUARE."
506 ;; We always have LEFT <= 0, RIGHT <= 0 and DEPL > 0 but we may very well
507 ;; have LEFT > RIGHT, indicating that no qtuple contains SQUARE along that
510 ((> left right
)) ; Quit
512 (let (depl square0 square1 square2 count delta
)
513 (setq depl
(landmark-xy-to-index dx dy
)
514 square0
(+ square
(* left depl
))
515 square1
(+ square
(* right depl
))
516 square2
(+ square0
(* 4 depl
)))
517 ;; Compute the contents of the first qtuple:
520 (while (<= square square2
)
521 (setq count
(+ count
(aref landmark-board square
))
522 square
(+ square depl
)))
523 (while (<= square0 square1
)
524 ;; Update the squares of the qtuple beginning in SQUARE0 and ending
526 (setq delta
(- (aref landmark-score-trans-table count
)
527 (aref landmark-score-trans-table
(- count dval
))))
528 (cond ((not (zerop delta
)) ; or else nothing to update
529 (setq square square0
)
530 (while (<= square square2
)
531 (if (zerop (aref landmark-board square
)) ; only for free squares
532 (aset landmark-score-table square
533 (+ (aref landmark-score-table square
) delta
)))
534 (setq square
(+ square depl
)))))
535 ;; Then shift the qtuple one square along DEPL, this only requires
536 ;; modifying SQUARE0 and SQUARE2.
537 (setq square2
(+ square2 depl
)
538 count
(+ count
(- (aref landmark-board square0
))
539 (aref landmark-board square2
))
540 square0
(+ square0 depl
)))))))
546 ;; Several variables are used to monitor a game, including a GAME-HISTORY (the
547 ;; list of all (SQUARE . PREVSCORE) played) that allows to take moves back
548 ;; (anti-updating the score table) and to compute the table from scratch in
549 ;; case of an interruption.
551 (defvar landmark-game-in-progress nil
552 "Non-nil if a game is in progress.")
554 (defvar landmark-game-history nil
555 "A record of all moves that have been played during current game.")
557 (defvar landmark-number-of-moves nil
558 "Number of moves already played in current game.")
560 (defvar landmark-number-of-human-moves nil
561 "Number of moves already played by human in current game.")
563 (defvar landmark-emacs-played-first nil
564 "Non-nil if Emacs played first.")
566 (defvar landmark-human-took-back nil
567 "Non-nil if Human took back a move during the game.")
569 (defvar landmark-human-refused-draw nil
570 "Non-nil if Human refused Emacs offer of a draw.")
572 (defvar landmark-emacs-is-computing nil
573 ;; This is used to detect interruptions. Hopefully, it should not be needed.
574 "Non-nil if Emacs is in the middle of a computation.")
577 (defun landmark-start-game (n m
)
578 "Initialize a new game on an N by M board."
579 (setq landmark-emacs-is-computing t
) ; Raise flag
580 (setq landmark-game-in-progress t
)
581 (setq landmark-board-width n
582 landmark-board-height m
583 landmark-vector-length
(1+ (* (+ m
2) (1+ n
)))
584 landmark-draw-limit
(/ (* 7 n m
) 10))
585 (setq landmark-emacs-won nil
586 landmark-game-history nil
587 landmark-number-of-moves
0
588 landmark-number-of-human-moves
0
589 landmark-emacs-played-first nil
590 landmark-human-took-back nil
591 landmark-human-refused-draw nil
)
592 (landmark-init-display n m
) ; Display first: the rest takes time
593 (landmark-init-score-table) ; INIT-BOARD requires that the score
594 (landmark-init-board) ; table be already created.
595 (setq landmark-emacs-is-computing nil
))
597 (defun landmark-play-move (square val
&optional dont-update-score
)
598 "Go to SQUARE, play VAL and update everything."
599 (setq landmark-emacs-is-computing t
) ; Raise flag
600 (cond ((= 1 val
) ; a Human move
601 (setq landmark-number-of-human-moves
(1+ landmark-number-of-human-moves
)))
602 ((zerop landmark-number-of-moves
) ; an Emacs move. Is it first ?
603 (setq landmark-emacs-played-first t
)))
604 (setq landmark-game-history
605 (cons (cons square
(aref landmark-score-table square
))
606 landmark-game-history
)
607 landmark-number-of-moves
(1+ landmark-number-of-moves
))
608 (landmark-plot-square square val
)
609 (aset landmark-board square val
) ; *BEFORE* UPDATE-SCORE !
610 (if dont-update-score nil
611 (landmark-update-score-table square val
) ; previous val was 0: dval = val
612 (aset landmark-score-table square -
1))
613 (setq landmark-emacs-is-computing nil
))
615 (defun landmark-take-back ()
616 "Take back last move and update everything."
617 (setq landmark-emacs-is-computing t
)
618 (let* ((last-move (car landmark-game-history
))
619 (square (car last-move
))
620 (oldval (aref landmark-board square
)))
622 (setq landmark-number-of-human-moves
(1- landmark-number-of-human-moves
)))
623 (setq landmark-game-history
(cdr landmark-game-history
)
624 landmark-number-of-moves
(1- landmark-number-of-moves
))
625 (landmark-plot-square square
0)
626 (aset landmark-board square
0) ; *BEFORE* UPDATE-SCORE !
627 (landmark-update-score-table square
(- oldval
))
628 (aset landmark-score-table square
(cdr last-move
)))
629 (setq landmark-emacs-is-computing nil
))
632 ;;;_ + SESSION CONTROL.
634 (defvar landmark-number-of-trials
0
635 "The number of times that landmark has been run.")
637 (defvar landmark-sum-of-moves
0
638 "The total number of moves made in all games.")
640 (defvar landmark-number-of-emacs-wins
0
641 "Number of games Emacs won in this session.")
643 (defvar landmark-number-of-human-wins
0
644 "Number of games you won in this session.")
646 (defvar landmark-number-of-draws
0
647 "Number of games already drawn in this session.")
650 (defun landmark-terminate-game (result)
651 "Terminate the current game with RESULT."
652 (setq landmark-number-of-trials
(1+ landmark-number-of-trials
))
653 (setq landmark-sum-of-moves
(+ landmark-sum-of-moves landmark-number-of-moves
))
654 (if (eq result
'crash-game
)
656 "Sorry, I have been interrupted and cannot resume that game..."))
657 (landmark-display-statistics)
659 (setq landmark-game-in-progress nil
))
661 (defun landmark-crash-game ()
662 "What to do when Emacs detects it has been interrupted."
663 (setq landmark-emacs-is-computing nil
)
664 (landmark-terminate-game 'crash-game
)
665 (sit-for 4) ; Let's see the message
666 (landmark-prompt-for-other-game))
669 ;;;_ + INTERACTIVE COMMANDS.
671 (defun landmark-emacs-plays ()
672 "Compute Emacs next move and play it."
674 (landmark-switch-to-window)
676 (landmark-emacs-is-computing
677 (landmark-crash-game))
678 ((not landmark-game-in-progress
)
679 (landmark-prompt-for-other-game))
681 (message "Let me think...")
683 (setq square
(landmark-strongest-square))
685 (landmark-terminate-game 'nobody-won
))
687 (setq score
(aref landmark-score-table square
))
688 (landmark-play-move square
6)
689 (cond ((>= score landmark-winning-threshold
)
690 (setq landmark-emacs-won t
) ; for font-lock
691 (landmark-find-filled-qtuple square
6)
692 (landmark-terminate-game 'emacs-won
))
694 (landmark-terminate-game 'nobody-won
))
695 ((and (> landmark-number-of-moves landmark-draw-limit
)
696 (not landmark-human-refused-draw
)
697 (landmark-offer-a-draw))
698 (landmark-terminate-game 'draw-agreed
))
700 (landmark-prompt-for-move)))))))))
702 ;; For small square dimensions this is approximate, since though measured in
703 ;; pixels, event's (X . Y) is a character's top-left corner.
704 (defun landmark-click (click)
705 "Position at the square where you click."
707 (and (windowp (posn-window (setq click
(event-end click
))))
708 (numberp (posn-point click
))
709 (select-window (posn-window click
))
710 (setq click
(posn-col-row click
))
712 (min (max (/ (+ (- (car click
)
716 landmark-square-width
717 (% landmark-square-width
2)
718 (/ landmark-square-width
2))
719 landmark-square-width
)
721 landmark-board-width
)
722 (min (max (/ (+ (- (cdr click
)
725 (let ((inhibit-point-motion-hooks t
))
726 (count-lines 1 (window-start)))
727 landmark-square-height
728 (% landmark-square-height
2)
729 (/ landmark-square-height
2))
730 landmark-square-height
)
732 landmark-board-height
))))
734 (defun landmark-mouse-play (click)
735 "Play at the square where you click."
737 (if (landmark-click click
)
738 (landmark-human-plays)))
740 (defun landmark-human-plays ()
741 "Signal to the Landmark program that you have played.
742 You must have put the cursor on the square where you want to play.
743 If the game is finished, this command requests for another game."
745 (landmark-switch-to-window)
747 (landmark-emacs-is-computing
748 (landmark-crash-game))
749 ((not landmark-game-in-progress
)
750 (landmark-prompt-for-other-game))
753 (setq square
(landmark-point-square))
755 (error "Your point is not on a square. Retry!"))
756 ((not (zerop (aref landmark-board square
)))
757 (error "Your point is not on a free square. Retry!"))
759 (setq score
(aref landmark-score-table square
))
760 (landmark-play-move square
1)
761 (cond ((and (>= score landmark-losing-threshold
)
762 ;; Just testing SCORE > THRESHOLD is not enough for
763 ;; detecting wins, it just gives an indication that
764 ;; we confirm with LANDMARK-FIND-FILLED-QTUPLE.
765 (landmark-find-filled-qtuple square
1))
766 (landmark-terminate-game 'human-won
))
768 (landmark-emacs-plays)))))))))
770 (defun landmark-human-takes-back ()
771 "Signal to the Landmark program that you wish to take back your last move."
773 (landmark-switch-to-window)
775 (landmark-emacs-is-computing
776 (landmark-crash-game))
777 ((not landmark-game-in-progress
)
778 (message "Too late for taking back...")
780 (landmark-prompt-for-other-game))
781 ((zerop landmark-number-of-human-moves
)
782 (message "You have not played yet... Your move?"))
784 (message "One moment, please...")
785 ;; It is possible for the user to let Emacs play several consecutive
786 ;; moves, so that the best way to know when to stop taking back moves is
787 ;; to count the number of human moves:
788 (setq landmark-human-took-back t
)
789 (let ((number landmark-number-of-human-moves
))
790 (while (= number landmark-number-of-human-moves
)
791 (landmark-take-back)))
792 (landmark-prompt-for-move))))
794 (defun landmark-human-resigns ()
795 "Signal to the Landmark program that you may want to resign."
797 (landmark-switch-to-window)
799 (landmark-emacs-is-computing
800 (landmark-crash-game))
801 ((not landmark-game-in-progress
)
802 (message "There is no game in progress"))
803 ((y-or-n-p "You mean, you resign? ")
804 (landmark-terminate-game 'human-resigned
))
805 ((y-or-n-p "You mean, we continue? ")
806 (landmark-prompt-for-move))
808 (landmark-terminate-game 'human-resigned
)))) ; OK. Accept it
810 ;;;_ + PROMPTING THE HUMAN PLAYER.
812 (defun landmark-prompt-for-move ()
813 "Display a message asking for Human's move."
814 (message (if (zerop landmark-number-of-human-moves
)
815 "Your move? (move to a free square and hit X, RET ...)"
818 (defun landmark-prompt-for-other-game ()
819 "Ask for another game, and start it."
820 (if (y-or-n-p "Another game? ")
821 (if (y-or-n-p "Retain learned weights ")
824 (message "Chicken!")))
826 (defun landmark-offer-a-draw ()
827 "Offer a draw and return t if Human accepted it."
828 (or (y-or-n-p "I offer you a draw. Do you accept it? ")
829 (not (setq landmark-human-refused-draw t
))))
832 (defun landmark-max-width ()
833 "Largest possible board width for the current window."
834 (1+ (/ (- (window-width)
835 landmark-x-offset landmark-x-offset
1)
836 landmark-square-width
)))
838 (defun landmark-max-height ()
839 "Largest possible board height for the current window."
840 (1+ (/ (- (window-height)
841 landmark-y-offset landmark-y-offset
2)
842 ;; 2 instead of 1 because WINDOW-HEIGHT includes the mode line !
843 landmark-square-height
)))
845 (defun landmark-point-y ()
846 "Return the board row where point is."
847 (let ((inhibit-point-motion-hooks t
))
848 (1+ (/ (- (count-lines 1 (point)) landmark-y-offset
(if (bolp) 0 1))
849 landmark-square-height
))))
851 (defun landmark-point-square ()
852 "Return the index of the square point is on."
853 (let ((inhibit-point-motion-hooks t
))
854 (landmark-xy-to-index (1+ (/ (- (current-column) landmark-x-offset
)
855 landmark-square-width
))
856 (landmark-point-y))))
858 (defun landmark-goto-square (index)
859 "Move point to square number INDEX."
860 (landmark-goto-xy (landmark-index-to-x index
) (landmark-index-to-y index
)))
862 (defun landmark-goto-xy (x y
)
863 "Move point to square at X, Y coords."
864 (let ((inhibit-point-motion-hooks t
))
865 (goto-char (point-min))
866 (forward-line (+ landmark-y-offset
(* landmark-square-height
(1- y
)))))
867 (move-to-column (+ landmark-x-offset
(* landmark-square-width
(1- x
)))))
869 (defun landmark-plot-square (square value
)
870 "Draw 'X', 'O' or '.' on SQUARE depending on VALUE, leave point there."
872 (landmark-goto-square square
))
873 (let ((inhibit-read-only t
)
874 (inhibit-point-motion-hooks t
))
875 (insert-and-inherit (cond ((= value
1) ?.
)
883 (add-text-properties (1- (point)) (point)
884 '(mouse-face highlight
886 mouse-1: get robot moving, mouse-2: play on this square")))
889 (sit-for 0)) ; Display NOW
891 (defun landmark-init-display (n m
)
892 "Display an N by M Landmark board."
893 (buffer-disable-undo (current-buffer))
894 (let ((inhibit-read-only t
)
898 ;; Try to minimize number of chars (because of text properties)
900 (if (zerop (% landmark-x-offset landmark-square-width
))
901 landmark-square-width
902 (max (/ (+ (% landmark-x-offset landmark-square-width
)
903 landmark-square-width
1) 2) 2)))
905 (newline landmark-y-offset
)
908 x
(- landmark-x-offset landmark-square-width
))
909 (while (>= (setq j
(1- j
)) 0)
910 (insert-char ?
\t (/ (- (setq x
(+ x landmark-square-width
))
913 (insert-char ?
(- x
(current-column)))
914 (if (setq intangible
(not intangible
))
915 (put-text-property point
(point) 'intangible
2))
920 (append-to-buffer (current-buffer) opoint
(point))
922 (goto-char (point-max))))
925 (add-text-properties point
(point)
926 '(mouse-face highlight help-echo
"\
927 mouse-1: get robot moving, mouse-2: play on this square")))
928 (> (setq i
(1- i
)) 0))
931 (insert-char ?
\n landmark-square-height
))
932 (or (eq (char-after 1) ?.
)
933 (put-text-property 1 2 'point-entered
934 (lambda (_x _y
) (if (bobp) (forward-char)))))
936 (put-text-property point
(point) 'intangible
2))
937 (put-text-property point
(point) 'point-entered
938 (lambda (_x _y
) (if (eobp) (backward-char))))
939 (put-text-property (point-min) (point) 'category
'landmark-mode
))
940 (landmark-goto-xy (/ (1+ n
) 2) (/ (1+ m
) 2)) ; center of the board
941 (sit-for 0)) ; Display NOW
943 (defun landmark-display-statistics ()
944 "Obnoxiously display some statistics about previous games in mode line."
945 ;; We store this string in the mode-line-process local variable.
946 ;; This is certainly not the cleanest way out ...
947 (setq mode-line-process
948 (format ": Trials: %d, Avg#Moves: %d"
949 landmark-number-of-trials
950 (if (zerop landmark-number-of-trials
)
952 (/ landmark-sum-of-moves landmark-number-of-trials
))))
953 (force-mode-line-update))
955 (defun landmark-switch-to-window ()
956 "Find or create the Landmark buffer, and display it."
958 (let ((buff (get-buffer "*Landmark*")))
959 (if buff
; Buffer exists:
960 (switch-to-buffer buff
) ; no problem.
961 (if landmark-game-in-progress
962 (landmark-crash-game)) ; buffer has been killed or something
963 (switch-to-buffer "*Landmark*") ; Anyway, start anew.
967 ;;;_ + CROSSING WINNING QTUPLES.
969 ;; When someone succeeds in filling a qtuple, we draw a line over the five
970 ;; corresponding squares. One problem is that the program does not know which
971 ;; squares ! It only knows the square where the last move has been played and
972 ;; who won. The solution is to scan the board along all four directions.
974 (defun landmark-find-filled-qtuple (square value
)
975 "Return t if SQUARE belongs to a qtuple filled with VALUEs."
976 (or (landmark-check-filled-qtuple square value
1 0)
977 (landmark-check-filled-qtuple square value
0 1)
978 (landmark-check-filled-qtuple square value
1 1)
979 (landmark-check-filled-qtuple square value -
1 1)))
981 (defun landmark-check-filled-qtuple (square value dx dy
)
982 "Return t if SQUARE belongs to a qtuple filled with VALUEs along DX, DY."
984 (left square
) (right square
)
985 (depl (landmark-xy-to-index dx dy
)))
986 (while (and (> a -
4) ; stretch tuple left
987 (= value
(aref landmark-board
(setq left
(- left depl
)))))
989 (while (and (< b
(+ a
4)) ; stretch tuple right
990 (= value
(aref landmark-board
(setq right
(+ right depl
)))))
992 (cond ((= b
(+ a
4)) ; tuple length = 5 ?
993 (landmark-cross-qtuple (+ square
(* a depl
)) (+ square
(* b depl
))
997 (defun landmark-cross-qtuple (square1 square2 dx dy
)
998 "Cross every square between SQUARE1 and SQUARE2 in the DX, DY direction."
999 (save-excursion ; Not moving point from last square
1000 (let ((depl (landmark-xy-to-index dx dy
))
1001 (inhibit-read-only t
)
1002 (inhibit-point-motion-hooks t
))
1003 ;; WARNING: this function assumes DEPL > 0 and SQUARE2 > SQUARE1
1004 (while (/= square1 square2
)
1005 (landmark-goto-square square1
)
1006 (setq square1
(+ square1 depl
))
1008 ((= dy
0) ; Horizontal
1010 (insert-char ?-
(1- landmark-square-width
) t
)
1011 (delete-region (point) (progn
1012 (skip-chars-forward " \t")
1014 ((= dx
0) ; Vertical
1015 (let ((landmark-n 1)
1016 (column (current-column)))
1017 (while (< landmark-n landmark-square-height
)
1018 (setq landmark-n
(1+ landmark-n
))
1021 (insert-and-inherit ?|
))))
1022 ((= dx -
1) ; 1st Diagonal
1023 (indent-to (prog1 (- (current-column) (/ landmark-square-width
2))
1024 (forward-line (/ landmark-square-height
2))))
1025 (insert-and-inherit ?
/))
1027 (indent-to (prog1 (+ (current-column) (/ landmark-square-width
2))
1028 (forward-line (/ landmark-square-height
2))))
1029 (insert-and-inherit ?
\\))))))
1030 (sit-for 0)) ; Display NOW
1033 ;;;_ + CURSOR MOTION.
1035 ;; previous-line and next-line don't work right with intangible newlines
1036 (defun landmark-move-down ()
1037 "Move point down one row on the Landmark board."
1039 (if (< (landmark-point-y) landmark-board-height
)
1040 (let ((col (current-column)))
1041 (forward-line 1) ;;; landmark-square-height
1042 (move-to-column col
))))
1044 (defun landmark-move-up ()
1045 "Move point up one row on the Landmark board."
1047 (if (> (landmark-point-y) 1)
1048 (let ((col (current-column)))
1049 (forward-line (- landmark-square-height
))
1050 (move-to-column col
))))
1052 (defun landmark-move-ne ()
1053 "Move point North East on the Landmark board."
1058 (defun landmark-move-se ()
1059 "Move point South East on the Landmark board."
1061 (landmark-move-down)
1064 (defun landmark-move-nw ()
1065 "Move point North West on the Landmark board."
1070 (defun landmark-move-sw ()
1071 "Move point South West on the Landmark board."
1073 (landmark-move-down)
1076 (defun landmark-beginning-of-line ()
1077 "Move point to first square on the Landmark board row."
1079 (move-to-column landmark-x-offset
))
1081 (defun landmark-end-of-line ()
1082 "Move point to last square on the Landmark board row."
1084 (move-to-column (+ landmark-x-offset
1085 (* landmark-square-width
(1- landmark-board-width
)))))
1088 ;;;_ + Simulation variables
1090 ;;;_ - landmark-nvar
1091 (defvar landmark-nvar
0.0075
1093 Affects a noise generator which was used in an earlier incarnation of
1094 this program to add a random element to the way moves were made.")
1095 ;;;_ - lists of cardinal directions
1097 (defvar landmark-ns
'(landmark-n landmark-s
)
1098 "Used when doing something relative to the north and south axes.")
1099 (defvar landmark-ew
'(landmark-e landmark-w
)
1100 "Used when doing something relative to the east and west axes.")
1101 (defvar landmark-directions
'(landmark-n landmark-s landmark-e landmark-w
)
1102 "The cardinal directions.")
1103 (defvar landmark-8-directions
1104 '((landmark-n) (landmark-n landmark-w
) (landmark-w) (landmark-s landmark-w
)
1105 (landmark-s) (landmark-s landmark-e
) (landmark-e) (landmark-n landmark-e
))
1106 "The full 8 possible directions.")
1108 (defvar landmark-number-of-moves
1109 "The number of moves made by the robot so far.")
1112 ;;;_* Terry's mods to create lm.el
1114 ;;;(setq landmark-debug nil)
1115 (defvar landmark-debug nil
1116 "If non-nil, debugging is printed.")
1117 (defcustom landmark-one-moment-please nil
1118 "If non-nil, print \"One moment please\" when a new board is generated.
1119 The drawback of this is you don't see how many moves the last run took
1120 because it is overwritten by \"One moment please\"."
1123 (defcustom landmark-output-moves t
1124 "If non-nil, output number of moves so far on a move-by-move basis."
1129 (defun landmark-weights-debug ()
1131 (progn (landmark-print-wts) (landmark-blackbox) (landmark-print-y-s-noise)
1132 (landmark-print-smell))))
1134 ;;;_ - Printing various things
1135 (defun landmark-print-distance-int (direction)
1137 (insert (format "%S %S " direction
(get direction
'distance
))))
1140 (defun landmark-print-distance ()
1141 (insert (format "tree: %S \n" (calc-distance-of-robot-from 'landmark-tree
)))
1142 (mapc 'landmark-print-distance-int landmark-directions
))
1145 ;;(setq direction 'landmark-n)
1146 ;;(get 'landmark-n 'landmark-s)
1147 (defun landmark-nslify-wts-int (direction)
1148 (mapcar (lambda (target-direction)
1149 (get direction target-direction
))
1150 landmark-directions
))
1153 (defun landmark-nslify-wts ()
1155 (let ((l (apply 'append
(mapcar 'landmark-nslify-wts-int landmark-directions
))))
1156 (insert (format "set data_value WTS \n %s \n" l
))
1157 (insert (format "/* max: %S min: %S */"
1158 (eval (cons 'max l
)) (eval (cons 'min l
))))))
1160 (defun landmark-print-wts-int (direction)
1161 (mapc (lambda (target-direction)
1162 (insert (format "%S %S %S "
1165 (get direction target-direction
))))
1166 landmark-directions
)
1169 (defun landmark-print-wts ()
1171 (with-current-buffer "*landmark-wts*"
1172 (insert "==============================\n")
1173 (mapc 'landmark-print-wts-int landmark-directions
)))
1175 (defun landmark-print-moves (moves)
1177 (with-current-buffer "*landmark-moves*"
1178 (insert (format "%S\n" moves
))))
1181 (defun landmark-print-y-s-noise-int (direction)
1182 (insert (format "%S:landmark-y %S, s %S, noise %S \n"
1183 (symbol-name direction
)
1184 (get direction
'y_t
)
1186 (get direction
'noise
)
1189 (defun landmark-print-y-s-noise ()
1191 (with-current-buffer "*landmark-y,s,noise*"
1192 (insert "==============================\n")
1193 (mapc 'landmark-print-y-s-noise-int landmark-directions
)))
1195 (defun landmark-print-smell-int (direction)
1196 (insert (format "%S: smell: %S \n"
1197 (symbol-name direction
)
1198 (get direction
'smell
))))
1200 (defun landmark-print-smell ()
1202 (with-current-buffer "*landmark-smell*"
1203 (insert "==============================\n")
1204 (insert (format "tree: %S \n" (get 'z
't
)))
1205 (mapc 'landmark-print-smell-int landmark-directions
)))
1207 (defun landmark-print-w0-int (direction)
1208 (insert (format "%S: w0: %S \n"
1209 (symbol-name direction
)
1210 (get direction
'w0
))))
1212 (defun landmark-print-w0 ()
1214 (with-current-buffer "*landmark-w0*"
1215 (insert "==============================\n")
1216 (mapc 'landmark-print-w0-int landmark-directions
)))
1218 (defun landmark-blackbox ()
1219 (with-current-buffer "*landmark-blackbox*"
1220 (insert "==============================\n")
1221 (insert "I smell: ")
1222 (mapc (lambda (direction)
1223 (if (> (get direction
'smell
) 0)
1224 (insert (format "%S " direction
))))
1225 landmark-directions
)
1229 (mapc (lambda (direction)
1230 (if (> (get direction
'y_t
) 0)
1231 (insert (format "%S " direction
))))
1232 landmark-directions
)
1234 (landmark-print-wts-blackbox)
1235 (insert (format "z_t-z_t-1: %S" (- (get 'z
't
) (get 'z
't-1
))))
1236 (landmark-print-distance)
1239 (defun landmark-print-wts-blackbox ()
1241 (mapc 'landmark-print-wts-int landmark-directions
))
1243 ;;;_ - learning parameters
1244 (defcustom landmark-bound
0.005
1245 "The maximum that w0j may be."
1248 (defcustom landmark-c
1.0
1249 "A factor applied to modulate the increase in wij.
1250 Used in the function landmark-update-normal-weights."
1253 (defcustom landmark-c-naught
0.5
1254 "A factor applied to modulate the increase in w0j.
1255 Used in the function landmark-update-naught-weights."
1258 (defvar landmark-initial-w0
0.0)
1259 (defvar landmark-initial-wij
0.0)
1260 (defcustom landmark-no-payoff
0
1261 "The amount of simulation cycles that have occurred with no movement.
1262 Used to move the robot when he is stuck in a rut for some reason."
1265 (defcustom landmark-max-stall-time
2
1266 "The maximum number of cycles that the robot can remain stuck in a place.
1267 After this limit is reached, landmark-random-move is called to push him out of it."
1272 ;;;_ + Randomizing functions
1273 ;;;_ - landmark-flip-a-coin ()
1274 (defun landmark-flip-a-coin ()
1275 (if (> (random 5000) 2500)
1278 ;;;_ : landmark-very-small-random-number ()
1279 ;(defun landmark-very-small-random-number ()
1281 ; (* (/ (random 900000) 900000.0) .0001)))
1282 ;;;_ : landmark-randomize-weights-for (direction)
1283 (defun landmark-randomize-weights-for (direction)
1284 (mapc (lambda (target-direction)
1287 (* (landmark-flip-a-coin) (/ (random 10000) 10000.0))))
1288 landmark-directions
))
1289 ;;;_ : landmark-noise ()
1290 (defun landmark-noise ()
1291 (* (- (/ (random 30001) 15000.0) 1) landmark-nvar
))
1293 ;;;_ : landmark-fix-weights-for (direction)
1294 (defun landmark-fix-weights-for (direction)
1295 (mapc (lambda (target-direction)
1298 landmark-initial-wij
))
1299 landmark-directions
))
1302 ;;;_ + Plotting functions
1303 ;;;_ - landmark-plot-internal (sym)
1304 (defun landmark-plot-internal (sym)
1305 (landmark-plot-square (landmark-xy-to-index
1309 ;;;_ - landmark-plot-landmarks ()
1310 (defun landmark-plot-landmarks ()
1311 (setq landmark-cx
(/ landmark-board-width
2))
1312 (setq landmark-cy
(/ landmark-board-height
2))
1314 (put 'landmark-n
'x landmark-cx
)
1315 (put 'landmark-n
'y
1)
1316 (put 'landmark-n
'sym
2)
1318 (put 'landmark-tree
'x landmark-cx
)
1319 (put 'landmark-tree
'y landmark-cy
)
1320 (put 'landmark-tree
'sym
6)
1322 (put 'landmark-s
'x landmark-cx
)
1323 (put 'landmark-s
'y landmark-board-height
)
1324 (put 'landmark-s
'sym
3)
1326 (put 'landmark-w
'x
1)
1327 (put 'landmark-w
'y
(/ landmark-board-height
2))
1328 (put 'landmark-w
'sym
5)
1330 (put 'landmark-e
'x landmark-board-width
)
1331 (put 'landmark-e
'y
(/ landmark-board-height
2))
1332 (put 'landmark-e
'sym
4)
1334 (mapc 'landmark-plot-internal
'(landmark-n landmark-s landmark-e landmark-w landmark-tree
)))
1338 ;;;_ + Distance-calculation functions
1343 ;;;_ - distance (x x0 y y0)
1344 (defun distance (x x0 y y0
)
1345 (sqrt (+ (square (- x x0
)) (square (- y y0
)))))
1347 ;;;_ - calc-distance-of-robot-from (direction)
1348 (defun calc-distance-of-robot-from (direction)
1349 (put direction
'distance
1350 (distance (get direction
'x
)
1351 (landmark-index-to-x (landmark-point-square))
1353 (landmark-index-to-y (landmark-point-square)))))
1355 ;;;_ - calc-smell-internal (sym)
1356 (defun calc-smell-internal (sym)
1357 (let ((r (get sym
'r
))
1358 (d (calc-distance-of-robot-from sym
)))
1359 (if (> (* 0.5 (- 1 (/ d r
))) 0)
1360 (* 0.5 (- 1 (/ d r
)))
1364 ;;;_ + Learning (neural) functions
1365 (defun landmark-f (x)
1367 ((> x landmark-bound
) landmark-bound
)
1371 (defun landmark-y (direction)
1372 (put direction
'noise
(landmark-noise))
1374 (if (> (get direction
's
) 0.0)
1378 (defun landmark-update-normal-weights (direction)
1379 (mapc (lambda (target-direction)
1380 (put direction target-direction
1382 (get direction target-direction
)
1384 (- (get 'z
't
) (get 'z
't-1
))
1385 (get target-direction
'y_t
)
1386 (get direction
'smell
)))))
1387 landmark-directions
))
1389 (defun landmark-update-naught-weights (direction)
1390 (mapc (lambda (_target-direction)
1395 (* landmark-c-naught
1396 (- (get 'z
't
) (get 'z
't-1
))
1397 (get direction
'y_t
))))))
1398 landmark-directions
))
1401 ;;;_ + Statistics gathering and creating functions
1403 (defun landmark-calc-current-smells ()
1404 (mapc (lambda (direction)
1405 (put direction
'smell
(calc-smell-internal direction
)))
1406 landmark-directions
))
1408 (defun landmark-calc-payoff ()
1409 (put 'z
't-1
(get 'z
't
))
1410 (put 'z
't
(calc-smell-internal 'landmark-tree
))
1411 (if (= (- (get 'z
't
) (get 'z
't-1
)) 0.0)
1412 (cl-incf landmark-no-payoff
)
1413 (setf landmark-no-payoff
0)))
1415 (defun landmark-store-old-y_t ()
1416 (mapc (lambda (direction)
1417 (put direction
'y_t-1
(get direction
'y_t
)))
1418 landmark-directions
))
1421 ;;;_ + Functions to move robot
1423 (defun landmark-confidence-for (target-direction)
1425 (get target-direction
'w0
)
1426 (mapcar (lambda (direction)
1428 (get direction target-direction
)
1429 (get direction
'smell
)))
1430 landmark-directions
)))
1433 (defun landmark-calc-confidences ()
1434 (mapc (lambda (direction)
1435 (put direction
's
(landmark-confidence-for direction
)))
1436 landmark-directions
))
1438 (defun landmark-move ()
1439 (if (and (= (get 'landmark-n
'y_t
) 1.0) (= (get 'landmark-s
'y_t
) 1.0))
1441 (mapc (lambda (dir) (put dir
'y_t
0)) landmark-ns
)
1443 (message "n-s normalization."))))
1444 (if (and (= (get 'landmark-w
'y_t
) 1.0) (= (get 'landmark-e
'y_t
) 1.0))
1446 (mapc (lambda (dir) (put dir
'y_t
0)) landmark-ew
)
1448 (message "e-w normalization"))))
1450 (mapc (lambda (pair)
1451 (if (> (get (car pair
) 'y_t
) 0)
1452 (funcall (car (cdr pair
)))))
1454 (landmark-n landmark-move-up
)
1455 (landmark-s landmark-move-down
)
1456 (landmark-e forward-char
)
1457 (landmark-w backward-char
)))
1458 (landmark-plot-square (landmark-point-square) 1)
1459 (cl-incf landmark-number-of-moves
)
1460 (if landmark-output-moves
1461 (message "Moves made: %d" landmark-number-of-moves
)))
1464 (defun landmark-random-move ()
1466 (lambda (direction) (put direction
'y_t
0))
1467 landmark-directions
)
1468 (dolist (direction (nth (random 8) landmark-8-directions
))
1469 (put direction
'y_t
1.0))
1472 (defun landmark-amble-robot ()
1474 (while (> (calc-distance-of-robot-from 'landmark-tree
) 0)
1476 (landmark-store-old-y_t)
1477 (landmark-calc-current-smells)
1479 (if (> landmark-no-payoff landmark-max-stall-time
)
1480 (landmark-random-move)
1482 (landmark-calc-confidences)
1483 (mapc 'landmark-y landmark-directions
)
1486 (landmark-calc-payoff)
1488 (mapc 'landmark-update-normal-weights landmark-directions
)
1489 (mapc 'landmark-update-naught-weights landmark-directions
)
1491 (landmark-weights-debug)))
1492 (landmark-terminate-game nil
))
1495 ;;;_ - landmark-start-robot ()
1496 (defun landmark-start-robot ()
1497 "Signal to the Landmark program that you have played.
1498 You must have put the cursor on the square where you want to play.
1499 If the game is finished, this command requests for another game."
1501 (landmark-switch-to-window)
1503 (landmark-emacs-is-computing
1504 (landmark-crash-game))
1505 ((not landmark-game-in-progress
)
1506 (landmark-prompt-for-other-game))
1509 (setq square
(landmark-point-square))
1510 (cond ((null square
)
1511 (error "Your point is not on a square. Retry!"))
1512 ((not (zerop (aref landmark-board square
)))
1513 (error "Your point is not on a free square. Retry!"))
1516 (landmark-plot-square square
1)
1518 (landmark-store-old-y_t)
1519 (landmark-calc-current-smells)
1520 (put 'z
't
(calc-smell-internal 'landmark-tree
))
1522 (landmark-random-move)
1524 (landmark-calc-payoff)
1526 (mapc 'landmark-update-normal-weights landmark-directions
)
1527 (mapc 'landmark-update-naught-weights landmark-directions
)
1528 (landmark-amble-robot)
1532 ;;;_ + Misc functions
1533 ;;;_ - landmark-init (auto-start save-weights)
1534 (defvar landmark-tree-r
"")
1536 (defun landmark-init (auto-start save-weights
)
1538 (setq landmark-number-of-moves
0)
1540 (landmark-plot-landmarks)
1543 (save-current-buffer
1544 (set-buffer (get-buffer-create "*landmark-w0*"))
1546 (set-buffer (get-buffer-create "*landmark-moves*"))
1547 (set-buffer (get-buffer-create "*landmark-wts*"))
1549 (set-buffer (get-buffer-create "*landmark-y,s,noise*"))
1551 (set-buffer (get-buffer-create "*landmark-smell*"))
1553 (set-buffer (get-buffer-create "*landmark-blackbox*"))
1555 (set-buffer (get-buffer-create "*landmark-distance*"))
1559 (landmark-set-landmark-signal-strengths)
1561 (dolist (direction landmark-directions
)
1562 (put direction
'y_t
0.0))
1564 (if (not save-weights
)
1566 (mapc 'landmark-fix-weights-for landmark-directions
)
1567 (dolist (direction landmark-directions
)
1568 (put direction
'w0 landmark-initial-w0
)))
1569 (message "Weights preserved for this run."))
1573 (landmark-goto-xy (1+ (random landmark-board-width
)) (1+ (random landmark-board-height
)))
1574 (landmark-start-robot))))
1577 ;;;_ - something which doesn't work
1579 ;(defun landmark-sum-list (list)
1580 ; (if (> (length list) 0)
1581 ; (+ (car list) (landmark-sum-list (cdr list)))
1584 ; (eval (cons '+ list))
1585 ;;;_ - landmark-set-landmark-signal-strengths ()
1586 ;; on a screen higher than wide, I noticed that the robot would amble
1587 ;; left and right and not move forward. examining *landmark-blackbox*
1588 ;; revealed that there was no scent from the north and south
1589 ;; landmarks, hence, they need less factoring down of the effect of
1590 ;; distance on scent.
1592 (defun landmark-set-landmark-signal-strengths ()
1593 (setq landmark-tree-r
(* (sqrt (+ (square landmark-cx
) (square landmark-cy
))) 1.5))
1594 (mapc (lambda (direction)
1595 (put direction
'r
(* landmark-cx
1.1)))
1597 (mapc (lambda (direction)
1598 (put direction
'r
(* landmark-cy
1.1)))
1600 (put 'landmark-tree
'r landmark-tree-r
))
1603 ;;;_ + landmark-test-run ()
1606 (defalias 'landmark-repeat
'landmark-test-run
)
1608 (defun landmark-test-run ()
1609 "Run 100 Landmark games, each time saving the weights from the previous game."
1612 (dotimes (scratch-var 100)
1616 (defun landmark (parg)
1617 "Start or resume an Landmark game.
1618 If a game is in progress, this command allows you to resume it.
1619 Here is the relation between prefix args and game options:
1621 prefix arg | robot is auto-started | weights are saved from last game
1622 ---------------------------------------------------------------------
1628 You start by moving to a square and typing \\[landmark-start-robot],
1629 if you did not use a prefix arg to ask for automatic start.
1630 Use \\[describe-mode] for more info."
1633 (setf landmark-n nil landmark-m nil
)
1634 (landmark-switch-to-window)
1636 (landmark-emacs-is-computing
1637 (landmark-crash-game))
1638 ((or (not landmark-game-in-progress
)
1639 (<= landmark-number-of-moves
2))
1640 (let ((max-width (landmark-max-width))
1641 (max-height (landmark-max-height)))
1642 (or landmark-n
(setq landmark-n max-width
))
1643 (or landmark-m
(setq landmark-m max-height
))
1644 (cond ((< landmark-n
1)
1645 (error "I need at least 1 column"))
1647 (error "I need at least 1 row"))
1648 ((> landmark-n max-width
)
1649 (error "I cannot display %d columns in that window" landmark-n
)))
1650 (if (and (> landmark-m max-height
)
1651 (not (eq landmark-m landmark-saved-board-height
))
1652 ;; Use EQ because SAVED-BOARD-HEIGHT may be nil
1653 (not (y-or-n-p (format "Do you really want %d rows? " landmark-m
))))
1654 (setq landmark-m max-height
)))
1655 (if landmark-one-moment-please
1656 (message "One moment, please..."))
1657 (landmark-start-game landmark-n landmark-m
)
1658 (eval (cons 'landmark-init
1660 ((= parg
1) '(t nil
))
1662 ((= parg
3) '(nil t
))
1663 ((= parg
4) '(nil nil
))
1667 ;;;_ + Local variables
1669 ;;; The following `allout-layout' local variable setting:
1670 ;;; - closes all topics from the first topic to just before the third-to-last,
1671 ;;; - shows the children of the third to last (config vars)
1672 ;;; - and the second to last (code section),
1673 ;;; - and closes the last topic (this local-variables section).
1675 ;;;allout-layout: (0 : -1 -1 0)
1680 ;;; landmark.el ends here