phs@lifia.UUCP (Philippe Schnoebelen) (09/13/87)
Here is a GNU Emacs package which allow you to play Gomoku against your
favorite editor. Indeed, Emacs is a wonderful toolbox for programming such
strategic games. It gives you a powerful graphic interface, and its
customizable key bindings make it easy to program the event-manager for a
game session. Then you may use Lisp to write the logic of the program. This
is definitely better than using Basic on a micro. I am surprised that such
games do not already exist in the GNU Emacs distribution.
Gomoku is played on a rectangular board: each player in turn plays on a
free square (like in Go). The winner is the first one to obtain five
contiguous marks lined up horizontally, vertically or diagonally.
The game is simple but not at all trivial.
The program does not use standard AI methods: it is fast and strong (or
rather "rather fast and rather strong"), but it is not modest :-). It has
been tested with GNU Emacs version 18.44 but should not have trouble with
older versions.
I tried to make it fast because game players are often held responsible
for the heavy load of time-sharing systems. Then I tried to have an easy to
modify game interface, because having a finely tuned interface is the most
difficult thing in game-programming. Anyway, the program is already fat
(37K sources, 20K code) and I did not go too far in this direction.
Gomoku.el has been tested here for some weeks, but there probably remain
some bugs or misfeatures. Mail me any comments, questions, suggestions, bug
reports, etc ... I shall send a more final version to comp.sources.games
in some weeks.
--
Philippe SCHNOEBELEN, Best: phs@lifia.imag.fr
LIFIA - INPG,
46, Avenue Felix VIALLET 2nd: phs@lifia.UUCP
38000 Grenoble, FRANCE last: ..!mcvax!inria!lifia!phs
"Algebraic symbols are used when you do not know what you are talking about."
-- cut here --- cut here --- cut here --- cut here --- cut here --- cut here --
;;; Gomoku game between you and GNU Emacs.
;;;
;;; Written by Ph. Schnoebelen (phs@lifia.imag.fr), 1987
;;; with precious advices from J.-F. Rit (rit@lifia.imag.fr)
;;; This has been tested with GNU Emacs 18.44
;;;
;;; This software is distributed 'as is', without warranties of any
;;; kind, but all comments, suggestions and bug reports are welcome.
(provide 'gomoku)
;; RULES:
;;
;; Gomoku is a game played between two players on a rectangular board. Each
;; player, in turn, marks a free square of its choice. The winner is the first
;; one to mark five contiguous squares in any direction (horizontally,
;; vertically or diagonally).
;;
;; I have been told that, in "The TRUE Gomoku", some restrictions are made
;; about the squares where one may play, or else there is a known forced win
;; for the first player. This program has no such restriction, but it does not
;; know about the forced win, nor do I. Furthermore, you probably do not know
;; it yourself :-).
;; HOW TO INSTALL:
;;
;; There is nothing specific w.r.t. installation: just put this file in the
;; lisp directory and add an autoload for command gomoku in loaddefs.el. If
;; you don't want to rebuild Emacs, then every single user interested in
;; Gomoku will have to put the autoload command in its .emacs file. Another
;; possibility is to define in your .emacs some command using (require
;; 'gomoku).
;;
;; The most important thing is to BYTE-COMPILE gomoku.el because it is
;; important that the code be as fast as possible.
;;
;; There are two main places where you may want to customize the program: key
;; bindings and board display. These features are commented in the code. Go
;; and see.
;; HOW TO USE:
;;
;; Once this file has been installed, the command "M-x gomoku" will display a
;; board, the size of which depends on the size of the current window. The
;; size of the board is easily modified by giving numeric arguments to the
;; gomoku command and/or by customizing the displaying parameters.
;;
;; Emacs plays when it is its turn. When it is your turn, just put the cursor
;; on the square where you want to play and hit RET, or X, or whatever key you
;; bind to the command gomoku-human-plays. When it is your turn, Emacs is
;; idle: you may switch buffers, read your mail, ... Just come back to the
;; *Gomoku* buffer and resume play.
;; ALGORITHM:
;;
;; The algorithm is briefly described in section "HANDLING SCORES FOR
;; SQUARES". Some parameters may be modified if you want to change the style
;; exhibited by the program.
;;;
;;; GOMOKU MODE AND KEYMAP.
;;;
(defvar gomoku-mode-hook nil
"If non-nil, its value is called on entry to Gomoku mode.")
(defvar gomoku-mode-map nil
"Local keymap to use in Gomoku mode.")
(if gomoku-mode-map nil
(setq gomoku-mode-map (make-sparse-keymap))
;; Key bindings for cursor motion. Arrow keys are just "function"
;; keys, see below.
(define-key gomoku-mode-map "y" 'gomoku-move-nw)
(define-key gomoku-mode-map "u" 'gomoku-move-ne)
(define-key gomoku-mode-map "b" 'gomoku-move-sw)
(define-key gomoku-mode-map "n" 'gomoku-move-se)
(define-key gomoku-mode-map "h" 'gomoku-move-left)
(define-key gomoku-mode-map "l" 'gomoku-move-right)
(define-key gomoku-mode-map "j" 'gomoku-move-down)
(define-key gomoku-mode-map "k" 'gomoku-move-up)
(define-key gomoku-mode-map "\C-n" 'gomoku-move-down) ; Ctrl N
(define-key gomoku-mode-map "\C-p" 'gomoku-move-up) ; Ctrl P
(define-key gomoku-mode-map "\C-f" 'gomoku-move-right) ; Ctrl F
(define-key gomoku-mode-map "\C-b" 'gomoku-move-left) ; Ctrl B
;; Key bindings for entering Human moves.
;; If you have a mouse, you may also bind some mouse click ...
(define-key gomoku-mode-map "X" 'gomoku-human-plays) ; X
(define-key gomoku-mode-map "x" 'gomoku-human-plays) ; x
(define-key gomoku-mode-map "\C-m" 'gomoku-human-plays) ; RET
;; Key bindings for "function" keys. If your terminal have such
;; keys, make sure they are declared through the function-keymap
;; keymap (see file keypad.el).
;; One problem with keypad.el is that the function-key-sequence
;; function is really slow, so slow that you may want to comment out
;; the following lines ...
(if (featurep 'keypad)
(let (keys)
(if (setq keys (function-key-sequence ?u)) ; Up Arrow
(define-key gomoku-mode-map keys 'gomoku-move-up))
(if (setq keys (function-key-sequence ?d)) ; Down Arrow
(define-key gomoku-mode-map keys 'gomoku-move-down))
(if (setq keys (function-key-sequence ?l)) ; Left Arrow
(define-key gomoku-mode-map keys 'gomoku-move-left))
(if (setq keys (function-key-sequence ?r)) ; Right Arrow
(define-key gomoku-mode-map keys 'gomoku-move-right))
;; (if (setq keys (function-key-sequence ?e)) ; Enter
;; (define-key gomoku-mode-map keys 'gomoku-human-plays))
;; (if (setq keys (function-key-sequence ?I)) ; Insert
;; (define-key gomoku-mode-map keys 'gomoku-human-plays))
)))
(defun gomoku-mode ()
"Major mode for playing Gomoku against Emacs.
You indicate your move to Emacs by moving the cursor on a free square
where you want to play and hitting, e.g., \\[gomoku-human-plays].
Commands:
\\{gomoku-mode-map}
Entry to this mode calls the value of gomoku-mode-hook
if that value is non-nil."
(interactive)
(if (featurep 'picture) nil ; I would prefer
(load "picture") ; (require 'picture)
(provide 'picture))
(setq major-mode 'gomoku-mode
mode-name "Gomoku")
(gomoku-display-statistics)
(use-local-map gomoku-mode-map)
(run-hooks 'gomoku-mode-hook))
;;;
;;; THE BOARD.
;;;
(defvar gomoku-board-width nil
"Number of columns on the Gomoku board.")
(defvar gomoku-board-height nil
"Number of lines on the Gomoku board.")
(defvar gomoku-board-size nil
"Number of squares on the Gomoku board.")
;; The board state is recorded in a one dimensional vector containing 0 for
;; empty squares, 1 for O's, 6 for X's and -1 for padding squares, i.e.
;; squares outside the real board. The leftmost topmost square has index
;; gomoku-board-width + 2.
(defvar gomoku-board nil
"Vector recording the actual state of the Gomoku board.")
(defvar gomoku-vector-length nil
"Length of gomoku-board vector.")
(defun gomoku-init-board ()
"Create the gomoku-board vector and fill it with initial values."
(setq gomoku-board (make-vector gomoku-vector-length 0))
(let ((i 0) (ii (1- gomoku-vector-length)))
(while (<= i gomoku-board-width) ; The squares in [0..width] and in
(aset gomoku-board i -1) ; [length - width - 1..length - 1]
(aset gomoku-board ii -1) ; are padding squares.
(setq i (1+ i)
ii (1- ii))))
(let ((i 0))
(while (< i gomoku-vector-length)
(aset gomoku-board i -1) ; and also all k*(width+1)
(setq i (+ i gomoku-board-width 1)))))
(defun gomoku-xy-to-index (x y)
"Translate cartesian coordinates into the corresponding gomoku-board index."
(+ (* y gomoku-board-width) x y))
(defun gomoku-index-to-xy (index)
"Translate gomoku-board index into the corresponding cartesian coordinates."
(cons
(% index (1+ gomoku-board-width))
(/ index (1+ gomoku-board-width))))
;;;
;;; HANDLING SCORES FOR SQUARES.
;;;
;; Every (free) square has a score associated to it, recorded in the
;; GOMOKU-SCORE-TABLE vector. The program always plays in the square having
;; the highest score.
(defvar gomoku-score-table nil
"Vector recording the actual score of the free squares.")
;; The key point point about the algorithm is that, rather than considering
;; the board as just a set of squares, we prefer to see it as a "space" of
;; internested 5-tuples of contiguous squares (called q-tuples).
;;
;; The aim of the program is to fill one q-tuple with its O's while preventing
;; you from filling another one with your X's. To that effect, it computes a
;; score for every q-tuple, with better q-tuples having better scores. Of
;; course, the score of a q-tuple (taken in isolation) is just determined by
;; its contents as a set, i.e. not considering the order of its elements. The
;; highest score is given to the "OOOO" q-tuples because playing in such a
;; q-tuple is winning the game. Just after this comes the "XXXX" tuple because
;; not playing in it is just loosing the game, and so on. Note that a
;; "polluted" q-tuple, i.e. one containing at least one X and at least one O,
;; has score zero because there is no more any point in playing in it, from
;; both an attacking and a defending point of view.
;;
;; Given the score of every q-tuple, the score of a given free square on the
;; board is just the sum of the scores of all the q-tuples to which it
;; belongs, because playing in that square is playing in all its containing
;; q-tuples at once. And it is that function which takes into account the
;; internesting of the q-tuples.
;;
;; This algorithm is rather simple but anyway it gives a not so dumb level of
;; play. It easily extends to "n-dimensional Gomoku", where a win should not
;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !)
;; should be preferred.
;; Here are the scores of the nine "non-polluted" configurations.
;; Tuning these values will change (hopefully improve) the strength of
;; the program and may change its style (rather aggressive here).
(defvar nil-score 7 "Score of an empty q-tuple.")
(defvar Xscore 15 "Score of a q-tuple containing one X.")
(defvar XXscore 400 "Score of a q-tuple containing two X's.")
(defvar XXXscore 1800 "Score of a q-tuple containing three X's.")
(defvar XXXXscore 100000 "Score of a q-tuple containing four X's.")
(defvar Oscore 35 "Score of a q-tuple containing one O.")
(defvar OOscore 800 "Score of a q-tuple containing two O's.")
(defvar OOOscore 15000 "Score of a q-tuple containing three O's.")
(defvar OOOOscore 800000 "Score of a q-tuple containing four O's.")
;; These values are not just random: if, given the following situation:
;;
;; . . . . . . . O .
;; . X X a . . . X .
;; . . . X . . . X .
;; . . . X . . . X .
;; . . . . . . . b .
;;
;; you want Emacs to play in "a" and not in "b", then the parameters
;; must satisfy the inequality:
;;
;; 6 * XXscore > XXXscore + XXscore
;;
;; Other conditions are required to obtain sensible moves, but the
;; previous example should illustrate the point. If you manage to
;; improve on these values, please send me a note. Thanks.
;; As we choosed values 0, 1 and 6 to denote empty, X and O squares,
;; the contents of a q-tuple is uniquely determined by the sum of its
;; elements and we just have to set up a translation table.
(defconst gomoku-score-trans-table
(vector nil-score Xscore XXscore XXXscore XXXXscore 0
Oscore 0 0 0 0 0
OOscore 0 0 0 0 0
OOOscore 0 0 0 0 0
OOOOscore 0 0 0 0 0
0)
"Vector associating q-tuple contents to their score.")
;; If you do not modify drastically the previous constants, the only
;; way for a square to have a score higher than OOOOscore is to belong
;; to a "OOOO" q-tuple, thus to be a winning move. Similarly, the only
;; way for a square to have a score between XXXXscore and OOOOscore is
;; to belong to a "XXXX" q-tuple. We may use these considerations to
;; detect when a given move is winning or loosing.
(defconst gomoku-winning-threshold OOOOscore
"Threshold score beyond which a move is winning.")
(defconst gomoku-loosing-threshold XXXXscore
"Threshold score beyond which a move is loosing.")
(defun random-number (n)
"Return a random integer between 0 and N-1 inclusive."
(setq n (% (random) n))
(if (< n 0) (- n) n))
(defun gomoku-strongest-square ()
"Return the square with highest score, or nil if none is free."
(let ((score-max 0) ; Non-free squares have score -1
(count 0)
(begin (gomoku-xy-to-index 1 1))
(end (gomoku-xy-to-index gomoku-board-width gomoku-board-height))
best-square square score)
(setq square begin)
(while (<= square end)
;; Scan all squares, but there are two problems: 1/ padding squares
;; have been initialized with 20*nil-score and not -1 (for speed) and
;; 2/ we want to choose randomly between equivalent best squares.
(cond
((< (aref gomoku-score-table square) score-max))
((> (setq score (aref gomoku-score-table square))
score-max)
(if (zerop (aref gomoku-board square)) ; is it a padding square ?
(setq count 1 ; no: consider it !
best-square square
score-max score)
(aset gomoku-score-table square -1))) ; yes: get rid of it !
((not (zerop (aref gomoku-board square)))
(aset gomoku-score-table square -1)) ; another padding square
((= count (random-number ; if score = best-score,
(setq count (1+ count)))) ; choose randomly
(setq best-square square
score-max score)))
(setq square (1+ square)))
best-square))
;; We do not provide functions for computing the GOMOKU-SCORE-TABLE
;; given the contents of the GOMOKU-BOARD. This would involve heavy
;; nested loops, with time proportional to the size of the board.
;; Rather, we compute initial values for the gomoku-score-table (in
;; linear time, but this is used only once) and then update it after
;; every move. Updating needs not modify more than 36 squares: it is
;; done in constant time.
;; One problem is that an interruption during a computation kills
;; everything ! Maybe nested loops should be used anyway ?
;; As this initialization takes time and as it is likely that
;; successive games will be played on a board with same size, it is a
;; good idea to save the initial configuration.
(defvar gomoku-saved-score-table nil
"Recorded initial value of previous score table.")
(defvar gomoku-saved-board-width nil
"Recorded value of previous board width.")
(defvar gomoku-saved-board-height nil
"Recorded value of previous board height.")
(defun gomoku-init-score-table ()
"Create the score table vector and fill it with initial values."
(if (and gomoku-saved-score-table ; has it been stored last time ?
(= gomoku-board-width gomoku-saved-board-width)
(= gomoku-board-height gomoku-saved-board-height))
(setq gomoku-score-table (copy-sequence gomoku-saved-score-table))
;; No: compute it !
(setq gomoku-score-table
(make-vector gomoku-vector-length
(* 20 (aref gomoku-score-trans-table 0))))
;; Going through every square takes much time. So we initialized
;; the score table with 20*nil-score (because a square "far enough" from
;; the sides of the board belongs to 20 q-tuples) and there remain
;; only to initialize the squares at less than 5 squares from one side.
(let (i j maxi maxj maxi2 maxj2)
(setq maxi (/ (1+ gomoku-board-width) 2)
maxj (/ (1+ gomoku-board-height) 2)
maxi2 (min 4 maxi)
maxj2 (min 4 maxj))
;; We took symmetry into account and could use it more if
;; the board would have been square and not rectangular !
;; In our case we deal with all (i,j) in the set
;; [1..maxi2]*[1..maxj] U [maxi2+1..maxi]*[1..maxj2].
;; maxi2 and maxj2 are used because the board may well be less
;; than 8*8 !
(setq i 1)
(while (<= i maxi2)
(setq j 1)
(while (<= j maxj)
(gomoku-init-square-score i j)
(setq j (1+ j)))
(setq i (1+ i)))
(while (<= i maxi)
(setq j 1)
(while (<= j maxj2)
(gomoku-init-square-score i j)
(setq j (1+ j)))
(setq i (1+ i))))
(setq gomoku-saved-score-table (copy-sequence gomoku-score-table)
gomoku-saved-board-width gomoku-board-width
gomoku-saved-board-height gomoku-board-height)))
(defun gomoku-nb-qtuples (i j)
"Return the number of q-tuples containing square I,J."
;; This fonction is complicated because we have to deal
;; with ugly cases like 3 by 6 boards, but it works.
;; If you have a simpler (and correct) solution, send it to me. Thanks !
(let ((left (min 4 (1- i)))
(right (min 4 (- gomoku-board-width i)))
(up (min 4 (1- j)))
(down (min 4 (- gomoku-board-height j))))
(+ -12
(min (max (+ left right) 3) 8)
(min (max (+ up down) 3) 8)
(min (max (+ (min left up) (min right down)) 3) 8)
(min (max (+ (min right up) (min left down)) 3) 8))))
(defun gomoku-init-square-score (i j)
"Give initial score to square I,J and to its mirror images."
(let ((ii (1+ (- gomoku-board-width i)))
(jj (1+ (- gomoku-board-height j)))
(sc (* (gomoku-nb-qtuples i j) (aref gomoku-score-trans-table 0))))
(aset gomoku-score-table (gomoku-xy-to-index i j) sc)
(aset gomoku-score-table (gomoku-xy-to-index ii j) sc)
(aset gomoku-score-table (gomoku-xy-to-index i jj) sc)
(aset gomoku-score-table (gomoku-xy-to-index ii jj) sc)))
(defun gomoku-update-score-table (val square)
"Update score-table and board when VAL is played on SQUARE."
;; Updating scores is done by looking for q-tuples boundaries in all four
;; directions and then calling update-score-along-direction.
(let (xy imin imax jmin jmax)
(setq xy (gomoku-index-to-xy square)
imin (max -4 (- 1 (car xy)))
jmin (max -4 (- 1 (cdr xy)))
imax (min 0 (- gomoku-board-width (car xy) 4))
jmax (min 0 (- gomoku-board-height (cdr xy) 4)))
(gomoku-update-score-along-direction
imin imax square 1 0 val)
(gomoku-update-score-along-direction
jmin jmax square 0 1 val)
(gomoku-update-score-along-direction
(max imin jmin) (min imax jmax) square 1 1 val)
(gomoku-update-score-along-direction
(max -4 (- (car xy) gomoku-board-width) (- 1 (cdr xy)))
(min 0 (- (car xy) 5) (- gomoku-board-height (cdr xy) 4))
square -1 1 val))
(aset gomoku-board square val) ; *after* update-score-along-direction !
(aset gomoku-score-table square -1))
(defun gomoku-update-score-along-direction (left right square dx dy value)
"Update scores for all squares in the q-tuples starting between the LEFTth
square and the RIGHTth after SQUARE, along the direction DX,DY, considering
that VALUE will be played on SQUARE."
;; We always have LEFT <= 0, RIGHT <= 0 and DEPL > 0 but we may very well
;; have LEFT > RIGHT, indicating that no q-tuple contains SQUARE along that
;; DX,DY direction.
(cond
((> left right)) ; Quit
(t ; Else ..
(let (depl square0 square1 square2 count delta)
(setq depl (gomoku-xy-to-index dx dy)
square0 (+ square (* left depl))
square1 (+ square (* right depl))
count 0
square2 (+ square0 (* 4 depl)))
;; Compute the contents of the first q-tuple
(setq square square0)
(while (<= square square2)
(setq count (+ count (aref gomoku-board square))
square (+ square depl)))
(while (<= square0 square1)
;; Update the squares of the q-tuple beginning in square0 and ending
;; in square2.
(setq delta (- (aref gomoku-score-trans-table (+ value count))
(aref gomoku-score-trans-table count)))
(cond ((not (zerop delta)) ; or else nothing to update
(setq square square0)
(while (<= square square2)
(if (zerop (aref gomoku-board square)) ; only for free squares
(aset gomoku-score-table square
(+ (aref gomoku-score-table square) delta)))
(setq square (+ square depl)))))
;; Then shift the q-tuple one square along depl, this only requires
;; modifying square0 and square2.
(setq square2 (+ square2 depl)
count (+ count (- (aref gomoku-board square0))
(aref gomoku-board square2))
square0 (+ square0 depl)))))))
;;;
;;; DISPLAYING THE BOARD.
;;;
(defconst gomoku-dx 4
"*Horizontal spacing between squares on the Gomoku board.")
(defconst gomoku-dy 2
"*Vertical spacing between squares on the Gomoku board.")
(defconst gomoku-xoffset 3
"*Number of columns between the Gomoku board and the side of the window.")
(defconst gomoku-yoffset 1
"*Number of lines between the Gomoku board and the top of the window.")
;; You may change these values if you have a small screen or if the squares
;; look rectangular, but spacings should be at least 2 (MUST BE at least 1).
(defun gomoku-point-x ()
"Return the board column where point is, or nil if it is not a board column."
(let ((col (- (current-column) gomoku-xoffset)))
(if (and (>= col 0)
(zerop (% col gomoku-dx))
(<= (setq col (1+ (/ col gomoku-dx))) gomoku-board-width))
col)))
(defun gomoku-point-y ()
"Return the board row where point is, or nil if it is not a board row."
(let ((row (- (count-lines 1 (point)) gomoku-yoffset 1)))
(if (and (>= row 0)
(zerop (% row gomoku-dy))
(<= (setq row (1+ (/ row gomoku-dy))) gomoku-board-height))
row)))
(defun gomoku-point-square ()
"Return the index of the square point is on, or nil if not on the board."
(let (x y)
(if (and (setq x (gomoku-point-x))
(setq y (gomoku-point-y)))
(gomoku-xy-to-index x y))))
(defun gomoku-goto-square (index)
"Move point to the square denoted by INDEX."
(let ((xy (gomoku-index-to-xy index)))
(goto-line (+ 1 gomoku-yoffset (* gomoku-dy (1- (cdr xy)))))
(move-to-column (+ gomoku-xoffset (* gomoku-dx (1- (car xy)))))))
(defun gomoku-plot-square (index value)
"Draw 'X', 'O' or '.' on the square number INDEX, depending on VALUE
being 1, 6 or 0. Leave point on that same square."
(gomoku-goto-square index)
(gomoku-put-char (cond ((= value 1) ?X)
((= value 6) ?O)
(t ?.)))
(sit-for 0)) ; Display NOW
(defun gomoku-put-char (char)
"Draw CHAR on the Gomoku screen."
(if buffer-read-only (toggle-read-only))
(let ((last-input-char char))
;; LAST-INPUT-CHAR is an EmacsLisp global variable.
(picture-self-insert 1))
(picture-motion-reverse 1)
(toggle-read-only))
(defun gomoku-init-display (n m)
"Clean the screen and display an N by M Gomoku board."
(let ((space ? ) (dot ?.)
string1 string2)
(buffer-flush-undo (current-buffer))
(if buffer-read-only (toggle-read-only))
(erase-buffer)
(picture-move-down gomoku-yoffset)
;;
;; We do not use gomoku-plot-square which would be too slow for
;; initializing the display. Rather we build string1 for lines where
;; board squares are to be found, and string2 for empty lines. string1 is
;; like string2 except for dots every dx squares. Empty lines are filled
;; with squares so that cursor moving up and down remains on the same
;; column. Of course, this is already achieved by the picture-mode
;; functions bound to C-n, ... but these functions are not always bound
;; to other similar keys (e.g. arrow keys).
;;
(setq string1 (concat (make-string (1- gomoku-dx) space)
(char-to-string dot))
string1 (apply 'concat
(make-list (1- n) string1))
string1 (concat (make-string gomoku-xoffset space)
(char-to-string dot)
string1)
string2 (make-string (+ gomoku-xoffset (* (1- n) gomoku-dx) 1)
space))
(let ((i 1))
(while (<= i m)
(let ((j 0))
(while (< j gomoku-dy)
(cond ((zerop j) (insert string1))
((< i m) (insert string2)))
(beginning-of-line)
(if (< i m) (picture-move-down 1))
(setq j (1+ j))))
(setq i (1+ i))))
(toggle-read-only)
(gomoku-goto-square ; Put point in the center of the board.
(gomoku-xy-to-index (/ (1+ n) 2) (/ (1+ m) 2)))
(sit-for 0))) ; Display NOW
;; When someone succeeds in filling a q-tuple, we draw a line over the five
;; corresponding squares. One problem is that the program does not know which
;; squares ! It only knows the square where the last move has been played and
;; who won. The solution is to look at the board along all four possible
;; directions.
(defun gomoku-display-winning-line (square value)
"Draw a line over the q-tuple containing SQUARE filled with VALUE's."
(gomoku-try-to-draw-winning-line square value 1 0)
(gomoku-try-to-draw-winning-line square value 0 1)
(gomoku-try-to-draw-winning-line square value 1 1)
(gomoku-try-to-draw-winning-line square value -1 1)
(gomoku-goto-square square)
(sit-for 0)) ; Display NOW
(defun gomoku-try-to-draw-winning-line (square value dx dy)
"Draw a line over a q-tuple of 5 VALUEs around SQUARE in the direction given
by DX and DY, if such a q-tuple exists."
(let ((a 0) (b 0)
(left square) (right square)
(depl (gomoku-xy-to-index dx dy)))
(while (and (> a -4)
(= value (aref gomoku-board (setq left (- left depl)))))
(setq a (1- a)))
(while (and (< b (+ a 4))
(= value (aref gomoku-board (setq right (+ right depl)))))
(setq b (1+ b)))
(if (zerop (- b a 4))
(gomoku-draw-winning-line
(+ square (* a depl)) (+ square (* b depl)) dx dy))))
(defun gomoku-draw-winning-line (square1 square2 dx dy)
"Draw a line joining every square between SQUARE1 and SQUARE2 in the
direction given by DX and DY."
(let ((depl (gomoku-xy-to-index dx dy)))
;; WARNING: this function assumes DEPL > 0 and SQUARE2 > SQUARE1
(while (not (= square1 square2))
(gomoku-goto-square square1)
(setq square1 (+ square1 depl))
(cond
((and (= dx 1) (= dy 0)) ; Horizontal
(let ((n 1))
(while (< n gomoku-dx)
(setq n (1+ n))
(picture-forward-column 1)
(gomoku-put-char ?-))))
((and (= dx 0) (= dy 1)) ; Vertical
(let ((n 1))
(while (< n gomoku-dy)
(setq n (1+ n))
(picture-move-down 1)
(gomoku-put-char ?|))))
((and (= dx -1) (= dy 1)) ; 1st Diagonal
(picture-backward-column (/ gomoku-dx 2))
(picture-move-down (/ gomoku-dy 2))
(gomoku-put-char ?/))
((and (= dx 1) (= dy 1)) ; 2nd Diagonal
(picture-forward-column (/ gomoku-dx 2))
(picture-move-down (/ gomoku-dy 2))
(gomoku-put-char ?\\))))))
(defun gomoku-display-statistics ()
"Obnoxiously display some statistics about previous games in mode line."
;; We store this string in the mode-line-process local variable.
;; This is certainly not the cleanest way out ...
(setq mode-line-process
(cond
((not (zerop gomoku-number-of-draws))
(format ": Won %d, lost %d, drew %d"
gomoku-number-of-wins
gomoku-number-of-losses
gomoku-number-of-draws))
((not (zerop gomoku-number-of-losses))
(format ": Won %d, lost %d"
gomoku-number-of-wins
gomoku-number-of-losses))
((zerop gomoku-number-of-wins)
"")
((= 1 gomoku-number-of-wins)
": Already won one")
(t
(format ": Won %d in a row"
gomoku-number-of-wins))))
;; Then a (standard) kludgy line will force update of mode line.
(set-buffer-modified-p (buffer-modified-p)))
;;;
;;; GAME CONTROL.
;;;
(defvar gomoku-emacs-is-computing nil
"Non-nil if Emacs is in the middle of a computation.")
;; This is used to detect interruptions. Hopefully, it should not be needed.
(defvar gomoku-last-emacs-move nil
"The square where Emacs played last.")
(defvar gomoku-last-human-move nil
"The square where Human played last.")
(defvar gomoku-playing-first nil
"Non-nil if the program played first.")
(defvar gomoku-number-of-moves nil
"Number of moves already played.")
;; This is non-nil when a game is in progress.
(defvar gomoku-number-of-wins 0
"Number of games already won in this session.")
(defvar gomoku-number-of-losses 0
"Number of games already lost in this session.")
(defvar gomoku-number-of-draws 0
"Number of games already drawn in this session.")
(defun gomoku (&optional n m)
"Start a Gomoku game between you and Emacs.
You and Emacs play in turn by marking a free square. You mark it with X
and Emacs marks it with O. The winner is the first to get five contiguous
marks horizontally, vertically or in diagonal.
You play by moving the cursor over the square you choose and hitting RET,
x, .. or whatever has been set locally.
If a game is in progress, this command allow you to resume it.
If optional arguments N and M are given, an N by M board is used."
(interactive)
(gomoku-switch-to-window)
(if gomoku-number-of-moves ; a game is in progress
(gomoku-check-resign-or-continue)
(gomoku-start-game n m)))
;; Gomoku-switch-to-window is called by interactive functions. This may
;; seem complicated but, as we heavily rely on the display, it is safer.
(defun gomoku-switch-to-window ()
"Find or create the Gomoku buffer, and display it."
(interactive)
(let ((buff (get-buffer "*Gomoku*")))
(if buff ; Buffer exists:
(switch-to-buffer buff) ; no problem.
(if gomoku-number-of-moves ; A game is in progress:
(gomoku-crash-game)) ; buffer has been killed or something
(switch-to-buffer "*Gomoku*") ; Anyway, start anew.
(gomoku-mode))))
(defun gomoku-start-game (n m)
"Begin a new game on an N by M board."
(message "One moment, please...")
(let (maxn maxm)
(setq maxn (1+ (/ (- (window-width (selected-window))
gomoku-xoffset gomoku-xoffset 1) gomoku-dx))
maxm (1+ (/ (- (window-height (selected-window))
gomoku-yoffset gomoku-yoffset 2) gomoku-dy))
;;; 2 accounts for the mode line !
n (or n maxn)
m (or m maxm))
(cond ((< n 1)
(error "I need at least 1 column"))
((< m 1)
(error "I need at least 1 row"))
((> n maxn)
(error "I cannot display %d columns in that window" n)))
(if (and (> m maxm)
(not (equal m gomoku-saved-board-height))
(not (y-or-n-p (format "Do you really want %d rows " m))))
(setq m maxm))
(setq gomoku-board-width n
gomoku-board-height m
gomoku-vector-length (1+ (* (+ m 2) (1+ n)))))
(setq gomoku-emacs-is-computing t ; raise flag
gomoku-number-of-moves 0
gomoku-last-emacs-move nil
gomoku-last-human-move nil)
(gomoku-init-display n m) ; Display first: the rest may take some time...
(gomoku-init-score-table) ; INIT-BOARD requires that the score
(gomoku-init-board) ; table be already created.
(setq gomoku-emacs-is-computing nil)
(if (setq gomoku-playing-first (y-or-n-p "Do you allow me to play first "))
(gomoku-emacs-plays)
(gomoku-prompt-human-for-move)))
(defun gomoku-terminate-game ()
"Terminate the current game."
(ding)
(setq gomoku-number-of-moves nil
gomoku-emacs-is-computing nil))
;; The following functions are called when certain situations, typical in a
;; game session, arise.
(defun gomoku-emacs-won (square)
"What to do when Emacs won by playing on SQUARE."
(setq gomoku-number-of-wins (1+ gomoku-number-of-wins))
(gomoku-display-statistics)
(gomoku-display-winning-line square 6)
(message
(cond ((< gomoku-number-of-moves 20)
"This was a really quick win.")
((not gomoku-playing-first)
"I won ... Playing first did not help you much !")
((and (zerop gomoku-number-of-losses)
(zerop gomoku-number-of-draws)
(> gomoku-number-of-wins 1))
"I'm becoming tired of winning ...")
(t
"I won.")))
(gomoku-terminate-game))
(defun gomoku-human-won (square)
"What to do when Human won by playing on SQUARE."
(setq gomoku-number-of-losses (1+ gomoku-number-of-losses))
(gomoku-display-statistics)
(gomoku-display-winning-line square 1)
(message (if gomoku-playing-first
"OK, you won this one ... so what ?"
"OK, you won this one. Now, let me play first just once."))
(gomoku-terminate-game))
(defun gomoku-human-resigned ()
"What to do when Human resigned the current game."
(setq gomoku-number-of-wins (1+ gomoku-number-of-wins))
(gomoku-display-statistics)
(message "So you resign ? That's just one more win for me.")
(gomoku-terminate-game))
(defun gomoku-nobody-won ()
"What to do when nobody won."
(setq gomoku-number-of-draws (1+ gomoku-number-of-draws))
(gomoku-display-statistics)
(message (if gomoku-playing-first
"This is a draw. You managed to escape me, congratulations !"
"This is a draw. Now, let me play first just once."))
(gomoku-terminate-game))
(defun gomoku-crash-game ()
"What to do when Emacs detects it has been interrupted."
(gomoku-terminate-game)
(message "Sorry, I have been interrupted during the last move, and I cannot resume...")
(sit-for 4))
;; Code for prompting the Human player.
(defvar gomoku-novice-p t
"Nil if user has already been asked for one move.")
(defun gomoku-prompt-human-for-move ()
"Display a message asking for Human's move."
(cond (gomoku-novice-p
(setq gomoku-novice-p nil)
(message "Your move ? (move to a free square and hit X, RET ...)"))
(t
(message "Your move ?")))
(save-excursion (set-buffer (other-buffer)))
;; This may seem silly, but if one omits this line (or a similar one), the
;; cursor may very well go to some place where POINT is not.
)
(defun gomoku-prompt-human-for-other-game ()
"Ask for another game, and start it."
(interactive)
(if (y-or-n-p "Another game ")
(gomoku gomoku-board-width gomoku-board-height)
(message "Chicken !")))
;; Code for triggering certain actions.
(defun gomoku-emacs-plays ()
"Compute Emacs next move and play it."
(interactive)
(if gomoku-emacs-is-computing (gomoku-crash-game)
(message "Let me think...")
(setq gomoku-emacs-is-computing t) ; raise flag
(if gomoku-last-emacs-move
(progn (gomoku-update-score-table 6 gomoku-last-emacs-move)
(setq gomoku-last-emacs-move nil)))
(if gomoku-last-human-move
(progn (gomoku-update-score-table 1 gomoku-last-human-move)
(setq gomoku-last-human-move nil)))
(let (best-square best-score)
(setq best-square (gomoku-strongest-square))
(if (null best-square)
(gomoku-nobody-won)
(gomoku-plot-square best-square 6)
(setq gomoku-number-of-moves (1+ gomoku-number-of-moves)
gomoku-last-emacs-move best-square
best-score (aref gomoku-score-table best-square))
(cond ((>= best-score gomoku-winning-threshold)
(gomoku-emacs-won best-square))
((zerop best-score)
(gomoku-nobody-won))
(t
(setq gomoku-last-emacs-move best-square)
(gomoku-prompt-human-for-move)))))
(setq gomoku-emacs-is-computing nil)))
(defun gomoku-human-plays ()
"Signal to the Gomoku program that you have played.
You must have put the cursor on the square where you want to play.
If the game is finished, this command requests for another game."
(interactive)
(gomoku-switch-to-window)
(cond
(gomoku-emacs-is-computing
(gomoku-crash-game))
(gomoku-number-of-moves
(let ((square (gomoku-point-square)))
(cond ((null square)
(error "Your point is not on a square. Retry !"))
((or (not (zerop (aref gomoku-board square)))
(equal square gomoku-last-emacs-move)) ; board is not yet updated
(error "Your point is not on a free square. Retry !"))
(t
(gomoku-plot-square square 1)
(setq gomoku-number-of-moves (1+ gomoku-number-of-moves))
(if (>= (aref gomoku-score-table square) gomoku-loosing-threshold)
(gomoku-human-won square)
(setq gomoku-last-human-move square)
(gomoku-emacs-plays))))))
(t
(gomoku-prompt-human-for-other-game))))
(defun gomoku-check-resign-or-continue ()
"Signal to the Gomoku program that you may want to resign."
(interactive)
(gomoku-switch-to-window)
(cond
(gomoku-emacs-is-computing
(gomoku-crash-game))
((not gomoku-number-of-moves)
(message "There is no game in progress"))
((y-or-n-p "Shall we continue our game ")
(gomoku-prompt-human-for-move))
((y-or-n-p "You mean, you resign ")
(gomoku-human-resigned))
((y-or-n-p "You mean, we continue ")
(gomoku-prompt-human-for-move))
(t (gomoku-human-resigned)))) ; OK. Accept it
;;;
;;; CURSOR MOTION.
;;;
(defun gomoku-move-left ()
"Move point backward one column on the Gomoku board."
(interactive)
(let ((x (gomoku-point-x)))
(picture-backward-column
(cond ((null x) 1)
((> x 1) gomoku-dx)
(t 0)))))
(defun gomoku-move-right ()
"Move point forward one column on the Gomoku board."
(interactive)
(let ((x (gomoku-point-x)))
(picture-forward-column
(cond ((null x) 1)
((< x gomoku-board-width) gomoku-dx)
(t 0)))))
(defun gomoku-move-down ()
"Move point down one row on the Gomoku board."
(interactive)
(let ((y (gomoku-point-y)))
(picture-move-down
(cond ((null y) 1)
((< y gomoku-board-height) gomoku-dy)
(t 0)))))
(defun gomoku-move-up ()
"Move point up one row on the Gomoku board."
(interactive)
(let ((y (gomoku-point-y)))
(picture-move-up
(cond ((null y) 1)
((> y 1) gomoku-dy)
(t 0)))))
(defun gomoku-move-ne ()
"Move point North East on the Gomoku board."
(interactive)
(gomoku-move-up)
(gomoku-move-right))
(defun gomoku-move-se ()
"Move point South East on the Gomoku board."
(interactive)
(gomoku-move-down)
(gomoku-move-right))
(defun gomoku-move-nw ()
"Move point North West on the Gomoku board."
(interactive)
(gomoku-move-up)
(gomoku-move-left))
(defun gomoku-move-sw ()
"Move point South West on the Gomoku board."
(interactive)
(gomoku-move-down)
(gomoku-move-left))bob%aargh.cis.ohio-state.edu@tut.cis.ohio-state.edu (Bob Sutterfield) (09/15/87)
In article <2833@lifia.UUCP> phs@lifia.UUCP (Philippe Schnoebelen) writes: >... play Gomoku against your favorite editor. Indeed, Emacs is a >wonderful toolbox for programming such strategic games. It gives you >a powerful graphic interface ... gomoku.el plays even more nicely when your emacs is running as an X client. Use your middle mouse button (x-mouse-set-point) to place stones in a pretty natural way. Thanks for posting the game! -=- Bob Sutterfield, Department of Computer and Information Science The Ohio State University; 2036 Neil Ave. Columbus OH USA 43210-1277 bob@ohio-state.{arpa,csnet} or ...!cbosgd!osu-cis!bob soon: bob@cis.ohio-state.edu
jat@hpsemc.UUCP (Joe Talmadge) (09/17/87)
Speaking of Gomuku (and not at all of emacs, oh well), does anyone know anything about a computerized Go game, like the computerized chess games? Or is Go not widely played enough, or too complicated? Just wondering. I'd like to start playing again, and I don't know anyone else who plays. Sorry to put this in comp.emacs, but I figured a someone who knew Gomuku might know Go. Joe
rbj@ICST-CMR.ARPA (Root Boy Jim) (09/18/87)
From: Joe Talmadge <hpda!hpsemc!jat@UCBVAX.Berkeley.EDU>
Speaking of Gomuku (and not at all of emacs, oh well), does anyone
know anything about a computerized Go game, like the computerized
chess games? Or is Go not widely played enough, or too complicated?
I was going to say `now how about "go.el" :-)', but obviously not everyone
would get the joke. As far as I know, go programs are in their infancy.
It is just not very easy to write a program to play go with any real
degree of skill.
Usenix is having (or already had) a go tournament where you submit a
subroutine to make a move and the referee program coordinates and
checks the validity of your response. I would like to know what happenned.
I was going to submit code that made symmetrical moves to the opponents
move or took the center point if playing black, but never got around to it.
While this is not a very interesting strategy with humans, it might just
win the tournament, as it should produce a draw with almost every program
it plays against, and would win against any buggy code it played against
(if your program makes an illegal move, it forfeits).
My strategy is based on the `Prisoners Dilemna' tournament, where the
winning entry was called `Tit For Tat'. It echoed it's opponents last
move, and always `cooperated' on the first round. Interestingly enough,
it never beat anyone, but by drawing every `battle', it won the `war'.
Interested people can read about the Prisoner's Dilemna in `Metamagical
Themas', by Douglas Hofstadter. Disinterested people will I hope excuse
my ramblings in this newsgroup.
Joe
(Root Boy) Jim Cottrell <rbj@icst-cmr.arpa>
National Bureau of Standards
Flamer's Hotline: (301) 975-5688drw@culdev1.UUCP (Dale Worley) (09/22/87)
jat@hpsemc.UUCP (Joe Talmadge) writes: > Speaking of Gomuku (and not at all of emacs, oh well), does anyone > know anything about a computerized Go game, like the computerized > chess games? Or is Go not widely played enough, or too complicated? From what I've heard, the number of potential moves from any position in Go is so large that tree searching doesn't work. Thus, there's never been a good Go program. (But the Japanese are working on it as an AI project.) Oddly enough, good computer chess programs all use tree searching, but good human chess players don't. Dale
spike@bu-cs.BU.EDU (Spike) (09/22/87)
In article <1547@culdev1.UUCP> drw@culdev1.UUCP (Dale Worley) writes: >jat@hpsemc.UUCP (Joe Talmadge) writes: >> Speaking of Gomuku (and not at all of emacs, oh well), does anyone >> know anything about a computerized Go game, like the computerized >> chess games? Or is Go not widely played enough, or too complicated? > >From what I've heard, the number of potential moves from any position >in Go is so large that tree searching doesn't work. Thus, there's >never been a good Go program. (But the Japanese are working on it as >an AI project.) Oddly enough, good computer chess programs all use >tree searching, but good human chess players don't. > >Dale As I recall there is a very large prize, still unclamed, for the first person who writes an Go program that can be certified at the Go equivalent of a chess master. And yes, when I was taking lisp a while back the professor showed us that the Go game tree was unmanageably large. Tho not knowing Go I can prove it now... -- ->Spike
pierson@encore.UUCP (Dan Pierson) (09/23/87)
The complete search tree for Go obviously has to be very large, if just
because of the board size (19x19). On the other hand, my (limited)
experience is that Go players tend to look much further ahead than
chess players because the scope of look-ahead is more bounded. Chess
pieces *move*, many of them large distances; therefore a single move
can have direct, immediate consequences in a distant part of the board.
Go pieces are placed or (rarely) removed, but never moved; therefore most
tactical decisions are localized, leading to a deeper but simpler tree.
Srategic decisions are another matter altogether; the consequences can be
subtle and take a long time to mature. About fifteen years ago I heard
that one of the leading Go programs was using potential theory instead of
search trees for its strategic moves...
Can we please move this discussion to a more appropriate newsgroup?
--
In real life: Dan Pierson, Encore Computer Corporation, Research
UseNet: {talcott,linus,necis,decvax,ihnp4}!encore!pierson
ArpaNet: pierson@multimax.arparbj@ICST-CMR.ARPA.UUCP (10/01/87)
From: Dale Worley <culdev1!drw@XN.LL.MIT.EDU> From what I've heard, the number of potential moves from any position in Go is so large that tree searching doesn't work. To be precise, the maximum search tree is bounded by the number 381! The board is 19 square, giving 381 choices for the first move, 380 for the second, ... and the last move is forced. I say bounded, because I have not accounted for illegal moves or ko's. Assuming a game is `pretty much over' after half of the stones have been played, leaves 200 or so moves per half move level search. In chess, there are rarely even 100 moves (altho that's still pretty hefty) available. At the beginning, there are 20. Even so, all possible moves are not usually generated; they usually prune off the useless or bad ones at higher levels. Oddly enough, good computer chess programs all use tree searching, but good human chess players don't. I wouldn't say that. We all think to ourselves, "I take, he takes, I take, he takes, I guess I've got to protect it again". It has also been said that experts think about the same number of moves ahead that average players do, they just don't see the bad moves. What is really needed is a way to prune the tree of bad or meaningless moves and focus the search on a particularly interesting section. Dale (Root Boy) Jim Cottrell <rbj@icst-cmr.arpa> National Bureau of Standards Flamer's Hotline: (301) 975-5688 Jesus is my POSTMASTER GENERAL..