Dynamic Programming

[dmj]

Hi,

Here is an idea I did not try, but maybe someone else did. (let me know if this is what some of you have meant by the tree of chambers idea...)

If you and the opponent are separated by one or more articulation points, use dynamic programming to determine if the position is a win, and whether it is better to fill the space you are in, or run to cut off the other bot at a cut point. Alpha-beta / voronoi will find this if the moves are close enough, but maybe this idea could extend the look-ahead of these algorithms.

This might only help some of the weak spots in my evaluation function, and I ran out of time (and energy), so it did not happen.

Thanks,
Dave

[analyst74]

Finding Articulation Point and choose which chamber to fill will definitely improve the performance.
It reduces the chance your bot is end up in a smaller chamber; while based on voronoi your bot will mistakenly think it is at advantage and actively move into such (losing) situation.

I implemented a basic articulation point search from wikipedia () after reading the discussion on the forum. But due to time constraint the implementation was very rough, while it avoided some silly mistakes, it introduced some others..

[Fritzlein]

[a1k0n]

What you suggest is very similar to what mine does. I find all the articulation vertices *assuming squares in the opponent's voronoi region are unconnected* and then walk the tree of chambers: if a chamber contains a "battlefront", then count up the number of squares required to get onto the articulation vertex leading to the chamber (I had Dijkstra's precomputed for each player) and count up the squares within the chamber that are part of the player's territory, and optionally any chambers connected from there. The "value" is the largest of the count just described or the chamber (and sub-chambers) the player is currently in, because the player can choose to cut off either one.

But if it chooses to cut off the battlefront chamber, then it should award its territory in there to its opponent. I was going to count that territory negatively but I never got around to it. This idea was very roughly-formed when I implemented it Thursday night at 3am and it didn't work at all until I fixed it the next morning.

It's a very rough approximation and there certainly exist counterexamples (a cyclic graph of chambers for instance) but as long as you're not on a pathological map it's not worth worrying about too much. I'm sure there are better options though.

[Fritzlein]

[DjinnKahn]

[dmj]

[dmj]

[analyst74]