Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old July 2nd 07, 04:05 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2007
Posts: 6
Default 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

  #2   Report Post  
Old July 2nd 07, 04:29 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default Transposition and move table ordering with iterative deepening.

Greg 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!
  #3   Report Post  
Old July 2nd 07, 04:51 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2007
Posts: 6
Default Transposition and move table ordering with iterative deepening.

On Jul 2, 11:29 am, David Richerby
wrote:
Greg 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



  #4   Report Post  
Old July 3rd 07, 12:24 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2007
Posts: 14
Default Transposition and move table ordering with iterative deepening.

"Greg" wrote in message
ups.com...
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 =----
  #5   Report Post  
Old July 3rd 07, 06:49 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Sep 2003
Posts: 41
Default 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


  #6   Report Post  
Old July 3rd 07, 06:52 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Sep 2003
Posts: 41
Default 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
  #7   Report Post  
Old July 3rd 07, 02:50 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2007
Posts: 6
Default Transposition and move table ordering with iterative deepening.

Thanks for everyone's thoughts.
To summarize, 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

  #8   Report Post  
Old July 3rd 07, 03:14 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2007
Posts: 14
Default Transposition and move table ordering with iterative deepening.

"Gian-Carlo Pascutto" wrote in message
...
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 =----
  #9   Report Post  
Old July 3rd 07, 06:03 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Sep 2003
Posts: 41
Default Transposition and move table ordering with iterative deepening.

Hello wrote:
"Gian-Carlo Pascutto" wrote in message
...
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
  #10   Report Post  
Old July 3rd 07, 06:39 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2007
Posts: 14
Default Transposition and move table ordering with iterative deepening.

"Gian-Carlo Pascutto" wrote in message
...
Hello wrote:
"Gian-Carlo Pascutto" wrote in message
...
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 =----
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 09:08 PM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017