[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/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 - Source Code Thread

It is currently Thu Jun 29, 2017 10:33 am Advanced search

Source Code Thread

Share and discuss ideas for your entries here.

Source Code Thread

Postby henrikno » Sat Feb 27, 2010 6:36 am

Please share your tron source code here so everyone can learn and get better coders.


If you have a git repository, you can use or if you have a mercurial repo, .
If you don't, you can upload our code on


Let me start:
henrikno
Cadet
 
Posts: 9
Joined: Mon Feb 08, 2010 12:52 pm

Re: Source Code Thread

Postby DjinnKahn » Sat Feb 27, 2010 7:36 am

http://djinnkahn.host-ed.net/DjinnKahn.zip_ (slightly out of date)

remove the _ when you download the file

My search used iterative deepening + alpha-beta pruning + move reordering table (5 moves deep).

When the bots are separate, my evaluation function estimates the longest path using the "tree of chambers" idea. It finds the articulation points (one way passages) with a single DFS. Unfortunately, I don't cache the results, but it's fast at least.

When the bots are together, my evaluation function was originally using the Voronoi Territory idea, but I lost some games where it didn't work well. My bot was moving toward the opponent and liked controlling territory to the left AND right side, but once it reached the opponent, it had to choose EITHER the left OR right side. The "joust" map is a good example. I wanted my bot to KNOW that hugging the wall is better in that situation.

So, I came up with a way to try to count only the squares my bot controls on the left OR right. I mark each empty square with the distance to me and my opponent. A square is on a shortest path between me and my opponent if "dist to me" + "dist to opponent" = "dist from me to opponent". The "middle" is the set of all such squares. Then, I find all the connected regions, treating the "middle" as inaccessible. My score is the number of squares in the "middle" that I control PLUS the number of squares I control in my best region. The evaluation function is my score - opp's score.

This approach makes my bot smarter especially on Joust, Triangle, Oval, Box. I'm not sure if it's an improvement over Voronoi Territory overall, though.
DjinnKahn
Lieutenant
 
Posts: 18
Joined: Wed Feb 17, 2010 11:32 pm

Re: Source Code Thread

Postby ebrahim » Sat Feb 27, 2010 1:27 pm

A simple alpha-beta pruned minimax, with memoized sorted iterative deepening, and some simple evaluation, released into public domain: http://bitbucket.org/ebrahim/tronbot/src/tip/
WARNING #1: look after your eyes and brain while parsing my kind of C++ syntax
WARNING #1: my bot uses 3 GiB of RAM by default. Reduce it by decreasing CACHE_SIZE. Each cache item takes almost 600 bytes.
ebrahim
Lieutenant-Colonel
 
Posts: 49
Joined: Mon Feb 08, 2010 7:03 pm

Re: Source Code Thread

Postby wtarle » Sat Feb 27, 2010 2:12 pm

my implementation isn't great but here's the gory details:

First I flood fill to see if I'm sharing a region with the other guy.

If we're in the same zone, I find the shortest path to get to him using A* search g(n) = path depth, h(n) is dx + dy. If this times out he's too far away to do any convincing minimax so I just move towards him.

If I have time left, I do iterative deepening minimax search with alpha-beta pruning, starting with the direction that gets me closer to him to give me good pruning. My utility function rates draws at 0, wins at infinite, losses negative infinite. If we're connected, it cheaps out with number of squares close to me - number of squares close to him by dx + dy. If we aren't connected, the score is flood fill me - flood fill him scaled way up because my confidence level is higher.

If we aren't in the same zone, I do greedy best first searching with h(n) = 3*depth + flood fill and that does a reasonable job.
wtarle
Lieutenant
 
Posts: 15
Joined: Sun Feb 14, 2010 7:18 pm

Re: Source Code Thread

Postby kduleba » Sat Feb 27, 2010 2:57 pm

kduleba
Captain
 
Posts: 27
Joined: Fri Feb 05, 2010 12:35 am

Re: Source Code Thread

Postby iouri_ » Sat Feb 27, 2010 3:05 pm

kduleba, what did you use to convert c++ code to HTML?
iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Source Code Thread

Postby Queue29 » Sat Feb 27, 2010 3:05 pm

Queue29
Lieutenant-Colonel
 
Posts: 41
Joined: Sat Feb 06, 2010 5:43 am

Re: Source Code Thread

Postby cwbowron » Sat Feb 27, 2010 3:08 pm

cwbowron
Cadet
 
Posts: 6
Joined: Sat Feb 27, 2010 3:06 pm

Re: Source Code Thread

Postby a1k0n » Sat Feb 27, 2010 3:10 pm

http://github.com/a1k0n/tronbot/

Mine's pretty straightforward: alpha-beta search, voronoi territory idea except I separate "chambers" after finding the articulation vertices (but when doing so, I assume territory your opponent controls is inaccessible, so there are a lot more of them) I count territory that isn't on the "battlefront" as useless iff it's smaller than the region in the "battlefront" - the front being defined as the line where player 1 and 2 are equidistant. Actually I'm not explaining that very well; it does a linear search of the "chamber tree" to get a guess as to the most available space (using the red/black checkerboard idea to find the upper bound of fillable space). If the player's in the battlefront region then the biggest adjacent chamber is counted, and so on, but if the player is not in the battlefront region then it only counts the spaces necessary to get into the battlefront region, plus the size of its territory inside the region. Something like that. It helps on some maps, hurts on some maps.

I had negascout in there as a branch back when my bot had a lot of evaluation bugs, so I abandoned it for probably no good reason. I'm sure there are several other improvements to the engine that were possible but in the end I found it was far better to work on the evaluation function than to search deeper, because a bot that searches with a flawed evaluation heuristic is self-deluded and a bot that searches more deeply is even more self-deluded. This is why UCT is a good idea, but I was too committed to my approach to try it.

To handle the endgame (where you and your opponent are separated) I do an iterative deepening search with the terminal evaluation being done with a greedy local heuristic: repeatedly choose the direction that removes the fewest edges from the graph (i.e. it has the most wall neighbors), with a penalty for choosing a direction that is a potential articulation vertex -- defined as a vertex with a 3x3 neighborhood with the property that one of the diagonals blocks off one cardinal direction from another. I made a lookup table for that. Oh, and it also keeps track of the connected components along the way and obviously moves into the largest component if there is a separation.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Source Code Thread

Postby kduleba » Sat Feb 27, 2010 3:15 pm

kduleba
Captain
 
Posts: 27
Joined: Fri Feb 05, 2010 12:35 am

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron