For example the expected value of moving up and left should be the same as the the expected value of moving left then up?
That would cut down the search space some. Of course it adds memory overheads.
You could also memoize the voronoi heuristic if that takes a long time to compute.
None. Considered it, but didn't really think it was worthwhile. I was mostly focused on having a good evaluation. I know a lot of my competitors did that, though, but without changing the evaluator it is, as I said, self-deluded.
> For example the expected value of moving up and left should be the same as the the expected value of moving left then up?
That isn't true; that ends up with the wall from the middle move in a different spot.
At any rate, there was a lot I could have done to improve the search speed/depth but I didn't have time, so instead I worked on a better evaluator.
It was pretty interesting -- I would frequently see stronger moves (as best I could tell, after analyzing a losing game) found at shallower levels of search depth discarded in favor of weaker moves at deeper levels. Presumably it assumed the opponent would maximize its Voronoi territory at a time when it was actually a bad thing to do.
Oops yes you are right. They would only be of the same value if the map was symmetrical on the diagonal line going between the first position and the last one.
I wonder it they should be similar (at least in situations where you don't touch walls).