Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

AndyTang

Iterative Deepinging

This topic is 5732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I cant seem to get my head around Iterative Deepening - it doesnt seem to make sense and the algorithm I tried dont seem to make any improvement, infact it slowed it down! I know you run though alpha beta once with a depth of 2, resort the moves list, and run though it again at a depth of 3. But in this case you are running the algorithm twice with a depth of 2 the first time and a depth of 3 the next. The only time where I would see an improvemnt if there was a cut off, but the algorithm runs through the enitire move list twice (or more depending on the depth). What am I doing wrong?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
http://www.gamedev.net/community/forums/topic.asp?topic_id=122112

Share this post


Link to post
Share on other sites
First: Do you keep track of a principal variation, and use this to re-sort your moves? If you don''t then you''ll definately not get any kind of speed improvement. (A hash table will work in place of a Principal Variation)

I''ve run in to the same issues... The fact is that most of the literature regarding it is misleading. The search is technically ''faster''. It works like this: Doing a search to ply 7 may take 10 seconds. Using Iterative Deepening, it might only take 8 seconds. The catch is that you''ve spent 3 seconds searching depth 3,4,5, and 6. See what I mean?

The other reason why it''s not really going to give you a speed boost all the time is because the best move at ply 5 might not be the best move at ply 6.. This means that you wont get any advantage out of your sort.

Cheers
Will


Share this post


Link to post
Share on other sites
Thanks for all your help. It was as you said, without pricniple variation or hash table, there isnt any improvement, nothing to help the cutoff rate.

Share this post


Link to post
Share on other sites
I thought of something else this morning, that I should have added yesterday.

If you do some form of quite-move evaluation, you''ll increase your odds of returning the same PV from ply to ply.
The catch is that this will slow the general full-width search down.

I''ll give you an example. Game searches to ply 6. Move 6 has four capture possiblities. The computer will always choose one of these, because it doesn''t search to ply 7 to determine the consequences. Searching Ply 7 will reveal the consequences and the PV could change as a result. If the game only ''scored'' quite positions, it would not matter, because it would have resolved these captures.

Thats about it.. I really suggest adding Hash tables to your program. I''ve found that you get a big speed improvement by using it to reorder moves-- more so than you do from move transposition. Then again, I have problems with move transposition in my code, so....

Good luck with your program,
Will

Share this post


Link to post
Share on other sites
quote:
Original post by RPGeezus
Thats about it.. I really suggest adding Hash tables to your program. I''ve found that you get a big speed improvement by using it to reorder moves-- more so than you do from move transposition. Then again, I have problems with move transposition in my code, so....



Thanks for that. I just added a hash table and implemented a transposition table (with iterative deeping) which speeded by search a lot.

I also heard that using hash tables to reorder move - how is that done cause I dont really get it. How can hash tables help determine move order?

Share this post


Link to post
Share on other sites
Wow, you''re fast.

A word of warning: If your using AlphaBeta and Hash tables, you must be very careful not to allow your hash values to cause a cutoff. Do a search for Transposition AlphaBeta.

When you call AlphaBeta, it returns an upper or lower bound, not an exact score (well, sometimes an exacty score). You program will make stupid mistakes as the game progresses if you don''t be very careful with this.

So to reorder using the hash table.

When you come in to AlphaBeta, and generate a list of all available moves, go through each move and check to see if it''s in the hash table. Unlike move transposition, you''re not concerned with the depth to which the move was searched, only the score. If you''re in a max node, move moves which have higher scores in the hash table to the front of the move list. If your in a Min node, move moves which have a lower score to the front of this list. In this way, more ''promissing'' moves get searched first.

This way, you doing something very similar to Principal Variation, except you get to do it on way more moves.

Let me know how it turns out,
Will

Share this post


Link to post
Share on other sites
Thanks for your reply.

I think I am doing something wrong. My transposition table stores a hash version of the actual board at a certain position.

Now, implementing move ordering, the following steps:
- go into an alpha beta
- search transposition table for the current position (return score if found and the depth>=depth stored).
- generate moves
- for each move:
--- make move
--- check table for score, move move in the list (using method you have provided)
--- undo move
- do alphabeta

Is this right? that seems like a lot of work.

Share this post


Link to post
Share on other sites
Your hash table sounds fine, except you may need to store the TYPE of score that was returned (was it an upper bound, lower bound, or an exact value). You get upper and lower bounds when there is an alpha/beta cutoff. These scores are not exact, and can cause big trouble for your algorithm. A Max node returns a lower bound (lowest possible score) and a Min node returns an upper bound (highest possible score). (I think.. My transposition is broken right now)

What you described sounds right to me.. It is a lot of extra work, but the pay off is huge. I''ve gained about a 30% increase in speed as a result. Ohh yeah, now I remember what I had to add to make it all work right.

You''ll want to do one other thing that I forgot to mention: Hash table managment.

Instead of just adding things to your hash table willy-nilly, you only overwrite a hash value if: It''s stale (hasn''t been accessed so far during this search), OR the new hash entry will describe a deeper search.

You get this working by adding a ''stale'' flag to each entry in your hash table. Before you start each search, loop through the hash table and set the stale flag to TRUE for every entry. As you go through AlphaBeta, whenever you write a hash value, set the stale flag for that entry to FALSE.

Ohh yeah, whenever you use a hash value, you set the flag to FALSE. You do this because some values done in Iterative Deeping are good from ply to ply, AND if you let your program think on the opponents time you will be able to use any hash data gleaned from that search.

So really what you do is tell your game not to overwrite hash values that it''s written earlier on in the search. This made a big big difference (combined with the other stuff) in my engine. A 30 second search becomes a 20 second search.

Let me know if this all works out for you.

Will

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!