Behaviour Tree Genetic Algorithm

[BTree]

Hi all,

I am a Computer Science Master's student. For my thesis, I am interested in researching and creating an AI for BfW. I wanted to share my plan with you for feedback/discussion/criticism. All feedback is welcome.

I have played a bit of BfW, and I understand it is a highly complicated game in terms of strategy and randomness. However, I believe that a genetic algorithm, operating on a behaviour tree, may be able to provide a competitive AI.

A highly interesting paper is found here on the subject of behaviour trees and genetic algorithms: www.doc.ic.ac.uk/~sgc/papers/lim_evogames10.pdf

Behaviour trees are trees which define conditions and actions. The behaviour tree is evaluated by an agent, and selects an action for the agent to do. I was interested in combining this with the work of SeattleDad, on his amazing MLRecruiter. Particularily, his implementation of a goodness metric for units.

I was thinking that for each turn in a battle, this goodness metric could be summed up across a side. Then, the highest/average goodness would correspond to how good the strategy was during the battle. If multiple behaviour trees were evaluated, the best ones could be selected and mutated for the next generation of trees.

This isn't a full description of every part of my idea. Hopefully I've hit the main points, and I would be happy to discuss this further.

I do forsee difficulties with this project. I know the state-space of this game is quite large. Also, I may have quite a bit of trouble converting from the behaviour tree representation to the lua code. I haven't quite nailed down the details for that.

Of course, all work done would be given to the BfW community (barring nay issues with my University). Also, I am quite willing to co-author future papers once my Master's is done (hopefuly for April/May).

Thank you for reading. And a special thank you to SeattleDad for catching my eye with his project.

BTree

[Alarantalara]

Welcome!

If you haven't seen it yet, documentation on the existing AI and links about modification are available at http://wiki.wesnoth.org/AiWML You'll notice that Wesnoth's current AI, while not described as a behaviour tree, does define a set of ranked conditions and actions. The ranking is used to distinguish between multiple possible actions for the same unit (since it could be simultaneously possible to move it for healing, to kill a unit, or to block enemy movement or...).

[lipk]

Wow, we're going to have an unbeatable AI in a year's time if this goes on... I was thinking that, regarding the seemingly growing interest in experimental AI improvements, there could be a branch for this kind of stuff? I would be more eager to test patches myself if they didn't pollute my main working copy.

[SeattleDad]

BTree,

Thanks for your comments about the ML Recruiter. I'm glad to hear that another machine learning person thinks I'm on the right track. I've just released the ML Recruiter 0.4 patch, which you can find at https://gna.org/patch/?3479. With this version, I am migrating the project to join in with the AI-Demos project hosted at GitHub (https://github.com/mattsc/Wesnoth-AI-Demos) to allow for a faster release process and tighter integration with the work that mattsc and Alarantalara are doing on the "Ron" and "Fred" AI's.

I think it's a pretty cool idea what you are thinking of doing with the Unit Goodness metric. Just to clarify, Unit Goodness is a measure of how well a unit will perform in a given game state, e.g. the features that are input to the neural net concern the distribution of friendly and enemy units on the map plus stuff like friendly/enemy villages held. Do I understand that when you say "this goodness metric could be summed up across a side", the idea would be to call the neural net (the method is ai.get_ml_recruitment_score()) to get the unit goodness for each of the units on a side? If so, I think this is a great idea. I've been curious about how useful the ML Recruiter would be if used in this way. My only caveat is that the MLR's unit metric currently gives a unit's predicted usefulness at recruit time. This doesn't take into account the unit's hit points remaining or tactical combat questions like "the unit is surrounded". I think it would be pretty easy to modify MLR to do this, though. The way to do this would be to add the features and then start gathering training data of unit goodness going forward at the end of battles (e.g. what is the gold yield (http://wiki.wesnoth.org/Machine_Learnin ... Gold_Yield) from now until the end of the game given that this unit has only 25% of its original hitpoints?). It could be that predicting gold yield at recruit time would be just a special case of predicting gold yield for a unit at any point in the game.

Note that as I've mentioned on the forums, I'm aiming for a paper for Computational Intelligence in Games, which has a March 1 deadline. Although the focus of that paper would be on the neural net approach that I'm taking, if you had preliminary results by that time, perhaps you could join as a coauthor and we could perhaps mention that the approach was useful in evaluating tactical battle strategy as well as recruiting strategy.

This sounds like a really cool project that you're doing, so please let me how I can help. Perhaps we can map out a roadmap of what you're going to do and what your going to need from MLR.

SeattleDad

[SeattleDad]

Wow, we're going to have an unbeatable AI in a year's time if this goes on... I was thinking that, regarding the seemingly growing interest in experimental AI improvements, there could be a branch for this kind of stuff? I would be more eager to test patches myself if they didn't pollute my main working copy.

Speaking for myself, I've recently added the Lua and Python portions of my code to the AI-Demos add-on. I think it could be useful for us to work out the kinks on AI-Demos and then to merge it into mainline Wesnoth as the code matures. The problem I have is that 95% of my code is in Lua and Python, but it's dependent on some code from the Waffles machine learning toolkit and a tiny amount of Lua/C++ interface code that I added to src/ai/lua/core.cpp. I'm wondering if we could get this code integrated into Wesnoth while leaving the code that exploits that interface in AI-Demos. This way ML Recruiter and future code that's using machine learning could be tried out by anyone just by loading AI-Demos, rather than just those few who are confident enough of their C++ skills to apply a patch and build Wesnoth from source.

[lipk]

Speaking for myself, I've recently added the Lua and Python portions of my code to the AI-Demos add-on. I think it could be useful for us to work out the kinks on AI-Demos and then to merge it into mainline Wesnoth as the code matures. The problem I have is that 95% of my code is in Lua and Python, but it's dependent on some code from the Waffles machine learning toolkit and a tiny amount of Lua/C++ interface code that I added to src/ai/lua/core.cpp. I'm wondering if we could get this code integrated into Wesnoth while leaving the code that exploits that interface in AI-Demos. This way ML Recruiter and future code that's using machine learning could be tried out by anyone just by loading AI-Demos, rather than just those few who are confident enough of their C++ skills to apply a patch and build Wesnoth from source.

That could be an acceptable solution, too. (Although it would be nice to see someone successfully running your stuff on Linux & Windows before merging it into mainline ). Would you bother to present this idea on the dev mailing list?

[SeattleDad]

I may need help with Windows and Linux since I only have access to a Mac, but I'd be happy to debug any issues.

With regards to the mail, could you add me to the dev mailing list?

[BTree]

SeattleDad, if you need some help testing your code, I'm on Ubuntu Linux.

So I'm still getting a handle on Lua and the Wesnoth AI code. However, I have the beginnings of behaviour trees...

And a small amount of progress to show:
http://imgur.com/z1E74

I'm figuring out the test scripts of SeattleDad, and how all the output is fed into various scripts/functions. The above is me testing that I can get some numbers out of the game into a small plot.

The plot is of a defined fitness function over the turns of the game. The red line is the fitness of SeattleDad's Machine Learning Recruiter, while the blue line is of the standard AI. As the MLR AI won, I believe that this fitness function does a decent job of predicting victory.

However, this is not SeattleDad's full gold yield metric. It is only a sum of the hitpoints and of the future_basic_gold_yield for each unit on both teams. SeattleDad, I found your metric function, but I was unsure how to decouple it from the MLRecruiter class it was in. I would like to call it directly on a unit/team to get the fitness and not worry about the dictionaries and model_paths.

Here's another test, with just the future_basic_gold_yield metric: http://imgur.com/KV27W. It would be good in the future to get a formal measure of how this metric corresponds to victory. But at least it makes a nice figure for a paper...

BTree

Post 2
Does anyone know if there is a reason I cannot run multiple copies of BfW at the same time on Ubuntu Linux with --nogui mode? I need to run hundreds/thousands of copies for my algorithm, and it would speed it up immensely if I could run 30+ at once on my machine.

Or see how many I can run on a supercomputer...

[lipk]

With regards to the mail, could you add me to the dev mailing list?

You can subscribe yourself here. You only need to log in to Gna.

[BTree]

Hi everyone,

First off, congratulations on the 1.12 release of Wesnoth!

I wanted to update this posting with the link to my completed thesis: http://gram.cs.mcgill.ca/theses/oakes-13-practical.pdf

I've been meaning to come back and share my results and code for some time, but unfortunately I've been focused on other things. In fact, it will be at least a month until I can post my experimental code.

The work within this thesis needs further research in order to be viable within the game. When I started this research, I did not realize how hard it is to steer genetic algorithms towards a good result. As a result, the thesis is good exploratory work in this domain, but there is much farther to go.

Please feel free to ask any questions you have.

BTree / Bentley Oakes

[max_torch]

I skimmed over the thesis from top to bottom. By the way, before you read the whole post, I am not planning to do any work or contribute because I do not know how to program, I'm only a layman and I'm still studying (2 or 3 years to go) so I couldn't even devote time if I wanted. But it interests me because I do intend to go into computer science things like this someday and it is applications like this that entice me.
I see that you worked on it last August 2013. Wow so more than a year has passed since then, I wonder if you have made more progress? What about the game mechanics of Wesnoth that you did not include, and the other units of Wesnoth that you did not perform the test with, are you interested in finding a way for the evolutionary AI to incorporate/consider those elements?
By the way of all turn based games why did you choose wesnoth?
Also, what inspired you to study Computer Science?

[BTree]

Hi. Thanks for your questions!

1) Unfortunately I have not made any progress on this in a year. I'm now part of the Modelling, Design, and Simulation Lab at McGill University, so I've been working on completely different projects. In fact, the day after I handed in my thesis I was attending a modelling conference. So I didn't get any time to wind down and clean up my code like I wanted.

2) I cut out a lot of the game features (such as healing) in order to get a simpler game. In particular, I didn't want health to keep bouncing up and down as attacks and healing happened. For future work, I think a genetic algorithm approach is going to have to be combined with a visualization system such as http://yieldthought.com/post/9572288205 ... -better-ai. I was trying to write a program to write an AI for me, which was probably a little ambitious. Giving feedback to the AI/map designer on what works is probably an easier target to achieve.

3) I had a few requirements that led me to Battle for Wesnoth:

• * Open-source
  * Actively developed
  * Easy to load my own AI
  * Friendly community who responded to my questions
  * Other research was taking place (is SeattleDad still around?)
  * Game was turn-based, so I could collect metrics every second
  * The game mechanics are easy to learn, hard to master
  * Different maps/units
  * Also, Wesnoth looks really really good. I'm very impressed by the artistic quality of the characters and world.

4) Ever since I was young, I wanted to be a scientist. It seemed like fun exploring the universe around us and learning as much as possible. Bill Nye the science guy taught me that you can know things for certain, and ever since then I've had an appreciation for knowledge.

I also really enjoyed messing around with computers when I was younger. Everything is this complex system that you can figure out and change to better suit you. So later on, I was blown away by the career opportunity to combine my two favourite things and be a computer scientist.

I love computer science, and I could probably write a book about why, but I'll keep it short. It's the way that computers can be used to do things easier and faster, and in absolutely every human endeavour. Want to sequence genes to find out what causes cancer? Use a computer! Want to pay for things using your phone? Sure! Want to read Wikipedia and watch Youtube and learn information and skills in a fraction of the time it would take your ancestors? Okay! This is such an interesting field with such a wide scope that has dramatically changed human behaviour. I love how fast it moves along, and the amazing progress I've seen year-over-year.

[pyrophorus]

Hi !
I read your thesis this afternoon and found it very interesting and stimulating. I'm only a little frustrated with the fitness functions and would have been glad to learn more about them. Anyway, it would be fine if you could advance more in your work some day.

Thanks for sharing it !

Friendly,

[Wender_BR]

big ideia i'm studying neural network and genetic algorithms, good to see you working with wesnoth aha

thanks for sharing it - 2