| blob | 2c77aa62df1b1778e3c917ea47e7189174e1e699 |
1 ;;; gomoku.el --- Gomoku game between you and Emacs
3 ;; Copyright (C) 1988, 1994, 1996, 2001, 2002, 2003, 2004, 2005, 2006,
4 ;; 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
6 ;; Author: Philippe Schnoebelen <phs@lsv.ens-cachan.fr>
7 ;; Maintainer: FSF
8 ;; Adapted-By: ESR, Daniel Pfeiffer <occitan@esperanto.org>
9 ;; Keywords: games
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/>.
26 ;;; Commentary:
28 ;; RULES:
29 ;;
30 ;; Gomoku is a game played between two players on a rectangular board. Each
31 ;; player, in turn, marks a free square of its choice. The winner is the first
32 ;; one to mark five contiguous squares in any direction (horizontally,
33 ;; vertically or diagonally).
34 ;;
35 ;; I have been told that, in "The TRUE Gomoku", some restrictions are made
36 ;; about the squares where one may play, or else there is a known forced win
37 ;; for the first player. This program has no such restriction, but it does not
38 ;; know about the forced win, nor do I.
39 ;; See http://renju.nu/r1rulhis.htm for more information.
42 ;; There are two main places where you may want to customize the program: key
43 ;; bindings and board display. These features are commented in the code. Go
44 ;; and see.
47 ;; HOW TO USE:
48 ;;
49 ;; The command "M-x gomoku" displays a
50 ;; board, the size of which depends on the size of the current window. The
51 ;; size of the board is easily modified by giving numeric arguments to the
52 ;; gomoku command and/or by customizing the displaying parameters.
53 ;;
54 ;; Emacs plays when it is its turn. When it is your turn, just put the cursor
55 ;; on the square where you want to play and hit RET, or X, or whatever key you
56 ;; bind to the command gomoku-human-plays. When it is your turn, Emacs is
57 ;; idle: you may switch buffers, read your mail, ... Just come back to the
58 ;; *Gomoku* buffer and resume play.
61 ;; ALGORITHM:
62 ;;
63 ;; The algorithm is briefly described in section "THE SCORE TABLE". Some
64 ;; parameters may be modified if you want to change the style exhibited by the
65 ;; program.
67 ;;; Code:
68 \f
70 "Gomoku game between you and Emacs."
73 ;;;
74 ;;; GOMOKU MODE AND KEYMAP.
75 ;;;
77 "If non-nil, its value is called on entry to Gomoku mode.
78 One useful value to include is `turn-on-font-lock' to highlight the pieces."
82 ;;;
83 ;;; CONSTANTS FOR BOARD
84 ;;;
89 ;; You may change these values if you have a small screen or if the squares
90 ;; look rectangular, but spacings SHOULD be at least 2 (MUST BE at least 1).
108 ;; Key bindings for cursor motion.
130 ;; Key bindings for entering Human moves.
142 (define-key map [down-mouse-1] 'gomoku-click)
143 (define-key map [drag-mouse-1] 'gomoku-click)
144 (define-key map [mouse-1] 'gomoku-click)
145 (define-key map [down-mouse-2] 'gomoku-click)
146 (define-key map [mouse-2] 'gomoku-mouse-play)
147 (define-key map [drag-mouse-2] 'gomoku-mouse-play)
149 (define-key map [remap previous-line] 'gomoku-move-up)
150 (define-key map [remap next-line] 'gomoku-move-down)
151 (define-key map [remap move-beginning-of-line] 'gomoku-beginning-of-line)
152 (define-key map [remap move-end-of-line] 'gomoku-end-of-line)
153 (define-key map [remap undo] 'gomoku-human-takes-back)
154 (define-key map [remap advertised-undo] 'gomoku-human-takes-back)
155 map)
157 "Local keymap to use in Gomoku mode.")
160 (defvar gomoku-emacs-won ()
161 "For making font-lock use the winner's face for the line.")
163 (defface gomoku-O
164 '((((class color)) (:foreground "red" :weight bold)))
165 "Face to use for Emacs' O."
166 :group 'gomoku)
168 (defface gomoku-X
169 '((((class color)) (:foreground "green" :weight bold)))
170 "Face to use for your X."
171 :group 'gomoku)
173 (defvar gomoku-font-lock-keywords
174 '(("O" . 'gomoku-O)
175 ("X" . 'gomoku-X)
177 "*Font lock rules for Gomoku.")
179 (put 'gomoku-mode 'front-sticky
180 (put 'gomoku-mode 'rear-nonsticky '(intangible)))
181 (put 'gomoku-mode 'intangible 1)
182 ;; This one is for when they set view-read-only to t: Gomoku cannot
183 ;; allow View Mode to be activated in its buffer.
184 (put 'gomoku-mode 'mode-class 'special)
186 (define-derived-mode gomoku-mode nil "Gomoku"
187 "Major mode for playing Gomoku against Emacs.
188 You and Emacs play in turn by marking a free square. You mark it with X
189 and Emacs marks it with O. The winner is the first to get five contiguous
190 marks horizontally, vertically or in diagonal.
196 (gomoku-display-statistics)
197 (make-local-variable 'font-lock-defaults)
198 (setq font-lock-defaults '(gomoku-font-lock-keywords t)
199 buffer-read-only t))
200 \f
201 ;;;
202 ;;; THE BOARD.
203 ;;;
205 ;; The board is a rectangular grid. We code empty squares with 0, X's with 1
206 ;; and O's with 6. The rectangle is recorded in a one dimensional vector
207 ;; containing padding squares (coded with -1). These squares allow us to
208 ;; detect when we are trying to move out of the board. We denote a square by
209 ;; its (X,Y) coords, or by the INDEX corresponding to them in the vector. The
210 ;; leftmost topmost square has coords (1,1) and index gomoku-board-width + 2.
211 ;; Similarly, vectors between squares may be given by two DX, DY coords or by
212 ;; one DEPL (the difference between indexes).
214 (defvar gomoku-board-width nil
215 "Number of columns on the Gomoku board.")
217 (defvar gomoku-board-height nil
218 "Number of lines on the Gomoku board.")
220 (defvar gomoku-board nil
221 "Vector recording the actual state of the Gomoku board.")
223 (defvar gomoku-vector-length nil
224 "Length of `gomoku-board' vector.")
226 (defvar gomoku-draw-limit nil
227 ;; This is usually set to 70% of the number of squares.
228 "After how many moves will Emacs offer a draw?")
231 (defun gomoku-xy-to-index (x y)
232 "Translate X, Y cartesian coords into the corresponding board index."
233 (+ (* y gomoku-board-width) x y))
235 (defun gomoku-index-to-x (index)
236 "Return corresponding x-coord of board INDEX."
237 (% index (1+ gomoku-board-width)))
239 (defun gomoku-index-to-y (index)
240 "Return corresponding y-coord of board INDEX."
241 (/ index (1+ gomoku-board-width)))
243 (defun gomoku-init-board ()
244 "Create the `gomoku-board' vector and fill it with initial values."
245 (setq gomoku-board (make-vector gomoku-vector-length 0))
246 ;; Every square is 0 (i.e. empty) except padding squares:
247 (let ((i 0) (ii (1- gomoku-vector-length)))
248 (while (<= i gomoku-board-width) ; The squares in [0..width] and in
249 (aset gomoku-board i -1) ; [length - width - 1..length - 1]
250 (aset gomoku-board ii -1) ; are padding squares.
251 (setq i (1+ i)
252 ii (1- ii))))
253 (let ((i 0))
254 (while (< i gomoku-vector-length)
255 (aset gomoku-board i -1) ; and also all k*(width+1)
256 (setq i (+ i gomoku-board-width 1)))))
257 \f
258 ;;;
259 ;;; THE SCORE TABLE.
260 ;;;
262 ;; Every (free) square has a score associated to it, recorded in the
263 ;; GOMOKU-SCORE-TABLE vector. The program always plays in the square having
264 ;; the highest score.
266 (defvar gomoku-score-table nil
267 "Vector recording the actual score of the free squares.")
270 ;; The key point point about the algorithm is that, rather than considering
271 ;; the board as just a set of squares, we prefer to see it as a "space" of
272 ;; internested 5-tuples of contiguous squares (called qtuples).
273 ;;
274 ;; The aim of the program is to fill one qtuple with its O's while preventing
275 ;; you from filling another one with your X's. To that effect, it computes a
276 ;; score for every qtuple, with better qtuples having better scores. Of
277 ;; course, the score of a qtuple (taken in isolation) is just determined by
278 ;; its contents as a set, i.e. not considering the order of its elements. The
279 ;; highest score is given to the "OOOO" qtuples because playing in such a
280 ;; qtuple is winning the game. Just after this comes the "XXXX" qtuple because
281 ;; not playing in it is just losing the game, and so on. Note that a
282 ;; "polluted" qtuple, i.e. one containing at least one X and at least one O,
283 ;; has score zero because there is no more any point in playing in it, from
284 ;; both an attacking and a defending point of view.
285 ;;
286 ;; Given the score of every qtuple, the score of a given free square on the
287 ;; board is just the sum of the scores of all the qtuples to which it belongs,
288 ;; because playing in that square is playing in all its containing qtuples at
289 ;; once. And it is that function which takes into account the internesting of
290 ;; the qtuples.
291 ;;
292 ;; This algorithm is rather simple but anyway it gives a not so dumb level of
293 ;; play. It easily extends to "n-dimensional Gomoku", where a win should not
294 ;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !)
295 ;; should be preferred.
298 ;; Here are the scores of the nine "non-polluted" configurations. Tuning
299 ;; these values will change (hopefully improve) the strength of the program
300 ;; and may change its style (rather aggressive here).
302 (defconst gomoku-nil-score 7 "Score of an empty qtuple.")
303 (defconst gomoku-Xscore 15 "Score of a qtuple containing one X.")
304 (defconst gomoku-XXscore 400 "Score of a qtuple containing two X's.")
305 (defconst gomoku-XXXscore 1800 "Score of a qtuple containing three X's.")
306 (defconst gomoku-XXXXscore 100000 "Score of a qtuple containing four X's.")
307 (defconst gomoku-Oscore 35 "Score of a qtuple containing one O.")
308 (defconst gomoku-OOscore 800 "Score of a qtuple containing two O's.")
309 (defconst gomoku-OOOscore 15000 "Score of a qtuple containing three O's.")
310 (defconst gomoku-OOOOscore 800000 "Score of a qtuple containing four O's.")
312 ;; These values are not just random: if, given the following situation:
313 ;;
314 ;; . . . . . . . O .
315 ;; . X X a . . . X .
316 ;; . . . X . . . X .
317 ;; . . . X . . . X .
318 ;; . . . . . . . b .
319 ;;
320 ;; you want Emacs to play in "a" and not in "b", then the parameters must
321 ;; satisfy the inequality:
322 ;;
323 ;; 6 * gomoku-XXscore > gomoku-XXXscore + gomoku-XXscore
324 ;;
325 ;; because "a" mainly belongs to six "XX" qtuples (the others are less
326 ;; important) while "b" belongs to one "XXX" and one "XX" qtuples. Other
327 ;; conditions are required to obtain sensible moves, but the previous example
328 ;; should illustrate the point. If you manage to improve on these values,
329 ;; please send me a note. Thanks.
332 ;; As we chose values 0, 1 and 6 to denote empty, X and O squares, the
333 ;; contents of a qtuple are uniquely determined by the sum of its elements and
334 ;; we just have to set up a translation table.
336 (defconst gomoku-score-trans-table
337 (vector gomoku-nil-score gomoku-Xscore gomoku-XXscore gomoku-XXXscore gomoku-XXXXscore 0
338 gomoku-Oscore 0 0 0 0 0
339 gomoku-OOscore 0 0 0 0 0
340 gomoku-OOOscore 0 0 0 0 0
341 gomoku-OOOOscore 0 0 0 0 0
342 0)
343 "Vector associating qtuple contents to their score.")
346 ;; If you do not modify drastically the previous constants, the only way for a
347 ;; square to have a score higher than gomoku-OOOOscore is to belong to a "OOOO"
348 ;; qtuple, thus to be a winning move. Similarly, the only way for a square to
349 ;; have a score between gomoku-XXXXscore and gomoku-OOOOscore is to belong to a "XXXX"
350 ;; qtuple. We may use these considerations to detect when a given move is
351 ;; winning or losing.
353 (defconst gomoku-winning-threshold gomoku-OOOOscore
354 "Threshold score beyond which an Emacs move is winning.")
356 (defconst gomoku-losing-threshold gomoku-XXXXscore
357 "Threshold score beyond which a human move is winning.")
360 (defun gomoku-strongest-square ()
361 "Compute index of free square with highest score, or nil if none."
362 ;; We just have to loop other all squares. However there are two problems:
363 ;; 1/ The SCORE-TABLE only gives correct scores to free squares. To speed
364 ;; up future searches, we set the score of padding or occupied squares
365 ;; to -1 whenever we meet them.
366 ;; 2/ We want to choose randomly between equally good moves.
367 (let ((score-max 0)
368 (count 0) ; Number of equally good moves
369 (square (gomoku-xy-to-index 1 1)) ; First square
370 (end (gomoku-xy-to-index gomoku-board-width gomoku-board-height))
371 best-square score)
372 (while (<= square end)
373 (cond
374 ;; If score is lower (i.e. most of the time), skip to next:
375 ((< (aref gomoku-score-table square) score-max))
376 ;; If score is better, beware of non free squares:
377 ((> (setq score (aref gomoku-score-table square)) score-max)
378 (if (zerop (aref gomoku-board square)) ; is it free ?
379 (setq count 1 ; yes: take it !
380 best-square square
381 score-max score)
382 (aset gomoku-score-table square -1))) ; no: kill it !
383 ;; If score is equally good, choose randomly. But first check freeness:
384 ((not (zerop (aref gomoku-board square)))
385 (aset gomoku-score-table square -1))
386 ((zerop (random (setq count (1+ count))))
387 (setq best-square square
388 score-max score)))
389 (setq square (1+ square))) ; try next square
390 best-square))
391 \f
392 ;;;
393 ;;; INITIALIZING THE SCORE TABLE.
394 ;;;
396 ;; At initialization the board is empty so that every qtuple amounts for
397 ;; gomoku-nil-score. Therefore, the score of any square is gomoku-nil-score times the number
398 ;; of qtuples that pass through it. This number is 3 in a corner and 20 if you
399 ;; are sufficiently far from the sides. As computing the number is time
400 ;; consuming, we initialize every square with 20*gomoku-nil-score and then only
401 ;; consider squares at less than 5 squares from one side. We speed this up by
402 ;; taking symmetry into account.
403 ;; Also, as it is likely that successive games will be played on a board with
404 ;; same size, it is a good idea to save the initial SCORE-TABLE configuration.
406 (defvar gomoku-saved-score-table nil
407 "Recorded initial value of previous score table.")
409 (defvar gomoku-saved-board-width nil
410 "Recorded value of previous board width.")
412 (defvar gomoku-saved-board-height nil
413 "Recorded value of previous board height.")
416 (defun gomoku-init-score-table ()
417 "Create the score table vector and fill it with initial values."
418 (if (and gomoku-saved-score-table ; Has it been stored last time ?
419 (= gomoku-board-width gomoku-saved-board-width)
420 (= gomoku-board-height gomoku-saved-board-height))
421 (setq gomoku-score-table (copy-sequence gomoku-saved-score-table))
422 ;; No, compute it:
423 (setq gomoku-score-table
424 (make-vector gomoku-vector-length (* 20 gomoku-nil-score)))
425 (let (i j maxi maxj maxi2 maxj2)
426 (setq maxi (/ (1+ gomoku-board-width) 2)
427 maxj (/ (1+ gomoku-board-height) 2)
428 maxi2 (min 4 maxi)
429 maxj2 (min 4 maxj))
430 ;; We took symmetry into account and could use it more if the board
431 ;; would have been square and not rectangular !
432 ;; In our case we deal with all (i,j) in the set [1..maxi2]*[1..maxj] U
433 ;; [maxi2+1..maxi]*[1..maxj2]. Maxi2 and maxj2 are used because the
434 ;; board may well be less than 8 by 8 !
435 (setq i 1)
436 (while (<= i maxi2)
437 (setq j 1)
438 (while (<= j maxj)
439 (gomoku-init-square-score i j)
440 (setq j (1+ j)))
441 (setq i (1+ i)))
442 (while (<= i maxi)
443 (setq j 1)
444 (while (<= j maxj2)
445 (gomoku-init-square-score i j)
446 (setq j (1+ j)))
447 (setq i (1+ i))))
448 (setq gomoku-saved-score-table (copy-sequence gomoku-score-table)
449 gomoku-saved-board-width gomoku-board-width
450 gomoku-saved-board-height gomoku-board-height)))
452 (defun gomoku-nb-qtuples (i j)
453 "Return the number of qtuples containing square I,J."
454 ;; This function is complicated because we have to deal
455 ;; with ugly cases like 3 by 6 boards, but it works.
456 ;; If you have a simpler (and correct) solution, send it to me. Thanks !
457 (let ((left (min 4 (1- i)))
458 (right (min 4 (- gomoku-board-width i)))
459 (up (min 4 (1- j)))
460 (down (min 4 (- gomoku-board-height j))))
461 (+ -12
462 (min (max (+ left right) 3) 8)
463 (min (max (+ up down) 3) 8)
464 (min (max (+ (min left up) (min right down)) 3) 8)
465 (min (max (+ (min right up) (min left down)) 3) 8))))
467 (defun gomoku-init-square-score (i j)
468 "Give initial score to square I,J and to its mirror images."
469 (let ((ii (1+ (- gomoku-board-width i)))
470 (jj (1+ (- gomoku-board-height j)))
471 (sc (* (gomoku-nb-qtuples i j) (aref gomoku-score-trans-table 0))))
472 (aset gomoku-score-table (gomoku-xy-to-index i j) sc)
473 (aset gomoku-score-table (gomoku-xy-to-index ii j) sc)
474 (aset gomoku-score-table (gomoku-xy-to-index i jj) sc)
475 (aset gomoku-score-table (gomoku-xy-to-index ii jj) sc)))
476 \f
477 ;;;
478 ;;; MAINTAINING THE SCORE TABLE.
479 ;;;
481 ;; We do not provide functions for computing the SCORE-TABLE given the
482 ;; contents of the BOARD. This would involve heavy nested loops, with time
483 ;; proportional to the size of the board. It is better to update the
484 ;; SCORE-TABLE after each move. Updating needs not modify more than 36
485 ;; squares: it is done in constant time.
487 (defun gomoku-update-score-table (square dval)
488 "Update score table after SQUARE received a DVAL increment."
489 ;; The board has already been updated when this function is called.
490 ;; Updating scores is done by looking for qtuples boundaries in all four
491 ;; directions and then calling update-score-in-direction.
492 ;; Finally all squares received the right increment, and then are up to
493 ;; date, except possibly for SQUARE itself if we are taking a move back for
494 ;; its score had been set to -1 at the time.
495 (let* ((x (gomoku-index-to-x square))
496 (y (gomoku-index-to-y square))
497 (imin (max -4 (- 1 x)))
498 (jmin (max -4 (- 1 y)))
499 (imax (min 0 (- gomoku-board-width x 4)))
500 (jmax (min 0 (- gomoku-board-height y 4))))
501 (gomoku-update-score-in-direction imin imax
502 square 1 0 dval)
503 (gomoku-update-score-in-direction jmin jmax
504 square 0 1 dval)
505 (gomoku-update-score-in-direction (max imin jmin) (min imax jmax)
506 square 1 1 dval)
507 (gomoku-update-score-in-direction (max (- 1 y) -4
508 (- x gomoku-board-width))
509 (min 0 (- x 5)
510 (- gomoku-board-height y 4))
511 square -1 1 dval)))
513 (defun gomoku-update-score-in-direction (left right square dx dy dval)
514 "Update scores for all squares in the qtuples starting between the LEFTth
515 square and the RIGHTth after SQUARE, along the DX, DY direction, considering
516 that DVAL has been added on SQUARE."
517 ;; We always have LEFT <= 0, RIGHT <= 0 and DEPL > 0 but we may very well
518 ;; have LEFT > RIGHT, indicating that no qtuple contains SQUARE along that
519 ;; DX,DY direction.
520 (cond
521 ((> left right)) ; Quit
522 (t ; Else ..
523 (let (depl square0 square1 square2 count delta)
524 (setq depl (gomoku-xy-to-index dx dy)
525 square0 (+ square (* left depl))
526 square1 (+ square (* right depl))
527 square2 (+ square0 (* 4 depl)))
528 ;; Compute the contents of the first qtuple:
529 (setq square square0
530 count 0)
531 (while (<= square square2)
532 (setq count (+ count (aref gomoku-board square))
533 square (+ square depl)))
534 (while (<= square0 square1)
535 ;; Update the squares of the qtuple beginning in SQUARE0 and ending
536 ;; in SQUARE2.
537 (setq delta (- (aref gomoku-score-trans-table count)
538 (aref gomoku-score-trans-table (- count dval))))
539 (cond ((not (zerop delta)) ; or else nothing to update
540 (setq square square0)
541 (while (<= square square2)
542 (if (zerop (aref gomoku-board square)) ; only for free squares
543 (aset gomoku-score-table square
544 (+ (aref gomoku-score-table square) delta)))
545 (setq square (+ square depl)))))
546 ;; Then shift the qtuple one square along DEPL, this only requires
547 ;; modifying SQUARE0 and SQUARE2.
548 (setq square2 (+ square2 depl)
549 count (+ count (- (aref gomoku-board square0))
550 (aref gomoku-board square2))
551 square0 (+ square0 depl)))))))
552 \f
553 ;;;
554 ;;; GAME CONTROL.
555 ;;;
557 ;; Several variables are used to monitor a game, including a GAME-HISTORY (the
558 ;; list of all (SQUARE . PREVSCORE) played) that allows to take moves back
559 ;; (anti-updating the score table) and to compute the table from scratch in
560 ;; case of an interruption.
562 (defvar gomoku-game-in-progress nil
563 "Non-nil if a game is in progress.")
565 (defvar gomoku-game-history nil
566 "A record of all moves that have been played during current game.")
568 (defvar gomoku-number-of-moves nil
569 "Number of moves already played in current game.")
571 (defvar gomoku-number-of-human-moves nil
572 "Number of moves already played by human in current game.")
574 (defvar gomoku-emacs-played-first nil
575 "Non-nil if Emacs played first.")
577 (defvar gomoku-human-took-back nil
578 "Non-nil if Human took back a move during the game.")
580 (defvar gomoku-human-refused-draw nil
581 "Non-nil if Human refused Emacs offer of a draw.")
583 (defvar gomoku-emacs-is-computing nil
584 ;; This is used to detect interruptions. Hopefully, it should not be needed.
585 "Non-nil if Emacs is in the middle of a computation.")
588 (defun gomoku-start-game (n m)
589 "Initialize a new game on an N by M board."
590 (setq gomoku-emacs-is-computing t) ; Raise flag
591 (setq gomoku-game-in-progress t)
592 (setq gomoku-board-width n
593 gomoku-board-height m
594 gomoku-vector-length (1+ (* (+ m 2) (1+ n)))
595 gomoku-draw-limit (/ (* 7 n m) 10))
596 (setq gomoku-emacs-won nil
597 gomoku-game-history nil
598 gomoku-number-of-moves 0
599 gomoku-number-of-human-moves 0
600 gomoku-emacs-played-first nil
601 gomoku-human-took-back nil
602 gomoku-human-refused-draw nil)
603 (gomoku-init-display n m) ; Display first: the rest takes time
604 (gomoku-init-score-table) ; INIT-BOARD requires that the score
605 (gomoku-init-board) ; table be already created.
606 (setq gomoku-emacs-is-computing nil))
608 (defun gomoku-play-move (square val &optional dont-update-score)
609 "Go to SQUARE, play VAL and update everything."
610 (setq gomoku-emacs-is-computing t) ; Raise flag
611 (cond ((= 1 val) ; a Human move
612 (setq gomoku-number-of-human-moves (1+ gomoku-number-of-human-moves)))
613 ((zerop gomoku-number-of-moves) ; an Emacs move. Is it first ?
614 (setq gomoku-emacs-played-first t)))
615 (setq gomoku-game-history
616 (cons (cons square (aref gomoku-score-table square))
617 gomoku-game-history)
618 gomoku-number-of-moves (1+ gomoku-number-of-moves))
619 (gomoku-plot-square square val)
620 (aset gomoku-board square val) ; *BEFORE* UPDATE-SCORE !
621 (if dont-update-score nil
622 (gomoku-update-score-table square val) ; previous val was 0: dval = val
623 (aset gomoku-score-table square -1))
624 (setq gomoku-emacs-is-computing nil))
626 (defun gomoku-take-back ()
627 "Take back last move and update everything."
628 (setq gomoku-emacs-is-computing t)
629 (let* ((last-move (car gomoku-game-history))
630 (square (car last-move))
631 (oldval (aref gomoku-board square)))
632 (if (= 1 oldval)
633 (setq gomoku-number-of-human-moves (1- gomoku-number-of-human-moves)))
634 (setq gomoku-game-history (cdr gomoku-game-history)
635 gomoku-number-of-moves (1- gomoku-number-of-moves))
636 (gomoku-plot-square square 0)
637 (aset gomoku-board square 0) ; *BEFORE* UPDATE-SCORE !
638 (gomoku-update-score-table square (- oldval))
639 (aset gomoku-score-table square (cdr last-move)))
640 (setq gomoku-emacs-is-computing nil))
641 \f
642 ;;;
643 ;;; SESSION CONTROL.
644 ;;;
646 (defvar gomoku-number-of-emacs-wins 0
647 "Number of games Emacs won in this session.")
649 (defvar gomoku-number-of-human-wins 0
650 "Number of games you won in this session.")
652 (defvar gomoku-number-of-draws 0
653 "Number of games already drawn in this session.")
656 (defun gomoku-terminate-game (result)
657 "Terminate the current game with RESULT."
658 (message
659 (cond
660 ((eq result 'emacs-won)
661 (setq gomoku-number-of-emacs-wins (1+ gomoku-number-of-emacs-wins))
662 (cond ((< gomoku-number-of-moves 20)
663 "This was a REALLY QUICK win.")
664 (gomoku-human-refused-draw
665 "I won... Too bad you refused my offer of a draw!")
666 (gomoku-human-took-back
667 "I won... Taking moves back will not help you!")
668 ((not gomoku-emacs-played-first)
669 "I won... Playing first did not help you much!")
670 ((and (zerop gomoku-number-of-human-wins)
671 (zerop gomoku-number-of-draws)
672 (> gomoku-number-of-emacs-wins 1))
673 "I'm becoming tired of winning...")
674 ("I won.")))
675 ((eq result 'human-won)
676 (setq gomoku-number-of-human-wins (1+ gomoku-number-of-human-wins))
677 (concat "OK, you won this one."
678 (cond
679 (gomoku-human-took-back
680 " I, for one, never take my moves back...")
681 (gomoku-emacs-played-first
682 ".. so what?")
683 (" Now, let me play first just once."))))
684 ((eq result 'human-resigned)
685 (setq gomoku-number-of-emacs-wins (1+ gomoku-number-of-emacs-wins))
686 "So you resign. That's just one more win for me.")
687 ((eq result 'nobody-won)
688 (setq gomoku-number-of-draws (1+ gomoku-number-of-draws))
689 (concat "This is a draw. "
690 (cond
691 (gomoku-human-took-back
692 "I, for one, never take my moves back...")
693 (gomoku-emacs-played-first
694 "Just chance, I guess.")
695 ("Now, let me play first just once."))))
696 ((eq result 'draw-agreed)
697 (setq gomoku-number-of-draws (1+ gomoku-number-of-draws))
698 (concat "Draw agreed. "
699 (cond
700 (gomoku-human-took-back
701 "I, for one, never take my moves back...")
702 (gomoku-emacs-played-first
703 "You were lucky.")
704 ("Now, let me play first just once."))))
705 ((eq result 'crash-game)
706 "Sorry, I have been interrupted and cannot resume that game...")))
707 (gomoku-display-statistics)
708 ;;(ding)
709 (setq gomoku-game-in-progress nil))
711 (defun gomoku-crash-game ()
712 "What to do when Emacs detects it has been interrupted."
713 (setq gomoku-emacs-is-computing nil)
714 (gomoku-terminate-game 'crash-game)
715 (sit-for 4) ; Let's see the message
716 (gomoku-prompt-for-other-game))
717 \f
718 ;;;
719 ;;; INTERACTIVE COMMANDS.
720 ;;;
722 ;;;###autoload
723 (defun gomoku (&optional n m)
724 "Start a Gomoku game between you and Emacs.
726 If a game is in progress, this command allows you to resume it.
727 If optional arguments N and M are given, an N by M board is used.
728 If prefix arg is given for N, M is prompted for.
730 You and Emacs play in turn by marking a free square. You mark it with X
731 and Emacs marks it with O. The winner is the first to get five contiguous
732 marks horizontally, vertically or in diagonal.
734 You play by moving the cursor over the square you choose and hitting
737 This program actually plays a simplified or archaic version of the
738 Gomoku game, and ought to be upgraded to use the full modern rules.
741 (interactive (if current-prefix-arg
742 (list (prefix-numeric-value current-prefix-arg)
743 (eval (read-minibuffer "Height: ")))))
744 ;; gomoku-switch-to-window, but without the potential call to gomoku
745 ;; from gomoku-prompt-for-other-game.
746 (if (get-buffer gomoku-buffer-name)
747 (switch-to-buffer gomoku-buffer-name)
748 (when gomoku-game-in-progress
749 (setq gomoku-emacs-is-computing nil)
750 (gomoku-terminate-game 'crash-game)
751 (sit-for 4)
752 (or (y-or-n-p "Another game? ") (error "Chicken!")))
753 (switch-to-buffer gomoku-buffer-name)
754 (gomoku-mode))
755 (cond
756 (gomoku-emacs-is-computing
757 (gomoku-crash-game))
758 ((or (not gomoku-game-in-progress)
759 (<= gomoku-number-of-moves 2))
760 (let ((max-width (gomoku-max-width))
761 (max-height (gomoku-max-height)))
762 (or n (setq n max-width))
763 (or m (setq m max-height))
764 (cond ((< n 1)
765 (error "I need at least 1 column"))
766 ((< m 1)
767 (error "I need at least 1 row"))
768 ((> n max-width)
769 (error "I cannot display %d columns in that window" n)))
770 (if (and (> m max-height)
771 (not (eq m gomoku-saved-board-height))
772 ;; Use EQ because SAVED-BOARD-HEIGHT may be nil
773 (not (y-or-n-p (format "Do you really want %d rows? " m))))
774 (setq m max-height)))
775 (message "One moment, please...")
776 (gomoku-start-game n m)
777 (if (y-or-n-p "Do you allow me to play first? ")
778 (gomoku-emacs-plays)
779 (gomoku-prompt-for-move)))
780 ((y-or-n-p "Shall we continue our game? ")
781 (gomoku-prompt-for-move))
782 (t
783 (gomoku-human-resigns))))
785 (defun gomoku-emacs-plays ()
786 "Compute Emacs next move and play it."
787 (interactive)
788 (gomoku-switch-to-window)
789 (cond
790 (gomoku-emacs-is-computing
791 (gomoku-crash-game))
792 ((not gomoku-game-in-progress)
793 (gomoku-prompt-for-other-game))
794 (t
795 (message "Let me think...")
796 (let (square score)
797 (setq square (gomoku-strongest-square))
798 (cond ((null square)
799 (gomoku-terminate-game 'nobody-won))
800 (t
801 (setq score (aref gomoku-score-table square))
802 (gomoku-play-move square 6)
803 (cond ((>= score gomoku-winning-threshold)
804 (setq gomoku-emacs-won t) ; for font-lock
805 (gomoku-find-filled-qtuple square 6)
806 (gomoku-terminate-game 'emacs-won))
807 ((zerop score)
808 (gomoku-terminate-game 'nobody-won))
809 ((and (> gomoku-number-of-moves gomoku-draw-limit)
810 (not gomoku-human-refused-draw)
811 (gomoku-offer-a-draw))
812 (gomoku-terminate-game 'draw-agreed))
813 (t
814 (gomoku-prompt-for-move)))))))))
816 ;; For small square dimensions this is approximate, since though measured in
817 ;; pixels, event's (X . Y) is a character's top-left corner.
818 (defun gomoku-click (click)
819 "Position at the square where you click."
820 (interactive "e")
821 (and (windowp (posn-window (setq click (event-end click))))
822 (numberp (posn-point click))
823 (select-window (posn-window click))
824 (setq click (posn-col-row click))
825 (gomoku-goto-xy
826 (min (max (/ (+ (- (car click)
827 gomoku-x-offset
828 1)
829 (window-hscroll)
830 gomoku-square-width
831 (% gomoku-square-width 2)
832 (/ gomoku-square-width 2))
833 gomoku-square-width)
834 1)
835 gomoku-board-width)
836 (min (max (/ (+ (- (cdr click)
837 gomoku-y-offset
838 1)
839 (let ((inhibit-point-motion-hooks t))
840 (count-lines 1 (window-start)))
841 gomoku-square-height
842 (% gomoku-square-height 2)
843 (/ gomoku-square-height 2))
844 gomoku-square-height)
845 1)
846 gomoku-board-height))))
848 (defun gomoku-mouse-play (click)
849 "Play at the square where you click."
850 (interactive "e")
851 (if (gomoku-click click)
852 (gomoku-human-plays)))
854 (defun gomoku-human-plays ()
855 "Signal to the Gomoku program that you have played.
856 You must have put the cursor on the square where you want to play.
857 If the game is finished, this command requests for another game."
858 (interactive)
859 (gomoku-switch-to-window)
860 (cond
861 (gomoku-emacs-is-computing
862 (gomoku-crash-game))
863 ((not gomoku-game-in-progress)
864 (gomoku-prompt-for-other-game))
865 (t
866 (let (square score)
867 (setq square (gomoku-point-square))
868 (cond ((null square)
869 (error "Your point is not on a square. Retry!"))
870 ((not (zerop (aref gomoku-board square)))
871 (error "Your point is not on a free square. Retry!"))
872 (t
873 (setq score (aref gomoku-score-table square))
874 (gomoku-play-move square 1)
875 (cond ((and (>= score gomoku-losing-threshold)
876 ;; Just testing SCORE > THRESHOLD is not enough for
877 ;; detecting wins, it just gives an indication that
878 ;; we confirm with GOMOKU-FIND-FILLED-QTUPLE.
879 (gomoku-find-filled-qtuple square 1))
880 (gomoku-terminate-game 'human-won))
881 (t
882 (gomoku-emacs-plays)))))))))
884 (defun gomoku-human-takes-back ()
885 "Signal to the Gomoku program that you wish to take back your last move."
886 (interactive)
887 (gomoku-switch-to-window)
888 (cond
889 (gomoku-emacs-is-computing
890 (gomoku-crash-game))
891 ((not gomoku-game-in-progress)
892 (message "Too late for taking back...")
893 (sit-for 4)
894 (gomoku-prompt-for-other-game))
895 ((zerop gomoku-number-of-human-moves)
896 (message "You have not played yet... Your move?"))
897 (t
898 (message "One moment, please...")
899 ;; It is possible for the user to let Emacs play several consecutive
900 ;; moves, so that the best way to know when to stop taking back moves is
901 ;; to count the number of human moves:
902 (setq gomoku-human-took-back t)
903 (let ((number gomoku-number-of-human-moves))
904 (while (= number gomoku-number-of-human-moves)
905 (gomoku-take-back)))
906 (gomoku-prompt-for-move))))
908 (defun gomoku-human-resigns ()
909 "Signal to the Gomoku program that you may want to resign."
910 (interactive)
911 (gomoku-switch-to-window)
912 (cond
913 (gomoku-emacs-is-computing
914 (gomoku-crash-game))
915 ((not gomoku-game-in-progress)
916 (message "There is no game in progress"))
917 ((y-or-n-p "You mean, you resign? ")
918 (gomoku-terminate-game 'human-resigned))
919 ((y-or-n-p "You mean, we continue? ")
920 (gomoku-prompt-for-move))
921 (t
922 (gomoku-terminate-game 'human-resigned)))) ; OK. Accept it
923 \f
924 ;;;
925 ;;; PROMPTING THE HUMAN PLAYER.
926 ;;;
928 (defun gomoku-prompt-for-move ()
929 "Display a message asking for Human's move."
930 (message (if (zerop gomoku-number-of-human-moves)
931 "Your move? (Move to a free square and hit X, RET ...)"
932 "Your move?")))
934 (defun gomoku-prompt-for-other-game ()
935 "Ask for another game, and start it."
936 (if (y-or-n-p "Another game? ")
937 (gomoku gomoku-board-width gomoku-board-height)
938 (error "Chicken!")))
940 (defun gomoku-offer-a-draw ()
941 "Offer a draw and return t if Human accepted it."
942 (or (y-or-n-p "I offer you a draw. Do you accept it? ")
943 (not (setq gomoku-human-refused-draw t))))
944 \f
945 ;;;
946 ;;; DISPLAYING THE BOARD.
947 ;;;
949 (defun gomoku-max-width ()
950 "Largest possible board width for the current window."
951 (1+ (/ (- (window-width (selected-window))
952 gomoku-x-offset gomoku-x-offset 1)
953 gomoku-square-width)))
955 (defun gomoku-max-height ()
956 "Largest possible board height for the current window."
957 (1+ (/ (- (window-height (selected-window))
958 gomoku-y-offset gomoku-y-offset 2)
959 ;; 2 instead of 1 because WINDOW-HEIGHT includes the mode line !
960 gomoku-square-height)))
962 (defun gomoku-point-y ()
963 "Return the board row where point is."
964 (let ((inhibit-point-motion-hooks t))
965 (1+ (/ (- (count-lines 1 (point)) gomoku-y-offset (if (bolp) 0 1))
966 gomoku-square-height))))
968 (defun gomoku-point-square ()
969 "Return the index of the square point is on."
970 (let ((inhibit-point-motion-hooks t))
971 (gomoku-xy-to-index (1+ (/ (- (current-column) gomoku-x-offset)
972 gomoku-square-width))
973 (gomoku-point-y))))
975 (defun gomoku-goto-square (index)
976 "Move point to square number INDEX."
977 (gomoku-goto-xy (gomoku-index-to-x index) (gomoku-index-to-y index)))
979 (defun gomoku-goto-xy (x y)
980 "Move point to square at X, Y coords."
981 (let ((inhibit-point-motion-hooks t))
982 (goto-char (point-min))
983 (forward-line (+ gomoku-y-offset (* gomoku-square-height (1- y)))))
984 (move-to-column (+ gomoku-x-offset (* gomoku-square-width (1- x)))))
986 (defun gomoku-plot-square (square value)
987 "Draw 'X', 'O' or '.' on SQUARE depending on VALUE, leave point there."
988 (or (= value 1)
989 (gomoku-goto-square square))
990 (let ((inhibit-read-only t)
991 (inhibit-point-motion-hooks t))
992 (insert-and-inherit (cond ((= value 1) ?X)
993 ((= value 6) ?O)
994 (?.)))
995 (and (zerop value)
996 (add-text-properties
997 (1- (point)) (point)
998 '(mouse-face highlight help-echo "mouse-2: play at this square")))
999 (delete-char 1)
1000 (backward-char 1))
1001 (sit-for 0)) ; Display NOW
1003 (defun gomoku-init-display (n m)
1004 "Display an N by M Gomoku board."
1005 (buffer-disable-undo (current-buffer))
1006 (let ((inhibit-read-only t)
1007 (point 1) opoint
1008 (intangible t)
1009 (i m) j x)
1010 ;; Try to minimize number of chars (because of text properties)
1011 (setq tab-width
1012 (if (zerop (% gomoku-x-offset gomoku-square-width))
1013 gomoku-square-width
1014 (max (/ (+ (% gomoku-x-offset gomoku-square-width)
1015 gomoku-square-width 1) 2) 2)))
1016 (erase-buffer)
1017 (newline gomoku-y-offset)
1018 (while (progn
1019 (setq j n
1020 x (- gomoku-x-offset gomoku-square-width))
1021 (while (>= (setq j (1- j)) 0)
1023 (current-column))
1024 tab-width))
1025 (insert-char ? (- x (current-column)))
1026 (if (setq intangible (not intangible))
1027 (put-text-property point (point) 'intangible 2))
1028 (and (zerop j)
1029 (= i (- m 2))
1030 (progn
1031 (while (>= i 3)
1032 (append-to-buffer (current-buffer) opoint (point))
1033 (setq i (- i 2)))
1034 (goto-char (point-max))))
1035 (setq point (point))
1036 (insert ?.)
1037 (add-text-properties
1038 point (point)
1039 '(mouse-face highlight
1040 help-echo "mouse-2: play at this square")))
1041 (> (setq i (1- i)) 0))
1042 (if (= i (1- m))
1043 (setq opoint point))
1045 (or (eq (char-after 1) ?.)
1046 (put-text-property 1 2 'point-entered
1047 (lambda (x y) (if (bobp) (forward-char)))))
1048 (or intangible
1049 (put-text-property point (point) 'intangible 2))
1050 (put-text-property point (point) 'point-entered
1051 (lambda (x y) (if (eobp) (backward-char))))
1052 (put-text-property (point-min) (point) 'category 'gomoku-mode))
1053 (gomoku-goto-xy (/ (1+ n) 2) (/ (1+ m) 2)) ; center of the board
1054 (sit-for 0)) ; Display NOW
1056 (defun gomoku-display-statistics ()
1057 "Obnoxiously display some statistics about previous games in mode line."
1058 ;; We store this string in the mode-line-process local variable.
1059 ;; This is certainly not the cleanest way out ...
1060 (setq mode-line-process
1061 (format ": Won %d, lost %d%s"
1062 gomoku-number-of-human-wins
1063 gomoku-number-of-emacs-wins
1064 (if (zerop gomoku-number-of-draws)
1065 ""
1066 (format ", drew %d" gomoku-number-of-draws))))
1067 (force-mode-line-update))
1069 (defun gomoku-switch-to-window ()
1070 "Find or create the Gomoku buffer, and display it."
1071 (interactive)
1072 (if (get-buffer gomoku-buffer-name) ; Buffer exists:
1073 (switch-to-buffer gomoku-buffer-name) ; no problem.
1074 (if gomoku-game-in-progress
1075 (gomoku-crash-game)) ; buffer has been killed or something
1076 (switch-to-buffer gomoku-buffer-name) ; Anyway, start anew.
1077 (gomoku-mode)))
1078 \f
1079 ;;;
1080 ;;; CROSSING WINNING QTUPLES.
1081 ;;;
1083 ;; When someone succeeds in filling a qtuple, we draw a line over the five
1084 ;; corresponding squares. One problem is that the program does not know which
1085 ;; squares ! It only knows the square where the last move has been played and
1086 ;; who won. The solution is to scan the board along all four directions.
1088 (defun gomoku-find-filled-qtuple (square value)
1089 "Return t if SQUARE belongs to a qtuple filled with VALUEs."
1090 (or (gomoku-check-filled-qtuple square value 1 0)
1091 (gomoku-check-filled-qtuple square value 0 1)
1092 (gomoku-check-filled-qtuple square value 1 1)
1093 (gomoku-check-filled-qtuple square value -1 1)))
1095 (defun gomoku-check-filled-qtuple (square value dx dy)
1096 "Return t if SQUARE belongs to a qtuple filled with VALUEs along DX, DY."
1097 (let ((a 0) (b 0)
1098 (left square) (right square)
1099 (depl (gomoku-xy-to-index dx dy)))
1100 (while (and (> a -4) ; stretch tuple left
1101 (= value (aref gomoku-board (setq left (- left depl)))))
1102 (setq a (1- a)))
1103 (while (and (< b (+ a 4)) ; stretch tuple right
1104 (= value (aref gomoku-board (setq right (+ right depl)))))
1105 (setq b (1+ b)))
1106 (cond ((= b (+ a 4)) ; tuple length = 5 ?
1107 (gomoku-cross-qtuple (+ square (* a depl)) (+ square (* b depl))
1108 dx dy)
1109 t))))
1111 (defun gomoku-cross-qtuple (square1 square2 dx dy)
1112 "Cross every square between SQUARE1 and SQUARE2 in the DX, DY direction."
1113 (save-excursion ; Not moving point from last square
1114 (let ((depl (gomoku-xy-to-index dx dy))
1115 (inhibit-read-only t)
1116 (inhibit-point-motion-hooks t))
1117 ;; WARNING: this function assumes DEPL > 0 and SQUARE2 > SQUARE1
1118 (while (/= square1 square2)
1119 (gomoku-goto-square square1)
1120 (setq square1 (+ square1 depl))
1121 (cond
1122 ((= dy 0) ; Horizontal
1123 (forward-char 1)
1124 (insert-char ?- (1- gomoku-square-width) t)
1125 (delete-region (point) (progn
1127 (point))))
1128 ((= dx 0) ; Vertical
1129 (let ((n 1)
1130 (column (current-column)))
1131 (while (< n gomoku-square-height)
1132 (setq n (1+ n))
1133 (forward-line 1)
1134 (indent-to column)
1135 (insert-and-inherit ?|))))
1136 ((= dx -1) ; 1st Diagonal
1137 (indent-to (prog1 (- (current-column) (/ gomoku-square-width 2))
1138 (forward-line (/ gomoku-square-height 2))))
1139 (insert-and-inherit ?/))
1140 (t ; 2nd Diagonal
1141 (indent-to (prog1 (+ (current-column) (/ gomoku-square-width 2))
1142 (forward-line (/ gomoku-square-height 2))))
1144 (sit-for 0)) ; Display NOW
1145 \f
1146 ;;;
1147 ;;; CURSOR MOTION.
1148 ;;;
1149 ;; previous-line and next-line don't work right with intangible newlines
1150 (defun gomoku-move-down ()
1151 "Move point down one row on the Gomoku board."
1152 (interactive)
1153 (if (< (gomoku-point-y) gomoku-board-height)
1154 (let ((column (current-column)))
1155 (forward-line gomoku-square-height)
1156 (move-to-column column))))
1158 (defun gomoku-move-up ()
1159 "Move point up one row on the Gomoku board."
1160 (interactive)
1161 (if (> (gomoku-point-y) 1)
1162 (let ((column (current-column)))
1163 (forward-line (- 1 gomoku-square-height))
1164 (move-to-column column))))
1166 (defun gomoku-move-ne ()
1167 "Move point North East on the Gomoku board."
1168 (interactive)
1169 (gomoku-move-up)
1170 (forward-char))
1172 (defun gomoku-move-se ()
1173 "Move point South East on the Gomoku board."
1174 (interactive)
1175 (gomoku-move-down)
1176 (forward-char))
1178 (defun gomoku-move-nw ()
1179 "Move point North West on the Gomoku board."
1180 (interactive)
1181 (gomoku-move-up)
1182 (backward-char))
1184 (defun gomoku-move-sw ()
1185 "Move point South West on the Gomoku board."
1186 (interactive)
1187 (gomoku-move-down)
1188 (backward-char))
1190 (defun gomoku-beginning-of-line ()
1191 "Move point to first square on the Gomoku board row."
1192 (interactive)
1193 (move-to-column gomoku-x-offset))
1195 (defun gomoku-end-of-line ()
1196 "Move point to last square on the Gomoku board row."
1197 (interactive)
1198 (move-to-column (+ gomoku-x-offset
1199 (* gomoku-square-width (1- gomoku-board-width)))))
1201 (random t)
1203 (provide 'gomoku)
1205 ;;; gomoku.el ends here