| |
Main
Date: 02 Jul 2007 08:05:12
From: Greg
Subject: Transposition and move table ordering with iterative deepening.
|
I have a basic question which does not seem to be addressed by web
searches of this topic.
I understand how the TT can be used to assist move ordering by storing
a 'best' move and when re-encountering that position, try this move
first. However, it seems to me that the TT can provide additional
information for move ordering for the remaining moves as well. For
example, when performing a ply 2 search, the TT should contain the
scores of a ply 1 search. In general when attempting a ply n search,
the backed up scores for the previous ply < n searches should be
present in the TT.
Why not use the ply n-1 scores to order the remaining moves? That
would involve tentatively applying each move prior to looking up its
ply n-1 score, doing that for all generated moves, then sorting them.
To be clear, I'll provide a more specific example. Let's say we're
about to perform a depth 2 search. At the root node of the depth 2
search, we generate moves. Since we've already performed a depth 1
search, we should have the scores for all the moves about to be made
at the root node. We look these scores up for all genrated moves and
use that information to sort them before performing the ply 2 search.
This idea can be generalized to a search of any depth (except to depth
1 since previous search results will not be available in the TT).
It seem to me to be an obvious thing to do, yet none of the chess
programs I have examined or various web searches on this topic suggest
this. I can't see any reason why this approach wouldn't work. Am I
missing something?
Thanks.
-- Greg
|
|
| |
Date: 05 Jul 2007 11:40:38
From: Greg
Subject: Re: Transposition and move table ordering with iterative deepening.
|
On Jul 5, 1:27 pm, Gian-Carlo Pascutto <[email protected] > wrote:
>
> The answer depends on whether playing an illegal move inside the search
> tree will crash the program.
Here's a scenario, albeit seemingly remote:
Playing an illegal move never causes the engine to crash.
The "best move from TT" is considered at the root without first
checking that it is legal.
It is an illegal move.
It returns the highest backed up score and is therefore selected as
the next move (after all, being allowed to break the rules would seem
to offer an advantage).
The engine plays an illegal move and is thus disqualified.
-- Greg
|
| | |
Date: 05 Jul 2007 19:21:26
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg wrote:
> On Jul 5, 1:27 pm, Gian-Carlo Pascutto <[email protected]> wrote:
>> The answer depends on whether playing an illegal move inside the search
>> tree will crash the program.
>
> Here's a scenario, albeit seemingly remote:
>
> Playing an illegal move never causes the engine to crash.
> The "best move from TT" is considered at the root without first
> checking that it is legal.
> It is an illegal move.
> It returns the highest backed up score and is therefore selected as
> the next move (after all, being allowed to break the rules would seem
> to offer an advantage).
> The engine plays an illegal move and is thus disqualified.
This isn't a scenario to worry about. In a game that last on average
60 moves, the chance to get an error like this would be 60 * 1/(2^32).
This is less than the odds that you die by drowning in your bathtub.
On the other hand, if an illegal move anywhere in the tree crashes the
program, then, for example for a 5 minute game, it's more like 300
seconds * 1 million positions per second * 1/2^32. That's a crash in 1
out of 14 games.
If you move to 64 bit hashing then even the latter cases becomes
unlikely enough that there are more important things to worry about.
So, caring about legality depends on whether you use 32 or 64 bit
hashing and whether or not an illegal move from hash will crash the program.
But caring because it might produce an effect at the root? Nah.
--
GCP
|
| |
Date: 05 Jul 2007 07:36:22
From: Greg
Subject: Re: Transposition and move table ordering with iterative deepening.
|
On Jul 4, 12:32 pm, Gian-Carlo Pascutto <[email protected] > wrote:
> A 32-bit or 64-bit (more common) hashkey, making the probability of a
> collission equal to 1/2^64.
>
> There is additional research that shows that even if the probability of
> a colission would be *much* higher, the engine will play no weaker.
This raises an interesting question. Suppose a "best move from TT" is
obtained. Do most programs go through the trouble of checking that it
is, in fact, a legal move prior to applying it or do they assume its
not worth the effort because a match of the 64 bit hash is sufficient.
-- Greg
|
| | |
Date: 05 Jul 2007 17:27:47
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg wrote:
> On Jul 4, 12:32 pm, Gian-Carlo Pascutto <[email protected]> wrote:
>> A 32-bit or 64-bit (more common) hashkey, making the probability of a
>> collission equal to 1/2^64.
>>
>> There is additional research that shows that even if the probability of
>> a colission would be *much* higher, the engine will play no weaker.
>
> This raises an interesting question. Suppose a "best move from TT" is
> obtained. Do most programs go through the trouble of checking that it
> is, in fact, a legal move prior to applying it or do they assume its
> not worth the effort because a match of the 64 bit hash is sufficient.
The answer depends on whether playing an illegal move inside the search
tree will crash the program.
--
GCP
|
| |
Date:
From: Martin Brown
Subject: Re: Transposition and move table ordering with iterative deepening.
|
|
| | |
Date: 04 Jul 2007 16:32:57
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
tin Brown wrote:
> Are there any engines instrumented to measure the cutoff stats from
> various methods?
All of them? :P
Opensource: Crafty.
> Isn't it the case during iterative deepening that the leading
> principal variation produces close to maximal cutoofs, unless a
> refutation is found down some other path at a deeper level or search
> or selective extension?
I have no idea how to interpret "close to maximal cutoffs" in that sentence.
The moment at which the cutoff happens is what matters.
> One thing I have never been sure of is what entries in the TT contain
> to ensure that collisions do not result in a miss-score.
A 32-bit or 64-bit (more common) hashkey, making the probability of a
collission equal to 1/2^64.
There is additional research that shows that even if the probability of
a colission would be *much* higher, the engine will play no weaker.
> I have seen a
> few games where the annotating engine results have been very sensitive
> to cache status and size.
Sensititivity to hash size does not need to be related to collissions at
all. Simply whether or not a position is found in the hash can alter the
tree search.
> In particular the results with a dirty cache
> are sometimes obviously wrong!
That sounds like a buggy engine.
>> Figure 200 cycles * 35 moves is 7000 cycles just waiting for memory to
>> respond.
>
> This seems a bit steep. Large memory array access is typically 30-50x
> faster for cache aware algorithms than for worst case naive random
> access. I'd be surprised if TT access was significantly worse.
TT access is random and unpredictable, so you do really have the worst
case to deal with: *two* uncached accesses to main memory. One for a TLB
lookup, the second for the hash entry lookup.
>> That's more than 5 times the time it takes to generate the moves.
>
> But that is still probably quite a bit quicker than the time it takes
> to evaluate a positional score for the position resulting from making
> the move.
Depends entirely upon the engine. Evaluating a position can be fast as
noticing that you are a queen down and not looking any further for
pawnstructure finesses.
> Do some modern engines generate their moves in an order
> likely to optimise cutoffs( eg favourable captures, threat mitigation,
> and the rest) and then skip the sorting entirely?
A combination of both.
--
GCP
|
| |
Date: 03 Jul 2007 11:36:49
From: Greg
Subject: Re: Transposition and move table ordering with iterative deepening.
|
On Jul 3, 1:39 pm, Gian-Carlo Pascutto <[email protected] > wrote:
> Greg wrote:
> > Thanks for everyone's thoughts.
> > To sumize, I'll paraphrase the issues surrounding this idea that
> > have been discussed so far:
> ...
> > 2) Even if some useful information could be retrieved, it would be
> > partial information which would either have to be tolerated or
> > supplemented with a secondary method of evaluation.
>
> It's not partial information. The information which you want to use
> simply doesn't exist.
That's correct.
In my previous post I suggested caching *all* results to improve the
situation (I know of some single agent search programs that do this).
After thinking about this further, I don't think that helps here.
Adversarial search is a slightly different paradigm and because
cutoffs can occur, not all positions will be examined. Most of the
moves you'll be attempting to evaluate won't ever be considered so why
waste time on them? I think that is the main reason why this approach
won't work.
I do have one followup question. It seems to me that incremental move
generation and move sorting are incompatible. In order to sort moves,
you need to first generate them. Are there programs which avoid
generating moves altogether by first trying the TT & killers first
(after determining they are in fact legal moves), and then continue to
generate moves only if these do not produce a cutoff?
-- Greg
-- Greg
|
| | |
Date: 03 Jul 2007 19:01:37
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg wrote:
> I do have one followup question. It seems to me that incremental move
> generation and move sorting are incompatible. In order to sort moves,
> you need to first generate them. Are there programs which avoid
> generating moves altogether by first trying the TT & killers first
> (after determining they are in fact legal moves), and then continue to
> generate moves only if these do not produce a cutoff?
Fruit and everything based on it. Crafty also, if I remember correctly.
As long as you can generate moves incrementally in the order you know in
which you would sort them, you're fine.
--
GCP
|
| |
Date: 03 Jul 2007 06:50:36
From: Greg
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Thanks for everyone's thoughts.
To sumize, I'll paraphrase the issues surrounding this idea that
have been discussed so far:
1) The TT only contains a single 'eval' per node and thus has
incomplete information.
2) Even if some useful information could be retrieved, it would be
partial information which would either have to be tolerated or
supplemented with a secondary method of evaluation.
3) Modern chess programs typically generate cutoffs very early thus
obviating the need and cost of examining all moves at any given node.
4) Memory access is expensive and increases the per node overhead.
I'd like to make a few further points/observations:
1) I'm aware that much contemporary research involving single agent
search is concerned with increasing search performance by utilizing
the large memory capacities of modern computers. For example, it is
not unreasonable to attempt to cache every node. I can imagine this
being done for adversarial search (e.g. Chess programs), possibly in a
supplemental hash table in order to address issue #1 above.
2) There seems to be some circularity involved in promoting early
cutoffs and generating move ordering. What I mean by that is that it
seems to me that you have to generate the moves before you can sort
them. I suppose if you have a TT move along with some killers, you
would at least have to determine that these were legal before trying
them without the necessity of generating all moves. I don't know if
it is commonly done this way or not. But if you *are* already
generating all moves to support your ability to perform cutoffs, then
what I am suggesting may not be so unreasonable in terms of
computational cost.
3) It may be that if this scheme provides more benefit for plys nearer
to the root since good move ordering yields exponential payoffs.
-- Greg
|
| | |
Date: 03 Jul 2007 17:39:44
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg wrote:
> Thanks for everyone's thoughts.
> To sumize, I'll paraphrase the issues surrounding this idea that
> have been discussed so far:
...
> 2) Even if some useful information could be retrieved, it would be
> partial information which would either have to be tolerated or
> supplemented with a secondary method of evaluation.
It's not partial information. The information which you want to use
simply doesn't exist.
There are 3 classes of positions (nodes) in an alpha-beta searcher, and
this is what you know after searching them in each case:
PV nodes (small minority)
-------------------------
move e2e4 has a score of exactly x
move d2d4 has a score less than or equal to x
move f2f4 has a score less than or equal to x
move c2c4 has a score less than or equal to x
...
CUT nodes (about half)
-----------------------
move e2e4 has a score higher or equal to y
(no information about any other move)
ALL nodes (about half)
-----------------------
move e2e4 has a score less than or equal to z
move d2d4 has a score less than or equal to z
move f2f4 has a score less than or equal to z
move c2c4 has a score less than or equal to z
...
Not much there to order moves on, except for the "best" one, which the
TT already handles.
The speedup of alphabeta over minimax comes at a price, and that price
is knowing the exact scores of moves.
--
GCP
|
| |
Date: 03 Jul 2007 05:49:55
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg wrote:
> To be clear, I'll provide a more specific example. Let's say we're
> about to perform a depth 2 search. At the root node of the depth 2
> search, we generate moves. Since we've already performed a depth 1
> search, we should have the scores for all the moves about to be made
> at the root node.
No, you don't.
You will only know that one move y_1 is the best with score x, and that
all other moves y_2...y_n have a score <= x.
That's the only thing alpha-beta will tell you. Particularly, you do not
know the scores for y_2..y_n.
--
GCP
|
| |
Date: 02 Jul 2007 18:24:52
From: Hello
Subject: Re: Transposition and move table ordering with iterative deepening.
|
"Greg" <[email protected] > wrote in message
news:[email protected]...
>I have a basic question which does not seem to be addressed by web
> searches of this topic.
>
> Why not use the ply n-1 scores to order the remaining moves? That
> would involve tentatively applying each move prior to looking up its
> ply n-1 score, doing that for all generated moves, then sorting them.
A couple reasons.
First, you don't really need to. Modern chess programs tend to pick a
decent move more than 95% of the time as the first move searched. (Some
people say in excess of 98%, with a few saying 99%. To be safe, I'll say
95%.)
Note that doesn't mean it's the 'best' move, but only a move good enough to
cause a cut-off during the search.
That means that most of the time you wont even need to generate most of the
moves. The Trans Table and the Killers will often save you the trouble.
Still, I understand the need to do move ordering the rest of the time, and I
can see why you might want to do it. That brings me to the second reason
not to...
Do you know what the read access times for main memory is for random
addresses? A couple hundred cycles with modern cpu's.
Figure 200 cycles * 35 moves is 7000 cycles just waiting for memory to
respond.
That's more than 5 times the time it takes to generate the moves.
(Of course, that does depend on your processor and memory speed....)
Of course, having said all of that, if you want to try it, then feel free.
It it doesn't work well or you just don't like it, you don't have to keep
it.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| | |
Date: 03 Jul 2007 05:52:37
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Hello wrote:
> Do you know what the read access times for main memory is for random
> addresses? A couple hundred cycles with modern cpu's.
>
> Figure 200 cycles * 35 moves is 7000 cycles just waiting for memory to
> respond.
>
> That's more than 5 times the time it takes to generate the moves.
>
> (Of course, that does depend on your processor and memory speed....)
*If* the idea would be possible, then memory access latency doesn't
matter. You could apply it as long as "remaining depth" is fairly large.
This would get you improved move ordering for the deeper searches (= the
important ones). Because there are less, you won't feel the speed penalty.
ETC, which also involves making and doing a TT lookup for each move,
works like this.
But the idea doesn't work because it relies on information that is not
available.
--
GCP
|
| | | |
Date: 03 Jul 2007 09:14:48
From: Hello
Subject: Re: Transposition and move table ordering with iterative deepening.
|
"Gian-Carlo Pascutto" <[email protected] > wrote in message
news:[email protected]...
> Hello wrote:
>
> *If* the idea would be possible, then memory access latency doesn't
> matter. You could apply it as long as "remaining depth" is fairly large.
Memory access times do matter because the point I was making was that
current methods already order the moves pretty darn well without the obscene
memory access costs that the TT lookups would require.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| | | | |
Date: 03 Jul 2007 17:03:09
From: Gian-Carlo Pascutto
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Hello wrote:
> "Gian-Carlo Pascutto" <[email protected]> wrote in message
> news:[email protected]...
>> Hello wrote:
>>
>> *If* the idea would be possible, then memory access latency doesn't
>> matter. You could apply it as long as "remaining depth" is fairly large.
>
> Memory access times do matter because the point I was making was that
> current methods already order the moves pretty darn well without the obscene
> memory access costs that the TT lookups would require.
This argument holds no water: 99% move ordering accuracy is still an
improvement over 98%, as long as the effiency improvement resulting from
it offsets any slowdown you get.
Let me take the extreme example: you only do this at the root (remaining
depth = maximal), and we're at iteration 12 in an iterative deepening
system. Time lost because of memory lookups: maybe 12 (ply) * 40 (moves)
* 200ns, so essentially nothing even in a fast game. Potential speedup
if the better move ordering gets the right move higher in the move list:
up to a factor 2 in a typical engine and position.
--
GCP
|
| | | | | |
Date: 03 Jul 2007 12:39:34
From: Hello
Subject: Re: Transposition and move table ordering with iterative deepening.
|
"Gian-Carlo Pascutto" <[email protected] > wrote in message
news:[email protected]...
> Hello wrote:
>> "Gian-Carlo Pascutto" <[email protected]> wrote in message
>> news:[email protected]...
>>> Hello wrote:
>>>
>>> *If* the idea would be possible, then memory access latency doesn't
>>> matter. You could apply it as long as "remaining depth" is fairly large.
>>
>> Memory access times do matter because the point I was making was that
>> current methods already order the moves pretty darn well without the
>> obscene
>> memory access costs that the TT lookups would require.
>
> This argument holds no water: 99% move ordering accuracy is still an
> improvement over 98%, as long as the effiency improvement resulting from
> it offsets any slowdown you get.
That's a very big *IF*
And if you'll remember, I did tell the guy to go ahead and give it a try and
see if he liked it.
Not everybody programs the same way, and not every program is the same.
> Let me take the extreme example: you only do this at the root (remaining
> depth = maximal), and we're at iteration 12 in an iterative deepening
> system. Time lost because of memory lookups: maybe 12 (ply) * 40 (moves)
> * 200ns, so essentially nothing even in a fast game. Potential speedup
> if the better move ordering gets the right move higher in the move list:
> up to a factor 2 in a typical engine and position.
At the root and such, the cost is neglible.
But trying to order the moves that way at every (or most) node is going to
be time consuming.
First, you actually generate all the moves at each node. That's something
that most quality programs don't do because they don't need to. The trans
table move or the killer move is enough. (Or whatever other method they
happen to use.)
Second, you then have to spend lots of cycles retrieving the scores from the
TT to try and order the moves.
Close to the root, there's little cost.
But the deeper you go into the tree, the greater the cost. It gets very
expensive darn quick due to the exponential growth of chess trees.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| |
Date: 02 Jul 2007 08:51:13
From: Greg
Subject: Re: Transposition and move table ordering with iterative deepening.
|
On Jul 2, 11:29 am, David Richerby <[email protected] >
wrote:
> Greg <[email protected]> wrote:
> > Why not use the ply n-1 scores to order the remaining moves? That
> > would involve tentatively applying each move prior to looking up its
> > ply n-1 score, doing that for all generated moves, then sorting
> > them.
>
> You're not guaranteed that all the ply-(n-1) scores are in the TT --
> some of them may have been overwritten. In particular, positions that
> were considered a long time ago are more likely to have been over-
> written. Since we're using some sort of move-ordering, the moves that
> were considered a long time ago are likely to have been the best ones.
>
> So, how to deal with moves that you can't find in the TT?
I suppose you could still use the partial information available to
help form a partial move ordering. That would at least seem to be
better than random ordering. Barring that, I could envision doing one
or more of the following:
1) Utillize a separate hash table for ply n-1 results. This still may
not eliminate the problem entirely, but might be a significant
improvement. An alternative might be to lock the n-1 results in the
table and clear the lock after using the result for move ordering.
2) Invoke the evaluation function directly (or some other nominal
heuristic) for those positions not in the TT.
-- Greg
|
| |
Date: 02 Jul 2007 16:29:13
From: David Richerby
Subject: Re: Transposition and move table ordering with iterative deepening.
|
Greg <[email protected] > wrote:
> Why not use the ply n-1 scores to order the remaining moves? That
> would involve tentatively applying each move prior to looking up its
> ply n-1 score, doing that for all generated moves, then sorting
> them.
You're not guaranteed that all the ply-(n-1) scores are in the TT --
some of them may have been overwritten. In particular, positions that
were considered a long time ago are more likely to have been over-
written. Since we're using some sort of move-ordering, the moves that
were considered a long time ago are likely to have been the best ones.
So, how to deal with moves that you can't find in the TT?
Dave.
--
David Richerby Sadistic Metal Car (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ high-performance luxury car that's
made of steel but it wants to hurt
you!
|
|
