[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/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 Sat Apr 29, 2017 1:22 pm Advanced search

Source Code Thread

Share and discuss ideas for your entries here.

Re: Source Code Thread

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

grogers
Lieutenant
 
Posts: 15
Joined: Fri Feb 19, 2010 4:08 am

Re: Source Code Thread

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

I want to see the source of whoever had the high ranking Go bot.
Queue29
Lieutenant-Colonel
 
Posts: 41
Joined: Sat Feb 06, 2010 5:43 am

Re: Source Code Thread

Postby corey.abshire » Sat Feb 27, 2010 3:25 pm

Here's mine.

http://github.com/coreyabshire/Tron

It uses minimax and all that, but it never got deep enough because I wasn't able to come up with a decent way to approximate the space around us instead of counting it all. I tried just deriving whether the space count would be a simple decrement on the space count for the prior state, or whether I needed to count again based on changes in the walls immediately around each player, but the logic for that ended up being too complicated and caused more problems than I thought it was worth.

My fill strategy had issues because it didn't orient itself towards articulation points properly. It basically followed the wall, but it used the same count spaces function to avoid obviously bad choices. Wall would be fine if it filled in an order that optimized before the articulation points. For some reason I just kept avoiding thinking that through.

Some of the other strategies I came up with never worked all that well in practice. I kept experimenting with a bunch of different ideas when I probably would have made it further by optimizing to get deeper in minimax. Oh well, it was fun anyway.
corey.abshire
Cadet
 
Posts: 4
Joined: Sun Feb 07, 2010 4:58 pm

Re: Source Code Thread

Postby jmcarthur » Sat Feb 27, 2010 4:04 pm

There have been a few requests for me to reveal my source code, but I'd rather keep working on it a little bit longer and play it on dhartmei's server [1] a bit. I will open source it when I'm done with my little exercise. It will be a few days because I won't be able to work on it at all for a little while. I will post a link to the source once I have put it up.

[1] viewtopic.php?f=10&t=337

Edit: I changed my mind about posting the source code for the bot I had submitted. It's posted below.
Last edited by jmcarthur on Sat Feb 27, 2010 4:44 pm, edited 1 time in total.
jmcarthur
Colonel
 
Posts: 80
Joined: Fri Feb 05, 2010 3:41 pm

Re: Source Code Thread

Postby positron » Sat Feb 27, 2010 4:16 pm

My messy Common Lisp is here:

Nothing special, just minimax with iterative deepening, using the voronoi territory idea for eval. I have attempted trivial monte-carlo for flood-filling but didn't get to spend too much time on that, as it looked like it was doing worse than a simple DFS.
positron
Cadet
 
Posts: 3
Joined: Sun Feb 14, 2010 8:08 am

Re: Source Code Thread

Postby jmcarthur » Sat Feb 27, 2010 4:44 pm

I changed my mind. I will continue to develop my new bot, but here is the source for the one that actually made it to the server before the deadline. My bot used plain vanilla UCT written in Haskell with no special heuristics and ranked around #130 before the deadline, I think. For a day or two it was in the top 50-100, but I stopped maintaining it when I got the idea I'm working on now. My pure UCT algorithm is in GameTree.hs, and it's agnostic to the game it's applied to as long as it's 2 player and minimax. The actual Tron-specific game tree is generated lazily in MyTronBot.hs, including what I guess is an unusual use of unsafeInterleaveST: lazily generating the Monte Carlo results for each node of the tree.

This bot space fills very very badly, though. I would have been much better off abandoning UCT after being separated from my opponent and using a dedicated space filling algorithm.

http://patch-tag.com/r/jmcarthur/uct-tr ... ent/pretty
Last edited by jmcarthur on Sat Feb 27, 2010 4:59 pm, edited 2 times in total.
jmcarthur
Colonel
 
Posts: 80
Joined: Fri Feb 05, 2010 3:41 pm

Re: Source Code Thread

Postby dhartmei » Sat Feb 27, 2010 4:45 pm

Here's mine: .

Using a minimax tree with only four values (win, loss, draw, undecided), no pruning.
The weakness is chosing among undecided nodes, for which I only had simple Voronoi.
Stronger points are the space filling after separation: finding chambers (through articulations), and the way
to fill a chamber ("stretching rubber-band").
User avatar
dhartmei
Colonel
 
Posts: 65
Joined: Sun Feb 07, 2010 3:58 pm
Location: Basel, Switzerland

Re: Source Code Thread

Postby iouri_ » Sat Feb 27, 2010 5:13 pm

Here's my code:



Rough description:
- When near to or separated from opponent, use iterative deepening to search through available moves. Score moves using tree-of-chambers approach detailed here: . Pick best move using minimax.
- When far from opponent (> 6 steps), for each available move, replay the game from that move forward using the above method (evaluating 1 step deep) until the opponents are separated or one/both opponents die. If the opponents are separated, the score for that path was the final move score using the tree-of-chambers approach. This allowed to find 'strategically good' moves that would become useful only 20+ steps later.

Most calculation results were stored between the MakeMove() function invocations to avoid recalculating the same thing. The side effect was that in open spaces on small maps the program would take up to 600MB memory.
iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Source Code Thread

Postby achan1058 » Sat Feb 27, 2010 5:56 pm

Here's my source. I use basic Voroniod Territory (attempting to add "enhancements" such as distance to squares controlled and etc gives worse results) with alpha-beta search. Because player 1 and 2 are not symmetric when player 1 goes first, I ensured that all terminal search nodes are on even depth (where both players make the same number of moves).

When opponents are separated, I simply move to the space that maximizes the remaining squares available, and tie break by maximizing distance. For some reason, trying to do a search on it makes it do some poor moves.

There's a big bunch of macros defined all over the place for me to test the "enhancements" that doesn't work, so I don't have to create multiple source files and forget to modify a bunch of them. Not good coding style, but I like it for a project like this.
Attachments
cpp.zip
(5.14 KiB) Downloaded 161 times
achan1058
Cadet
 
Posts: 6
Joined: Thu Feb 18, 2010 2:06 am

Re: Source Code Thread

Postby dutchflyboy » Sun Feb 28, 2010 10:45 am

As everyone is sending in his bot, here's mine. It has gotten in the top 10 once (just after upload, but still, great feeling). The rest of the time it floated between 50-100 (EDIT: in final ranking: 81st).

Short description:
- Bot can be in three states, "Hunt", "Eat" and "Survive" (I wasn't very inspired the day I wrote the skeleton).
- Hunt is when the bots are far away and the minimax encourages getting near to the enemy without wasting space
- Eat is at short distances (when minimax gets deep enough to make a valid strategy) and the evaluation function only considers squares. In both cases (Hunt and Eat) tie-brakes are done by trying to stay in a straight line, if this isn't possible, with a random number (add some variance).
- The survive function was a maxmax algorithm (I don't know how it should be called, it's minimax while ignoring the enemy) which tried to maximize the available space and tried to stick to walls (1 wall touched = 1/5 square, so it's only used as tie brake).
- The square count algorithm is a simple counter with a queue that counts all but one dead-end. No other optimizations where added. No pruning either (I tried adding alpha-beta, but it didn't add any speed improvement, so I probably did something wrong in the implementation).
Attachments
StateBot.zip
C# bot
(10.29 KiB) Downloaded 171 times
Last edited by dutchflyboy on Mon Mar 01, 2010 10:03 pm, edited 1 time in total.
dutchflyboy
Colonel
 
Posts: 57
Joined: Sun Feb 07, 2010 1:08 am

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron