Jump to content
  • Advertisement
Sign in to follow this  
kluster

gomoku help!

This topic is 3810 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

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!

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!