[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Dynamic Programming

It is currently Sat Apr 29, 2017 1:18 pm Advanced search

Dynamic Programming

Share and discuss ideas for your entries here.

Dynamic Programming

Postby dmj » Tue Mar 02, 2010 2:22 am

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
dmj
Lieutenant-Colonel
 
Posts: 41
Joined: Thu Feb 11, 2010 11:36 am

Re: Dynamic Programming

Postby analyst74 » Tue Mar 02, 2010 3:46 am

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.. :(
analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm

Re: Dynamic Programming

Postby Fritzlein » Tue Mar 02, 2010 5:29 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Dynamic Programming

Postby a1k0n » Tue Mar 02, 2010 8:50 pm

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.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Dynamic Programming

Postby Fritzlein » Tue Mar 02, 2010 9:44 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Dynamic Programming

Postby DjinnKahn » Tue Mar 02, 2010 10:38 pm

DjinnKahn
Lieutenant
 
Posts: 18
Joined: Wed Feb 17, 2010 11:32 pm

Re: Dynamic Programming

Postby dmj » Wed Mar 03, 2010 2:09 am

dmj
Lieutenant-Colonel
 
Posts: 41
Joined: Thu Feb 11, 2010 11:36 am

Re: Dynamic Programming

Postby dmj » Wed Mar 03, 2010 2:18 am

dmj
Lieutenant-Colonel
 
Posts: 41
Joined: Thu Feb 11, 2010 11:36 am

Re: Dynamic Programming

Postby analyst74 » Wed Mar 03, 2010 3:27 am

analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm


Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron