A Chess forum. ChessBanter

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

Go Back   Home » ChessBanter forum » Chess Newsgroups » rec.games.chess.computer (Computer Chess)
Site Map Home Register Authors List Search Today's Posts Mark Forums Read Web Partners

Hash Table and Quiescence Search



 
 
Thread Tools Display Modes
  #1  
Old August 24th 03, 10:50 AM
Jih-tung Pai
external usenet poster
 
Posts: n/a
Default Hash Table and Quiescence Search

I wonder if there is conclusion or consensus on whether to store
quiescence search results in hash table. What are the advantages and
disadvantages? If I choose to store the results, is it better to store
in the same hash table as regular one or I should have separate one?
And reasons for that?

Thanks in advance!
  #2  
Old August 24th 03, 11:13 AM
Renze Steenhuisen
external usenet poster
 
Posts: n/a
Default Hash Table and Quiescence Search

Jih-tung Pai wrote:

I wonder if there is conclusion or consensus on whether to store
quiescence search results in hash table. What are the advantages and
disadvantages? If I choose to store the results, is it better to store
in the same hash table as regular one or I should have separate one?
And reasons for that?

Thanks in advance!


The general idea behind using techniques like transposition-tables is
that it gives you a performance gain. It is a good excercise to simply
experiment with it, untill it gives the best performance.

Clock your execution, count the number of nodes visited. Let the program
run solitairily on your computer and do some test. Normally you should
use some test suites, in this way you might be able to compare your
results with others.

You can of course also think about it a little while and guess... This
is normally not a good idea.

Good luck!

--
/**
* J.R.Steenhuisen
* Korvezeestraat 329
* 2628 DP Delft Netherlands
* +31152627758 +31621828440
*
* Crafty mirror:
* Chess site:
http://darkside.its-s.tudelft.nl/
*/

  #3  
Old August 24th 03, 09:31 PM
Dieter Buerssner
external usenet poster
 
Posts: n/a
Default Hash Table and Quiescence Search

Jih-tung Pai wrote:

I wonder if there is conclusion or consensus on whether to store
quiescence search results in hash table.


I think, there is no definite conclusion. I think many engine authors tried
it both ways. I for example use HTs in qsearch. Crafty for example, does
not.

What are the advantages and
disadvantages?


They should be rather obvious. Advantages - you can cut the trees or get a
reasonable move for move-ordering (even in normal search). Disadvantages:
complicates your qsearch function and adds processing time.

If I choose to store the results, is it better to store
in the same hash table as regular one or I should have separate one?


I use the same HT.

Regards,
Dieter
  #4  
Old August 25th 03, 03:27 AM
Robert Hyatt
external usenet poster
 
Posts: n/a
Default Hash Table and Quiescence Search

Jih-tung Pai wrote:
I wonder if there is conclusion or consensus on whether to store
quiescence search results in hash table. What are the advantages and
disadvantages? If I choose to store the results, is it better to store
in the same hash table as regular one or I should have separate one?
And reasons for that?


Thanks in advance!


I have done it both ways. Not hashing in the q-search makes my trees
about 10% bigger, but the program is 10% faster so it is a "wash".

Hashing in the q-search has one important effect that I actually like to
miss, that of overloading the hash on long searches. This lets smaller
hash sizes work fine. As a result, I don't hash q-search at the present.

If you do checks and/or other non-capture moves in the q-search, this
might change, so you have to test carefully...



--
Robert Hyatt Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #5  
Old August 25th 03, 05:59 PM
Noah Roberts
external usenet poster
 
Posts: n/a
Default Hash Table and Quiescence Search


Thanks for all the replies. I forgot to ask what kind of behavior
differences one should expect between cleaning hash table after
calculating each move and not cleaning it. I would think not cleaning
it will save some time, but I also know Crafty clean it after every
move. Why?


My engine has a boolean value for "keep" in each hash entry. When an
attempt to save a position is made the first check is based on this
variable, if it is false then the write occurs no matter what. If true
then the write occurs if the search depth of the to-save position is
greater than what is already there. When a search is started the first
thing done before we enter root search is to "clear" the hash table
which is that I turn the "keep" variable off for all entries. What then
happens is that interesting positions that where evaluated in the last
search are still available but uninteresting ones get deleted as the
search progresses.

The above is a depth based ttable, there are many other methods.

If this is your first engine you will find citeseer very helpful:
http://citeseer.nj.nec.com/cs

Search for "Transposition table chess" and read "Replacement Schemes for
Transposition Tables" and "Information in Transposition Tables" by
Breuker et. al.

NR

 




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT +1. The time now is 06:21 PM.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.Content Relevant URLs by vBSEO 2.4.0
Copyright 2004-2017 ChessBanter.
The comments are property of their posters.