Page 2 of 2
Re: Iterative DTS
Posted: Tue Jul 03, 2007 5:26 pm
by bob
Sorry. I was simply explaining the usual issue with an iterated search conversion. Your code was too long to look at on the older computer I was using at the time (a 1024 x 768 laptop with a small screen). It sounds like you did things the right way.
Next step would be to compare old vs new code to see what is drastically different... and it might work better on a 64 bit box where you have the extra 8 registers to handle the array subscripting stuff.
Making everything indirect on a pointer will have a cost, of course..
Re: Iterative DTS
Posted: Tue Jul 03, 2007 7:44 pm
by LoopList
At the moment I am satisfied with the iterative search speed. The main handycaps were too many indirect search phase calls via the switch-case-statement. Now I jump direct to the next search phase by using multiple "gotos". I only remember the return points.
Until now I was used to develop "clear" and "modern" code, but the new iterative search looks really ugly. As far as I understood the only advantage of DTS is the thread's possibility to choose its best split node from all possible active split nodes.
But I suppose it should be possible to do so in a recursive search environment, too!?
Re: Iterative DTS
Posted: Tue Jul 03, 2007 8:18 pm
by Zach Wegner
Here's a simplified version of my search. The explicit gotos make the compiler create a jump table. The macros also do quite a lot to insure maximum readability.
Code: Select all
#define SEARCH_CALL(d, p, a, b, fm, dn, nt, rp) \
do { \
search_call(sb, d, p, a, b, fm, dn, nt, rp); \
sb++; \
goto end; \
} while (FALSE)
#define RETURN(r) \
do { \
sb->return_value = r; \
sb--; \
goto end; \
} while (FALSE)
int search(SEARCH_BLOCK *sb)
{
while(1)
{
switch (sb->return_point)
{
case SEARCH_START:
goto search_start;
case SEARCH_1:
goto search_1;
case SEARCH_RETURN:
return (sb + 1)->return_value;
}
search_start:
nodes++;
if (sb->ply >= MAX_PLY - 1)
RETURN(evaluate());
if (board.fifty_count >= 100 || is_repetition(sb->ply == 1 ? 3 : 2))
RETURN(0);
if (sb->depth <= 0)
RETURN(evaluate());
score_moves(sb);
/* The main move loop. */
while (sb->move = select_move(sb))
{
if (!make_move(sb->move))
continue;
sb->moves++;
SEARCH_CALL(sb->depth - PLY, sb->ply + 1, -sb->beta,
-sb->alpha, sb->last_move, SEARCH_1);
search_1: r = -(sb + 1)->return_value;
if (r > sb->alpha)
{
sb->alpha = r;
if (r >= sb->beta)
RETURN(r);
}
}
end:
;
}
}
Re: Iterative DTS
Posted: Tue Jul 03, 2007 8:34 pm
by Dan Andersson
Re: Iterative DTS
Posted: Tue Jul 03, 2007 9:04 pm
by Aleks Peshkov
Jump table is generally slow, because it is not use modern processors' branch prediction heuristics.
Re: Iterative DTS
Posted: Tue Jul 03, 2007 10:37 pm
by bob
anything is possible, but it will be anything but easy. That's why I chose to stick with the recursive formulation of the search, it is more readable.
Cray Blitz was a mess in that regard.
Re: Iterative DTS
Posted: Tue Jul 03, 2007 11:03 pm
by Pradu
LoopList wrote:At the moment I am satisfied with the iterative search speed. The main handycaps were too many indirect search phase calls via the switch-case-statement. Now I jump direct to the next search phase by using multiple "gotos". I only remember the return points.
Until now I was used to develop "clear" and "modern" code, but the new iterative search looks really ugly. As far as I understood the only advantage of DTS is the thread's possibility to choose its best split node from all possible active split nodes.
But I suppose it should be possible to do so in a recursive search environment, too!?
Yes it's possible with recursive too but it'd be uglier and less efficient. You'd have to handle rolling back your call stack when a thread is expected to quit and you'd have to handle creating a new call stack every time you want to pass on your search stack to another thread.
Re: Iterative DTS
Posted: Fri Jul 13, 2007 11:03 pm
by jswaff
Definitely. I have started writing an iterative search, and it is just about the ugliest thing I've ever seen. I'm not finished, but as it stands now I have one jump out of the move loop and two jumps into the move loop. Yuck.
And it is definitely harder to read. :-/
--
James