[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/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 - Tronte Carlo

It is currently Fri Sep 22, 2017 1:37 pm Advanced search

Tronte Carlo

Share and discuss ideas for your entries here.

Tronte Carlo

Postby mosquito » Sat Feb 27, 2010 10:03 pm

I wondering if someone used Monte Carlo simulation extensively. I've used it with some success (last day of tournament I ended somewhere in 30-60. For a short time it was even in top 10 - what a great feeling!). I performed the same series of simulations for battlefield and for space filling (just moving only my bot and changing the evaluation function from the best scoring to longest move - it did reasonably well).

After reading some Monte Carlo for Go publications I've found out that the key is to make the random player less random (not making blunders), so I've used a bunch of strategies (aggressive, wallhugger, most open, ordered selection etc) with a varying randomness factor - some of them were almost pure wallhuggers others mostly random. So I've had a bunch of 50 different bots that fought with themselves. Then I choosed the best next move. The rationale was simple - find a move assuming it is fighting with various bots.

For those random playouts evaluation was simple - if the bots were separated I've counted reachable area (not counting dead-ends = spaces with 3 walls around) for both players and _not_ continued the random game.

After all I'm very satisfied with the strategy. If there was more time I would go in the direction of making random bots smarter and smarter. I think it would work nicely.
mosquito
Cadet
 
Posts: 6
Joined: Sat Feb 27, 2010 9:10 pm

Re: Tronte Carlo

Postby Maxime81 » Sat Feb 27, 2010 10:32 pm

I thought of it but never had the courage (and time) to try. I've used Monte Carlo on the "Samegame" last year (a single player game) but it was a little slow. More generally, I'd like to see how can we implement an efficient simulated annealing here. Your idea of making it choose between strategies were good but you have to do a lot of computing. Do you think a good Monte Carlo could beat a good Alpha-beta ?

It would have been really interesting to see bots that learn how the opponent "think" to guess the next moves but the maps were too small for that... (a bot which learn :D) I didn't have enough neural network courses to see what can be done... :(
Maxime81
Lieutenant-Colonel
 
Posts: 42
Joined: Sat Feb 13, 2010 10:56 pm
Location: INSA Toulouse, France

Re: Tronte Carlo

Postby mosquito » Sat Feb 27, 2010 10:58 pm

mosquito
Cadet
 
Posts: 6
Joined: Sat Feb 27, 2010 9:10 pm

Re: Tronte Carlo

Postby sasp777 » Sun Feb 28, 2010 12:49 am

I've done UCT on min-max trees in C# ( the algorithm used in the Go Papers). AFAIK at least two more people have done UCT. Let's wait for the finals and have a look at how well the monte-carlo bots are doing ( I doubt they will beat the alpha-beta + heuristics players).

BTW your approach with using 50 random strategies for simulations is really good. Did you do UCT or just monte carlo ?
sasp777
Lieutenant
 
Posts: 16
Joined: Sat Feb 13, 2010 11:57 am

Re: Tronte Carlo

Postby mosquito » Sun Feb 28, 2010 1:50 am

mosquito
Cadet
 
Posts: 6
Joined: Sat Feb 27, 2010 9:10 pm

Re: Tronte Carlo

Postby Janzert » Sun Feb 28, 2010 4:58 am

I started with UCT and it got into the top 30 at the time (last submission of it was 2/12), but then didn't see a clear way forward to improving it. The obvious way of course is changing the playout move choices but I knew from go that stronger playouts don't necessarily improve overall play. At that point I was actually going to just leave it and see how it went. But I mentioned the contest to Fritzlein and he was quite interested and encouraged me with quite a few ideas for evaluation. So I ended up switching to alpha-beta search at that point with him providing the graph theory. :) I was able to improve it to be quite a bit better than the straight UCT bot. I'll try and get source code out from both of them in the next week or so.

Janzert
Janzert
Contest Organizer
 
Posts: 271
Joined: Sun Feb 07, 2010 1:59 am

Re: Tronte Carlo

Postby sasp777 » Sun Feb 28, 2010 10:38 am

sasp777
Lieutenant
 
Posts: 16
Joined: Sat Feb 13, 2010 11:57 am

Re: Tronte Carlo

Postby Fritzlein » Sun Feb 28, 2010 3:30 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Tronte Carlo

Postby sasp777 » Sun Feb 28, 2010 4:13 pm

For survival mode, I am switching to a single player UCT, effectively giving rewards depending how deep I go, which is quite sucessful ( in my laptop at least I've never seen it failing). Survival mode is not the main issue I think with UCT. The main problems are cpu time and the huge number of irrelevant random monte carlo games.
sasp777
Lieutenant
 
Posts: 16
Joined: Sat Feb 13, 2010 11:57 am

Re: Tronte Carlo

Postby mosquito » Mon Mar 01, 2010 8:44 pm

mosquito
Cadet
 
Posts: 6
Joined: Sat Feb 27, 2010 9:10 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest