[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/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 - How did you handle quadrant?

It is currently Mon Oct 22, 2018 1:15 pm Advanced search

How did you handle quadrant?

Share and discuss ideas for your entries here.

How did you handle quadrant?

Postby EdwardTonai » Sat Feb 27, 2010 3:52 am

Handling the quadrant map was something that I never got around to. My AI (Beatrix) was too aggressive, usually being the first to charge into another chamber. I could easily beat it (in human vs AI mode) by just simulating a fill (favoring spaces away from Beatrix) until Beatrix chose a chamber.

An example:

Granted, this was against the mighty a1k0n_, but I've seen similar results against weaker opponents!

What was your algorithm to detect the class of boards similar to quadrant, and what was your AI's strategy in that case?
(I'm mostly looking for algorithms, but I know people are interested in seeing code)

Ed
EdwardTonai
Lieutenant
 
Posts: 10
Joined: Wed Feb 17, 2010 8:04 pm

Re: How did you handle quadrant?

Postby antimatroid » Sat Feb 27, 2010 4:05 am

Our evaluation function for our minimax algorithm seemed to handle the correct strategy on this map, even when we extended it to a 51x51 sized board (although it seems we wasted out time ensuring it was just as fast on larger maps, they aren't going above 15x15 in the competition). The only times I've found we lose anymore is if we can separate with more squares available than them but then aren't capable of filling as many as our opponent. Although some other problems may become apparent in the actual tournament once we see some more pairing amongst the top players.

If we'd have known earlier how small the maps were going to be we would probably run through and check which player can fill the most upon separation and do the evaluation based on that rather than raw number of squares available.
antimatroid
Brigadier-General
 
Posts: 126
Joined: Tue Feb 16, 2010 7:41 am

Re: How did you handle quadrant?

Postby iouri_ » Sat Feb 27, 2010 2:21 pm

I found that minimax together with evaluation function that would split the reachable area into a tree of chambers and then find the sequence of chambers with highest number of squares (detailed here viewtopic.php?f=8&t=319#p1536) would naturally play correctly on Quadrant when the possible moves were explored a few steps deep. After implementing this, I do not recall losing on that map (after I weeded out all the bugs).
iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: How did you handle quadrant?

Postby a1k0n » Sat Feb 27, 2010 2:32 pm

Yeah, I did pretty much the same thing as iouri.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: How did you handle quadrant?

Postby ademar » Sat Feb 27, 2010 8:26 pm

Hi! First let me say that I had a lot of fun programming this bot and having the opportunity of competing with you guys have been great.

Quadrant is a very interesting map.

There is no winning strategy in this game. Is easy to construct maps illustrating this. I suspect quadrant might fall in this case.
Ultimately you will come across a move where you would need to gamble.

My algorithm is an iterative deepening of alpha-beta pruning, where on each iteration I cache the moves in an ordered list.
This gets me 6 ~ 8 plies (one move each) on average, sometimes deeper.

The evaluation function uses the difference of the amount of squares on each player's Voronoi domain. To differentiate from draws (score 0)
the case where domain counts are equal I assigned a negative number between -1 .. 0, not including -1 and 0.
Now here is where I do my gambling in a double sense, my latest submission returns here a random value, ie -0.5*Rnd.NextDouble().

I'm not sure this approach is correct, but while fighting different versions of my bot against each other I found that this one performed better on average, in particular on the quadrant map. Returning a randomized value seems to add some spice to the search tree. It also have the nice effect the bot is not determinist.
ademar
Lieutenant
 
Posts: 12
Joined: Sat Feb 27, 2010 7:38 pm

Re: How did you handle quadrant?

Postby analyst74 » Sat Feb 27, 2010 8:56 pm

I originally used Voronoi and my bot performed poorly in Quadrant or similar ones, because the bot cannot tell that stepping into a choke-point will cause problems. When it gets close enough to the choke-point though, once the consequence of stepping into it is within reachable search depth, it will turn around. And in the process, causing spots within the starting zone to become dead end and eventually force my bot to choose to enter next zone.

I changed the heuristic scoring to take chambers into account (not tree of chambers, unfortunately), and it performed better, but still cannot beat my first version of "survival-only" bot. :(
analyst74
Major
 
Posts: 39
Joined: Wed Feb 17, 2010 7:45 pm

Re: How did you handle quadrant?

Postby dutchflyboy » Sat Feb 27, 2010 11:58 pm

Honestly, I didn't think about it while writing code, my minimax function did it for me (that's AI!). It always started filling it's own square and as soon as the enemy crossed a junction point, it closed it off and continued filling (of course this didn't always happen, but it mostly went that way). My evaluation function simply took the difference in territory size and added an advantage to nearing the enemy. So it seems that the space argument outweighted the distance argument.
dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: How did you handle quadrant?

Postby analyst74 » Sun Feb 28, 2010 12:27 am

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

Re: How did you handle quadrant?

Postby dutchflyboy » Sun Feb 28, 2010 12:38 am

On my computer, my iterative deepening reached about 7 plies (1 move each) before cutting off. And for the space count, it's simply a function that counts all accessible fields that aren't dead ends, +1 if there was a dead end (as only one dead end can be filled).
dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am


Return to Strategy

Who is online

Users browsing this forum: No registered users and 0 guests

cron