Life In 19x19

daniel_the_smith wrote:I thought about doing local fights via MCTS, but I just don't think I'll be able to get enough playouts for it to be useful. So far my only real accomplishment is an algorithm to split up the board into local fights in < 1ms. :/

AVAVT, you can modify A* to start from multiple sources. Depending on what you need to accomplish, you can also do multiple dests if you drop the heuristic (i.e., switch back to Dijkstra).

Lurking on their IRC channel is a good way to pick up strategy tips.

There is some good info on A* here: http://theory.stanford.edu/~amitp/GameP ... stics.html

-- each turn
foodList = get all visible food;
for each ant{
   A* search from all food in foodList to the ant;
   if foodList not empty && a short enough path (10 steps away) is found{
      order the ant toward nearest food according to A*;
      remove the food from foodList; 
   }
   else if enemy hill found{
      order the ant toward the first hill
   }
   else{
      order the ant to explore map
   }
}

AVAVT wrote:

Code: Select all

-- each turn
foodList = get all visible food;
for each ant{
   A* search from all food in foodList to the ant;

daniel_the_smith wrote:I thought about doing local fights via MCTS, but I just don't think I'll be able to get enough playouts for it to be useful. So far my only real accomplishment is an algorithm to split up the board into local fights in < 1ms. :/

lorill wrote:I replaced my attack/retreat mechanism by a simple montecarlo simulation, the number of playouts depends on the time available and the number of local fights. I can do 60 playouts by millisecond on a slow computer. I don't use MCTS, since I look for only one move deep. We don't need to finish the game to score it as in go.

daniel_the_smith wrote:So basically, you try a bunch of random moves, score the position, and repeat? Hm. How does it do in mass battles?

lorill wrote:

daniel_the_smith wrote:So basically, you try a bunch of random moves, score the position, and repeat? Hm. How does it do in mass battles?

Yup, I do exactly this for all directions. This is the first game played with this version :
http://ants.fluxid.pl/replay.18826

Too bad I didn't manage to explore better to enter berserk-mode

daniel_the_smith wrote:Not bad at all. But it doesn't seem quite as good as whatever Xathis is doing... :/