[elpa] externals/gnugo 4b866c7 127/357: [gnugo int] Avoid lower move-num candidates in déjà-vu search.

[Stefan Monnier]

branch: externals/gnugo
commit 4b866c7748247c68e05f583e147f6996b1f1f0b0
Author: Thien-Thi Nguyen <ttn@gnu.org>
Commit: Thien-Thi Nguyen <ttn@gnu.org>

    [gnugo int] Avoid lower move-num candidates in déjà-vu search.
    
    * packages/gnugo/gnugo.el (gnugo-note): Truncate
    branch search on encoutering node w/ insufficient move number.
---
 gnugo.el | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/gnugo.el b/gnugo.el
index f8da28b..fb3e379 100644
--- a/gnugo.el
+++ b/gnugo.el
@@ -961,6 +961,8 @@ are dimmed.  The buffer is in View minor mode."
         (let* ((tree (gnugo-get :sgf-gametree))
                (ends (gnugo--tree-ends tree))
                (mnum (gnugo--tree-mnum tree))
+               (count (length ends))
+               (tip-move-num (gethash tip mnum))
                (bidx (aref monkey 1)))
           ;; Detect déjà-vu.  That is, when placing "A", avoid:
           ;;
@@ -973,23 +975,28 @@ are dimmed.  The buffer is in View minor mode."
           ;;   X---Y---A         new
           ;;            \
           ;;             --B     old
+          ;;
+          ;; This linear search loses for multiple ‘old’ w/ "A",
+          ;; a very unusual (but not invalid, sigh) situation.
           (loop
-           with count = (length ends)
            with (bx previous)
            for i
            ;; Start with latest / highest likelihood for hit.
-           ;; todo: prune unfeasible candidates
+           ;; (See "to the right" comment, below.)
            from (if (gnugo--no-regrets monkey ends)
                     1
                   0)
            below count
            if (setq bx (mod (+ bidx i) count)
                     previous
-                    ;; todo: early termination based on move number
-                    (loop for m on (aref ends bx)
+                    (loop with node
+                          for m on (aref ends bx)
+                          while (< tip-move-num
+                                   (gethash (setq node (car m))
+                                            mnum))
                           if (eq mem (cdr m))
                           return
-                          (when (equal pair (assoc property (car m)))
+                          (when (equal pair (assoc property node))
                             m)
                           finally return
                           nil))