Maybe not *that* different. Tony Scherzer (BeBe) for years searched
every other depth, the only "odd" thing was he did odd ply searches
(1,3,5,7,...) skipping the "easier" even ply searches. As I recall,
this was due, not to performance issues, but to aggressiveness concerns.
If you can make 4 moves, and your opponent can only make 3 (for example)
before you evaluate, you will be more aggressive. If you both make
the same number of moves, then each threat is parried by opponent,
and you end up choosing a more "conservative" line.
Think I might re-visit the even/odd thing as since I have added internal
iterative deepening into crafty, maybe it won't be so sensitive to skipping
every other depth and missing the move ordering info it would get had it
not skipped. Certainly easy to test, in iterate.c, simply change
iteration_depth++ to iteration_depth+=2 in the for-loop and away it
goes. Have to test this... :)
Bob
dee
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
In most (but not all for some circumstances) cases adding one move (two ply) to a
search will increase strength but perhaps this is not uniform across the two plies.
Maybe it tends to be more efficient to go for odd (or even) ply searches.
Perhaps rather than evaluating all interesting variations to 13 ply it may be better
to evaluate some to 12 and some to 14 for example.
Perhaps this effect does not exist or perhaps it does exist but is too small to be
of much benefit.
Perhaps some extensive rating studies of programs could see if this is worth
pursuing.
John Olle
If you study alpha/beta trees, you immediately notice that if you look
at all moves at a particular ply, then with good move ordering, you look
at only one move at the ply before or after that ply.
What does this mean? Since ply=1 will always have all moves searched,
except for the first ply=1 move (PV move) ply=2 will need to search only
one move for each ply=1 move. Suppose you search to depth "n" and you
have exactly 1,000,000 tip positions at that depth (not counting any sort
of quiescence search whatsoever). If we search this tree to depth N+1,
and N+1 is even, for each tip position in N, we only search one move at
depth N+1, doubling the number of positions searched. However, if N+1
is odd, we have to search every legal move at N+1, which is obviously
a lot more than "1" if N+1 is even.
So, you are correct. Even plies are quicker to search than are odd
plies, because at depth=9 you look at one move for each depth=8 node,
while if depth=10, you only search one move for each depth 9 move.
I have not studied the effect of doing an iterated search but limiting
depths to n where n=even, because it's more complex than that. Every
search extension (out of check, recapture, etc.) adds 1 to D and turns
an odd depth into an even one and vice versa. Obviously not as clear,
and just as obviously depends on the position and how many extensions
you do.
I'll be glad to explain anything in CB or Crafty. However, I'm not quite
sure exactly what you mean about "optional deepening to N+1 ply." Explain
further and I'll give it a shot.
BTW, my earlier comments about trying even iterations only was predicated on
the fact that there would be no substantial penalty. You are exactly correct
when you say that to go 14 once and 12 three times is likely worse than
going 13 every time. That's a choice I would not make without some serious
thought to make sure that I go 12 when it's safe, and 14 when it's necessary.
That might be difficult. :)
Bob