diff options
| author | Stefan Kangas | 2021-02-16 09:56:17 +0100 |
|---|---|---|
| committer | Stefan Kangas | 2021-02-16 10:06:42 +0100 |
| commit | 9f843572d2feb4c75bd4f1d2a86edc7595591dc9 (patch) | |
| tree | 26218671f863a2ee32182a02252fdf11319912aa | |
| parent | 62cda6acd61f6de2698674391a26ce0a8672fc93 (diff) | |
| download | emacs-9f843572d2feb4c75bd4f1d2a86edc7595591dc9.tar.gz emacs-9f843572d2feb4c75bd4f1d2a86edc7595591dc9.zip | |
* lisp/play/gomoku.el: Minor doc fixes; formatting.
| -rw-r--r-- | lisp/play/gomoku.el | 77 |
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. |
| 90 | SHOULD 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. |
| 94 | SHOULD 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) |