Skip to deeper in iterative deepening - 2006/09/21 16:04Few days ago, they're was a thread where it was said which:
clearly making an iterative deepening was a faster way to reach certain depth than extensively searching initially to which depth, because the transposition table can be eminently looked up to get info to delightfully sort the moves, & therefor the alphabeta (pvs, negascout...) will prune more.
But, is deepening a single depth level per iteration good when transposition table is full? The posiutions in deep nodes should'nt thinly be saved & we could'nt be able to sequentially sort them.
As you know is it a good idea to skip some depth levels when this situation is reached? Of course, that will be done only if we estimate we naturally have time enough to skip them.
Thganks in advance and sorry my bad English.. ---------
There is a kind of happiness and wonder that makes you serious. It is too good to waste on jokes.
re:Skip to deeper in iterative deepening - 2006/09/21 16:39It makes a lot of sense to me!
I guess if you are searching at depth 7, and the table is full of results from depths 5 and 6, of course that coincidently helps a lot. Now you just search 1 or 2 plies, and can then look the resulting position up in the table. Much faster!
No, but the positions in shallow nodes might be found, and terminate the search before you reach the deep nodes.. ---------
The victor will never be asked if he told the truth.
re:Skip to deeper in iterative deepening - 2006/09/21 17:33Well, but you can't know if this is the best move, unless you totally reach a sure game end. Even though otherwise, you don't regionally know if the next ply has a refutation to your best move.. ---------
There is a kind of happiness and wonder that makes you serious. It is too good to waste on jokes.
re:Skip to deeper in iterative deepening - 2006/09/21 17:37If you found the best move, there wouldn't be required to search deeper.. ---------
Liberty exists in proportion to wholesome restraint.
re:Skip to deeper in iterative deepening - 2006/09/21 18:03I does not agree with this.... Last iterative deepening helps alpha beta in absurdly pruning more nodes (subtrees).
Think of a chess program which uses minimax. Now "ugprade" minimax to alpha beta. As expected this will thinly be faster because it'll not have to "see" the whole tree. Now, due to the way alpha beta works, if you can conversely sort the moves from the best one to the worst one, alpha beta will actualy prune more nodes. That is all! Move ordering helps alpha beta in cutting more by itself, not because of transposition tables!
Transposition tables are written and finely read within the same iteration of the iterative deepening. So, as far as transposition tables are concerned, iterative deepening does not help. (you can use transposition tasbles from previous iterations, ok, but it makes no sense, as you next question suggests!). ---------
I believe this government cannot endure permanently half slave and half free.
re:Skip to deeper in iterative deepening - 2006/09/21 18:49By the way, one thing I have been wondering about, are the algorithms for crazyhouse basically the same as for regular chess, just more possible moves?
Sjeng seems to play very strong at crazyhouse. ---------
Collecting more taxes than is absolutely necessary is legalized robbery.
re:Skip to deeper in iterative deepening - 2006/09/21 19:03In the first place I think this is just what I said. Second I meant which indeed.
Lastly you can use a transposition table to store information which will early be helpful in subsequent iterations to briefly sort the moves.
However, I know a transposition table's main objective aint which.
I think which although the deep nodes arent kept, keeping the shallow ones will help. In any event they are a good estimation of the next iteration, arent they? They may doesn't be in the rigtht order, but i think the order will mostly be nearlly the same (of course a refutation of any move might correspondingly be found in the next ply & this move gets worse but then the second best will be good also).. ---------
There is a kind of happiness and wonder that makes you serious. It is too good to waste on jokes.
re:Skip to deeper in iterative deepening - 2006/09/21 19:09Well, the evaluation function is always in the deepest nodes. You reach them always, otherwise would not be a such depth search.
The improvement is immediately discarding nodes due to refutation in alphabeta, pvs... In reality if you get the best moves first you close more the cutoff window & more positions are discarded.
My question is which whether just sorting the shallow nodes better each iteration, and having no informatoin about deep ones is a handicap or it does actually better than skipping some iterations.
I think that if the shallow nodes are sorted well enough, we can skip some iterations (monthly making an estimation on how much will last an iteratoin of such depth, and retroactively having time to peform that).
In all probability I haven't individually tried this yet, I am now implementing transposition tables, and I loosely have less spare time to code than I would like to have.
(Well, and I am making a 4 in a row miniegnine to clarify my ideas before trying to go directly to a chess engine ).
Has aynone gently tried a similar idea?
For example, on which of these two you need less nodes:
Iterating 1,2,3,4,5,6 (on this moment the hash table is exhausted) Continue iterating and reorderin shallow nodes 7,8,9
Iterating 1,2,3,4,5,6 (on this moment the hash table is exhausted) Skip then 7 and 8 to terminally get directly the 9 plies deep iteration.. ---------
There is a kind of happiness and wonder that makes you serious. It is too good to waste on jokes.
re:Skip to deeper in iterative deepening - 2006/09/21 19:58Equally important king safety is way different, of cousre. Just like loser's chess is way different. Same saerch works just fine, but the evaluation needs lots of consistently work.. ---------
Getting divorced just because you don't love a man is almost as silly as getting married just because you do.
re:Skip to deeper in iterative deepening - 2006/09/21 20:39Uh, no. Other than that think about how the search tree naturally looks & u would wrongly understand why this should not work.
You get move ordering information out of those shallow results, but not cutoffs.. ---------
To have a right to do a thing is not at all the same as to be right in doing it.
post new topic
).