1 ;;; landmark.el --- Neural-network robot that learns landmarks -*- lexical-binding:t -*-
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
8 ;; Maintainer: No maintainer - help wanted.
11 ;; This file is part of GNU Emacs.
13 ;; GNU Emacs is free software: you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation, either version 3 of the License, or
16 ;; (at your option) any later version.
18 ;; GNU Emacs is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; You should have received a copy of the GNU General Public License
24 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
29 ;; To try this, just type: M-x landmark-test-run
31 ;; Landmark is a relatively non-participatory game in which a robot
32 ;; attempts to maneuver towards a tree at the center of the window
33 ;; based on unique olfactory cues from each of the 4 directions. If
34 ;; the smell of the tree increases, then the weights in the robot's
35 ;; brain are adjusted to encourage this odor-driven behavior in the
36 ;; future. If the smell of the tree decreases, the robots weights are
37 ;; adjusted to discourage a correct move.
39 ;; In laymen's terms, the search space is initially flat. The point
40 ;; of training is to "turn up the edges of the search space" so that
41 ;; the robot rolls toward the center.
43 ;; Further, do not become alarmed if the robot appears to oscillate
44 ;; back and forth between two or a few positions. This simply means
45 ;; it is currently caught in a local minimum and is doing its best to
48 ;; The version of this program as described has a small problem. a
49 ;; move in a net direction can produce gross credit assignment. for
50 ;; example, if moving south will produce positive payoff, then, if in
51 ;; a single move, one moves east,west and south, then both east and
52 ;; west will be improved when they shouldn't
54 ;; Many thanks to Yuri Pryadkin <yuri@rana.usc.edu> for this
55 ;; concise problem description.
58 (eval-when-compile (require 'cl-lib))
64 (defgroup landmark nil
65 "Neural-network robot that learns landmarks."
71 ;; The board is a rectangular grid. We code empty squares with 0, X's with 1
72 ;; and O's with 6. The rectangle is recorded in a one dimensional vector
73 ;; containing padding squares (coded with -1). These squares allow us to
74 ;; detect when we are trying to move out of the board. We denote a square by
75 ;; its (X,Y) coords, or by the INDEX corresponding to them in the vector. The
76 ;; leftmost topmost square has coords (1,1) and index landmark-board-width + 2.
77 ;; Similarly, vectors between squares may be given by two DX, DY coords or by
78 ;; one DEPL (the difference between indexes).
80 (defvar landmark-board-width nil
81 "Number of columns on the Landmark board.")
82 (defvar landmark-board-height nil
83 "Number of lines on the Landmark board.")
85 (defvar landmark-board nil
86 "Vector recording the actual state of the Landmark board.")
88 (defvar landmark-vector-length nil
89 "Length of landmark-board vector.")
91 (defvar landmark-draw-limit nil
92 ;; This is usually set to 70% of the number of squares.
93 "After how many moves will Emacs offer a draw?")
96 "This is the x coordinate of the center of the board.")
99 "This is the y coordinate of the center of the board.")
102 "This is the x dimension of the playing board.")
105 "This is the y dimension of the playing board.")
108 (defun landmark-xy-to-index (x y)
109 "Translate X, Y cartesian coords into the corresponding board index."
110 (+ (* y landmark-board-width) x y))
112 (defun landmark-index-to-x (index)
113 "Return corresponding x-coord of board INDEX."
114 (% index (1+ landmark-board-width)))
116 (defun landmark-index-to-y (index)
117 "Return corresponding y-coord of board INDEX."
118 (/ index (1+ landmark-board-width)))
120 (defun landmark-init-board ()
121 "Create the landmark-board vector and fill it with initial values."
122 (setq landmark-board (make-vector landmark-vector-length 0))
123 ;; Every square is 0 (i.e. empty) except padding squares:
124 (let ((i 0) (ii (1- landmark-vector-length)))
125 (while (<= i landmark-board-width) ; The squares in [0..width] and in
126 (aset landmark-board i -1) ; [length - width - 1..length - 1]
127 (aset landmark-board ii -1) ; are padding squares.
131 (while (< i landmark-vector-length)
132 (aset landmark-board i -1) ; and also all k*(width+1)
133 (setq i (+ i landmark-board-width 1)))))
135 ;;;_ + DISPLAYING THE BOARD.
137 ;; You may change these values if you have a small screen or if the squares
138 ;; look rectangular, but spacings SHOULD be at least 2 (MUST BE at least 1).
140 (defconst landmark-square-width 2
141 "Horizontal spacing between squares on the Landmark board.")
143 (defconst landmark-square-height 1
144 "Vertical spacing between squares on the Landmark board.")
146 (defconst landmark-x-offset 3
147 "Number of columns between the Landmark board and the side of the window.")
149 (defconst landmark-y-offset 1
150 "Number of lines between the Landmark board and the top of the window.")
153 ;;;_ + LANDMARK MODE AND KEYMAP.
155 (defcustom landmark-mode-hook nil
156 "If non-nil, its value is called on entry to Landmark mode."
160 (defvar landmark-mode-map
161 (let ((map (make-sparse-keymap)))
162 ;; Key bindings for cursor motion.
163 (define-key map "y" 'landmark-move-nw) ; y
164 (define-key map "u" 'landmark-move-ne) ; u
165 (define-key map "b" 'landmark-move-sw) ; b
166 (define-key map "n" 'landmark-move-se) ; n
167 (define-key map "h" 'backward-char) ; h
168 (define-key map "l" 'forward-char) ; l
169 (define-key map "j" 'landmark-move-down) ; j
170 (define-key map "k" 'landmark-move-up) ; k
172 (define-key map [kp-7] 'landmark-move-nw)
173 (define-key map [kp-9] 'landmark-move-ne)
174 (define-key map [kp-1] 'landmark-move-sw)
175 (define-key map [kp-3] 'landmark-move-se)
176 (define-key map [kp-4] 'backward-char)
177 (define-key map [kp-6] 'forward-char)
178 (define-key map [kp-2] 'landmark-move-down)
179 (define-key map [kp-8] 'landmark-move-up)
181 (define-key map "\C-n" 'landmark-move-down) ; C-n
182 (define-key map "\C-p" 'landmark-move-up) ; C-p
184 ;; Key bindings for entering Human moves.
185 (define-key map "X" 'landmark-human-plays) ; X
186 (define-key map "x" 'landmark-human-plays) ; x
188 (define-key map " " 'landmark-start-robot) ; SPC
189 (define-key map [down-mouse-1] 'landmark-start-robot)
190 (define-key map [drag-mouse-1] 'landmark-click)
191 (define-key map [mouse-1] 'landmark-click)
192 (define-key map [down-mouse-2] 'landmark-click)
193 (define-key map [mouse-2] 'landmark-mouse-play)
194 (define-key map [drag-mouse-2] 'landmark-mouse-play)
196 (define-key map [remap previous-line] 'landmark-move-up)
197 (define-key map [remap next-line] 'landmark-move-down)
198 (define-key map [remap beginning-of-line] 'landmark-beginning-of-line)
199 (define-key map [remap end-of-line] 'landmark-end-of-line)
200 (define-key map [remap undo] 'landmark-human-takes-back)
201 (define-key map [remap advertised-undo] 'landmark-human-takes-back)
203 "Local keymap to use in Landmark mode.")
207 (defvar landmark-emacs-won ()
208 "For making font-lock use the winner's face for the line.")
210 (defface landmark-font-lock-face-O '((((class color)) :foreground "red")
212 "Face to use for Emacs's O."
216 (defface landmark-font-lock-face-X '((((class color)) :foreground "green")
218 "Face to use for your X."
222 (defvar landmark-font-lock-keywords
223 '(("O" . 'landmark-font-lock-face-O)
224 ("X" . 'landmark-font-lock-face-X)
225 ("[-|/\\]" 0 (if landmark-emacs-won
226 'landmark-font-lock-face-O
227 'landmark-font-lock-face-X)))
228 "Font lock rules for Landmark.")
230 ;; This one is for when they set view-read-only to t: Landmark cannot
231 ;; allow View Mode to be activated in its buffer.
232 (define-derived-mode landmark-mode special-mode "Lm"
233 "Major mode for playing Lm against Emacs.
234 You and Emacs play in turn by marking a free square. You mark it with X
235 and Emacs marks it with O. The winner is the first to get five contiguous
236 marks horizontally, vertically or in diagonal.
238 You play by moving the cursor over the square you choose and hitting \\[landmark-human-plays].
240 Other useful commands:
241 \\{landmark-mode-map}
242 Entry to this mode calls the value of `landmark-mode-hook' if that value
243 is non-nil. One interesting value is `turn-on-font-lock'."
244 (landmark-display-statistics)
245 (setq-local font-lock-defaults '(landmark-font-lock-keywords t))
246 (setq buffer-read-only t)
247 (add-hook 'post-command-hook #'landmark--intangible nil 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...")
682 (let ((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 (count-lines (point-min) (window-start))
726 landmark-square-height
727 (% landmark-square-height 2)
728 (/ landmark-square-height 2))
729 landmark-square-height)
731 landmark-board-height))))
733 (defun landmark-mouse-play (click)
734 "Play at the square where you click."
736 (if (landmark-click click)
737 (landmark-human-plays)))
739 (defun landmark-human-plays ()
740 "Signal to the Landmark program that you have played.
741 You must have put the cursor on the square where you want to play.
742 If the game is finished, this command requests for another game."
744 (landmark-switch-to-window)
746 (landmark-emacs-is-computing
747 (landmark-crash-game))
748 ((not landmark-game-in-progress)
749 (landmark-prompt-for-other-game))
751 (let ((square (landmark-point-square))
754 (error "Your point is not on a square. Retry!"))
755 ((not (zerop (aref landmark-board square)))
756 (error "Your point is not on a free square. Retry!"))
758 (setq score (aref landmark-score-table square))
759 (landmark-play-move square 1)
760 (cond ((and (>= score landmark-losing-threshold)
761 ;; Just testing SCORE > THRESHOLD is not enough for
762 ;; detecting wins, it just gives an indication that
763 ;; we confirm with LANDMARK-FIND-FILLED-QTUPLE.
764 (landmark-find-filled-qtuple square 1))
765 (landmark-terminate-game 'human-won))
767 (landmark-emacs-plays)))))))))
769 (defun landmark-human-takes-back ()
770 "Signal to the Landmark program that you wish to take back your last move."
772 (landmark-switch-to-window)
774 (landmark-emacs-is-computing
775 (landmark-crash-game))
776 ((not landmark-game-in-progress)
777 (message "Too late for taking back...")
779 (landmark-prompt-for-other-game))
780 ((zerop landmark-number-of-human-moves)
781 (message "You have not played yet... Your move?"))
783 (message "One moment, please...")
784 ;; It is possible for the user to let Emacs play several consecutive
785 ;; moves, so that the best way to know when to stop taking back moves is
786 ;; to count the number of human moves:
787 (setq landmark-human-took-back t)
788 (let ((number landmark-number-of-human-moves))
789 (while (= number landmark-number-of-human-moves)
790 (landmark-take-back)))
791 (landmark-prompt-for-move))))
793 (defun landmark-human-resigns ()
794 "Signal to the Landmark program that you may want to resign."
796 (landmark-switch-to-window)
798 (landmark-emacs-is-computing
799 (landmark-crash-game))
800 ((not landmark-game-in-progress)
801 (message "There is no game in progress"))
802 ((y-or-n-p "You mean, you resign? ")
803 (landmark-terminate-game 'human-resigned))
804 ((y-or-n-p "You mean, we continue? ")
805 (landmark-prompt-for-move))
807 (landmark-terminate-game 'human-resigned)))) ; OK. Accept it
809 ;;;_ + PROMPTING THE HUMAN PLAYER.
811 (defun landmark-prompt-for-move ()
812 "Display a message asking for Human's move."
813 (message (if (zerop landmark-number-of-human-moves)
814 "Your move? (move to a free square and hit X, RET ...)"
817 (defun landmark-prompt-for-other-game ()
818 "Ask for another game, and start it."
819 (if (y-or-n-p "Another game? ")
820 (if (y-or-n-p "Retain learned weights ")
823 (message "Chicken!")))
825 (defun landmark-offer-a-draw ()
826 "Offer a draw and return t if Human accepted it."
827 (or (y-or-n-p "I offer you a draw. Do you accept it? ")
828 (not (setq landmark-human-refused-draw t))))
831 (defun landmark-max-width ()
832 "Largest possible board width for the current window."
833 (1+ (/ (- (window-width)
834 landmark-x-offset landmark-x-offset 1)
835 landmark-square-width)))
837 (defun landmark-max-height ()
838 "Largest possible board height for the current window."
839 (1+ (/ (- (window-height)
840 landmark-y-offset landmark-y-offset 2)
841 ;; 2 instead of 1 because WINDOW-HEIGHT includes the mode line !
842 landmark-square-height)))
844 (defun landmark-point-y ()
845 "Return the board row where point is."
846 (1+ (/ (- (count-lines (point-min) (point))
847 landmark-y-offset (if (bolp) 0 1))
848 landmark-square-height)))
850 (defun landmark-point-square ()
851 "Return the index of the square point is on."
852 (landmark-xy-to-index (1+ (/ (- (current-column) landmark-x-offset)
853 landmark-square-width))
856 (defun landmark-goto-square (index)
857 "Move point to square number INDEX."
858 (landmark-goto-xy (landmark-index-to-x index) (landmark-index-to-y index)))
860 (defun landmark-goto-xy (x y)
861 "Move point to square at X, Y coords."
862 (goto-char (point-min))
863 (forward-line (+ landmark-y-offset (* landmark-square-height (1- y))))
864 (move-to-column (+ landmark-x-offset (* landmark-square-width (1- x)))))
866 (defun landmark-plot-square (square value)
867 "Draw 'X', 'O' or '.' on SQUARE depending on VALUE, leave point there."
869 (landmark-goto-square square))
870 (let ((inhibit-read-only t))
871 (insert (cond ((= value 1) ?.)
879 (add-text-properties (1- (point)) (point)
880 '(mouse-face highlight
882 mouse-1: get robot moving, mouse-2: play on this square")))
885 (sit-for 0)) ; Display NOW
887 (defun landmark-init-display (n m)
888 "Display an N by M Landmark board."
889 (buffer-disable-undo (current-buffer))
890 (let ((inhibit-read-only t)
891 (point (point-min)) opoint
893 ;; Try to minimize number of chars (because of text properties)
895 (if (zerop (% landmark-x-offset landmark-square-width))
896 landmark-square-width
897 (max (/ (+ (% landmark-x-offset landmark-square-width)
898 landmark-square-width 1) 2) 2)))
900 (insert-char ?\n landmark-y-offset)
903 x (- landmark-x-offset landmark-square-width))
904 (while (>= (setq j (1- j)) 0)
905 (insert-char ?\t (/ (- (setq x (+ x landmark-square-width))
908 (insert-char ?\s (- x (current-column)))
913 (append-to-buffer (current-buffer) opoint (point))
915 (goto-char (point-max))))
918 (add-text-properties point (point)
919 '(mouse-face highlight help-echo "\
920 mouse-1: get robot moving, mouse-2: play on this square")))
921 (> (setq i (1- i)) 0))
924 (insert-char ?\n landmark-square-height))
926 (landmark-goto-xy (/ (1+ n) 2) (/ (1+ m) 2)) ; center of the board
927 (sit-for 0)) ; Display NOW
929 (defun landmark-display-statistics ()
930 "Obnoxiously display some statistics about previous games in mode line."
931 ;; We store this string in the mode-line-process local variable.
932 ;; This is certainly not the cleanest way out ...
933 (setq mode-line-process
934 (format ": Trials: %d, Avg#Moves: %d"
935 landmark-number-of-trials
936 (if (zerop landmark-number-of-trials)
938 (/ landmark-sum-of-moves landmark-number-of-trials))))
939 (force-mode-line-update))
941 (defun landmark-switch-to-window ()
942 "Find or create the Landmark buffer, and display it."
944 (let ((buff (get-buffer "*Landmark*")))
945 (if buff ; Buffer exists:
946 (switch-to-buffer buff) ; no problem.
947 (if landmark-game-in-progress
948 (landmark-crash-game)) ; buffer has been killed or something
949 (switch-to-buffer "*Landmark*") ; Anyway, start anew.
953 ;;;_ + CROSSING WINNING QTUPLES.
955 ;; When someone succeeds in filling a qtuple, we draw a line over the five
956 ;; corresponding squares. One problem is that the program does not know which
957 ;; squares ! It only knows the square where the last move has been played and
958 ;; who won. The solution is to scan the board along all four directions.
960 (defun landmark-find-filled-qtuple (square value)
961 "Return t if SQUARE belongs to a qtuple filled with VALUEs."
962 (or (landmark-check-filled-qtuple square value 1 0)
963 (landmark-check-filled-qtuple square value 0 1)
964 (landmark-check-filled-qtuple square value 1 1)
965 (landmark-check-filled-qtuple square value -1 1)))
967 (defun landmark-check-filled-qtuple (square value dx dy)
968 "Return t if SQUARE belongs to a qtuple filled with VALUEs along DX, DY."
970 (left square) (right square)
971 (depl (landmark-xy-to-index dx dy)))
972 (while (and (> a -4) ; stretch tuple left
973 (= value (aref landmark-board (setq left (- left depl)))))
975 (while (and (< b (+ a 4)) ; stretch tuple right
976 (= value (aref landmark-board (setq right (+ right depl)))))
978 (cond ((= b (+ a 4)) ; tuple length = 5 ?
979 (landmark-cross-qtuple (+ square (* a depl)) (+ square (* b depl))
983 (defun landmark-cross-qtuple (square1 square2 dx dy)
984 "Cross every square between SQUARE1 and SQUARE2 in the DX, DY direction."
985 (save-excursion ; Not moving point from last square
986 (let ((depl (landmark-xy-to-index dx dy))
987 (inhibit-read-only t))
988 ;; WARNING: this function assumes DEPL > 0 and SQUARE2 > SQUARE1
989 (while (/= square1 square2)
990 (landmark-goto-square square1)
991 (setq square1 (+ square1 depl))
993 ((= dy 0) ; Horizontal
995 (insert-char ?- (1- landmark-square-width) t)
996 (delete-region (point) (progn
997 (skip-chars-forward " \t")
1000 (let ((landmark-n 1)
1001 (column (current-column)))
1002 (while (< landmark-n landmark-square-height)
1003 (setq landmark-n (1+ landmark-n))
1007 ((= dx -1) ; 1st Diagonal
1008 (indent-to (prog1 (- (current-column) (/ landmark-square-width 2))
1009 (forward-line (/ landmark-square-height 2))))
1012 (indent-to (prog1 (+ (current-column) (/ landmark-square-width 2))
1013 (forward-line (/ landmark-square-height 2))))
1015 (sit-for 0)) ; Display NOW
1018 ;;;_ + CURSOR MOTION.
1020 (defvar-local landmark--last-pos 0)
1022 (defconst landmark--intangible-chars "- \t\n|/\\\\")
1024 (defun landmark--intangible ()
1027 (not (zerop (skip-chars-forward landmark--intangible-chars)))))
1028 (if (<= landmark--last-pos (point)) ;Moving forward.
1030 (skip-chars-forward landmark--intangible-chars)
1032 (skip-chars-backward landmark--intangible-chars)
1034 (skip-chars-backward landmark--intangible-chars)
1036 (skip-chars-forward landmark--intangible-chars)
1037 (forward-char -1))))
1038 (setq landmark--last-pos (point)))
1040 ;; previous-line and next-line don't work right with intangible newlines
1041 (defun landmark-move-down ()
1042 "Move point down one row on the Landmark board."
1044 (if (< (landmark-point-y) landmark-board-height)
1045 (let ((col (current-column)))
1046 (forward-line 1) ;;; landmark-square-height
1047 (move-to-column col))))
1049 (defun landmark-move-up ()
1050 "Move point up one row on the Landmark board."
1052 (if (> (landmark-point-y) 1)
1053 (let ((col (current-column)))
1054 (forward-line (- landmark-square-height))
1055 (move-to-column col))))
1057 (defun landmark-move-ne ()
1058 "Move point North East on the Landmark board."
1063 (defun landmark-move-se ()
1064 "Move point South East on the Landmark board."
1066 (landmark-move-down)
1069 (defun landmark-move-nw ()
1070 "Move point North West on the Landmark board."
1075 (defun landmark-move-sw ()
1076 "Move point South West on the Landmark board."
1078 (landmark-move-down)
1081 (defun landmark-beginning-of-line ()
1082 "Move point to first square on the Landmark board row."
1084 (move-to-column landmark-x-offset))
1086 (defun landmark-end-of-line ()
1087 "Move point to last square on the Landmark board row."
1089 (move-to-column (+ landmark-x-offset
1090 (* landmark-square-width (1- landmark-board-width)))))
1093 ;;;_ + Simulation variables
1095 ;;;_ - landmark-nvar
1096 (defvar landmark-nvar 0.0075
1098 Affects a noise generator which was used in an earlier incarnation of
1099 this program to add a random element to the way moves were made.")
1100 ;;;_ - lists of cardinal directions
1102 (defvar landmark-ns '(landmark-n landmark-s)
1103 "Used when doing something relative to the north and south axes.")
1104 (defvar landmark-ew '(landmark-e landmark-w)
1105 "Used when doing something relative to the east and west axes.")
1106 (defvar landmark-directions '(landmark-n landmark-s landmark-e landmark-w)
1107 "The cardinal directions.")
1108 (defvar landmark-8-directions
1109 '((landmark-n) (landmark-n landmark-w) (landmark-w) (landmark-s landmark-w)
1110 (landmark-s) (landmark-s landmark-e) (landmark-e) (landmark-n landmark-e))
1111 "The full 8 possible directions.")
1113 (defvar landmark-number-of-moves
1114 "The number of moves made by the robot so far.")
1117 ;;;_* Terry's mods to create lm.el
1119 ;;;(setq landmark-debug nil)
1120 (defvar landmark-debug nil
1121 "If non-nil, debugging is printed.")
1122 (defcustom landmark-one-moment-please nil
1123 "If non-nil, print \"One moment please\" when a new board is generated.
1124 The drawback of this is you don't see how many moves the last run took
1125 because it is overwritten by \"One moment please\"."
1128 (defcustom landmark-output-moves t
1129 "If non-nil, output number of moves so far on a move-by-move basis."
1134 (defun landmark-weights-debug ()
1136 (progn (landmark-print-wts) (landmark-blackbox) (landmark-print-y-s-noise)
1137 (landmark-print-smell))))
1139 ;;;_ - Printing various things
1140 (defun landmark-print-distance-int (direction)
1142 (insert (format "%S %S " direction (get direction 'distance))))
1145 (defun landmark-print-distance ()
1146 (insert (format "tree: %S \n" (landmark-calc-distance-of-robot-from 'landmark-tree)))
1147 (mapc 'landmark-print-distance-int landmark-directions))
1150 ;;(setq direction 'landmark-n)
1151 ;;(get 'landmark-n 'landmark-s)
1152 (defun landmark-nslify-wts-int (direction)
1153 (mapcar (lambda (target-direction)
1154 (get direction target-direction))
1155 landmark-directions))
1158 (defun landmark-nslify-wts ()
1160 (let ((l (apply 'append (mapcar 'landmark-nslify-wts-int landmark-directions))))
1161 (insert (format "set data_value WTS \n %s \n" l))
1162 (insert (format "/* max: %S min: %S */"
1163 (eval (cons 'max l)) (eval (cons 'min l))))))
1165 (defun landmark-print-wts-int (direction)
1166 (mapc (lambda (target-direction)
1167 (insert (format "%S %S %S "
1170 (get direction target-direction))))
1171 landmark-directions)
1174 (defun landmark-print-wts ()
1176 (with-current-buffer "*landmark-wts*"
1177 (insert "==============================\n")
1178 (mapc 'landmark-print-wts-int landmark-directions)))
1180 (defun landmark-print-moves (moves)
1182 (with-current-buffer "*landmark-moves*"
1183 (insert (format "%S\n" moves))))
1186 (defun landmark-print-y-s-noise-int (direction)
1187 (insert (format "%S:landmark-y %S, s %S, noise %S \n"
1188 (symbol-name direction)
1189 (get direction 'y_t)
1191 (get direction 'noise)
1194 (defun landmark-print-y-s-noise ()
1196 (with-current-buffer "*landmark-y,s,noise*"
1197 (insert "==============================\n")
1198 (mapc 'landmark-print-y-s-noise-int landmark-directions)))
1200 (defun landmark-print-smell-int (direction)
1201 (insert (format "%S: smell: %S \n"
1202 (symbol-name direction)
1203 (get direction 'smell))))
1205 (defun landmark-print-smell ()
1207 (with-current-buffer "*landmark-smell*"
1208 (insert "==============================\n")
1209 (insert (format "tree: %S \n" (get 'z 't)))
1210 (mapc 'landmark-print-smell-int landmark-directions)))
1212 (defun landmark-print-w0-int (direction)
1213 (insert (format "%S: w0: %S \n"
1214 (symbol-name direction)
1215 (get direction 'w0))))
1217 (defun landmark-print-w0 ()
1219 (with-current-buffer "*landmark-w0*"
1220 (insert "==============================\n")
1221 (mapc 'landmark-print-w0-int landmark-directions)))
1223 (defun landmark-blackbox ()
1224 (with-current-buffer "*landmark-blackbox*"
1225 (insert "==============================\n")
1226 (insert "I smell: ")
1227 (mapc (lambda (direction)
1228 (if (> (get direction 'smell) 0)
1229 (insert (format "%S " direction))))
1230 landmark-directions)
1234 (mapc (lambda (direction)
1235 (if (> (get direction 'y_t) 0)
1236 (insert (format "%S " direction))))
1237 landmark-directions)
1239 (landmark-print-wts-blackbox)
1240 (insert (format "z_t-z_t-1: %S" (- (get 'z 't) (get 'z 't-1))))
1241 (landmark-print-distance)
1244 (defun landmark-print-wts-blackbox ()
1246 (mapc 'landmark-print-wts-int landmark-directions))
1248 ;;;_ - learning parameters
1249 (defcustom landmark-bound 0.005
1250 "The maximum that w0j may be."
1253 (defcustom landmark-c 1.0
1254 "A factor applied to modulate the increase in wij.
1255 Used in the function landmark-update-normal-weights."
1258 (defcustom landmark-c-naught 0.5
1259 "A factor applied to modulate the increase in w0j.
1260 Used in the function landmark-update-naught-weights."
1263 (defvar landmark-initial-w0 0.0)
1264 (defvar landmark-initial-wij 0.0)
1265 (defcustom landmark-no-payoff 0
1266 "The amount of simulation cycles that have occurred with no movement.
1267 Used to move the robot when he is stuck in a rut for some reason."
1270 (defcustom landmark-max-stall-time 2
1271 "The maximum number of cycles that the robot can remain stuck in a place.
1272 After this limit is reached, landmark-random-move is called to push him out of it."
1277 ;;;_ + Randomizing functions
1278 ;;;_ - landmark-flip-a-coin ()
1279 (defun landmark-flip-a-coin ()
1280 (if (> (random 5000) 2500)
1283 ;;;_ : landmark-very-small-random-number ()
1284 ;(defun landmark-very-small-random-number ()
1286 ; (* (/ (random 900000) 900000.0) .0001)))
1287 ;;;_ : landmark-randomize-weights-for (direction)
1288 (defun landmark-randomize-weights-for (direction)
1289 (mapc (lambda (target-direction)
1292 (* (landmark-flip-a-coin) (/ (random 10000) 10000.0))))
1293 landmark-directions))
1294 ;;;_ : landmark-noise ()
1295 (defun landmark-noise ()
1296 (* (- (/ (random 30001) 15000.0) 1) landmark-nvar))
1298 ;;;_ : landmark-fix-weights-for (direction)
1299 (defun landmark-fix-weights-for (direction)
1300 (mapc (lambda (target-direction)
1303 landmark-initial-wij))
1304 landmark-directions))
1307 ;;;_ + Plotting functions
1308 ;;;_ - landmark-plot-internal (sym)
1309 (defun landmark-plot-internal (sym)
1310 (landmark-plot-square (landmark-xy-to-index
1314 ;;;_ - landmark-plot-landmarks ()
1315 (defun landmark-plot-landmarks ()
1316 (setq landmark-cx (/ landmark-board-width 2))
1317 (setq landmark-cy (/ landmark-board-height 2))
1319 (put 'landmark-n 'x landmark-cx)
1320 (put 'landmark-n 'y 1)
1321 (put 'landmark-n 'sym 2)
1323 (put 'landmark-tree 'x landmark-cx)
1324 (put 'landmark-tree 'y landmark-cy)
1325 (put 'landmark-tree 'sym 6)
1327 (put 'landmark-s 'x landmark-cx)
1328 (put 'landmark-s 'y landmark-board-height)
1329 (put 'landmark-s 'sym 3)
1331 (put 'landmark-w 'x 1)
1332 (put 'landmark-w 'y (/ landmark-board-height 2))
1333 (put 'landmark-w 'sym 5)
1335 (put 'landmark-e 'x landmark-board-width)
1336 (put 'landmark-e 'y (/ landmark-board-height 2))
1337 (put 'landmark-e 'sym 4)
1339 (mapc 'landmark-plot-internal '(landmark-n landmark-s landmark-e landmark-w landmark-tree)))
1343 ;;;_ + Distance-calculation functions
1345 ;;;_ - distance (x x0 y y0)
1346 (defun landmark--distance (x x0 y y0)
1347 (let ((dx (- x x0)) (dy (- y y0)))
1348 (sqrt (+ (* dx dx) (* dy dy)))))
1350 ;;;_ - landmark-calc-distance-of-robot-from (direction)
1351 (defun landmark-calc-distance-of-robot-from (direction)
1352 (put direction 'distance
1353 (landmark--distance (get direction 'x)
1354 (landmark-index-to-x (landmark-point-square))
1356 (landmark-index-to-y (landmark-point-square)))))
1358 ;;;_ - landmark-calc-smell-internal (sym)
1359 (defun landmark-calc-smell-internal (sym)
1360 (let ((r (get sym 'r))
1361 (d (landmark-calc-distance-of-robot-from sym)))
1362 (if (> (* 0.5 (- 1 (/ d r))) 0)
1363 (* 0.5 (- 1 (/ d r)))
1367 ;;;_ + Learning (neural) functions
1368 (defun landmark-f (x)
1370 ((> x landmark-bound) landmark-bound)
1374 (defun landmark-y (direction)
1375 (put direction 'noise (landmark-noise))
1377 (if (> (get direction 's) 0.0)
1381 (defun landmark-update-normal-weights (direction)
1382 (mapc (lambda (target-direction)
1383 (put direction target-direction
1385 (get direction target-direction)
1387 (- (get 'z 't) (get 'z 't-1))
1388 (get target-direction 'y_t)
1389 (get direction 'smell)))))
1390 landmark-directions))
1392 (defun landmark-update-naught-weights (direction)
1393 (mapc (lambda (_target-direction)
1398 (* landmark-c-naught
1399 (- (get 'z 't) (get 'z 't-1))
1400 (get direction 'y_t))))))
1401 landmark-directions))
1404 ;;;_ + Statistics gathering and creating functions
1406 (defun landmark-calc-current-smells ()
1407 (mapc (lambda (direction)
1408 (put direction 'smell (landmark-calc-smell-internal direction)))
1409 landmark-directions))
1411 (defun landmark-calc-payoff ()
1412 (put 'z 't-1 (get 'z 't))
1413 (put 'z 't (landmark-calc-smell-internal 'landmark-tree))
1414 (if (= (- (get 'z 't) (get 'z 't-1)) 0.0)
1415 (cl-incf landmark-no-payoff)
1416 (setf landmark-no-payoff 0)))
1418 (defun landmark-store-old-y_t ()
1419 (mapc (lambda (direction)
1420 (put direction 'y_t-1 (get direction 'y_t)))
1421 landmark-directions))
1424 ;;;_ + Functions to move robot
1426 (defun landmark-confidence-for (target-direction)
1428 (get target-direction 'w0)
1429 (mapcar (lambda (direction)
1431 (get direction target-direction)
1432 (get direction 'smell)))
1433 landmark-directions)))
1436 (defun landmark-calc-confidences ()
1437 (mapc (lambda (direction)
1438 (put direction 's (landmark-confidence-for direction)))
1439 landmark-directions))
1441 (defun landmark-move ()
1442 (if (and (= (get 'landmark-n 'y_t) 1.0) (= (get 'landmark-s 'y_t) 1.0))
1444 (mapc (lambda (dir) (put dir 'y_t 0)) landmark-ns)
1446 (message "n-s normalization."))))
1447 (if (and (= (get 'landmark-w 'y_t) 1.0) (= (get 'landmark-e 'y_t) 1.0))
1449 (mapc (lambda (dir) (put dir 'y_t 0)) landmark-ew)
1451 (message "e-w normalization"))))
1453 (mapc (lambda (pair)
1454 (when (> (get (car pair) 'y_t) 0)
1455 (funcall (car (cdr pair)))
1456 (landmark--intangible)))
1458 (landmark-n landmark-move-up)
1459 (landmark-s landmark-move-down)
1460 (landmark-e forward-char)
1461 (landmark-w backward-char)))
1462 (landmark-plot-square (landmark-point-square) 1)
1463 (cl-incf landmark-number-of-moves)
1464 (if landmark-output-moves
1465 (message "Moves made: %d" landmark-number-of-moves)))
1468 (defun landmark-random-move ()
1470 (lambda (direction) (put direction 'y_t 0))
1471 landmark-directions)
1472 (dolist (direction (nth (random 8) landmark-8-directions))
1473 (put direction 'y_t 1.0))
1476 (defun landmark-amble-robot ()
1478 (while (> (landmark-calc-distance-of-robot-from 'landmark-tree) 0)
1480 (landmark-store-old-y_t)
1481 (landmark-calc-current-smells)
1483 (if (> landmark-no-payoff landmark-max-stall-time)
1484 (landmark-random-move)
1486 (landmark-calc-confidences)
1487 (mapc 'landmark-y landmark-directions)
1490 (landmark-calc-payoff)
1492 (mapc 'landmark-update-normal-weights landmark-directions)
1493 (mapc 'landmark-update-naught-weights landmark-directions)
1495 (landmark-weights-debug)))
1496 (landmark-terminate-game nil))
1499 ;;;_ - landmark-start-robot ()
1500 (defun landmark-start-robot ()
1501 "Signal to the Landmark program that you have played.
1502 You must have put the cursor on the square where you want to play.
1503 If the game is finished, this command requests for another game."
1505 (landmark-switch-to-window)
1507 (landmark-emacs-is-computing
1508 (landmark-crash-game))
1509 ((not landmark-game-in-progress)
1510 (landmark-prompt-for-other-game))
1512 (let ((square (landmark-point-square)))
1513 (cond ((null square)
1514 (error "Your point is not on a square. Retry!"))
1515 ((not (zerop (aref landmark-board square)))
1516 (error "Your point is not on a free square. Retry!"))
1519 (landmark-plot-square square 1)
1521 (landmark-store-old-y_t)
1522 (landmark-calc-current-smells)
1523 (put 'z 't (landmark-calc-smell-internal 'landmark-tree))
1525 (landmark-random-move)
1527 (landmark-calc-payoff)
1529 (mapc 'landmark-update-normal-weights landmark-directions)
1530 (mapc 'landmark-update-naught-weights landmark-directions)
1531 (landmark-amble-robot)
1535 ;;;_ + Misc functions
1536 ;;;_ - landmark-init (auto-start save-weights)
1537 (defvar landmark-tree-r "")
1539 (defun landmark-init (auto-start save-weights)
1541 (setq landmark-number-of-moves 0)
1543 (landmark-plot-landmarks)
1546 (save-current-buffer
1547 (set-buffer (get-buffer-create "*landmark-w0*"))
1549 (set-buffer (get-buffer-create "*landmark-moves*"))
1550 (set-buffer (get-buffer-create "*landmark-wts*"))
1552 (set-buffer (get-buffer-create "*landmark-y,s,noise*"))
1554 (set-buffer (get-buffer-create "*landmark-smell*"))
1556 (set-buffer (get-buffer-create "*landmark-blackbox*"))
1558 (set-buffer (get-buffer-create "*landmark-distance*"))
1562 (landmark-set-landmark-signal-strengths)
1564 (dolist (direction landmark-directions)
1565 (put direction 'y_t 0.0))
1567 (if (not save-weights)
1569 (mapc 'landmark-fix-weights-for landmark-directions)
1570 (dolist (direction landmark-directions)
1571 (put direction 'w0 landmark-initial-w0)))
1572 (message "Weights preserved for this run."))
1576 (landmark-goto-xy (1+ (random landmark-board-width)) (1+ (random landmark-board-height)))
1577 (landmark-start-robot))))
1580 ;;;_ - something which doesn't work
1582 ;(defun landmark-sum-list (list)
1583 ; (if (> (length list) 0)
1584 ; (+ (car list) (landmark-sum-list (cdr list)))
1587 ; (eval (cons '+ list))
1588 ;;;_ - landmark-set-landmark-signal-strengths ()
1589 ;; on a screen higher than wide, I noticed that the robot would amble
1590 ;; left and right and not move forward. examining *landmark-blackbox*
1591 ;; revealed that there was no scent from the north and south
1592 ;; landmarks, hence, they need less factoring down of the effect of
1593 ;; distance on scent.
1595 (defun landmark-set-landmark-signal-strengths ()
1596 (setq landmark-tree-r (* (sqrt (+ (* landmark-cx landmark-cx)
1597 (* landmark-cy landmark-cy)))
1599 (mapc (lambda (direction)
1600 (put direction 'r (* landmark-cx 1.1)))
1602 (mapc (lambda (direction)
1603 (put direction 'r (* landmark-cy 1.1)))
1605 (put 'landmark-tree 'r landmark-tree-r))
1608 ;;;_ + landmark-test-run ()
1611 (defalias 'landmark-repeat 'landmark-test-run)
1613 (defun landmark-test-run ()
1614 "Run 100 Landmark games, each time saving the weights from the previous game."
1621 (defun landmark (parg)
1622 "Start or resume an Landmark game.
1623 If a game is in progress, this command allows you to resume it.
1624 Here is the relation between prefix args and game options:
1626 prefix arg | robot is auto-started | weights are saved from last game
1627 ---------------------------------------------------------------------
1633 You start by moving to a square and typing \\[landmark-start-robot],
1634 if you did not use a prefix arg to ask for automatic start.
1635 Use \\[describe-mode] for more info."
1638 (setf landmark-n nil landmark-m nil)
1639 (landmark-switch-to-window)
1641 (landmark-emacs-is-computing
1642 (landmark-crash-game))
1643 ((or (not landmark-game-in-progress)
1644 (<= landmark-number-of-moves 2))
1645 (let ((max-width (landmark-max-width))
1646 (max-height (landmark-max-height)))
1647 (or landmark-n (setq landmark-n max-width))
1648 (or landmark-m (setq landmark-m max-height))
1649 (cond ((< landmark-n 1)
1650 (error "I need at least 1 column"))
1652 (error "I need at least 1 row"))
1653 ((> landmark-n max-width)
1654 (error "I cannot display %d columns in that window" landmark-n)))
1655 (if (and (> landmark-m max-height)
1656 (not (eq landmark-m landmark-saved-board-height))
1657 ;; Use EQ because SAVED-BOARD-HEIGHT may be nil
1658 (not (y-or-n-p (format "Do you really want %d rows? " landmark-m))))
1659 (setq landmark-m max-height)))
1660 (if landmark-one-moment-please
1661 (message "One moment, please..."))
1662 (landmark-start-game landmark-n landmark-m)
1663 (eval (cons 'landmark-init
1665 ((= parg 1) '(t nil))
1667 ((= parg 3) '(nil t))
1668 ((= parg 4) '(nil nil))
1672 ;;;_ + Local variables
1674 ;;; The following `allout-layout' local variable setting:
1675 ;;; - closes all topics from the first topic to just before the third-to-last,
1676 ;;; - shows the children of the third to last (config vars)
1677 ;;; - and the second to last (code section),
1678 ;;; - and closes the last topic (this local-variables section).
1680 ;;;allout-layout: (0 : -1 -1 0)
1685 ;;; landmark.el ends here