Tronte Carlo

[mosquito]

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.

[Maxime81]

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 ) I didn't have enough neural network courses to see what can be done...

[mosquito]

[sasp777]

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 ?

[mosquito]

[Janzert]

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

[sasp777]

[Fritzlein]

[sasp777]

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.

[mosquito]