Hello, I've got some performance problems with Iterative Deepening and my Alpha Beta Search for my connect4 game. I made tests with a game board starting with 6 stones on it. If I'm searching with Iterative Deepening from depth 7 to 42 (max depth) with step 1 my search takes 1:20 minutes and 106.000.000 nodes were searched. If I do a search without Iterative Deepening to the max depth (42), my heuristic evaluation won't be used and I'll only use normal evaluation (win, draw, loss) it takes about 30 seconds and 52.000.000 nodes are searched. If I first search to depth 25 and then to max depth (42) it takes about 13 seconds!! and only 19.000.000 nodes were searched. Some more information about my game: I'm using MTD(f) with the same start value for all three tests. My transposition table had 15999961 entries where 2 positions can be stored per entry. I'm replacing the first position in the entry if any position was searched to a deeper depth or it is the same position, otherwise I'm replacing the second position. I'm ordering moves statically or I'm searching the best move first if there's any in the TT. My question: Why is the Iterative Deepening with step 1 so slow and is searching so much? I couldn't find any explanation... I think especially in the deeper search it takes very long in addition to the last test with depth 25 and then 42. Could it be that the best moves in my TT are overwritten in the deeper searches if important moves were in the second position of an entry? Could I design the Hash Table better that that does not happen? Another explanation I don't have... any other ideas? Thanks so far.

My best guess is that perhaps your evaluation function is poor and the results of one search don't help you much with searching the same position a little deeper.

Better hash tables might also help the situation. For instance, you can play with other replacement schemes. I usually get good results allowing any of 4 consecutive entries to hold a position (I override the one with the lowest depth). It's also important to store the best move (or the one that caused a beta cut) so you can try that move first when you revisit the node; I don't know if you are already doing that.

Quote: Original post by alvaro
My best guess is that perhaps your evaluation function is poor and the results of one search don't help you much with searching the same position a little deeper.

Better hash tables might also help the situation. For instance, you can play with other replacement schemes. I usually get good results allowing any of 4 consecutive entries to hold a position (I override the one with the lowest depth). It's also important to store the best move (or the one that caused a beta cut) so you can try that move first when you revisit the node; I don't know if you are already doing that.

Yes, it could be that my evaluation function is not so good. I think it is similar that you described here: http://www.gamedev.net/community/forums/topic.asp?topic_id=225611
I'm collecting all threats of 3 stones which can be completed and I'm looking for which threat could be a win for one player. So, I can only evaluate if there are threats with could lead to a win. Otherwise I'll return draw. Because of the threats my evaluate function works often in deeper depths. But your version is also looking for threats, so I think that won't make much difference. I don't know how I should improve my evaluation function...

What do you mean with 4 consecutive entries to hold a position? 4 positions in one hash entry?

Yes, I'm storing the best move in the TT and I'm searching it first.

Quote: Original post by flush
What do you mean with 4 consecutive entries to hold a position? 4 positions in one hash entry?

Not exactly, although the results are probably similar. I store a single position in each hash entry, but when I store a position I may store it in its normal entry hash, or in hash[i+1], or in hash[i+2], or in hash[i+3]. If all 4 entries contain searches with depth higher than the current depth, I don't store the result anywhere (I don't think I did much testing to support that decision). When I look for the position in the hash, I simply look in all 4 places before deciding that it's not there.

Quote: Original post by alvaro

Quote: Original post by flush
What do you mean with 4 consecutive entries to hold a position? 4 positions in one hash entry?

Not exactly, although the results are probably similar. I store a single position in each hash entry, but when I store a position I may store it in its normal entry hash, or in hash[i+1], or in hash[i+2], or in hash[i+3]. If all 4 entries contain searches with depth higher than the current depth, I don't store the result anywhere (I don't think I did much testing to support that decision). When I look for the position in the hash, I simply look in all 4 places before deciding that it's not there.

ok, I know what you mean. I tried it and some other variants, but I didn't get any good improvement. So I think I'll get better results if I work on my evaluation function. I'll try your version, perhaps it will perform better.