aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorStefan Kangas2021-02-16 09:56:17 +0100
committerStefan Kangas2021-02-16 10:06:42 +0100
commit9f843572d2feb4c75bd4f1d2a86edc7595591dc9 (patch)
tree26218671f863a2ee32182a02252fdf11319912aa
parent62cda6acd61f6de2698674391a26ce0a8672fc93 (diff)
downloademacs-9f843572d2feb4c75bd4f1d2a86edc7595591dc9.tar.gz
emacs-9f843572d2feb4c75bd4f1d2a86edc7595591dc9.zip
* lisp/play/gomoku.el: Minor doc fixes; formatting.
-rw-r--r--lisp/play/gomoku.el77
1 files changed, 38 insertions, 39 deletions
diff --git a/lisp/play/gomoku.el b/lisp/play/gomoku.el
index 8db40d7f94f..61b67aeb70d 100644
--- a/lisp/play/gomoku.el
+++ b/lisp/play/gomoku.el
@@ -28,39 +28,36 @@
28;; RULES: 28;; RULES:
29;; 29;;
30;; Gomoku is a game played between two players on a rectangular board. Each 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 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, 32;; one to mark five contiguous squares in any direction (horizontally,
33;; vertically or diagonally). 33;; vertically or diagonally).
34;; 34;;
35;; I have been told that, in "The TRUE Gomoku", some restrictions are made 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 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 37;; for the first player. This program has no such restriction, but it does not
38;; know about the forced win, nor do I. 38;; know about the forced win, nor do I.
39;; See http://renju.se/rif/r1rulhis.htm for more information. 39;; See https://renju.se/rif/r1rulhis.htm for more information.
40
41 40
42;; There are two main places where you may want to customize the program: key 41;; 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 42;; bindings and board display. These features are commented in the code. Go
44;; and see. 43;; and see.
45 44
46
47;; HOW TO USE: 45;; HOW TO USE:
48;; 46;;
49;; The command "M-x gomoku" displays a 47;; The command `M-x gomoku' displays a board, the size of which depends on the
50;; board, the size of which depends on the size of the current window. The 48;; size of the current window. The size of the board is easily modified by
51;; size of the board is easily modified by giving numeric arguments to the 49;; giving numeric arguments to the gomoku command and/or by customizing the
52;; gomoku command and/or by customizing the displaying parameters. 50;; displaying parameters.
53;; 51;;
54;; Emacs plays when it is its turn. When it is your turn, just put the cursor 52;; 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 53;; 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 54;; 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 55;; idle: you may switch buffers, read your mail, ... Just come back to the
58;; *Gomoku* buffer and resume play. 56;; *Gomoku* buffer and resume play.
59 57
60
61;; ALGORITHM: 58;; ALGORITHM:
62;; 59;;
63;; The algorithm is briefly described in section "THE SCORE TABLE". Some 60;; 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 61;; parameters may be modified if you want to change the style exhibited by the
65;; program. 62;; program.
66 63
@@ -86,13 +83,15 @@ One useful value to include is `turn-on-font-lock' to highlight the pieces."
86 "Name of the Gomoku buffer.") 83 "Name of the Gomoku buffer.")
87 84
88;; You may change these values if you have a small screen or if the squares 85;; You may change these values if you have a small screen or if the squares
89;; look rectangular, but spacings SHOULD be at least 2 (MUST BE at least 1). 86;; look rectangular.
90 87
91(defconst gomoku-square-width 4 88(defconst gomoku-square-width 4
92 "Horizontal spacing between squares on the Gomoku board.") 89 "Horizontal spacing between squares on the Gomoku board.
90SHOULD be at least 2 (MUST BE at least 1).")
93 91
94(defconst gomoku-square-height 2 92(defconst gomoku-square-height 2
95 "Vertical spacing between squares on the Gomoku board.") 93 "Vertical spacing between squares on the Gomoku board.
94SHOULD be at least 2 (MUST BE at least 1).")
96 95
97(defconst gomoku-x-offset 3 96(defconst gomoku-x-offset 3
98 "Number of columns between the Gomoku board and the side of the window.") 97 "Number of columns between the Gomoku board and the side of the window.")
@@ -270,13 +269,13 @@ Other useful commands:\n
270;; internested 5-tuples of contiguous squares (called qtuples). 269;; internested 5-tuples of contiguous squares (called qtuples).
271;; 270;;
272;; The aim of the program is to fill one qtuple with its O's while preventing 271;; The aim of the program is to fill one qtuple with its O's while preventing
273;; you from filling another one with your X's. To that effect, it computes a 272;; you from filling another one with your X's. To that effect, it computes a
274;; score for every qtuple, with better qtuples having better scores. Of 273;; score for every qtuple, with better qtuples having better scores. Of
275;; course, the score of a qtuple (taken in isolation) is just determined by 274;; course, the score of a qtuple (taken in isolation) is just determined by
276;; its contents as a set, i.e. not considering the order of its elements. The 275;; its contents as a set, i.e. not considering the order of its elements. The
277;; highest score is given to the "OOOO" qtuples because playing in such a 276;; highest score is given to the "OOOO" qtuples because playing in such a
278;; qtuple is winning the game. Just after this comes the "XXXX" qtuple because 277;; qtuple is winning the game. Just after this comes the "XXXX" qtuple because
279;; not playing in it is just losing the game, and so on. Note that a 278;; not playing in it is just losing the game, and so on. Note that a
280;; "polluted" qtuple, i.e. one containing at least one X and at least one O, 279;; "polluted" qtuple, i.e. one containing at least one X and at least one O,
281;; has score zero because there is no more any point in playing in it, from 280;; has score zero because there is no more any point in playing in it, from
282;; both an attacking and a defending point of view. 281;; both an attacking and a defending point of view.
@@ -284,11 +283,11 @@ Other useful commands:\n
284;; Given the score of every qtuple, the score of a given free square on the 283;; Given the score of every qtuple, the score of a given free square on the
285;; board is just the sum of the scores of all the qtuples to which it belongs, 284;; board is just the sum of the scores of all the qtuples to which it belongs,
286;; because playing in that square is playing in all its containing qtuples at 285;; because playing in that square is playing in all its containing qtuples at
287;; once. And it is that function which takes into account the internesting of 286;; once. And it is that function which takes into account the internesting of
288;; the qtuples. 287;; the qtuples.
289;; 288;;
290;; This algorithm is rather simple but anyway it gives a not so dumb level of 289;; This algorithm is rather simple but anyway it gives a not so dumb level of
291;; play. It easily extends to "n-dimensional Gomoku", where a win should not 290;; play. It easily extends to "n-dimensional Gomoku", where a win should not
292;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !) 291;; be obtained with as few as 5 contiguous marks: 6 or 7 (depending on n !)
293;; should be preferred. 292;; should be preferred.
294 293
@@ -323,8 +322,8 @@ Other useful commands:\n
323;; because "a" mainly belongs to six "XX" qtuples (the others are less 322;; because "a" mainly belongs to six "XX" qtuples (the others are less
324;; important) while "b" belongs to one "XXX" and one "XX" qtuples. Other 323;; important) while "b" belongs to one "XXX" and one "XX" qtuples. Other
325;; conditions are required to obtain sensible moves, but the previous example 324;; conditions are required to obtain sensible moves, but the previous example
326;; should illustrate the point. If you manage to improve on these values, 325;; should illustrate the point. If you manage to improve on these values,
327;; please send me a note. Thanks. 326;; please send me a note. Thanks.
328 327
329 328
330;; As we chose values 0, 1 and 6 to denote empty, X and O squares, the 329;; As we chose values 0, 1 and 6 to denote empty, X and O squares, the
@@ -343,9 +342,9 @@ Other useful commands:\n
343 342
344;; If you do not modify drastically the previous constants, the only way for a 343;; If you do not modify drastically the previous constants, the only way for a
345;; square to have a score higher than gomoku-OOOOscore is to belong to a "OOOO" 344;; square to have a score higher than gomoku-OOOOscore is to belong to a "OOOO"
346;; qtuple, thus to be a winning move. Similarly, the only way for a square to 345;; qtuple, thus to be a winning move. Similarly, the only way for a square to
347;; have a score between gomoku-XXXXscore and gomoku-OOOOscore is to belong to a "XXXX" 346;; have a score between gomoku-XXXXscore and gomoku-OOOOscore is to belong to a "XXXX"
348;; qtuple. We may use these considerations to detect when a given move is 347;; qtuple. We may use these considerations to detect when a given move is
349;; winning or losing. 348;; winning or losing.
350 349
351(defconst gomoku-winning-threshold gomoku-OOOOscore 350(defconst gomoku-winning-threshold gomoku-OOOOscore
@@ -357,8 +356,8 @@ Other useful commands:\n
357 356
358(defun gomoku-strongest-square () 357(defun gomoku-strongest-square ()
359 "Compute index of free square with highest score, or nil if none." 358 "Compute index of free square with highest score, or nil if none."
360 ;; We just have to loop other all squares. However there are two problems: 359 ;; We just have to loop other all squares. However there are two problems:
361 ;; 1/ The SCORE-TABLE only gives correct scores to free squares. To speed 360 ;; 1/ The SCORE-TABLE only gives correct scores to free squares. To speed
362 ;; up future searches, we set the score of padding or occupied squares 361 ;; up future searches, we set the score of padding or occupied squares
363 ;; to -1 whenever we meet them. 362 ;; to -1 whenever we meet them.
364 ;; 2/ We want to choose randomly between equally good moves. 363 ;; 2/ We want to choose randomly between equally good moves.
@@ -378,7 +377,7 @@ Other useful commands:\n
378 best-square square 377 best-square square
379 score-max score) 378 score-max score)
380 (aset gomoku-score-table square -1))) ; no: kill it ! 379 (aset gomoku-score-table square -1))) ; no: kill it !
381 ;; If score is equally good, choose randomly. But first check freedom: 380 ;; If score is equally good, choose randomly. But first check freedom:
382 ((not (zerop (aref gomoku-board square))) 381 ((not (zerop (aref gomoku-board square)))
383 (aset gomoku-score-table square -1)) 382 (aset gomoku-score-table square -1))
384 ((zerop (random (setq count (1+ count)))) 383 ((zerop (random (setq count (1+ count))))
@@ -392,11 +391,11 @@ Other useful commands:\n
392;;; 391;;;
393 392
394;; At initialization the board is empty so that every qtuple amounts for 393;; At initialization the board is empty so that every qtuple amounts for
395;; gomoku-nil-score. Therefore, the score of any square is gomoku-nil-score times the number 394;; gomoku-nil-score. Therefore, the score of any square is gomoku-nil-score times the number
396;; of qtuples that pass through it. This number is 3 in a corner and 20 if you 395;; of qtuples that pass through it. This number is 3 in a corner and 20 if you
397;; are sufficiently far from the sides. As computing the number is time 396;; are sufficiently far from the sides. As computing the number is time
398;; consuming, we initialize every square with 20*gomoku-nil-score and then only 397;; consuming, we initialize every square with 20*gomoku-nil-score and then only
399;; consider squares at less than 5 squares from one side. We speed this up by 398;; consider squares at less than 5 squares from one side. We speed this up by
400;; taking symmetry into account. 399;; taking symmetry into account.
401;; Also, as it is likely that successive games will be played on a board with 400;; Also, as it is likely that successive games will be played on a board with
402;; same size, it is a good idea to save the initial SCORE-TABLE configuration. 401;; same size, it is a good idea to save the initial SCORE-TABLE configuration.
@@ -451,7 +450,7 @@ Other useful commands:\n
451 "Return the number of qtuples containing square I,J." 450 "Return the number of qtuples containing square I,J."
452 ;; This function is complicated because we have to deal 451 ;; This function is complicated because we have to deal
453 ;; with ugly cases like 3 by 6 boards, but it works. 452 ;; with ugly cases like 3 by 6 boards, but it works.
454 ;; If you have a simpler (and correct) solution, send it to me. Thanks ! 453 ;; If you have a simpler (and correct) solution, send it to me. Thanks !
455 (let ((left (min 4 (1- i))) 454 (let ((left (min 4 (1- i)))
456 (right (min 4 (- gomoku-board-width i))) 455 (right (min 4 (- gomoku-board-width i)))
457 (up (min 4 (1- j))) 456 (up (min 4 (1- j)))
@@ -477,9 +476,9 @@ Other useful commands:\n
477;;; 476;;;
478 477
479;; We do not provide functions for computing the SCORE-TABLE given the 478;; We do not provide functions for computing the SCORE-TABLE given the
480;; contents of the BOARD. This would involve heavy nested loops, with time 479;; contents of the BOARD. This would involve heavy nested loops, with time
481;; proportional to the size of the board. It is better to update the 480;; proportional to the size of the board. It is better to update the
482;; SCORE-TABLE after each move. Updating needs not modify more than 36 481;; SCORE-TABLE after each move. Updating needs not modify more than 36
483;; squares: it is done in constant time. 482;; squares: it is done in constant time.
484 483
485(defun gomoku-update-score-table (square dval) 484(defun gomoku-update-score-table (square dval)