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..
Iterative DTS
Moderators: hgm, Rebel, chrisw
Re: Iterative DTS
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!?
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!?
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Iterative DTS
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:
;
}
}
-
- Posts: 442
- Joined: Wed Mar 08, 2006 8:54 pm
Re: Iterative DTS
A couple of links to analysis and techniques:
http://www.complang.tuwien.ac.at/forth/ ... -code.html
http://www.complang.tuwien.ac.at/forth/ ... ortability
http://compilers.iecc.com/comparch/article/07-05-044
http://www.complang.tuwien.ac.at/forth/ ... .html#jilp
MvH Dan Andersson
http://www.complang.tuwien.ac.at/forth/ ... -code.html
http://www.complang.tuwien.ac.at/forth/ ... ortability
http://compilers.iecc.com/comparch/article/07-05-044
http://www.complang.tuwien.ac.at/forth/ ... .html#jilp
MvH Dan Andersson
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Iterative DTS
Jump table is generally slow, because it is not use modern processors' branch prediction heuristics.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Iterative DTS
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.
Cray Blitz was a mess in that regard.
-
- Posts: 287
- Joined: Sat Mar 11, 2006 3:19 am
- Location: Atlanta, GA
Re: Iterative DTS
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.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!?
Re: Iterative DTS
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
And it is definitely harder to read. :-/
--
James