1 ;;; gomoku.el --- Gomoku game between you and Emacs
3 ;; Copyright (C) 1988 Free Software Foundation, Inc.
5 ;; Author: Phillippe Schnoebelen <phs@lifia.imag.fr>
9 ;; This file is part of GNU Emacs.
11 ;; GNU Emacs is free software; you can redistribute it and/or modify
12 ;; it under the terms of the GNU General Public License as published by
13 ;; the Free Software Foundation; either version 2, or (at your option)
16 ;; GNU Emacs is distributed in the hope that it will be useful,
17 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
18 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 ;; GNU General Public License for more details.
21 ;; You should have received a copy of the GNU General Public License
22 ;; along with GNU Emacs; see the file COPYING. If not, write to
23 ;; the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
27 ;;; Gomoku game between you and GNU Emacs. Last modified on 13 Sep 1988
29 ;;; Written by Ph. Schnoebelen (phs@lifia.imag.fr), 1987, 1988
30 ;;; with precious advices from J.-F. Rit.
31 ;;; This has been tested with GNU Emacs 18.50.
35 ;; Gomoku is a game played between two players on a rectangular board. Each
36 ;; player, in turn, marks a free square of its choice. The winner is the first
37 ;; one to mark five contiguous squares in any direction (horizontally,
38 ;; vertically or diagonally).
40 ;; I have been told that, in "The TRUE Gomoku", some restrictions are made
41 ;; about the squares where one may play, or else there is a known forced win
42 ;; for the first player. This program has no such restriction, but it does not
43 ;; know about the forced win, nor do I. Furthermore, you probably do not know
47 ;; There are two main places where you may want to customize the program: key
48 ;; bindings and board display. These features are commented in the code. Go
54 ;; The command "M-x gomoku" displays a
55 ;; board, the size of which depends on the size of the current window. The
56 ;; size of the board is easily modified by giving numeric arguments to the
57 ;; gomoku command and/or by customizing the displaying parameters.
59 ;; Emacs plays when it is its turn. When it is your turn, just put the cursor
60 ;; on the square where you want to play and hit RET, or X, or whatever key you
61 ;; bind to the command gomoku-human-plays. When it is your turn, Emacs is
62 ;; idle: you may switch buffers, read your mail, ... Just come back to the
63 ;; *Gomoku* buffer and resume play.
68 ;; The algorithm is briefly described in section "THE SCORE TABLE". Some
69 ;; parameters may be modified if you want to change the style exhibited by the
75 ;;; GOMOKU MODE AND KEYMAP.
77 (defvar gomoku-mode-hook nil
78 "If non-nil, its value is called on entry to Gomoku mode.")
80 (defvar gomoku-mode-map nil
81 "Local keymap to use in Gomoku mode.")
83 (if gomoku-mode-map nil
84 (setq gomoku-mode-map
(make-sparse-keymap))
86 ;; Key bindings for cursor motion. Arrow keys are just "function"
88 (define-key gomoku-mode-map
"y" 'gomoku-move-nw
) ; Y
89 (define-key gomoku-mode-map
"u" 'gomoku-move-ne
) ; U
90 (define-key gomoku-mode-map
"b" 'gomoku-move-sw
) ; B
91 (define-key gomoku-mode-map
"n" 'gomoku-move-se
) ; N
92 (define-key gomoku-mode-map
"h" 'gomoku-move-left
) ; H
93 (define-key gomoku-mode-map
"l" 'gomoku-move-right
) ; L
94 (define-key gomoku-mode-map
"j" 'gomoku-move-down
) ; J
95 (define-key gomoku-mode-map
"k" 'gomoku-move-up
) ; K
96 (define-key gomoku-mode-map
"\C-n" 'gomoku-move-down
) ; C-N
97 (define-key gomoku-mode-map
"\C-p" 'gomoku-move-up
) ; C-P
98 (define-key gomoku-mode-map
"\C-f" 'gomoku-move-right
) ; C-F
99 (define-key gomoku-mode-map
"\C-b" 'gomoku-move-left
) ; C-B
101 ;; Key bindings for entering Human moves.
102 ;; If you have a mouse, you may also bind some mouse click ...
103 (define-key gomoku-mode-map
"X" 'gomoku-human-plays
) ; X
104 (define-key gomoku-mode-map
"x" 'gomoku-human-plays
) ; x
105 (define-key gomoku-mode-map
"\C-m" 'gomoku-human-plays
) ; RET
106 (define-key gomoku-mode-map
"\C-cp" 'gomoku-human-plays
) ; C-C P
107 (define-key gomoku-mode-map
"\C-cb" 'gomoku-human-takes-back
) ; C-C B
108 (define-key gomoku-mode-map
"\C-cr" 'gomoku-human-resigns
) ; C-C R
109 (define-key gomoku-mode-map
"\C-ce" 'gomoku-emacs-plays
) ; C-C E
111 (define-key gomoku-mode-map
[up] 'gomoku-move-up)
112 (define-key gomoku-mode-map [down] 'gomoku-move-down)
113 (define-key gomoku-mode-map [left] 'gomoku-move-left)
114 (define-key gomoku-mode-map [right] 'gomoku-move-right)
115 (define-key gomoku-mode-map [kp-enter] 'gomoku-human-plays)
116 (define-key gomoku-mode-map [insert] 'gomoku-human-plays))
118 (defun gomoku-mode ()
119 "Major mode for playing Gomoku against Emacs.
120 You and Emacs play in turn by marking a free square. You mark it with X
121 and Emacs marks it with O. The winner is the first to get five contiguous
122 marks horizontally, vertically or in diagonal.
124 You play by moving the cursor over the square you choose and hitting \\[gomoku-human-plays].
126 Other useful commands:
128 Entry to this mode calls the value of `gomoku-mode-hook' if that value
131 (setq major-mode 'gomoku-mode
133 (gomoku-display-statistics)
134 (use-local-map gomoku-mode-map)
135 (run-hooks 'gomoku-mode-hook))
141 ;; The board is a rectangular grid. We code empty squares with 0, X's with 1
142 ;; and O's with 6. The rectangle is recorded in a one dimensional vector
143 ;; containing padding squares (coded with -1). These squares allow us to
144 ;; detect when we are trying to move out of the board. We denote a square by
145 ;; its (X,Y) coords, or by the INDEX corresponding to them in the vector. The
146 ;; leftmost topmost square has coords (1,1) and index gomoku-board-width + 2.
147 ;; Similarly, vectors between squares may be given by two DX, DY coords or by
148 ;; one DEPL (the difference between indexes).
150 (defvar gomoku-board-width nil
151 "Number of columns on the Gomoku board.")
153 (defvar gomoku-board-height nil
154 "Number of lines on the Gomoku board.")
156 (defvar gomoku-board nil
157 "Vector recording the actual state of the Gomoku board.")
159 (defvar gomoku-vector-length nil
160 "Length of gomoku-board vector.")
162 (defvar gomoku-draw-limit nil
163 ;; This is usually set to 70% of the number of squares.
164 "After how many moves will Emacs offer a draw?")
167 (defun gomoku-xy-to-index (x y)
168 "Translate X, Y cartesian coords into the corresponding board index."
169 (+ (* y gomoku-board-width) x y))
171 (defun gomoku-index-to-x (index)
172 "Return corresponding x-coord of board INDEX."
173 (% index (1+ gomoku-board-width)))
175 (defun gomoku-index-to-y (index)
176 "Return corresponding y-coord of board INDEX."
177 (/ index (1+ gomoku-board-width)))
179 (defun gomoku-init-board ()
180 "Create the gomoku-board vector and fill it with initial values."
181 (setq gomoku-board (make-vector gomoku-vector-length 0))
182 ;; Every square is 0 (i.e. empty) except padding squares:
183 (let ((i 0) (ii (1- gomoku-vector-length)))
184 (while (<= i gomoku-board-width) ; The squares in [0..width] and in
185 (aset gomoku-board i -1) ; [length - width - 1..length - 1]
186 (aset gomoku-board ii -1) ; are padding squares.
190 (while (< i gomoku-vector-length)
191 (aset gomoku-board i -1) ; and also all k*(width+1)
192 (setq i (+ i gomoku-board-width 1)))))
198 ;; Every (free) square has a score associated to it, recorded in the
199 ;; GOMOKU-SCORE-TABLE vector. The program always plays in the square having
200 ;; the highest score.
202 (defvar gomoku-score-table nil
203 "Vector recording the actual score of the free squares.")
206 ;; The key point point about the algorithm is that, rather than considering
207 ;; the board as just a set of squares, we prefer to see it as a "space" of
208 ;; internested 5-tuples of contiguous squares (called qtuples).
210 ;; The aim of the program is to fill one qtuple with its O's while preventing
211 ;; you from filling another one with your X's. To that effect, it computes a
212 ;; score for every qtuple, with better qtuples having better scores. Of
213 ;; course, the score of a qtuple (taken in isolation) is just determined by
214 ;; its contents as a set, i.e. not considering the order of its elements. The
215 ;; highest score is given to the "OOOO" qtuples because playing in such a
216 ;; qtuple is winning the game. Just after this comes the "XXXX" qtuple because
217 ;; not playing in it is just loosing the game, and so on. Note that a
218 ;; "polluted" qtuple, i.e. one containing at least one X and at least one O,
219 ;; has score zero because there is no more any point in playing in it, from
220 ;; both an attacking and a defending point of view.
222 ;; Given the score of every qtuple, the score of a given free square on the
223 ;; board is just the sum of the scores of all the qtuples to which it belongs,
224 ;; because playing in that square is playing in all its containing qtuples at
225 ;; once. And it is that function which takes into account the internesting of
228 ;; This algorithm is rather simple but anyway it gives a not so dumb level of
229 ;; play. It easily extends to "n-dimensional Gomoku", where a win should not
230 ;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !)
231 ;; should be preferred.
234 ;; Here are the scores of the nine "non-polluted" configurations. Tuning
235 ;; these values will change (hopefully improve) the strength of the program
236 ;; and may change its style (rather aggressive here).
238 (defconst nil-score 7 "Score of an empty qtuple.")
239 (defconst Xscore 15 "Score of a qtuple containing one X.")
240 (defconst XXscore 400 "Score of a qtuple containing two X's.")
241 (defconst XXXscore 1800 "Score of a qtuple containing three X's.")
242 (defconst XXXXscore 100000 "Score of a qtuple containing four X's.")
243 (defconst Oscore 35 "Score of a qtuple containing one O.")
244 (defconst OOscore 800 "Score of a qtuple containing two O's.")
245 (defconst OOOscore 15000 "Score of a qtuple containing three O's.")
246 (defconst OOOOscore 800000 "Score of a qtuple containing four O's.")
248 ;; These values are not just random: if, given the following situation:
256 ;; you want Emacs to play in "a" and not in "b", then the parameters must
257 ;; satisfy the inequality:
259 ;; 6 * XXscore > XXXscore + XXscore
261 ;; because "a" mainly belongs to six "XX" qtuples (the others are less
262 ;; important) while "b" belongs to one "XXX" and one "XX" qtuples. Other
263 ;; conditions are required to obtain sensible moves, but the previous example
264 ;; should illustrate the point. If you manage to improve on these values,
265 ;; please send me a note. Thanks.
268 ;; As we choosed values 0, 1 and 6 to denote empty, X and O squares, the
269 ;; contents of a qtuple is uniquely determined by the sum of its elements and
270 ;; we just have to set up a translation table.
272 (defconst gomoku-score-trans-table
273 (vector nil-score Xscore XXscore XXXscore XXXXscore 0
279 "Vector associating qtuple contents to their score.")
282 ;; If you do not modify drastically the previous constants, the only way for a
283 ;; square to have a score higher than OOOOscore is to belong to a "OOOO"
284 ;; qtuple, thus to be a winning move. Similarly, the only way for a square to
285 ;; have a score between XXXXscore and OOOOscore is to belong to a "XXXX"
286 ;; qtuple. We may use these considerations to detect when a given move is
287 ;; winning or loosing.
289 (defconst gomoku-winning-threshold OOOOscore
290 "Threshold score beyond which an Emacs move is winning.")
292 (defconst gomoku-loosing-threshold XXXXscore
293 "Threshold score beyond which a human move is winning.")
296 (defun gomoku-strongest-square ()
297 "Compute index of free square with highest score, or nil if none."
298 ;; We just have to loop other all squares. However there are two problems:
299 ;; 1/ The SCORE-TABLE only gives correct scores to free squares. To speed
300 ;; up future searches, we set the score of padding or occupied squares
301 ;; to -1 whenever we meet them.
302 ;; 2/ We want to choose randomly between equally good moves.
304 (count 0) ; Number of equally good moves
305 (square (gomoku-xy-to-index 1 1)) ; First square
306 (end (gomoku-xy-to-index gomoku-board-width gomoku-board-height))
308 (while (<= square end)
310 ;; If score is lower (i.e. most of the time), skip to next:
311 ((< (aref gomoku-score-table square) score-max))
312 ;; If score is better, beware of non free squares:
313 ((> (setq score (aref gomoku-score-table square)) score-max)
314 (if (zerop (aref gomoku-board square)) ; is it free ?
315 (setq count 1 ; yes: take it !
318 (aset gomoku-score-table square -1))) ; no: kill it !
319 ;; If score is equally good, choose randomly. But first check freeness:
320 ((not (zerop (aref gomoku-board square)))
321 (aset gomoku-score-table square -1))
322 ((zerop (random (setq count (1+ count))))
323 (setq best-square square
325 (setq square (1+ square))) ; try next square
329 ;;; INITIALIZING THE SCORE TABLE.
332 ;; At initialization the board is empty so that every qtuple amounts for
333 ;; nil-score. Therefore, the score of any square is nil-score times the number
334 ;; of qtuples that pass through it. This number is 3 in a corner and 20 if you
335 ;; are sufficiently far from the sides. As computing the number is time
336 ;; consuming, we initialize every square with 20*nil-score and then only
337 ;; consider squares at less than 5 squares from one side. We speed this up by
338 ;; taking symmetry into account.
339 ;; Also, as it is likely that successive games will be played on a board with
340 ;; same size, it is a good idea to save the initial SCORE-TABLE configuration.
342 (defvar gomoku-saved-score-table nil
343 "Recorded initial value of previous score table.")
345 (defvar gomoku-saved-board-width nil
346 "Recorded value of previous board width.")
348 (defvar gomoku-saved-board-height nil
349 "Recorded value of previous board height.")
352 (defun gomoku-init-score-table ()
353 "Create the score table vector and fill it with initial values."
354 (if (and gomoku-saved-score-table ; Has it been stored last time ?
355 (= gomoku-board-width gomoku-saved-board-width)
356 (= gomoku-board-height gomoku-saved-board-height))
357 (setq gomoku-score-table (copy-sequence gomoku-saved-score-table))
359 (setq gomoku-score-table
360 (make-vector gomoku-vector-length (* 20 nil-score)))
361 (let (i j maxi maxj maxi2 maxj2)
362 (setq maxi (/ (1+ gomoku-board-width) 2)
363 maxj (/ (1+ gomoku-board-height) 2)
366 ;; We took symmetry into account and could use it more if the board
367 ;; would have been square and not rectangular !
368 ;; In our case we deal with all (i,j) in the set [1..maxi2]*[1..maxj] U
369 ;; [maxi2+1..maxi]*[1..maxj2]. Maxi2 and maxj2 are used because the
370 ;; board may well be less than 8 by 8 !
375 (gomoku-init-square-score i j)
381 (gomoku-init-square-score i j)
384 (setq gomoku-saved-score-table (copy-sequence gomoku-score-table)
385 gomoku-saved-board-width gomoku-board-width
386 gomoku-saved-board-height gomoku-board-height)))
388 (defun gomoku-nb-qtuples (i j)
389 "Return the number of qtuples containing square I,J."
390 ;; This function is complicated because we have to deal
391 ;; with ugly cases like 3 by 6 boards, but it works.
392 ;; If you have a simpler (and correct) solution, send it to me. Thanks !
393 (let ((left (min 4 (1- i)))
394 (right (min 4 (- gomoku-board-width i)))
396 (down (min 4 (- gomoku-board-height j))))
398 (min (max (+ left right) 3) 8)
399 (min (max (+ up down) 3) 8)
400 (min (max (+ (min left up) (min right down)) 3) 8)
401 (min (max (+ (min right up) (min left down)) 3) 8))))
403 (defun gomoku-init-square-score (i j)
404 "Give initial score to square I,J and to its mirror images."
405 (let ((ii (1+ (- gomoku-board-width i)))
406 (jj (1+ (- gomoku-board-height j)))
407 (sc (* (gomoku-nb-qtuples i j) (aref gomoku-score-trans-table 0))))
408 (aset gomoku-score-table (gomoku-xy-to-index i j) sc)
409 (aset gomoku-score-table (gomoku-xy-to-index ii j) sc)
410 (aset gomoku-score-table (gomoku-xy-to-index i jj) sc)
411 (aset gomoku-score-table (gomoku-xy-to-index ii jj) sc)))
414 ;;; MAINTAINING THE SCORE TABLE.
417 ;; We do not provide functions for computing the SCORE-TABLE given the
418 ;; contents of the BOARD. This would involve heavy nested loops, with time
419 ;; proportional to the size of the board. It is better to update the
420 ;; SCORE-TABLE after each move. Updating needs not modify more than 36
421 ;; squares: it is done in constant time.
423 (defun gomoku-update-score-table (square dval)
424 "Update score table after SQUARE received a DVAL increment."
425 ;; The board has already been updated when this function is called.
426 ;; Updating scores is done by looking for qtuples boundaries in all four
427 ;; directions and then calling update-score-in-direction.
428 ;; Finally all squares received the right increment, and then are up to
429 ;; date, except possibly for SQUARE itself if we are taking a move back for
430 ;; its score had been set to -1 at the time.
431 (let* ((x (gomoku-index-to-x square))
432 (y (gomoku-index-to-y square))
433 (imin (max -4 (- 1 x)))
434 (jmin (max -4 (- 1 y)))
435 (imax (min 0 (- gomoku-board-width x 4)))
436 (jmax (min 0 (- gomoku-board-height y 4))))
437 (gomoku-update-score-in-direction imin imax
439 (gomoku-update-score-in-direction jmin jmax
441 (gomoku-update-score-in-direction (max imin jmin) (min imax jmax)
443 (gomoku-update-score-in-direction (max (- 1 y) -4
444 (- x gomoku-board-width))
446 (- gomoku-board-height y 4))
449 (defun gomoku-update-score-in-direction (left right square dx dy dval)
450 "Update scores for all squares in the qtuples starting between the LEFTth
451 square and the RIGHTth after SQUARE, along the DX, DY direction, considering
452 that DVAL has been added on SQUARE."
453 ;; We always have LEFT <= 0, RIGHT <= 0 and DEPL > 0 but we may very well
454 ;; have LEFT > RIGHT, indicating that no qtuple contains SQUARE along that
457 ((> left right)) ; Quit
459 (let (depl square0 square1 square2 count delta)
460 (setq depl (gomoku-xy-to-index dx dy)
461 square0 (+ square (* left depl))
462 square1 (+ square (* right depl))
463 square2 (+ square0 (* 4 depl)))
464 ;; Compute the contents of the first qtuple:
467 (while (<= square square2)
468 (setq count (+ count (aref gomoku-board square))
469 square (+ square depl)))
470 (while (<= square0 square1)
471 ;; Update the squares of the qtuple beginning in SQUARE0 and ending
473 (setq delta (- (aref gomoku-score-trans-table count)
474 (aref gomoku-score-trans-table (- count dval))))
475 (cond ((not (zerop delta)) ; or else nothing to update
476 (setq square square0)
477 (while (<= square square2)
478 (if (zerop (aref gomoku-board square)) ; only for free squares
479 (aset gomoku-score-table square
480 (+ (aref gomoku-score-table square) delta)))
481 (setq square (+ square depl)))))
482 ;; Then shift the qtuple one square along DEPL, this only requires
483 ;; modifying SQUARE0 and SQUARE2.
484 (setq square2 (+ square2 depl)
485 count (+ count (- (aref gomoku-board square0))
486 (aref gomoku-board square2))
487 square0 (+ square0 depl)))))))
493 ;; Several variables are used to monitor a game, including a GAME-HISTORY (the
494 ;; list of all (SQUARE . PREVSCORE) played) that allows to take moves back
495 ;; (anti-updating the score table) and to compute the table from scratch in
496 ;; case of an interruption.
498 (defvar gomoku-game-in-progress nil
499 "Non-nil if a game is in progress.")
501 (defvar gomoku-game-history nil
502 "A record of all moves that have been played during current game.")
504 (defvar gomoku-number-of-moves nil
505 "Number of moves already played in current game.")
507 (defvar gomoku-number-of-human-moves nil
508 "Number of moves already played by human in current game.")
510 (defvar gomoku-emacs-played-first nil
511 "Non-nil if Emacs played first.")
513 (defvar gomoku-human-took-back nil
514 "Non-nil if Human took back a move during the game.")
516 (defvar gomoku-human-refused-draw nil
517 "Non-nil if Human refused Emacs offer of a draw.")
519 (defvar gomoku-emacs-is-computing nil
520 ;; This is used to detect interruptions. Hopefully, it should not be needed.
521 "Non-nil if Emacs is in the middle of a computation.")
524 (defun gomoku-start-game (n m)
525 "Initialize a new game on an N by M board."
526 (setq gomoku-emacs-is-computing t) ; Raise flag
527 (setq gomoku-game-in-progress t)
528 (setq gomoku-board-width n
529 gomoku-board-height m
530 gomoku-vector-length (1+ (* (+ m 2) (1+ n)))
531 gomoku-draw-limit (/ (* 7 n m) 10))
532 (setq gomoku-game-history nil
533 gomoku-number-of-moves 0
534 gomoku-number-of-human-moves 0
535 gomoku-emacs-played-first nil
536 gomoku-human-took-back nil
537 gomoku-human-refused-draw nil)
538 (gomoku-init-display n m) ; Display first: the rest takes time
539 (gomoku-init-score-table) ; INIT-BOARD requires that the score
540 (gomoku-init-board) ; table be already created.
541 (setq gomoku-emacs-is-computing nil))
543 (defun gomoku-play-move (square val &optional dont-update-score)
544 "Go to SQUARE, play VAL and update everything."
545 (setq gomoku-emacs-is-computing t) ; Raise flag
546 (cond ((= 1 val) ; a Human move
547 (setq gomoku-number-of-human-moves (1+ gomoku-number-of-human-moves)))
548 ((zerop gomoku-number-of-moves) ; an Emacs move. Is it first ?
549 (setq gomoku-emacs-played-first t)))
550 (setq gomoku-game-history
551 (cons (cons square (aref gomoku-score-table square))
553 gomoku-number-of-moves (1+ gomoku-number-of-moves))
554 (gomoku-plot-square square val)
555 (aset gomoku-board square val) ; *BEFORE* UPDATE-SCORE !
556 (if dont-update-score nil
557 (gomoku-update-score-table square val) ; previous val was 0: dval = val
558 (aset gomoku-score-table square -1))
559 (setq gomoku-emacs-is-computing nil))
561 (defun gomoku-take-back ()
562 "Take back last move and update everything."
563 (setq gomoku-emacs-is-computing t)
564 (let* ((last-move (car gomoku-game-history))
565 (square (car last-move))
566 (oldval (aref gomoku-board square)))
568 (setq gomoku-number-of-human-moves (1- gomoku-number-of-human-moves)))
569 (setq gomoku-game-history (cdr gomoku-game-history)
570 gomoku-number-of-moves (1- gomoku-number-of-moves))
571 (gomoku-plot-square square 0)
572 (aset gomoku-board square 0) ; *BEFORE* UPDATE-SCORE !
573 (gomoku-update-score-table square (- oldval))
574 (aset gomoku-score-table square (cdr last-move)))
575 (setq gomoku-emacs-is-computing nil))
581 (defvar gomoku-number-of-wins 0
582 "Number of games already won in this session.")
584 (defvar gomoku-number-of-losses 0
585 "Number of games already lost in this session.")
587 (defvar gomoku-number-of-draws 0
588 "Number of games already drawn in this session.")
591 (defun gomoku-terminate-game (result)
592 "Terminate the current game with RESULT."
595 ((eq result 'emacs-won)
596 (setq gomoku-number-of-wins (1+ gomoku-number-of-wins))
598 (cond ((< gomoku-number-of-moves 20)
599 "This was a REALLY QUICK win.")
600 (gomoku-human-refused-draw
601 "I won... Too bad you refused my offer of a draw !")
602 (gomoku-human-took-back
603 "I won... Taking moves back will not help you !")
604 ((not gomoku-emacs-played-first)
605 "I won... Playing first did not help you much !")
606 ((and (zerop gomoku-number-of-losses)
607 (zerop gomoku-number-of-draws)
608 (> gomoku-number-of-wins 1))
609 "I'm becoming tired of winning...")
612 ((eq result 'human-won)
613 (setq gomoku-number-of-losses (1+ gomoku-number-of-losses))
616 (gomoku-human-took-back
617 "OK, you won this one. I, for one, never take my moves back...")
618 (gomoku-emacs-played-first
619 "OK, you won this one... so what ?")
621 "OK, you won this one. Now, let me play first just once."))))
622 ((eq result 'human-resigned)
623 (setq gomoku-number-of-wins (1+ gomoku-number-of-wins))
624 (setq message "So you resign. That's just one more win for me."))
625 ((eq result 'nobody-won)
626 (setq gomoku-number-of-draws (1+ gomoku-number-of-draws))
629 (gomoku-human-took-back
630 "This is a draw. I, for one, never take my moves back...")
631 (gomoku-emacs-played-first
632 "This is a draw. Just chance, I guess.")
634 "This is a draw. Now, let me play first just once."))))
635 ((eq result 'draw-agreed)
636 (setq gomoku-number-of-draws (1+ gomoku-number-of-draws))
639 (gomoku-human-took-back
640 "Draw agreed. I, for one, never take my moves back...")
641 (gomoku-emacs-played-first
642 "Draw agreed. You were lucky.")
644 "Draw agreed. Now, let me play first just once."))))
645 ((eq result 'crash-game)
647 "Sorry, I have been interrupted and cannot resume that game...")))
649 (gomoku-display-statistics)
650 (if message (message message))
652 (setq gomoku-game-in-progress nil)))
654 (defun gomoku-crash-game ()
655 "What to do when Emacs detects it has been interrupted."
656 (setq gomoku-emacs-is-computing nil)
657 (gomoku-terminate-game 'crash-game)
658 (sit-for 4) ; Let's see the message
659 (gomoku-prompt-for-other-game))
662 ;;; INTERACTIVE COMMANDS.
666 (defun gomoku (&optional n m)
667 "Start a Gomoku game between you and Emacs.
668 If a game is in progress, this command allow you to resume it.
669 If optional arguments N and M are given, an N by M board is used.
671 You and Emacs play in turn by marking a free square. You mark it with X
672 and Emacs marks it with O. The winner is the first to get five contiguous
673 marks horizontally, vertically or in diagonal.
675 You play by moving the cursor over the square you choose and hitting
676 \\<gomoku-mode-map>\\[gomoku-human-plays].
677 Use \\[describe-mode] for more info."
679 (gomoku-switch-to-window)
681 (gomoku-emacs-is-computing
683 ((not gomoku-game-in-progress)
684 (let ((max-width (gomoku-max-width))
685 (max-height (gomoku-max-height)))
686 (or n (setq n max-width))
687 (or m (setq m max-height))
689 (error "I need at least 1 column"))
691 (error "I need at least 1 row"))
693 (error "I cannot display %d columns in that window" n)))
694 (if (and (> m max-height)
695 (not (equal m gomoku-saved-board-height))
696 ;; Use EQUAL because SAVED-BOARD-HEIGHT may be nil
697 (not (y-or-n-p (format "Do you really want %d rows " m))))
698 (setq m max-height)))
699 (message "One moment, please...")
700 (gomoku-start-game n m)
701 (if (y-or-n-p "Do you allow me to play first ")
703 (gomoku-prompt-for-move)))
704 ((y-or-n-p "Shall we continue our game ")
705 (gomoku-prompt-for-move))
707 (gomoku-human-resigns))))
709 (defun gomoku-emacs-plays ()
710 "Compute Emacs next move and play it."
712 (gomoku-switch-to-window)
714 (gomoku-emacs-is-computing
716 ((not gomoku-game-in-progress)
717 (gomoku-prompt-for-other-game))
719 (message "Let me think...")
721 (setq square (gomoku-strongest-square))
723 (gomoku-terminate-game 'nobody-won))
725 (setq score (aref gomoku-score-table square))
726 (gomoku-play-move square 6)
727 (cond ((>= score gomoku-winning-threshold)
728 (gomoku-find-filled-qtuple square 6)
729 (gomoku-cross-winning-qtuple)
730 (gomoku-terminate-game 'emacs-won))
732 (gomoku-terminate-game 'nobody-won))
733 ((and (> gomoku-number-of-moves gomoku-draw-limit)
734 (not gomoku-human-refused-draw)
735 (gomoku-offer-a-draw))
736 (gomoku-terminate-game 'draw-agreed))
738 (gomoku-prompt-for-move)))))))))
740 (defun gomoku-human-plays ()
741 "Signal to the Gomoku program that you have played.
742 You must have put the cursor on the square where you want to play.
743 If the game is finished, this command requests for another game."
745 (gomoku-switch-to-window)
747 (gomoku-emacs-is-computing
749 ((not gomoku-game-in-progress)
750 (gomoku-prompt-for-other-game))
753 (setq square (gomoku-point-square))
755 (error "Your point is not on a square. Retry !"))
756 ((not (zerop (aref gomoku-board square)))
757 (error "Your point is not on a free square. Retry !"))
759 (setq score (aref gomoku-score-table square))
760 (gomoku-play-move square 1)
761 (cond ((and (>= score gomoku-loosing-threshold)
762 ;; Just testing SCORE > THRESHOLD is not enough for
763 ;; detecting wins, it just gives an indication that
764 ;; we confirm with GOMOKU-FIND-FILLED-QTUPLE.
765 (gomoku-find-filled-qtuple square 1))
766 (gomoku-cross-winning-qtuple)
767 (gomoku-terminate-game 'human-won))
769 (gomoku-emacs-plays)))))))))
771 (defun gomoku-human-takes-back ()
772 "Signal to the Gomoku program that you wish to take back your last move."
774 (gomoku-switch-to-window)
776 (gomoku-emacs-is-computing
778 ((not gomoku-game-in-progress)
779 (message "Too late for taking back...")
781 (gomoku-prompt-for-other-game))
782 ((zerop gomoku-number-of-human-moves)
783 (message "You have not played yet... Your move ?"))
785 (message "One moment, please...")
786 ;; It is possible for the user to let Emacs play several consecutive
787 ;; moves, so that the best way to know when to stop taking back moves is
788 ;; to count the number of human moves:
789 (setq gomoku-human-took-back t)
790 (let ((number gomoku-number-of-human-moves))
791 (while (= number gomoku-number-of-human-moves)
793 (gomoku-prompt-for-move))))
795 (defun gomoku-human-resigns ()
796 "Signal to the Gomoku program that you may want to resign."
798 (gomoku-switch-to-window)
800 (gomoku-emacs-is-computing
802 ((not gomoku-game-in-progress)
803 (message "There is no game in progress"))
804 ((y-or-n-p "You mean, you resign ")
805 (gomoku-terminate-game 'human-resigned))
806 ((y-or-n-p "You mean, we continue ")
807 (gomoku-prompt-for-move))
809 (gomoku-terminate-game 'human-resigned)))) ; OK. Accept it
812 ;;; PROMPTING THE HUMAN PLAYER.
815 (defun gomoku-prompt-for-move ()
816 "Display a message asking for Human's move."
817 (message (if (zerop gomoku-number-of-human-moves)
818 "Your move ? (move to a free square and hit X, RET ...)"
820 ;; This may seem silly, but if one omits the following line (or a similar
821 ;; one), the cursor may very well go to some place where POINT is not.
822 (save-excursion (set-buffer (other-buffer))))
824 (defun gomoku-prompt-for-other-game ()
825 "Ask for another game, and start it."
826 (if (y-or-n-p "Another game ")
827 (gomoku gomoku-board-width gomoku-board-height)
828 (message "Chicken !")))
830 (defun gomoku-offer-a-draw ()
831 "Offer a draw and return T if Human accepted it."
832 (or (y-or-n-p "I offer you a draw. Do you accept it ")
833 (prog1 (setq gomoku-human-refused-draw t)
837 ;;; DISPLAYING THE BOARD.
840 ;; You may change these values if you have a small screen or if the squares
841 ;; look rectangular, but spacings SHOULD be at least 2 (MUST BE at least 1).
843 (defconst gomoku-square-width 4
844 "*Horizontal spacing between squares on the Gomoku board.")
846 (defconst gomoku-square-height 2
847 "*Vertical spacing between squares on the Gomoku board.")
849 (defconst gomoku-x-offset 3
850 "*Number of columns between the Gomoku board and the side of the window.")
852 (defconst gomoku-y-offset 1
853 "*Number of lines between the Gomoku board and the top of the window.")
856 (defun gomoku-max-width ()
857 "Largest possible board width for the current window."
858 (1+ (/ (- (window-width (selected-window))
859 gomoku-x-offset gomoku-x-offset 1)
860 gomoku-square-width)))
862 (defun gomoku-max-height ()
863 "Largest possible board height for the current window."
864 (1+ (/ (- (window-height (selected-window))
865 gomoku-y-offset gomoku-y-offset 2)
866 ;; 2 instead of 1 because WINDOW-HEIGHT includes the mode line !
867 gomoku-square-height)))
869 (defun gomoku-point-x ()
870 "Return the board column where point is, or nil if it is not a board column."
871 (let ((col (- (current-column) gomoku-x-offset)))
873 (zerop (% col gomoku-square-width))
874 (<= (setq col (1+ (/ col gomoku-square-width)))
878 (defun gomoku-point-y ()
879 "Return the board row where point is, or nil if it is not a board row."
880 (let ((row (- (count-lines 1 (point)) gomoku-y-offset 1)))
882 (zerop (% row gomoku-square-height))
883 (<= (setq row (1+ (/ row gomoku-square-height)))
884 gomoku-board-height))
887 (defun gomoku-point-square ()
888 "Return the index of the square point is on, or nil if not on the board."
890 (and (setq x (gomoku-point-x))
891 (setq y (gomoku-point-y))
892 (gomoku-xy-to-index x y))))
894 (defun gomoku-goto-square (index)
895 "Move point to square number INDEX."
896 (gomoku-goto-xy (gomoku-index-to-x index) (gomoku-index-to-y index)))
898 (defun gomoku-goto-xy (x y)
899 "Move point to square at X, Y coords."
900 (goto-line (+ 1 gomoku-y-offset (* gomoku-square-height (1- y))))
901 (move-to-column (+ gomoku-x-offset (* gomoku-square-width (1- x)))))
903 (defun gomoku-plot-square (square value)
904 "Draw 'X', 'O' or '.' on SQUARE (depending on VALUE), leave point there."
905 (gomoku-goto-square square)
906 (gomoku-put-char (cond ((= value 1) ?X)
909 (sit-for 0)) ; Display NOW
911 (defun gomoku-put-char (char)
912 "Draw CHAR on the Gomoku screen."
913 (if buffer-read-only (toggle-read-only))
919 (defun gomoku-init-display (n m)
920 "Display an N by M Gomoku board."
921 (buffer-disable-undo (current-buffer))
922 (if buffer-read-only (toggle-read-only))
924 (let (string1 string2 string3 string4)
925 ;; We do not use gomoku-plot-square which would be too slow for
926 ;; initializing the display. Rather we build STRING1 for lines where
927 ;; board squares are to be found, and STRING2 for empty lines. STRING1 is
928 ;; like STRING2 except for dots every DX squares. Empty lines are filled
929 ;; with spaces so that cursor moving up and down remains on the same
931 (setq string1 (concat (make-string (1- gomoku-square-width) ? ) ".")
932 string1 (apply 'concat
933 (make-list (1- n) string1))
934 string1 (concat (make-string gomoku-x-offset ? ) "." string1 "\n")
935 string2 (make-string (+ 1 gomoku-x-offset
936 (* (1- n) gomoku-square-width))
938 string2 (concat string2 "\n")
939 string3 (apply 'concat
940 (make-list (1- gomoku-square-height) string2))
941 string3 (concat string3 string1)
942 string3 (apply 'concat
943 (make-list (1- m) string3))
944 string4 (apply 'concat
945 (make-list gomoku-y-offset string2)))
946 (insert string4 string1 string3))
948 (gomoku-goto-xy (/ (1+ n) 2) (/ (1+ m) 2)) ; center of the board
949 (sit-for 0)) ; Display NOW
951 (defun gomoku-display-statistics ()
952 "Obnoxiously display some statistics about previous games in mode line."
953 ;; We store this string in the mode-line-process local variable.
954 ;; This is certainly not the cleanest way out ...
955 (setq mode-line-process
957 ((not (zerop gomoku-number-of-draws))
958 (format ": Won %d, lost %d, drew %d"
959 gomoku-number-of-wins
960 gomoku-number-of-losses
961 gomoku-number-of-draws))
962 ((not (zerop gomoku-number-of-losses))
963 (format ": Won %d, lost %d"
964 gomoku-number-of-wins
965 gomoku-number-of-losses))
966 ((zerop gomoku-number-of-wins)
968 ((= 1 gomoku-number-of-wins)
971 (format ": Won %d in a row"
972 gomoku-number-of-wins))))
973 ;; Then a (standard) kludgy line will force update of mode line.
974 (set-buffer-modified-p (buffer-modified-p)))
976 (defun gomoku-switch-to-window ()
977 "Find or create the Gomoku buffer, and display it."
979 (let ((buff (get-buffer "*Gomoku*")))
980 (if buff ; Buffer exists:
981 (switch-to-buffer buff) ; no problem.
982 (if gomoku-game-in-progress
983 (gomoku-crash-game)) ; buffer has been killed or something
984 (switch-to-buffer "*Gomoku*") ; Anyway, start anew.
988 ;;; CROSSING WINNING QTUPLES.
991 ;; When someone succeeds in filling a qtuple, we draw a line over the five
992 ;; corresponding squares. One problem is that the program does not know which
993 ;; squares ! It only knows the square where the last move has been played and
994 ;; who won. The solution is to scan the board along all four directions.
996 (defvar gomoku-winning-qtuple-beg nil
997 "First square of the winning qtuple.")
999 (defvar gomoku-winning-qtuple-end nil
1000 "Last square of the winning qtuple.")
1002 (defvar gomoku-winning-qtuple-dx nil
1003 "Direction of the winning qtuple (along the X axis).")
1005 (defvar gomoku-winning-qtuple-dy nil
1006 "Direction of the winning qtuple (along the Y axis).")
1009 (defun gomoku-find-filled-qtuple (square value)
1010 "Return T if SQUARE belongs to a qtuple filled with VALUEs."
1011 (or (gomoku-check-filled-qtuple square value 1 0)
1012 (gomoku-check-filled-qtuple square value 0 1)
1013 (gomoku-check-filled-qtuple square value 1 1)
1014 (gomoku-check-filled-qtuple square value -1 1)))
1016 (defun gomoku-check-filled-qtuple (square value dx dy)
1017 "Return T if SQUARE belongs to a qtuple filled with VALUEs along DX, DY."
1018 ;; And record it in the WINNING-QTUPLE-... variables.
1020 (left square) (right square)
1021 (depl (gomoku-xy-to-index dx dy))
1023 (while (and (> a -4) ; stretch tuple left
1024 (= value (aref gomoku-board (setq left (- left depl)))))
1027 (while (and (< b a+4) ; stretch tuple right
1028 (= value (aref gomoku-board (setq right (+ right depl)))))
1030 (cond ((= b a+4) ; tuple length = 5 ?
1031 (setq gomoku-winning-qtuple-beg (+ square (* a depl))
1032 gomoku-winning-qtuple-end (+ square (* b depl))
1033 gomoku-winning-qtuple-dx dx
1034 gomoku-winning-qtuple-dy dy)
1037 (defun gomoku-cross-winning-qtuple ()
1038 "Cross winning qtuple, as found by `gomoku-find-filled-qtuple'."
1039 (gomoku-cross-qtuple gomoku-winning-qtuple-beg
1040 gomoku-winning-qtuple-end
1041 gomoku-winning-qtuple-dx
1042 gomoku-winning-qtuple-dy))
1044 (defun gomoku-cross-qtuple (square1 square2 dx dy)
1045 "Cross every square between SQUARE1 and SQUARE2 in the DX, DY direction."
1046 (save-excursion ; Not moving point from last square
1047 (let ((depl (gomoku-xy-to-index dx dy)))
1048 ;; WARNING: this function assumes DEPL > 0 and SQUARE2 > SQUARE1
1049 (while (not (= square1 square2))
1050 (gomoku-goto-square square1)
1051 (setq square1 (+ square1 depl))
1053 ((and (= dx 1) (= dy 0)) ; Horizontal
1055 (while (< n gomoku-square-width)
1058 (gomoku-put-char ?-))))
1059 ((and (= dx 0) (= dy 1)) ; Vertical
1061 (while (< n gomoku-square-height)
1064 (gomoku-put-char ?|))))
1065 ((and (= dx -1) (= dy 1)) ; 1st Diagonal
1066 (backward-char (/ gomoku-square-width 2))
1067 (next-line (/ gomoku-square-height 2))
1068 (gomoku-put-char ?/))
1069 ((and (= dx 1) (= dy 1)) ; 2nd Diagonal
1070 (forward-char (/ gomoku-square-width 2))
1071 (next-line (/ gomoku-square-height 2))
1072 (gomoku-put-char ?\\))))))
1073 (sit-for 0)) ; Display NOW
1078 (defun gomoku-move-left ()
1079 "Move point backward one column on the Gomoku board."
1081 (let ((x (gomoku-point-x)))
1082 (backward-char (cond ((null x) 1)
1083 ((> x 1) gomoku-square-width)
1086 (defun gomoku-move-right ()
1087 "Move point forward one column on the Gomoku board."
1089 (let ((x (gomoku-point-x)))
1090 (forward-char (cond ((null x) 1)
1091 ((< x gomoku-board-width) gomoku-square-width)
1094 (defun gomoku-move-down ()
1095 "Move point down one row on the Gomoku board."
1097 (let ((y (gomoku-point-y)))
1098 (next-line (cond ((null y) 1)
1099 ((< y gomoku-board-height) gomoku-square-height)
1102 (defun gomoku-move-up ()
1103 "Move point up one row on the Gomoku board."
1105 (let ((y (gomoku-point-y)))
1106 (previous-line (cond ((null y) 1)
1107 ((> y 1) gomoku-square-height)
1110 (defun gomoku-move-ne ()
1111 "Move point North East on the Gomoku board."
1114 (gomoku-move-right))
1116 (defun gomoku-move-se ()
1117 "Move point South East on the Gomoku board."
1120 (gomoku-move-right))
1122 (defun gomoku-move-nw ()
1123 "Move point North West on the Gomoku board."
1128 (defun gomoku-move-sw ()
1129 "Move point South West on the Gomoku board."
1136 ;;; gomoku.el ends here