Re: [Bug-gnubg] How do move filters work?

[Joern Thyssen]

On Fri, May 30, 2003 at 10:11:56AM -0700, Rod Roark wrote
> Could someone please explain (or tell me where to find an
> explanation of) how move filters work and how to set them up
> effectively?

doc/movefilters.texi:

gnubg uses a technique called ``move filters'' in order to prune the
complete list of legal moves when analysing chequer play decisions.
Move filters can be considering a generalising of the search space used
in earlier versions of gnubg.

A move filter for a given ply, say, 2-ply, consists of four parameters
for each subply:
  1. whether to analyse at all at this subply,

  2. the number of moves always accepted at the given level,

  3. the number of extra moves to add,

  4. the threshold for adding extra moves.

For example, for 2-ply chequer play decisions there are two
movefilters: one for pruning at 0-ply, and another for pruning at
1-ply. The predefined setting ``Normal'' has: accept 0 moves and add up
to 8 moves within 0.16 at 0-ply, and no pruning at 1-ply.

Consider the opening position where 6-2 has been rolled:

 GNU Backgammon  Position ID: 4HPwATDgc/ABMA
                 Match ID   : cAkZAAAAAAAA
 +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
 | X           O    |   | O              X |     0 points
 | X           O    |   | O              X |
 | X           O    |   | O                |
 | X                |   | O                |
 | X                |   | O                |
v|                  |BAR|                  |     (Cube: 1)
 | O                |   | X                |
 | O                |   | X                |
 | O           X    |   | X                |
 | O           X    |   | X              O |     Rolled 24
 | O           X    |   | X              O |     0 points
 +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth
Pip counts: O 167, X 167


gnubg starts by finding all possible moves and evaluate those at
0-ply:

    1. Cubeful 0-ply    8/4 6/4                      Eq.:  +0.207
       0.548 0.172 0.009 - 0.452 0.121 0.005
        0-ply cubeful [expert]
    2. Cubeful 0-ply    13/11 13/9                   Eq.:  +0.050 ( -0.156)
       0.509 0.155 0.009 - 0.491 0.137 0.007
        0-ply cubeful [expert]
    3. Cubeful 0-ply    24/20 13/11                  Eq.:  +0.049 ( -0.158)
       0.513 0.137 0.007 - 0.487 0.132 0.004
        0-ply cubeful [expert]
    4. Cubeful 0-ply    24/22 13/9                   Eq.:  +0.037 ( -0.170)
       0.508 0.142 0.007 - 0.492 0.134 0.004
        0-ply cubeful [expert]
    5. Cubeful 0-ply    24/22 24/20                  Eq.:  -0.008 ( -0.215)
       0.501 0.121 0.006 - 0.499 0.133 0.003
        0-ply cubeful [expert]
    6. Cubeful 0-ply    24/18                        Eq.:  -0.015 ( -0.222)
       0.502 0.121 0.006 - 0.498 0.140 0.004
        0-ply cubeful [expert]
    7. Cubeful 0-ply    24/20 6/4                    Eq.:  -0.023 ( -0.229)
       0.497 0.132 0.007 - 0.503 0.144 0.005
        0-ply cubeful [expert]
    8. Cubeful 0-ply    13/9 6/4                     Eq.:  -0.026 ( -0.233)
       0.494 0.146 0.008 - 0.506 0.151 0.009
        0-ply cubeful [expert]
[10 moves deleted]


Accoring to the move filter the first 0 moves are accepted. The equity
of the best move is +0.207, and according to the movefilter we add up
to 8 extra moves if they're within 0.160, that is, if they have equity
higher than +0.047. Move 4-18 all have equity lower that +0.047, so
the move list after pruning at 0-ply consists of move 1-3. According
to the move filter we do not perform any pruning at 1-ply, so move 1-3
are submitted for evaluation at 2-ply;

    1. Cubeful 2-ply    8/4 6/4                      Eq.:  +0.197
       0.546 0.172 0.008 - 0.454 0.123 0.005
        2-ply cubeful 100% speed [world class]
    2. Cubeful 2-ply    24/20 13/11                  Eq.:  +0.058 ( -0.138)
       0.515 0.141 0.007 - 0.485 0.130 0.005
        2-ply cubeful 100% speed [world class]
    3. Cubeful 2-ply    13/11 13/9                   Eq.:  +0.050 ( -0.147)
       0.508 0.156 0.007 - 0.492 0.136 0.006
        2-ply cubeful 100% speed [world class]
    4. Cubeful 0-ply    24/22 13/9                   Eq.:  +0.037 ( -0.159)
       0.508 0.142 0.007 - 0.492 0.134 0.004
        0-ply cubeful [expert]
    5. Cubeful 0-ply    24/22 24/20                  Eq.:  -0.008 ( -0.205)
       0.501 0.121 0.006 - 0.499 0.133 0.003
        0-ply cubeful [expert]
    6. Cubeful 0-ply    24/18                        Eq.:  -0.015 ( -0.212)
       0.502 0.121 0.006 - 0.498 0.140 0.004
        0-ply cubeful [expert]
    7. Cubeful 0-ply    24/20 6/4                    Eq.:  -0.023 ( -0.219)
       0.497 0.132 0.007 - 0.503 0.144 0.005
        0-ply cubeful [expert]
    8. Cubeful 0-ply    13/9 6/4                     Eq.:  -0.026 ( -0.222)
       0.494 0.146 0.008 - 0.506 0.151 0.009
        0-ply cubeful [expert]


If we instead request a 4-ply chequer play decision, gnubg will use
the move filters defined for 4-ply:
*Ply*          *Accept moves* *Extra moves*  *Threshold for extra moves*
0              0              8              0.160
1              no pruning                    
2              0              2              0.040
3              no pruning                    

The 4-ply move filter is identical to the 2-ply for pruning at 0-ply,
so after 0-ply we have the same three moves as above. Since there is no
pruning at 1-ply these three moves are evaluated at 2-ply as
above. There is no pruning at 3-ply.

At 4-ply we do not accept any moves, but add up to two moves if there
within 0.040 from the best move. Since the second best move is -0.138
worse than the best move, we do not accept any moves to be evaluated
at 4-ply. Hence gnubg will actually not evaluate any moves on
4-ply.



The predefined movefilters all have ``accept 0 moves'', in order to
facilitate fast decisions and analysis, i.e., no need to waste much
time over obvious moves.

For post-mortem analysis it may be worthwhile to ensure
that gnubg analyses at least two moves at the specified ply. To do
this, specify ``accept 2 moves'' in the move filters you use for
analysis. However, do note that gnubg will force evaluation at the
specified ply if the actual move made is doubtful.  This ensures that
all errors and blunders are evaluted at the same level.