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

It is currently Tue Oct 17, 2017 8:15 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 corey.abshire » Sat Feb 27, 2010 5:35 am

Since the contest is over, I went ahead and posted my full code on github. My bots not that great, but I thought people still might be interested in seeing the code.

Anyway, here's the URL: http://github.com/coreyabshire/Tron

I'm definitely interested in seeing other people's code and learning from all of you.
corey.abshire
Cadet
 
Posts: 4
Joined: Sun Feb 07, 2010 4:58 pm

Re: Hoping for lots of discussion after Friday

Postby a1k0n » Sat Feb 27, 2010 6:31 am

here's mine. Total garbage of course. I used Dijkstra's on what most people were just doing breadth-first-searches for, and I feel kind of silly for it.

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

I think it has an accounting problem in the endgame where it will carefully position itself to lose by one or two squares. I hope it wins, but I think hebbie's bot is stronger.
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am

Re: Hoping for lots of discussion after Friday

Postby ebrahim » Sat Feb 27, 2010 6:37 am

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

Postby Savaron » Sat Feb 27, 2010 8:25 am

Unfortunately I had no time the last day to fix the problems of my latest submission so I won't make a big rank.. This contest is one of my first project. I had some knowledge of java/c# before, read a lot of books, but never actually did something by myself.

So I started first with trying simple approaches like the WallHugger, Chaser, FloodFiller. Then I ported the framework of , which helped me a lot, especially in structuring my code.

I switched over to minimax with alphabeta which resulted in a top #100-#200 bot, but my evaluation functions were bad and my space-filling was worse. I played with Voronoi-Territory, some CutOff, but it was never satisfied. I found big big mistakes (like generating the game-tree wrong) each day and made it apparently worse ;)

I then heard of Monte-Carlo in the IRC and applied (which has successfully beat every other method in computer go) to it. I did combine the winrate with each nodes voronoi-territory which made my best bot so far. Space-filling was still bad and my last try was a breadth first search, which took the remaining territory and depth in account, but I had problems to combine them in a sensefull way.

It would be great to hear a more talk about the evaluations, as a lot of people implemented minimax and the evaluations did make the difference.
Savaron
Captain
 
Posts: 22
Joined: Tue Feb 09, 2010 10:32 pm

Re: Hoping for lots of discussion after Friday

Postby sausagefeet » Sat Feb 27, 2010 10:43 am

My bot started out as a simple chaser bot. It was a dumb chaser bot basing its moves on the euclidean distance between it and its opponent.

Then, I added minimax. The evaluation function simply calculated the # of free squares immediately beside it vs. that of its opponent. The previously mentioned chaser strategy was then used for far distance. The minimax was used to close combat. But, of course, this was not good enough.

Then I moved on to a wacky room calculation where I scan a player's location outwards until a wall is hit, marking each square along the way. This is done for each row and column. The intersection of all was the definition of a room. Doing this for both players and subtracting presented a new evaluation function. Not great, but getting there...

I then changed my far strategy to use a breadth first search to count all reachable squares. The direction with the most was the chosen move. Ties were broken by implementing the chaser strategy. That was OK. But, I later changed to an A* implementation where my heuristic was the euclidean distance from me to the opponent. This was much better. And, combined with the previously mentioned eval function for the minimax, it got me to the top 20 for a bit. But, of course, this did not last...

After this, I tried using the breadth first search calculation in the minimax eval function. But, it was too slow. I couldn't get deep enough. The eureka happened when I moved to a territory calculation for each player. Basically, spiral outwards from each player, marking squares and visiting neighbours. When the squares belonging to each player met, a boundary is defined. The difference between territory sizes is the score used for the evaluation function. No scoring is done for draws; only sizes (+ if my advantage, - otherwise), a win (max value), or a loss (min value). I found that attempting to value a draw just resulting in my bot making stupid decisions.

So, that is what I ended up using as my main strategy; along with alpha beta pruning and iterative deepening to watch the clock. I wanted to implement move ordering to see if I could get to lower depths, but I didn't get around to it. I started by ordering the best final moves at the end of each iteration. But, of course, that does nothing except waste cycles. The tree of moves needs to be ordered. Stupid me even left the half-ass move ordering in the final submission.

Anyway, I combined the above with a flood fill strategy for when I'm isolated from the opponent. I determine isolation when my A* algorithm for shortest path can not find a path. For the flood fill, ties are broken by hugging the closest wall. It works pretty well. Experimenting with graph components and articulation verticies would have been fun, but I ran out of time.

And, there you have the life of my bot. I was hovering between 2nd and 10th before the deadline. Whether or not it was an accurate ranking, I don't know. But, I guess we'll find out in a few days. :)
on freenode as nloko
sausagefeet
Cadet
 
Posts: 4
Joined: Sun Feb 14, 2010 9:38 am

Re: Hoping for lots of discussion after Friday

Postby sasp777 » Sat Feb 27, 2010 11:51 am

I am using UCT as well.

Links to the MOGO paper:
http://hal.archives-ouvertes.fr/docs/00 ... R-6062.pdf

and

and a theoretical analysis of the bandit problem:

http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf

My bot can found at http://github.com/sasp777/TronUCT.

It is basically UCT on a min-max tree ( with rewards 1.0/0.5/0.0). Once the board is split (I use floodfill to detect this), the bot sheds the min-max tree and does UCT with rewards based on longest path.

I am biasing UCB1 slightly for exploration ( using 3 instead of 2 in the in the exploration part of the value equation). UCT-TUNED, which is mainly used for GO does not seem to work in tron ( it exploits too aggresevily)

There is a definite need to somehow do better monte carlo simulations (as a lot of time is wasted on useless moves). This is a MUST for almost all UCT implementations(it is used heavily in go), and without it you end up with a somewhat lame bot.
sasp777
Lieutenant
 
Posts: 16
Joined: Sat Feb 13, 2010 11:57 am

Re: Hoping for lots of discussion after Friday

Postby barank » Sat Feb 27, 2010 12:26 pm

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

Re: Hoping for lots of discussion after Friday

Postby kduleba » Sat Feb 27, 2010 12:49 pm

Savaron - thanks for pointing out UTC, it looks very interesting. I only tried vanilla MC and it didn't perform well.

I was all about search depth. I have 3 strategies:
1) search for the winning move (null window [-1, 1]). On 25x25 empty board this reaches 30 ply in 0.15s.
2) alpha beta. On 25x25 board it reaches 18 ply in 0.7s.
3) A*-like search in survival mode - performance depends on board regularity. Totally random 50x50 board - 60-80 ply. More regular boards are easily solved perfectly. This has to do with how well evaluation function estimates the true number of moves left.

Taking about eval function: I used a very fast O(n+m) implementation of voronoi separation (with articulation nodes). I can do 20k calls per second on an empty 25x25 map. In (2), I use my score - opponent's score. In (3), I only use my score. This function is a very nice admissible heuristic for A*

More about (2): I use iterative deepening, transposition table to order moves (+3 ply) and to store estimates (+20% speed improvement), negascout variation (+1-2 ply on average), aspiration window (+1-2 ply). All very standard.

Code: http://www.duleba.com/tron/
kduleba
Captain
 
Posts: 27
Joined: Fri Feb 05, 2010 12:35 am

Re: Hoping for lots of discussion after Friday

Postby grogers » Sat Feb 27, 2010 3:03 pm

http://github.com/grogers0/grogers-tron-ai

I didn't try as many things as I would have liked, but oh well.

Search depth is supreme - Whoever is optimized the best will likely win. I definitely didn't spend enough time optimizing (and was very stupid in my method of finding articulation vertices), and I also should probably save the results of the search for the next iteration and just change the root node - that would start it at a depth only 1 move each worse than the previous best.

kduleba - thats clever searching for the winning move first, since that is simpler you can likely get significantly deeper even with less time.
grogers
Lieutenant
 
Posts: 15
Joined: Fri Feb 19, 2010 4:08 am

Re: Hoping for lots of discussion after Friday

Postby sausagefeet » Sun Feb 28, 2010 5:13 am

on freenode as nloko
sausagefeet
Cadet
 
Posts: 4
Joined: Sun Feb 14, 2010 9:38 am

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron