Combat strategy: Bee algorithms and alpha-beta pruning.

[mac]

Has anybody implemented anything like the bee algorithms and the alpha-beta pruning described in this SO question?

Care to share your experience or comment on their appropriateness?

[BenJackson]

Has anybody implemented anything like the bee algorithms and the alpha-beta pruning described in this SO question?

Care to share your experience or comment on their appropriateness?

Seems roughly equivalent do doing multiple simultaneous runs of simulated annealing while weighting the computation allotted to each anneal by how well it is doing so far. So I suspect it would produce similar outcomes to simulated annealing. The advantages would be that the multiple initial solutions might converge to different solutions so you could avoid the problem of a single anneal hitting a local maximum. The disadvantage is that it's proportionally more resource intensive (more saved states) and slower (if we presume operating a single anneal is faster than the same number of operations flipping between data sets). Also the single anneal can see "deeper" but that really just means it has "more attention to detail". For a given problem there's usually a sufficient bound for that anyway.

If you want to look at simulated annealing you can check out my bot. anneal.h is a template functor that does one annealing run. combat.cc and territory.cc both use it on local data structures to optimize some goals. Combat::neighbor() selects a neighbor (as in the algorithm description) which is just one move of one of my ants. Then the score is updated and if the anneal doesn't keep it undo() puts it back.

[mac]

If you want to look at simulated annealing you can check out my bot. anneal.h is a template functor that does one annealing run. combat.cc and territory.cc both use it on local data structures to optimize some goals. Combat::neighbor() selects a neighbor (as in the algorithm description) which is just one move of one of my ants. Then the score is updated and if the anneal doesn't keep it undo() puts it back.

Thank you Ben for your answer. I will definitively look at your code (although it might take me a couple of weeks before I can dedicate myself to ai-challenge related issues again). What's the URI of your repo?

[mac]

Just for reference: it seems that the contest winner used a very similar approach!