[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/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 - Post-mortem

It is currently Mon Dec 11, 2017 11:34 am Advanced search

Post-mortem

Share and discuss ideas for your entries here.

Post-mortem

Postby a1k0n » Fri Mar 05, 2010 12:27 am

It's a rehash of everything I've posted here so far, but if anyone's interested in reading my post-mortem, here it is:

http://a1k0n.net/blah/archives/2010/03/ ... _00_21.txt

I know there are others, for instance jaspervdj's:
http://jaspervdj.be/posts/2010-03-01-my-tron-bot.html
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Post-mortem

Postby DjinnKahn » Fri Mar 05, 2010 3:01 am

Interesting read : )

Besides a better endgame evaluation, how else do you think you could improve your bot?
DjinnKahn
Lieutenant
 
Posts: 18
Joined: Wed Feb 17, 2010 11:32 pm

Re: Post-mortem

Postby a1k0n » Fri Mar 05, 2010 5:39 am

Endgame evaluation is huge, but there's also a lot of opportunity in the heuristic board position evaluator. The first thing that pops into my mind is extracting better features than just node and edge counts from an open space and doing more data mining on existing games between higher-ranked bots, and then iteratively improving a bot and running more games and re-feeding those games in as data. No idea how successful that approach will prove to be, but there's still quite a lot of room for improvement.

Not only that but there are a number of bugs that could use fixing.

Still, I don't know what bruudruuster is doing, but he's made extremely significant improvements in his bot today, if dhartmei's ELO ratings are any judge:

http://www.benzedrine.cx/tron/getratings

His bot completely spanks mine now.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Post-mortem

Postby bruudruuster » Fri Mar 05, 2010 8:12 am

Congratulations Andy!
Currently I am not ahead any more :-(

In a rush to make tree-of-chambers very efficient, I managed to squeeze in a few horrible bugs 2 minutes before the deadline, so I ended somewhere not-so-near to the top.
The version on dhartmei's server is the one with the bugs removed. I'm sure I was up for a top-10 position.

What I do is basically the same as most others. Alpha-beta with voronoi+tree-of-chambers as static evaluation function.
The voronoi calculation also assumes weights for each square: 0 if there is one edge, 12 if there are 2, 16 if there are 3 edges and 20 for squares with 4 edges. Squares in the center quarter of the board get an additional weight of 3.
I do something similar to your battlefront idea: each player gets only his part of the battlefront chamber. I also allow multiple battlefront chambers, important for maps such as triangle, square etc.
I also do quiesence search: null window search for moves to squares that look like articulation vertices, based on the immediate surrounding.

Draws are penalized slightly: a draw gets a weight between -1 and -100 depending on the number of moves it takes to get to the draw. This is correct as long as the static evaluation is correct.

The end-game play is a simple optimized version of the alpha-beta: it considers only one player. First it computes how many squares to fill and then does iteratively deepened DFS with the same evaluation function, except that center squares don't get a bonus. If a sufficiently long trajectory is found then search stops; otherwise the "accessibility" of the remaining area after the trajectory is optimized.

I also use the warnsdorff heuristic to order moves in alpha-beta and DFS.

I think the strength of my bot comes mostly from highly optimized algorithms, allowing it to look deep. At least that's what I like to think. I haven't checked other players code in detail yet.
For instance, several analyses require that a state for every square on the board is initialized (e.g. an initial distance to the players equal to infinity for dividing the map in each players area, or labelling all squares as WHITE when computing articulation vertices.) These initializations take somewhat time, usually some O(N) as the analysis pass itself. So I optimize that away by setting a global cur_color and bumping it up by 2 before every analysis. Then I define WHITE to cur_color and BLACK to cur_color+1. The query IS_WHITE(color) tests (color <= WHITE) instead of (color == WHITE). This avoids initializing every cell to WHITE and saves a scan over the board. There is no overflow on cur_color since I can't do 2G evaluations per second ;-)

I think it's extensive use of tricks like these that give my bot deeper lookahead than similar alpha-beta approaches.

I wanted to optimize static evaluation further. Now it does:
1) division of maps between players and determining connectedness and the battlefront
2) DFS for each player to determine their reachable tree-of-chambers
3) DFS on the articulation vertex tree to compute the max weight of divergent paths in the tree-of-chambers.
What I wanted to do was to calculate chambers while dividing the map in step 1) and come up with a much smaller graph to run the DFS on in steps 2 and 3. That would have been much faster but I couldn't get it correct immediately.
I guess we all have our wish list of things to do ;-)

Yours sincerely.
bruudruuster
Cadet
 
Posts: 6
Joined: Fri Feb 12, 2010 10:13 pm

Re: Post-mortem

Postby Accoun » Fri Mar 05, 2010 8:13 am

Accoun
Colonel
 
Posts: 82
Joined: Tue Mar 02, 2010 10:11 am

Re: Post-mortem

Postby bruudruuster » Fri Mar 05, 2010 9:42 am

Perhaps we can ask dhartmei to add 1s of leniency before deciding on a time-out.
bruudruuster
Cadet
 
Posts: 6
Joined: Fri Feb 12, 2010 10:13 pm

Re: Post-mortem

Postby Accoun » Fri Mar 05, 2010 10:00 am

Accoun
Colonel
 
Posts: 82
Joined: Tue Mar 02, 2010 10:11 am

Re: Post-mortem

Postby luv2run » Sat Mar 06, 2010 5:14 pm

luv2run
Lieutenant
 
Posts: 11
Joined: Sun Feb 28, 2010 4:57 pm

Re: Post-mortem

Postby a1k0n » Sat Mar 06, 2010 10:15 pm

That's pretty close to what mine does, except with the battlefront modification. (Yes, a gate is pretty much the same as an articulation vertex, but articulation vertices aren't computed from a particular direction so there are more of them.) But consider this: if a given chamber has a battlefront, then the territory inside it is liable to not stay "yours" unless you head directly toward the middle of it. If you instead try to fill another chamber efficiently, your opponent can head towards you and take over that space. Therefore the chamber you're in is of no use at all unless you intend to not use the battlefront chamber.

So my code just figures out whether it will last longer if it cuts off battlefronts and fills up the rest of the space, or if it cuts off its useless space and stakes a claim on the battlefront.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Post-mortem

Postby Accoun » Sun Mar 07, 2010 10:43 am

for big maps like used on http://www.benzedrine.cx/tron/getratings
there algoritmas realy need
but the statistical assessment of areas is questionable and depends strongly on the maps
a1k0n's implementation not perfect but I was too lazy to rewrite the free
Accoun
Colonel
 
Posts: 82
Joined: Tue Mar 02, 2010 10:11 am

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron