Description

Nephro - Improving and extending LuaAI

The artificial intelligence module of Battle for Wesnoth is written in C++ and is pretty complicated for scenario developers to configure. That's why Wesnoth developers decided to extend it and allow users to write AI configurations in Lua, which is not possible at the moment.

The Project

It is no secret that the artificial opponents in Battle for Wesnoth are not the strongest out there. As stated in http://wiki.wesnoth.org/WhyWritingAWesnothAIIsHard, “discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.” If we let the computer analyze a situation using discrete methods, it will not only last forever to calculate a good set of moves (with all the units, recruiting and recalling), it will also suffer failure when the factor of randomness comes in.

Imagine an AI (after long calculations) has discovered a perfect combination of moves, which relies on the success of the attacks of some units. The first warrior’s attacks do not reach its target. The AI has foreseen that and sends the next fighter to battle, but he fails too, even though, he had high probabilities to strike the enemy. This can last forever, and at some point the AI would be forced to recalculate its moves again and again.

After thinking about this problem I’ve decided to analyze, how a human mind makes its decisions. It is obvious that we do not do a lot of calculations during the game. But what do we do, when we play? First of all, we have a plan, which might be simple or complicated, depending on our skills, knowledge of the opponent and experience. It is hard to give an AI a plan, especially a flexible one, but this problem will be partially solved later on. Second, we take a look at the map, to get a comprehensive view on, where is a good place for us to fight, where is a good place for us to defend, where is a good place for us to flee, etc. After this I almost instantly came to a mobility and battle map concept. This could serve as a foundation for an AI “brain”. If we know all the types of units we can recruit at the beginning of the game, these maps would be calculated only once. What we can do next is generate such maps for the opponent.

At first, I thought that the existing system the RCA AI will ask these maps for an opinion on the move, but that seemed weird, since each map could give different evaluations and the RCA loop would have to make decisions (and what if we add more maps to the “brain”)? I found the solution to this problem in layering all maps together using some formula (will discuss this later). The end product could show us the key positions on the map, the capture of which are essential to win. “Wait, Nephro, isn’t this discrete analysis all over again?” It is not, note that the “brain” doesn’t produce move suggestions(yet), it just tells its opinion. Also, note that the “brain” is like an observer; it sits there and thinks all the time, taking a look on the game, when something happens there. In the beginning, when it hasn’t generated much, it stays neutral, but while the game goes on it becomes “smarter” and at some point might even take over control and start telling RCA AI what to do, instead of evaluating suggested by the RCA AI moves. This is all very optimistic, but possible, and it fits perfectly with the existing AI system.

This is a very simplified example, only to illustrate the idea of the maps and layering. Colors represent numerical values: dark green = good, red = bad, other colors are something in between. On the layered map, black = horrible spot, blue = good spots. Consider the RCA AI wants to move the leader to the cell, which is black on the layered map(the example is extreme, but illustrates the idea well), in this case, the "brain" will give a horrible evaluation to a move and toss the RCA loop an idea to move the leader to the blue spot.

The next concept I want to introduce is the formation graph. This complex data structure would represent the current position of all the units on the map. Again, the “brain” will not generate good formations (at least in the beginnings), it will look for weak spots in the existing ones and tell the RCA AI, whether the suggested move improves the formation or not. The next logical decision would be, of course, layer this graph with the mobility, battle and the rest of the maps. As you can see, closer to mid-game, we receive a heavy object that lives its own life and gives opinions. Closer to late-game it is expected to start giving move suggestions instead of opinions.

The example is again very simple and it's main purpose is the illustration of the idea. The colored circles represent the strength of the position of a single unit. Green dots represent strong positions: the leader is well defended and at decent health, the fighter is ready to level-up and is also on safe distance. The red dotted unit is in trouble: not only is he at dangerously low-health, he is also a potential victim of the two enemies nearby. The colored lines represent the links between the units, representing, how fast could the neighbors come to the rescue, how safe will they be if they come, how much help can they bring, etc...

The design of such structures, in my opinion, is pure art. Each one is sophisticated by itself, but their merge must be a real challenge. As I already said, at first, the structures will be simple, they will not take into consideration a lot of the factors, aspects of the game, but it will constantly grow, like a snowball, taking more and more information into account with each step. The extension of the structure code can also be endless, everybody can add their own maps and tell the "brain", how to merge them with the others.

This design involves some fun facts, for example, the faster the opponents make their moves, the less time the “brain” is given to think, and the worse its performance will be. It is hard to evaluate the actual speed of this “thinking” process, but it is obvious, that the it will continue throughout the whole game.
This is how I see the very end-product. How it should perform? The most optimistic goal I can set, is that it should be able to beat the AI Wesnoth has now and should challenge newcomers by the end of the summer. Who knows, maybe in a year or so, people will search for ways to beat it using their own AI implementations(too bad Wesnoth is open-source and anyone can look in the very depths of the "brain" :D )

The Timeline

Date	Description	Importance level
April 17 – May 17	University exam session(detailed description below)	-
May 18 – May 22	Travelling home and preparing for work	-
May 23 – June 1	Work on the exposure of the simplest parts of C++ AI(aspects, goals, actions) to Lua	Compulsory
June 2 – June 10	Creation of the low-level Lua function library, code cleanup	Compulsory
June 11 – July 11	Gather low-level Lua function sequences into higher level function libraries (e.g. move() -> wait() -> move() = patrol())	High
End of the compulsory part of the project
July 12 – July 15	Beginning of the work on the “brain”, design of the communication system	Compulsory
July 16 – August 1	Creation of the “brain’s” structures, design of the layer merging mechanism	High
August 2 – August 15	Finalization of the main part of the brain, testing it in battle against the current AI	Medium
August 16 – August 22	Completion of work and polishing of the project	Compulsory
August 22 – September **	Vacation time and travelling back to University	-
October - …	Further work on the “brain”, making the thing become more angry and unbeatable J	Low(no priority for the GSoC)

- I have 4 exams during the period from 18th of April to 16th of May, I will probably spend a lot of time preparing, but will be able to investigate further the AI and get an even better understanding - After that I will travel back to home and will be perfectly free to work on the project

IRC

Nephro, Nephx

SoC Application

Questionnaire

Basics

1.1) Write a small introduction to yourself. Hello! My name is Dmitry Kovalenko and I am a candidate student for GSoC 2011. I study computing science and hope to become a game developer, because, in my opinion, it is one of the rare industries, where programming is still interesting. I am fond of algorithms and data structures, which combines to an interest in the field of artificial intelligence for games. It's common for the top chess players of the world to play against computer opponents, but who knows, maybe in 5 years, computers will challenge the big names in the computer gaming community.

1.2) State your preferred email address.
nephro dot wes at gmail dot com.
1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?
IRC: Nephro, nephx(alternative)
Wiki, forums, GNA: Nephro

1.4) Why do you want to participate in summer of code?
I am intending to become a software developer and know the difference between a good and a bad one. It's practice and experience! It isn't possible to become a good programmer by just reading a book and finishing a University, that's why I always take the opportunities to participate in projects, do somebody's homework or just help random people on the net.
Lately I was looking for something more serious to do, even wrote a letter to some lecturers in the Uni, but no one seemed to be interested in my help. I looked up the list of Open Source projects and skimmed through it. Somewhere near the end I noticed BfW and remembered how I used to play the game when travelling to school. I went to the developer channel at freenode and started asking about chances to work on the AI(one of my fields of interest). Someone told me that GSoC is coming and that Crab_ has an AI idea for it and the next thing I know, I am writing answers to this questionnaire.

1.5) What are you studying, subject, level and school?
I am a first year student of Computing Science in the University of Glasgow. Besides programming and general computing topics(information management, HCI, systems) I study Maths and Electronics Engineering.

1.6) What country are you from, at what time are you most likely to be able to join IRC?
During summer I will stay in Latvia, which is my home country, but during term time I live in Glasgow, Scotland. Most likely I turn on my computer in the morning and the IRC client is on for the whole day. If I am programming I am available all the time, from 10 o'clock in the morning till late night, depends on how much do I want to accomplish and when did I start.
The timezone in Latvia is GMT+2, so the European community member should have no difficulties contacting me during daytime.

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.
No, I don't have any commitments at all, except for weekly ballgame matches, but they take place on weekends, so will not affect my work.

Experience

2.1) What programs/software have you worked on before?
Most of the time I developed software for various contests, never had a chance to do my own projects, but I don't regret that, because my "career" was not only challenging and fun, it also provided a wide range of sophisticated tasks, which I had to implement using set technologies and languages, often unsuitable ones. From that I learnt, which languages are good/bad and where can I use them efficiently.
I also had the opportunity to work on a large social network in a real company when I was 17, which I am proud of.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)
Two of the contests I participated in 12th grade were nationwide team contests. After winning the first one, I got invited to the same team to win the second one. This experience was probably very valuable, I had a chance to learn to evaluate tasks, decide how to distribute the tasks between the team and, of course, complete them in fixed time.
Aside from the contests, I had the experience to work in a professional team(social network mentioned in 2.1). There I learn the importance of documentation, responsibility and of course cleaning up the mess made by bad programmers before us(we received the half made project in a horrible condition). As the youngest member of the team I got to do lots of refactoring, which I started to hate by the end of the summer, but it was still valuable, since i learnt to write reusable generic code from the start, evading the need to refactor later.

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?
This is my first year in university, therefore my first attempt at GSoC.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
No, I haven't contributed to any open source projects yet, since I was always busy working or participating in contests.

2.5) Gaming experience - Are you a gamer?
I can't say that I am a gamer. Maybe I was earlier, when I had tons of free time and cared less about programming. Games were always a big part of my life, but those were not always computer games... Maybe the questions below will clear that out.
2.5.1) What type of gamer are you?
Googling "types of gamers" didn't help me :) I don't have a type, I just play when I want and what I want. The game itself doesn't mean a lot to me, I enjoy the challenge, the chance to outplay weaker players or lose to stronger ones.
2.5.2) What type of games?
When I was younger the games changed almost every week, but had the tendency to strategic gameplay. I was keen on Warcraft III TFT, played it competitively, until I understood that at some point your thinking abilities, strategy and tactics don't matter as much as microcontrol(the ability to control single units and small groups in a fight). I like thinking more than clicking the mouse 300 times per minute. Then I moved to WoW, which bored me to death with the quests that are all the same. When I spent ages to level up my character and then understood that I don't like this class, instead of creating a new char I just quit the game.
Then came the DotA family(that's what I call DotA, HoN, LoL and the rest). These games don't need hours of leveling up, don't need 300 clicks per minute, give a chance to think. After travelling between the games of this family I stopped at LoL, the engine of which provides me with what I want: dynamics, speed, flexibility.
Abbreviations:
- DotA: Defence of the Ancients, a custom Warcraft III map, where two team of 5 heroes fight each other
- LoL: League of Legends, game similar to DotA, but running on its own engine
- HoN: Heroes of Newerth, another similae to DotA and LoL game
2.5.3) What type of opponents do you prefer?
I prefer opponents that are slightly stronger than I am, mostly because beating up young(bad?) players is no fun to me, as well as dieing without a single chance to succeed against hardcore pros.
2.5.4) Are you more interested in story or gameplay?
The short answer would be: gameplay.
In PvP games the story has almost no value, because players concentrate on winning each other. Despite that, a beautiful storyline behind the characters and the world itself can certainly add to the pleasure gained while playing
2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
I've found Wesnoth in summer of 2009, when I was working in an office, used to play it during lunch breaks. In autumn, I played it in the train, while travelling to school. My friend noticed that and showed interest, so we started battling each other every morning. Although most of the play time I played single player scenarios, I certainly lean towards multiplayer games, PvP or versus AI.

2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
At the moment of writing(28/3/11) I submitted only one patch, the purpose of which was only to get to know the codebase better, experiment with Lua and C++ and just to mark my existence at GNA :)
The patch itself: https://gna.org/patch/?2599

Update: I have submitted another patch, which is significantly bigger, but still incomplete. http://gna.org/patch/?2626 This patch will not be committed as it the work is still in progress and I intend to finish it before April 14th(it would be done faster, but I was unable to work due to illness from April 8 till April 11)

Communication skills
3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
I think my knowledge of English is sufficient to work on and contribute to Wesnoth. I passed the IELTS test with overall band of 7.5 and study in Scotland, where everything takes place in English.

3.2) What spoken languages are you fluent in?
Russian(native)
Latvian(as good as native)
English(fluent)

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
I am good at interacting with players, who are good at interacting with players :) If the team is passive I usually try to start some tactical discussions, give advice to players, who aren't doing too good. If they are active and polite we manage to interact pretty well, but people, who start insulting others usually get punished by not receiving help from me(which is very important in teamplay games like LoL). The enemies, well, I always admire people, who outplay me with style and beauty, and I always tell them that, but most of the time I hear bad things in my address and I may sometimes verbally fight back, using this as a psychological weapon to make the enemies more unstable and willing to punish me.

3.4) Do you give constructive advice?
I usually try to help people with constructive advice if I feel that they want to hear it, but as practice shows, not everybody is interested in argumented and constructive advice as much as they want to hear a plain answer to their question.
3.5) Do you receive advice well?
I think that I do, I learnt that from my other hobby, electronic music production, where the first steps were very tough, and the criticism received - as rough as it can get. But I managed to get through that point and now I will never ask for an answer, I'll ask for the reason.
3.6) Are you good at sorting useful criticisms from useless ones?
It can sometimes get tricky, but I usually find respected people in the community and listen to them first, since they are less likely to give obviously bad advice. My experience in programming also allows me to understand, whether the given advice is a good idea or not.
3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want
I do not like the "see how it turns out" approach, because that led me to tons of refactoring of my code(and code of other people). I'd rather spend 5 minutes of a more experienced programmer to find out what I am asked to do, then spend 20 minutes of him explaining to me what have I done wrong and why, and how to fix it now. Time investments before starting the work will almost always lead to time economy later.

Project
4.1)Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?
I selected Crab's project on improving and extending the AI of BfW(http://wiki.wesnoth.org/SoC_Ideas_LuaAI_2011), since AI is one of my fields of interest and this is the perfect opportunity to learn, how real AIs actually work. The experience on developing and investigating the current AI will let me not make mistakes in the future. in my opinion, game AI is one of the most fun programming spheres out there.
I want to concentrate on the last part of the idea: the interaction between the AI teams. That seems very challenging and even more fun, but to get there, of course, I will have to work efficiently to complete the other tasks in time.
4.2) If you have invented your own project, please describe the project and the scope.
-- not relevant --
4.3) Why did you choose this project?
AI(as I stated many times before) is a very fun programming topic, in my opinion, but I never really had a chance to try myself out in it. Wesnoth is a complicated positional strategy, where discrete analysis fails and any AI solution that can fight against a human mind must be a peace of art.
4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".
I don't have any significant plans for the summer. I have two trainings a week, both in the evenings and some matches that always take place on Saturdays and Sundays.

The timeline is here: http://wiki.wesnoth.org/index.php?title=SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Timeline

AI improvement: there are some AI improvements proposed by Crab_ in his idea page, but those are not obligatory to be done. Instead, he said he welcomes discussion about interesting ideas in the AI field.

4.5) Include as much technical detail about your implementation as you can
The "Brain": http://wiki.wesnoth.org/index.php?title=SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Project
One of the ideas I wanted to implement myself, was creating a "brain" for Wesnoth. The "brain" would be a horribly sophisticated data structure that could help the RCA AI evaluate candidate moves. The "brain" would "think" in a different thread and answer to RCA requests depending on the current state. While the player makes his moves, the "brain" would constantly rebalance itself by doing positional and discrete analysis. The positional analysis would allow the AI to have a plan, and that would make it much more stronger than it is now. Discrete analysis is a bad solution for Wesnoth, because it would take forever to calculate even a small part of the possible moves, but if we have a pre-planned position the discrete analysis would boost it, find the holes in it and patch them up.
4.6) What do you expect to gain from this project?
Tons of experience, friends and confidence in my programming skills. The stipend is also very tempting, since I study abroad and life in Glasgow is much more expensive that in Latvia. It would help me concentrate on my studies and think less about part time jobs and other money matters.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
Instead of answering this question directly, I will tell you what would make me leave the Wesnoth community :) I would leave if senior devs would reject my ideas and proposals. Wesnoth is a perfect project for aspiring developers to try out their skills. My numerous ideas for the AI are impossible to implement during one summer, and since I have a lot of free time during my studies at University, I will most certainly continue making the AI more powerful than it is at the moment in autumn, winter and spring(or even this summer, if I don't get accepted :D)

Practical considerations
5.1) Are you familiar with any of the following tools or languages?

Subversion (used for all commits) -- I have used Mercurial for my work and I doubt that I will not be able to use SVN after reading the manual

C++ (language used for all the normal source code) -- I took a course on C++, read books on it and still have a lot to learn there. My favorite language.

STL, Boost, Sdl (C++ libraries used by Wesnoth) -- STL is used in all my projects, therefore I can find my way around it. I haven't used Boost a lot, but remember refactoring a peace of code that used it extensively. Again, nothing is impossible, while we have the manuals. I used SDL only once, for a simple ping-pong game, know the basic concepts, but don't think that this library is at all relevant to AI development.

Python (optional, mainly used for tools) -- took a course on python and currently finished studying it at university. Not a fan of it, but it's very useful in some cases, when you have to write something small, fast, inefficient, insecure...(j.k. everything depends on the developer)

build environments (eg cmake/scons) -- didn't have experience with such before, but successfully compiled Wesnoth in Linux and Windows(windows was a pain, but the solution was out there)...

WML (the wesnoth specific scenario language) -- not at all, yet. Hopefully it isn't a big problem, there still is time to learn.

Lua (used in combination with WML to create scenarios) -- learnt Lua in the beginning of March, after talking with Wesnoth's crew for the first time.
5.2) Which tools do you normally use for development? Why do you use them?
I like to use simple IDE's, not overstuffed with tools. I used Dev-C++ for a long time, but it had problems, that's why I transfered to Code::Blocks, which seems like a fine IDE to me atm. For Wesnoth I use MSVC9, because it is easy to compile Wesnoth in it and it also seems comfortable. I prefer Linux for development, but don't have a possibility to use a Linux machine.
5.3) What programming languages are you fluent in?
C/C++ - constantly use them and try to deepen my knowledge on every occasion.
Pascal - my first language, which I was taught to program in.
Python - fluent, but not a fan.
Java - basic knowledge, am able to create small simple applications, with a simple GUI.
PHP - used for work on a social network, don't like it, though.
Other languages are not worth mentioning.

5.4) Would you mind talking with your mentor on telephone / internet phone?
No, not at all. I do not have a phone number in Latvia at the moment, but I will post one here as soon as I get one.

SummerOfCodeProposal LuaAI Improvement Nephro

Contents