Question:
I need to implement ACO in tic-tac-toc game playing. The problem is when i studied the algorithm that was on static graph called TSP problem. But in T-T-T there will be dynamic graph or tree.
My Answer:
You can always apply Ant Colony Optimization(ACO) on any search graph. Actually basic fundamental behind this concept is the Ant's foraging nature. Path from nest to food is never a static search graph. When Ant starts searching for food from its nest, it even don't know where the food is?
I have applied ACO on routing in Mobile Adhoc Network(MANETs). MANETs by nature are dynamic so its search graph is always dynamic.
For solving this problem, you need to know best heuristic for solving Tic-Tac-Toe. Once that is known to you, I can really help you out in solving your problem.
One heuristic for Tic-Tac-Toe game is the position. If you are at the centre position then you have highest chances to win(Say 3 points). Then if you are at corner position then you have lesser chances to win(Say 2 points). If you are at any other postion then you have even lesser chances to win(Say 1 point). So a heuristic you can apply is, try to go for the postion which does not make you loose as well as gives highest points. As you have at max 4 corner postions so in that case your selection of any of the available corner postion should be driven by Pheromone. I mean the postion which has highest pheromone value should be considered. So this is the postion which is good as per heurustic values and better as per prior experience(having higher pheromone intensity). I guess Tic-Tac-Toe is solved using ACO. Isn't it???
You can always apply other better Heurisitics. Also you can try to apply different weightage on Heuristics and Pheromone by changing values of Alpha and Beta.
Hope you will be in a postion to start your implementation. You are very welcome to ask your doubts here, if any.
I need to implement ACO in tic-tac-toc game playing. The problem is when i studied the algorithm that was on static graph called TSP problem. But in T-T-T there will be dynamic graph or tree.
My Answer:
You can always apply Ant Colony Optimization(ACO) on any search graph. Actually basic fundamental behind this concept is the Ant's foraging nature. Path from nest to food is never a static search graph. When Ant starts searching for food from its nest, it even don't know where the food is?
I have applied ACO on routing in Mobile Adhoc Network(MANETs). MANETs by nature are dynamic so its search graph is always dynamic.
For solving this problem, you need to know best heuristic for solving Tic-Tac-Toe. Once that is known to you, I can really help you out in solving your problem.
One heuristic for Tic-Tac-Toe game is the position. If you are at the centre position then you have highest chances to win(Say 3 points). Then if you are at corner position then you have lesser chances to win(Say 2 points). If you are at any other postion then you have even lesser chances to win(Say 1 point). So a heuristic you can apply is, try to go for the postion which does not make you loose as well as gives highest points. As you have at max 4 corner postions so in that case your selection of any of the available corner postion should be driven by Pheromone. I mean the postion which has highest pheromone value should be considered. So this is the postion which is good as per heurustic values and better as per prior experience(having higher pheromone intensity). I guess Tic-Tac-Toe is solved using ACO. Isn't it???
You can always apply other better Heurisitics. Also you can try to apply different weightage on Heuristics and Pheromone by changing values of Alpha and Beta.
Hope you will be in a postion to start your implementation. You are very welcome to ask your doubts here, if any.
