I've entered the Waterloo university Google AI Challenge, hiding under a cunning nickname, since I saw that you could develop in Haskell, and a few others Haskellers are on it too! At the moment, I'm cruising at around the 110th position, which is not too bad given that I only worked a few hours at night on it (I have a day job, you know...) and that I implemented everything myself since the starter pack wasn't ready when I started working. I've played a bit with the standard strategies, implemented some flood fill, reuse some A* implementation I have.
All of this is interesting, of course, but there is no AI as such. The only intelligence in my code is the one I put in, and the strategies I devised. So I'm thinking of playing around with genetic programming and evolution techniques to try to get my code to find the right strategies at the right time. I have the feeling the trick will be to design something that is not too restricted and is truly able to evolve into some more advanced and complex than what I've designed myself. But hey, I'll learn, even if my program doesn't (-:
4 comments:
At a certain point, I was using a sorf of genetic algorithm. It was more or less like this:
- Create a new, stupid bot that takes a random direction every turn.
- Simulate this bot and see how many steps it takes before it crashes into a wall.
- Repeat this a lot and select the bot that was able to take most steps.
- Choose the direction the best bot took first.
This initially performed very well, but then a lot of very smart bots started to appear...
The method the first poster mentioned has the merit as being a first step to a Monte Carlo Tree Searcher by adding a random opponent. I have no problem imaginig MCTS as being effective for playing TRON.
MCTS is used successfully in Go with its brutal search and state space. Additional benefits is that by using winning percentages you don't need an evaluation function.
Implementing the simple UCT algorithm is done in a wink and as an additional bonus the algorithm is best-first and always has a best move ready.
The Go site Sensei's Library has enough information (I think) to get a basic implementation going:
http://senseis.xmp.net/?MonteCarloTreeSearch
http://senseis.xmp.net/?UCT
Post a Comment