Author: Dann Corbit
Date: 01:57:01 04/14/04
Go up one level in this thread
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}
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.