Odd ply versus even ply searches
Robert Hyatt
Kenneth Sloan <sl...@willis.cis.uab.edu> wrote:
-->In article <4h1j5e$q...@pelham.cis.uab.edu>,
-->Robert Hyatt <hy...@willis.cis.uab.edu> wrote:
-->>...
-->>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.
-->>...
-->>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.
-->
-->Bob is, of course, the local expert on chess - but I have some small
-->experience with Othello. We discovered very early that it made a lot of
-->sense to search ONLY even search depths. One reason is the one Bob
-->gives above - there is a great disparity in the amount of effort to
-->search odd vs even depths. Another is that we don't use any search
-->extensions (there doesn't seem to be as much use for them in Othello -
-->or perhaps our program is simply too primitive...). Finally, we
-->discovered that some evaluation terms are VERY sensitive to which side
-->is on move. In situations where there are several moves at the root
-->which are very, very close in evaluation, the choice could flip-flop on
-->every iteration. This is bad! We discovered that searching only EVEN
-->serch depths was most efficient, and our iterative deepening now
-->searches depths 2,4,6,8,10,12,...etc.
-->
-->Beware: Othello is very different than Chess, and this experience may or
-->may not transfer.
-->
-->
-->--
-->Kenneth Sloan sl...@cis.uab.edu
-->Computer and Information Sciences (205) 934-2213
-->University of Alabama at Birmingham FAX (205) 934-5473
-->Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/
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
John Olle
the ply is important?
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
Robert Hyatt
John Olle <J.O...@bendigo.latrobe.edu.au> wrote:
-->Has anyone ever studied whether the 'polarity' (i.e. whether it is odd or even) of
-->the ply is important?
-->
-->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.
Robert Hyatt
SheppardCo <shepp...@aol.com> wrote:
> <snip>
>Perhaps Bob can describe the time-control strategy for Cray Blitz,
>which successfully made use of optional deepening to N+1 ply.
>
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