[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/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 - Hoping for lots of discussion after Friday

It is currently Wed Aug 23, 2017 5:35 pm Advanced search

Hoping for lots of discussion after Friday

Share and discuss ideas for your entries here.

Re: Hoping for lots of discussion after Friday

Postby Maxime81 » Sun Feb 28, 2010 9:20 am

Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Hoping for lots of discussion after Friday

Postby barank » Sun Feb 28, 2010 12:13 pm

Maxime81 -
Oh i also had that problem for a time. I used A* in decision process for a short time ; after that it was all about "if isolated" and count territories while checking isolation etc.
And in that time , I used a tie-breaker for that. With a little tie-breaker which i cant exactly remember right now ; it always preferred the squares closer to opponent ( actually , not the closer ones. More like ; it'll choose the square closer to , direct line between me and opponent ). Really hard to describe ; so lemme just find it..... ugh can't find it , my coding folders are total mess :( i'll just try here ;

x1 = current_square.x - opponent.x
y1 = current_square.y - opponent.y
x2 = my.x - opponent.x
y2 = my.y - opponent.y
h = h+ (x1*y2 - x2*y1) *0.001 // kk i thought i would be easier to understand like this but doesn't seem so now eh?

This is kinda , "best of both worlds". It'll move diagonally in maps like "empty-room" or "huge-room" but it'll also prefer "NNNNWWWW" like movement (any word to describe this? ) in maps like "joust".

Still i don't think A* is a crucial part of anybodies bot so it's just a little enhancement.
barank
Lieutenant
 
Posts: 13
Joined: Thu Feb 25, 2010 2:45 am

Re: Hoping for lots of discussion after Friday

Postby dutchflyboy » Sun Feb 28, 2010 12:37 pm

dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: Hoping for lots of discussion after Friday

Postby barank » Sun Feb 28, 2010 1:56 pm

barank
Lieutenant
 
Posts: 13
Joined: Thu Feb 25, 2010 2:45 am

Re: Hoping for lots of discussion after Friday

Postby dutchflyboy » Sun Feb 28, 2010 2:24 pm

dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

Re: Hoping for lots of discussion after Friday

Postby psb217 » Sun Feb 28, 2010 9:36 pm

One thing that I haven't seen mentioned yet is any variable weights being given to the vertices "dominated" by each player when doing any of the various voronoi-based heuristics. I wrote my bot in Python and it seemed to be doing fairly well with respect to the other Python bots, despite only achieving 2-3 plies of minimax, with the occasional 1-ply search on large maps.

One of the largest jumps in my bot's apparent performance came with the introduction of variable weighting for each vertex within a player's voronoi region. Basically, I counted each vertex with 1 neighbor in the region as 0 points, "..." with 2 neighbors as 1 point, etc. I thought of this as representing the overall "robustness" of the region that each player controlled, and it implicitly includes the "move to least neighbored neighbor" heuristic while somewhat maximizing the degrees of freedom within a controlled region. It also helped avoid the growth of "abscesses" around single-neighbored vertices to which some algorithms seemed prone. This weighting provided a significant boost over simple vertex counting.

Unfortunately, my algorithm was pretty general and didn't properly account for either the grid structure of the graphs represented by tron game boards. This really killed my evaluation time when I extended my algorithm to use the "tree of chambers" approach, as I was unaware of efficient algorithms for calculating articulation vertices in general graphs, so I brute forced it by checking neighbor connectivity after removal of each vertex. This made things really slow. I wish I had known of some of the techniques that kduleba was using, as I would have had to worry less about some of the dramatic horizon effects that have to be accounted for when you can't be certain that an algorithm will achieve more than one step of lookahead...

Hopefully my bot can hang on and do alright, though it wasn't until Friday morning that I got around to adding the articulation vertex and tree-of-chambers code, so I didn't have time to fully work the kinks out before my final submission. Though, later testing shows that performance shouldn't be _worse_ than my previous attempt (with the strange exception of the quadrant map).
psb217
Cadet
 
Posts: 3
Joined: Sun Feb 28, 2010 9:09 pm

Re: Hoping for lots of discussion after Friday

Postby a1k0n » Sun Feb 28, 2010 10:34 pm

a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Hoping for lots of discussion after Friday

Postby psb217 » Sun Feb 28, 2010 10:49 pm

psb217
Cadet
 
Posts: 3
Joined: Sun Feb 28, 2010 9:09 pm

Re: Hoping for lots of discussion after Friday

Postby luv2run » Sun Feb 28, 2010 11:05 pm

I also weighted the squares, but surprisingly did not see much difference in ranking before and after doing so.
I gave each square a name:
DEADEND = surrounded on 3 sides by walls
TUNNEL = surrounded by walls on 2 opposite sides
CORNER = surrounded by walls on 2 adjacent sides
TRI = a wall on only one side
QUAD = no walls on any side
Scores:
DEADEND: 0.01 because you can only ever use one of these, so an area with 99 of them is no better than an area with 1.
TUNNEL: 1 because once you go through, you can't come back unless there's a tunnel back.
CORNER: 2 good square to use usually.
TRI: 2.5
QUAD: 3

Very ad-hoc but the scores seemed logical to me.
luv2run
Lieutenant
 
Posts: 11
Joined: Sun Feb 28, 2010 4:57 pm

Re: Hoping for lots of discussion after Friday

Postby a1k0n » Sun Feb 28, 2010 11:07 pm

Actually you'd need to multiply the edges by 3, not by 0.25... The edges totally dominate the heuristic value. Dunno why, but it seems to work. It definitely keeps it from cluttering up its own space though.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron