Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Question for the MTD(f) experts

Author: Andrew Williams

Date: 02:00:27 04/14/04

Go up one level in this thread


On April 14, 2004 at 04:57:01, Dann Corbit wrote:

>On April 14, 2004 at 04:38:01, Dann Corbit wrote:
>
>>On April 14, 2004 at 04:26:10, Richard Pijl wrote:
>>
>>>On April 14, 2004 at 03:49:06, Dann Corbit wrote:
>>>
>>>>On April 14, 2004 at 03:46:08, Richard Pijl wrote:
>>>>
>>>>>On April 14, 2004 at 03:30:22, Dann Corbit wrote:
>>>>>
>>>>>>I decided to toss an MTD(f) search into TSCP, and I've got something wrong, but
>>>>>>I can't quite see what it is.
>>>>>
>>>>>MTD(f) requires a transposition hashtable and a fail-soft search to function
>>>>>properly. Did you add/change that too?
>>>>
>>>>With hash table, I get this behavior:
>>>>post
>>>>sd 99
>>>>st 99
>>>>go
>>>>Depth   Eval    Time    Nodes   PV
>>>>1       48      0       172
>>>>2       0       20      2224    d2d3
>>>>3       35      40      4858
>>>>4       5       321     41505   e2e3
>>>>5       35      711     93485
>>>>6       13      5438    780563  d2d4
>>>>7       30      11878   1638246
>>>>8       18      81509   11563089        e2e4
>>>>move e2e4
>>>>
>>>
>>>I guess you're referring to the empty PV lines?
>>>That's normal, as TSCP doesn't store the PV on a fail high/low. As TSCP is
>>>searching with an open window in the root, you will always have a PV. But with
>>>MTD(f) you're searching with null-windows, so you won't have a PV.
>>>
>>>Did you change stuff in search to deal with pv with fail high/lows?
>>>
>>>In your code below, you're setting a move in the pv array, but that move is
>>>basically random:
>>>
>>>        if (f < beta)
>>>            greatest = f;
>>>        else {
>>>            int             j;
>>>            smallest = f; /* performs a cut-off */
>>>            if (smallest >= greatest) {
>>>                pv[ply][ply] = gen_dat[depth].m;
>>>                for (j = ply + 1; j < pv_length[ply + 1]; ++j)
>>>                    pv[ply][j] = pv[ply + 1][j];
>>>                pv_length[ply] = pv_length[ply + 1];
>>>            }
>>>        }
>>>
>>>gen_dat[depth].m is a generated move in the movelist, but it is not the
>>>bestmove. It isn't even the first move in the move list as depth is increased on
>>>every iteration.
>>
>>I pulled the pm from the hash table, so the pv move is right (when it is there)
>>but the search still blows chunks of green goo:
>>
>>pvs:
>>post
>>sd 99
>>st 99
>>go
>>Depth   Eval    Time    Nodes   PV
>>1       48      0       21      d2d4
>>2       0       0       84      d2d4 d7d5
>>3       35      40      797     d2d4 d7d5 b1c3
>>4       5       80      4313    e2e4 d7d5 f1b5 c8d7 b5d3
>>5       35      241     19619   e2e4 e7e5 d2d4 d7d5 g1f3
>>6       13      872     88472   e2e4 e7e5 d2d4 e5d4 d1d4 g8f6
>>7       30      4517    570969  e2e4 d7d5 e4d5 d8d5 d2d4 d5e4 g1e2 e7e5
>>8       18      30655   3279256 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6
>>
>>mtdf:
>>post
>>sd 99
>>st 99
>>go
>>Depth   Eval    Time    Nodes   PV
>>1       48      0       172
>>2       0       30      2224    d2d4
>>3       35      60      4602
>>4       5       451     41509   e2e4
>>5       35      1362    103001
>>6       13      7741    799578  e2e4
>>7       30      15553   1623933
>>move e2e4
>
>Picking out the hash value and moving the lookup to the end gives a bit better
>result:
>
>/* MTD(f) is an alternative search to pvs */
>int             mtdf(int f, int depth)
>{
>    int             beta;
>    int             smallest = -INFINITY;
>    int             greatest = INFINITY;
>    TranspositionEntry *entry;
>
>    do {
>        if (f == smallest)
>            beta = f + 1;
>        else
>            beta = f;           /* beta is starting with a first best guess */
>        f = AlphaBeta(beta - 1, beta, depth);
>
>        if (f < beta)
>            greatest = f;
>        else {
>            int             j;
>            smallest = f;       /* performs a cut-off */
>            if (smallest >= greatest) {
>            }
>        }
>    } while (smallest < greatest);
>    entry = &transpositionTable[hash & (TRANSPOSITION_SIZE - 1)];
>    if (entry->hash == hash) {
>        if (entry->move.rawValue != 0 && entry->depth >= depth) {
>            pv[ply][0] = entry->move;
>            pvLength[ply] = 1;
>        }
>    }
>    return f;
>}
>
>
>post
>sd 99
>st 99
>go
>Depth   Eval    Time    Nodes   PV
>1       48      0       172     d2d3
>2       0       20      2224    d2d4
>3       35      40      4602    d2d4
>4       5       320     41509   e2e4
>5       35      751     102983  d2d4
>6       13      5488    799216  e2e4
>7       30      12068   1709733 d2d4
>8       18      82330   11635407        e2e4
>move e2e4
>
>So my next question is, how do you normally populate a hash table with PV nodes,
>since we only get edge values during the search?  Do I need to follow the pv
>from hash to hash with a makemove for each succeeding pv node?
>{ICK}

When you fail high in your alphabeta() function, put the move which caused the
fail-high in the hash table.

Andrew



This page took 0.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.