Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old April 22nd 04, 02:42 AM
Tommy
 
Posts: n/a
Default transposition tables and quiescence

Hello,

My program has a transposition table and quiescence search but I only
probe/store things from/to the transposition table when I am in the normal
alphabeta search and not when I am in the quiescence search. Is it possible
to use transposition tables also in the quiescence? how?

Thanks in advance,

Tommy

  #2   Report Post  
Old April 22nd 04, 07:34 AM
Alexander Belov
 
Posts: n/a
Default transposition tables and quiescence

I consider q-search as a part of evaluation. The result of the q-search
is a lower bound of the position evaluation which becomes equal
to the position evaluation when the PV exchange in q-search becomes
the best variation. So I use the result of q-search as 0 depth ab-search
for all q-search subtree, and for all 0 depth probes it returns correct
value - the same as q-search finds in re-search.

"Tommy" wrote in message
...
Hello,

My program has a transposition table and quiescence search but I only
probe/store things from/to the transposition table when I am in the normal
alphabeta search and not when I am in the quiescence search. Is it

possible
to use transposition tables also in the quiescence? how?

Thanks in advance,

Tommy



  #3   Report Post  
Old April 22nd 04, 10:50 AM
Tommy
 
Posts: n/a
Default transposition tables and quiescence


"Alexander Belov" wrote in message


I consider q-search as a part of evaluation. The result of the q-search
is a lower bound of the position evaluation which becomes equal
to the position evaluation when the PV exchange in q-search becomes
the best variation. So I use the result of q-search as 0 depth ab-search
for all q-search subtree, and for all 0 depth probes it returns correct
value - the same as q-search finds in re-search.


ok, so you store the results of the qsearch from the caller (ab search), you
do not store all the q-nodes in the q-search.

This is what I am doing. It is just that with mvv/lva, when there are many
pieces on the board the q-search goes too far and it is too slow. At the
beginning of the game, when it is at depth 6, for instance, the qsearch has
done an additional 18 levels for a total of 24 plies!!! and of course this
is not too fast! I just thought that i could use the tt not to re-calculate
things all the time. (I think I am correctly implementing the stading pat.)

Thanks,

Tommy

  #4   Report Post  
Old April 22nd 04, 01:40 PM
Mikko Nummelin
 
Posts: n/a
Default On slow quiescence search ( transposition tables)

On Thu, 22 Apr 2004, Tommy wrote:

pieces on the board the q-search goes too far and it is too slow. At
the beginning of the game, when it is at depth 6, for instance, the
qsearch has done an additional 18 levels for a total of 24 plies!!! and
of course this


Do you order the captures by MVV/LVA or SEE in quiescence search? Remember
also to break the quiescence search in case that static evaluation is
above beta! Failing to do the first one (correctly) causes search
explosion and failing to do the second one causes program to give
material.


Mikko Nummelin
  #5   Report Post  
Old April 22nd 04, 03:37 PM
Tommy
 
Posts: n/a
Default On slow quiescence search ( transposition tables)


"Mikko Nummelin" wrote

Do you order the captures by MVV/LVA or SEE in quiescence search?


I do MVV/LVA, i do not want to write something as complicated as SEE for
now. MVV/LVA is a bit better than without any sorting, i just thought it
would help even more ;-)

Remember also to break the quiescence search in
case that static evaluation is above beta!


yeah, the stand pat, right? yeah, I have that!

Failing to do the first one (correctly) causes search
explosion and failing to do the second one causes
program to give material.


yeah, my problem appers to be search explosion. But I have MVV/LVA.
I know SSE is better and someday I want to write that, but for now, MVV/LVA
should probably work better than this....

Thanks

Tommy






  #6   Report Post  
Old April 22nd 04, 07:31 PM
Tord Kallqvist Romstad
 
Posts: n/a
Default On slow quiescence search ( transposition tables)

Do you use futility pruning in the qsearch?

--
Tord Romstad

  #7   Report Post  
Old April 22nd 04, 10:49 PM
Tommy
 
Posts: n/a
Default On slow quiescence search ( transposition tables)


"Tord Kallqvist Romstad" wrote

Do you use futility pruning in the qsearch?


No. I tried, but, since I sue MVV/LVA it is difficult to decide which
captures to prune. For example capturing a pawn with a queen is really bad
in MVV/LVA terms, but if the pawn is undefended it is actually a good
capture. As a result, I was pruning "bad catpures" but those were not
actually bad and the quiescence was making mistakes. I guess with SEE is
easier (and makes more sense) to write futility pruning.....

Am I right?

Tommy

  #8   Report Post  
Old April 23rd 04, 06:58 AM
Tord Kallqvist Romstad
 
Posts: n/a
Default On slow quiescence search ( transposition tables)

"Tommy" writes:

"Tord Kallqvist Romstad" wrote

Do you use futility pruning in the qsearch?


No. I tried, but, since I sue MVV/LVA it is difficult to decide which
captures to prune. For example capturing a pawn with a queen is really bad
in MVV/LVA terms, but if the pawn is undefended it is actually a good
capture. As a result, I was pruning "bad catpures" but those were not
actually bad and the quiescence was making mistakes. I guess with SEE is
easier (and makes more sense) to write futility pruning.....

Am I right?


I am not sure, but it seems to me that you might have misunderstood
what is meant by futility pruning. This technique is entirely
unrelated to MVV/LVA or SEE move ordering.

The point is to prune all captures which are extremely unlikely to
bring the score above alpha:

if(static_eval + PieceValue[capture(move)] alpha-margin)
don't search this capture

For instance, if alpha is 0.0 and the static eval is -6.0, there is no
point in searching captures of a pawn or a minor piece.

--
Tord Romstad
  #9   Report Post  
Old April 23rd 04, 09:32 AM
Alexander Belov
 
Posts: n/a
Default transposition tables and quiescence

"Tommy" wrote in message
...

"Alexander Belov" wrote in message
I consider q-search as a part of evaluation. The result of the q-search
is a lower bound of the position evaluation which becomes equal
to the position evaluation when the PV exchange in q-search becomes
the best variation. So I use the result of q-search as 0 depth ab-search
for all q-search subtree, and for all 0 depth probes it returns correct
value - the same as q-search finds in re-search.


ok, so you store the results of the qsearch from the caller (ab search),

you
do not store all the q-nodes in the q-search.

This is what I am doing. It is just that with mvv/lva, when there are many
pieces on the board the q-search goes too far and it is too slow. At the
beginning of the game, when it is at depth 6, for instance, the qsearch

has
done an additional 18 levels for a total of 24 plies!!! and of course this
is not too fast! I just thought that i could use the tt not to

re-calculate
things all the time. (I think I am correctly implementing the stading

pat.)

Thanks,

Tommy

Not at all. I store q-search results for all q-search plies - they are
considered as 0 depth search of evaluation even if they are results
of n ply q-search.
As I understand stand-pat score - it is the score of any valid non-capture
move from the scored position, while q-search is the score of
valid capture move and it is searched for valid capture moves from the
position. The implication from this - I don't use stand-pat score for
position which doesn't have valid non-capture moves from it.


  #10   Report Post  
Old April 23rd 04, 11:18 AM
Tommy
 
Posts: n/a
Default On slow quiescence search ( transposition tables)


"Tord Kallqvist Romstad" wrote

I am not sure, but it seems to me that you might have misunderstood
what is meant by futility pruning. This technique is entirely
unrelated to MVV/LVA or SEE move ordering.

The point is to prune all captures which are extremely unlikely to
bring the score above alpha:

if(static_eval + PieceValue[capture(move)] alpha-margin)
don't search this capture

For instance, if alpha is 0.0 and the static eval is -6.0, there is no
point in searching captures of a pawn or a minor piece.


Ok, I understand now.
The formula I have is slightly different, it has material_gain instead of
value_of_the_piece!

if(mat_balance(node) + mat_gain(move) + futility_margin = alpha(node))
don't search this capture

Of course without SEE it is difficult to know the real material gain; but
you are right, using the piece value it is possible to have a less precise
form of futility pruning. I will have a go, thanks

Tommy

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hash Table and Quiescence Search Jih-tung Pai rec.games.chess.computer (Computer Chess) 4 August 25th 03 04:59 PM
Search extensions and transposition tables Delphi rec.games.chess.computer (Computer Chess) 2 August 21st 03 10:10 PM


All times are GMT +1. The time now is 08:53 AM.

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