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

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

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

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