Hi! I have implemented a gomoku-AI in C++ (great fun!!) I can easily search to level 7 on 15x15 tables. But at this level, I have a problem with my implementation. I think the AI gives up when it thinks it is loosing. If AI is RING/MIN. at the first level(result from all recursion), all child-moves returns the value INT_MAX, i.e, the winning score for me, and then the AI just chooses the first move. The first move which is a bad one, and not a move that could save the AI from loosing if I make a bad move after that. What could be wrong here? I understand it is hard for you to help me without seeing any code, but perhaps its a common problem and someone could recognice it. This problem only arises when I'm winning. I would like my AI to at least try to block me from winning, right!? Thanks for any help!

Is is a common problem. One technique that makes it a lot less noticeable is iterative deepening. You first do a search at depth 1, then 2, then 3... until you run out of time. Whenever you find a move that looks the best so far, move it to the top of the list. This way even if a particular search determines that all moves lose, the first move will be the move that took the deepest search to prove that it was losing.

Iterative deepening also allows you to control time better, and if you are using alpha-beta with transposition tables (which you should), will help order the moves in the search correctly and your search will also take less time than it would have if you just search depth 7 from the start.

I hope that helps.

Quote: Original post by alvaro
Is is a common problem. One technique that makes it a lot less noticeable is iterative deepening. You first do a search at depth 1, then 2, then 3... until you run out of time. Whenever you find a move that looks the best so far, move it to the top of the list. This way even if a particular search determines that all moves lose, the first move will be the move that took the deepest search to prove that it was losing.

Iterative deepening also allows you to control time better, and if you are using alpha-beta with transposition tables (which you should), will help order the moves in the search correctly and your search will also take less time than it would have if you just search depth 7 from the start.

I hope that helps.

Thanks for the answer!

Sounds lika a nice idea to implement iterative deepening, but I guess it will
be alot slower? calculete level 6 and and then restart to calc down to level 7 etc? I have never implemented a hashtable before, and how about the hashkeys? is there a fast way of generating unique keys?
btw, how deep can a good gomoku AI search?
Alot of questions, sorry :)

Iterative deepening isn't that much slower than the common fixed-depth search, at least not as much as one would expect. Its great advantage is that you'll have a good move ready all the time and you'll be just searching for a better one, so if you are for example obliged to return the AI's move in 5 seconds, you're sure to have a good move ready in that time. When searching to a fixed depth, you may possibly not evaluate any good move altogether in the time limit.

As about implementing a hash table and unique hash keys, see a series of AI articles here on GameDev by F. D. Laramée:
http://www.gamedev.net/reference/list.asp?categoryid=18

Quote: Original post by Chjooodge
Iterative deepening isn't that much slower than the common fixed-depth search, at least not as much as one would expect. Its great advantage is that you'll have a good move ready all the time and you'll be just searching for a better one, so if you are for example obliged to return the AI's move in 5 seconds, you're sure to have a good move ready in that time. When searching to a fixed depth, you may possibly not evaluate any good move altogether in the time limit.

As about implementing a hash table and unique hash keys, see a series of AI articles here on GameDev by F. D. Laramée:
http://www.gamedev.net/reference/list.asp?categoryid=18

Thanks for link, looks like a good archive.
Anyway, I implemented iterative deepening and it works great. If the AI
returns INT_MAX and AI is MIN, I swap to the last move and break the iteration.

How about a good evalutation function for gomoku? I have done some test my self, but is there any good standard evaluation algorithm that works great?