User:PL kolek

This page is related to Summer of Code 2013

See the list of Summer of Code 2013 Ideas

This is a Summer of Code 2013 student page

WARNING: Unfinished

Description

PL_kolek - AI 'total defense strategy'

My goal is to make AI play more cautiously. Currently it only tries to kill as many units as possible without taking into account possible enemy moves. I'm going to build into the current algorithm some mechanism to improve AI behavious, that connected together would boost it's thinking great boost.

IRC

PL_kolek, PL_kolek_, PL_kolek__, PL_kolek___

The project

Introduction

How complicated wesnoth AI is everyone knows. But there is no single recipe how to improve its behaviour. My plan is to incorporate into current RCA AI several mechanisms, that, working together, will make it better opponent. Predicting damage dealt in the next turn wouldn't give much advantage if used separately, but it's a bulding block of forming defensive lines, which can be programmed as Candidate Action. There is also one mechanism, that is required to devise working AI: statistics.

General picture

I'd like to combine several parts into a working mechanism.

1. AI should have a way to judge it's movements not only by damage dealt and taken in its turn, but also in enemy's response. This is done with some heuristics described later.

2. Damage is not only target to achieve. We must protect our villages, don't let enemy get on our back. This evaluation is done with movement evaluation heuristics. (Described later too).

Those point will make the AI play more cautiously without artificial use of 'aggression' parameter (it's meaaning is to tell how aggressive AI is, not forcing it to simulate playing defensively). But they're also needed to get the next points to work:

3. Moving units 'together'. One unit at a time is a huge limitation. Without previous 2 points it's hard to judge whether move made by 3 units in conjuction is better then moving them separately. But now we can calculate the result (our_losses-enemy_losses) in both scenarios and choose better option.

4. With those tools writing CAs for typical human defensive behaviours line forming a wall should be simpler and effective. Everything is in place and the AI can make smart choices.

There are two additional tasks not directly related to AI, but required for it to work:

5. Logging every possible data. Tuning the AI requires lots of experiments, and I must be able to gather data from them.

6. WML configuration tags. If everything works, why not let the user change the way it works?

Heuristics to evaluate enemy response

First and most important step in making AI smarter is teaching it to take into account enemy actions in the following turn (by turn I mean what happens direcly after I click 'end turn'). In a perfect world that would suffice - we could even learn from the computer new tactics for ideal balance between my and enemy losses. But we all know that Wesnoth game tree branches so quick, that PCs cannot even check all it's possible moves, not to mention the next level of the tree. For those reasons we need to quickly evaluate our losses in enemy's turn.

Basic concepts

Damage estimation

Input: Position after our move
Output: Damage dealt and taken in next turn/score
How it works: Simulates an enemy turn in a very simplified manner and produces outcome.
NOTE: This way will always get score not higher than the perfect player could achieve. Moreover, the simpler our heuristic is, the lower score is expected. 

Iterative damage estimation

Input: Current position and it's score (damage dealt and taken during enemy's moves), selected move
Output: Damage dealt and taken in next turn/score
How it works: Recalculates the parts affected by the move, greatly (?) lowering the complexity
NOTE: This way will always get score not higher than the perfect player could achieve. Moreover, the simpler our heuristic is, the lower score is expected.
NOTE 2: I don't know if that's possible to achieve, but it's desired.

Estimation constant

After making lot's of experiments, I'll find out how much the calculated damage differs from close-to-real outcome. This contant is meant to balance that, it's the ratio from my experiments. How it differs from 'aggression'? Aggression is set because we know that the AI is stupid and we don't want it to commit suicide with every move. However, if used in situation it was devised for, it tells how to value our units in respect to enemy unit during attack. By contrast, estimation constant doesn't affect AI's thinking in some any way, just helps it calculate the correct value of required parameter. I'll let the user decide (if he REALLY wants to) what should be the value of that, but most of the time, this shouldn't be touched (apart from situation, where someone wrrites new heuristic for enemy response).

Exemplary estimation algoriths

Simulate enemy turn

Simplify a lot CAs, cut out not needed and play it! Simple idea, providing that AI is really good at killing things, the results will be accurate. But... the CPU will burn. With some work, maybe on little 1 vs 1 maps it would work.

Furthest first heuristic

Order units from the farthest, choose best attack possible, evaluate outcome. The order is chosen that way, so that no unit will be blocked from its attack by other units having more possibilities.

Random order heuristic

Choose order of units randomly, simulate, calculate result. Repeat a few times and take the worst case scenario. If the evaluation is quick, it may be repeated many times (controllable by [random_evaluation_repetitions] tag).

Simplification

In case all the mentioned heuristics are too slow and each AI's turn requires the user to go make a coffee just not to be bored, we will need to another mechanism to better that up. Note: I don't plan them to be too slow. However, that idea is simple and might give good results, and can always be used as fallback if the scenario involves many units. Also, it's always good to have plan B.

Tetris minigame

Just make the user do something without turning wesnoth off. That's a joke (<- and that's unnecessary statement).

Important points

Maybe that doesn't make sense to evaluate whole enemy's turn with every our planned move? Why should we consider attacks on units that haven't moved yet? Or we can assume this full hp dwarven defender won't die and skip it in calculations?

General idea: Identify units that we must protect: heavily wounded, leader and run estimation that consider's only them. Most of our losses come from units that can can be killed in one, two attacks, so protecting them is a good tactic. If the enemy heavily focuses on one unit, we wouldn't have prevented it in any way (in most situations).

Curtailing enemy movements

Damage is only one of the parameters we need to take into account. Next one is how our choice affects enemy possibility to make actions. Basically the less hexes he can reach the better. The more our move limits the enemy, the higher it's score is. I hope this would make AI catch the enemy between two of its units naturally, without special CA for that. Moreover, every time we prevent the enemy from reaching our/neutral/his village (leader, unit, etc.) it will be reflected in higher score for that move.

Sketch of algorithm

Input: Position and move
Output: Score for limiting enemy actions
How it works:
 For every enemy unit check it's reachable hexes:
  add to score the hex value
 Return difference between currect and previous score

Scoring

Empty hex: 1 point for each 10% of defense on it
His village: 10 points
Neutral village: 20 points
My village: 30 points
Allied leader: 20 points

Note: This'll be adjusted while working on that part.

Connecting moves together

Because of complexity, thinking of turns in terms of moving all units at once is impossible. To simplify calculations, RCA AI takes unit after unit, move after move and considers them in separation (roughly speaking). It considers more units at once when it attacks, but that's mechanism to focus on one defender and it doesn't give more. While it decreases complexity exponentially, it makes is impossible to think about setting up a wall, backstabbing and so on. Furthermore, every CA requires a global plan and coordination of units. For example:

1. Attacking with first unit in a turn usually means that at a first glance, that unit will die according to our evaluation:

Our unit is in line with other units, can't be killed.
We assign some score.
It moves, attacks, takes some damage and is alone in the front.
Evaluate. The result is: some damage dealt, one more unit lost.

But if we could think a little more, we would notice that our next moves will bring the rest of army together, protecting that lonely unit.

2. Forming a defensive line. First unit doesn't give us anything - neither it deals massive damage, nor it protects injured friend in the village. The second and third will form an impassable wall.

3. Backstabbing. There is no point in attackimg a full health enemy protected from sides. Taking into account second move - backstab, it turns out that it was profitable.

Possible solutions to that problem: -Give higher scores to CAs in range of many friendly units which haven't moved yet. That solves (1.).

-Add specific CAs just specific group moves. With mechanisms decribed earlier, such CAs should be easy to write and easy to evaluate. There is not that much such tactics, and that would be sufficient.

-Refactor AI and allow it to move units in small groups. For example the AI would consider 3 adjacent units, plan a move for them together, then separately and choose better option. This will require to devise special algorithms for choosing units which should go to one group. That's hardest of the solutions.

Notice the difference between second and third solution. Second involves only special situations with specific units. The third is a general modification in AI thinking and can be used in any circumstance, and that's what makes it complicated.

WML parameters

New AI behaviour involves many new tunable parameters. For example: putting the blocks mentioned earlier together requires many appropiate weights for each behaviour. We wouldn't like to have AI focused on blocking enemy movements more than killing or defending wounded units, would we? I'd like to expose them in WML for scenario creators, so that AI can behave differently in every scenario, or in case defaults don't fit this particular use case. For example:

[ai]
 ...
 prevent_enemy_moves=2
[ai]

Value indicating how focused the AI should be on limiting enemy's movement choices.

[ai]
 ...
 max_group_size=3
[ai]

If the AI considers the units in groups, how big should the groups be.

[ai]
 ...
 [damage_evaluation]
  engine=lua
  name=example
  evaluation="return rand()"
 [/damage_evaluation]
[/ai]

[ai]
 ...
 damage_evaluation="simulate_enemy_turn"
[/ai]

This way scenario creator could choose more accurate (but computation heavy) algorithm in small scenario and lightweight (but less accurate) for bigger ones. He can even write with Lua his own function for some specific purpose.

[ai]
 ...
 [iterative_damage_evaluation]
  engine=lua
  name=iterative_example
  evaluation="return rand()"
 [/iterative_damage_evaluation]
[/ai]
iterative_damage_evaluation="some_cool_iterative_algorithm"

That's the tag for functionality I described before. If it turns out that it's not possible, I'll drop that tag.

[ai]
 ...
 estimation_constant=1.5
[/ai]

That's exactly the parameter I described earlier.

Of course these are just examples, but in principle I'd like the new AI to be as versatile and configurable as possible, so every parameter I encounter during coding will be exposed to scenario creators. They'll be optional, with rational default values chosen.

Statistics logging

Algorithms play a big role in my project and generally in AI, but it won't work without lots of experimentation, tuning and tweaking. Every constant, unit value and so on needs to be set carefully to ensure proper behaviour. For that I'll need a logging system to gather all important information, that I can then plot and analyse.

Exemplary data to gather

-Estimated enemy damage

-Enemy damage - what harm the enemy caused in reality.

-Group move value - how we estimated value of chosen move of group of units.

-Separate move value - as before, but for moves made separately.

Prototype

http://pastebin.com/XDghMJY5

I implemented a dirty prototype, which currently is slow and doesn't give real advantage to AI utilising it. That's because I plugged it only into attack CA and it's only one component of the whole system. Moreover I didn't play with any constants - it can't work in real usecase. But... I also created a test scenario to show that evaluation can have and has effect on strategy.

Picture on the left shows starting situation. AI being tested is red and it moves now. If it does nothing, the cavalryman can attack level 3 Dwarf and kill it with one hit. Who wants to lose such a powerful unit that can heal itself in the village? The only way to prevent that is to move that little dwarven defender on the hex between the horse and our 1HP unit (precisely, it's not the only way - for example we could run away with this lvl 3 unit, but the best way).

What does default AI do (middle screenshot)? When it chooses attack option for level 1 dwarf, it analyses reachable hexes next to cavalryman and decides to move on the mountains - it guarantees best defense and minimal losses in retaliation. Of course - it also guarantees big losses next turn.

What does my prototype do (right one)? It calculates for every adjacent hex possible losses next turn, and decides to risk more damage on the grass to protect wounded unit. Success!

Timeline

May 3 - May 27 (pre-GSoC)

• Further improve proposal
• Dig deeper into the AI and AI code
• Try to implement simple ideas as a training

May 27 - June 17 (community bonding period)

• Get into details of the AI
• Exams at the university
• Start coding

June 17 - July 25

• Writing movement and damage evaluation heuristics
• Integrating some log for easy comparison of AI algorithms

July 25 - August 2 (midterm evaluation)

• Test, test, test
• Find out magic constants
• Resolve any issues

August 2 - August 31

• Implementing CAs for walls, backstabs, retreats, etc...
• Heuristics for taking into account other moves

September 1 - September 16

• Test, test, test
• Improve code, so that it can be merged into master
• Tweaking and benchmarking the AI

September 16 - September 27 (final evaluation)

• Stop playing around, polish to state of 100% finished product
• Write documentation.
• Update wiki pages.

Any time left if I finish earlier than planned

• Do something with the wiki. Something means: navigation, write/update tutorials on writing AI, etc.

Goals / Milestones

Note: Optional goals are goals that I really want to do, and are optional, because I can resign of them if the more important things will take too much time. I plan to implement them though. Moreover, I am sure, that more optional ideas will come to my mind while working on the project and will be added here (and implemented, I hope).

ID	PRIORITY	DESCRIPTION	PROGRESS
1	MANDATORY	Learn everything current AI and plan where to change it	Somewhere in the middle
2	OPTIONAL	Implement simplified version of some ideas decribed here	One hacky heuristic implemented
3	OPTIONAL	Analyze current work on Fred AI, decide how much of this can be used in the project.
4	MANDATORY	Use results of previous steps to detail and improve proposal as much as possible.	Devised plan B for heuristics
-	MILESTONE 0	Have all mandatory steps and at least one optional above done when the coding period starts (Jun 16)
5	MANDATORY	Write one good and general heuristic calculating estimated value of enemy's damage dealt.
6	OPTIONAL	Write other heuristics (fast, randomised, precise) for that purspose.
7	MANDATORY	Write one good and general heuristic calculating estimated value of enemy's possible moves.
8	OPTIONAL	Write other heuristics (fast, randomised, precise) for that purspose.
9	OPTIONAL	Add possibility for users to choose and implement their own heuristics (WML)
10	MANDATORY	Implement logging of important AI statistics and results.
11	MANDATORY	Experiment a lot and choose best values for all involved parameters.
11	OPTIONAL	Let the user configure those parameters in WML
-	MILESTONE 1	Have at least all mandatory steps above done until August 2.
12	MANDATORY	Add support for group Candidate Actions
13	MANDATORY	Implement Canditate Actions for group moves like backstab, defensive wall etc..
14	MANDATORY	Revisit all Canditate Actions, change scoring if necessary, so that it becomes comparable with group CAs
15	OPTIONAL	Allow AI to think in terms of groups of units in general, any case, not only in those specific CAs
16	MANDATORY	Experiment a lot and choose best values for all involved parameters.
17	OPTIONAL	Let the user configure those parameters in WML
-	MILESTONE 2	Have at least all mandatory steps above done until Sep 9
18	MANDATORY	Clean up the code
19	MANDATORY	Benchmark, optimise, compare performance with previous AI
20	MANDATORY	Write documentation
21	MANDATORY	Update/add wiki pages with detailed and friendly description
22	MANDATORY	Test, Test, Test
-	MILESTONE 3	Have at least all mandatory steps above done until Sep 23.
-	OPTIONAL	If everything is done before the end time, improve wiki
-	SUPER OPTIONAL	Write minigame for enemy's turns

Questionnaire

1) Basics

1.1) Write a small introduction to yourself. My name is Mateusz Kolaczek, I come from Poland and because other general information can be found in the following answers I'll try to be less generic. I have recently discovered that I sometimes prefer programming to gaming, that's sad. On the other, I can now write games, and that's one level higher. I'd be relieved if I could just stay at home all the summer and code for Wesnoth. But seriously, full time job for this summer developing my favourite turn-based strategy game is my short-term dream ;).

1.2) State your preferred email address. mateusz.kolaczek@gmail.com 1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it? PL_kolek 1.4) Why do you want to participate in summer of code? This definitely sounds like the best idea to work during summer and get some coding experience. I've always thought of joining an open-source project, but I didn't know how to start. GSoC motivated me to make the first steps to Wesnoth development (reading through the code, some easy-coding task). Now, being accepted means that I can spend my time, that I'd otherwise use to something else, contributing to not only open-source project, but also to my favourite turn-based strategy game. I could do it full-time, because I wouldn't have to worry about the money. 1.5) What are you studying, subject, level and school? Computer Science, 3rd year bachelor level, University of Wroclaw. 1.6) What country are you from, at what time are you most likely to be able to join IRC? I'm from Poland. Most likely at the afternoon (GMT+1), but I often just sit at the IRC much longer. That means: whenever I have access to the computer and some spare time. During summer: most of the time. 1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when. No, if I get a chance to work for wesnoth team, I won't have any commitments. Vacations? Not sure now, but if yes, then one, two weeks at the end of Semptember. (Pencils down!)

2) Experience

2.1) What programs/software have you worked on before? Bigger and smaller programming tasks at the university and for myself. Last semester I worked on flight simulator (hard to get the physics into a working state) and now I work with my girlfriend on an indie platformer game. I enjoy that really much.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own) Mentioned before flight simulator was written by around 10 people. Unfortunately, half of them resigned in the middle, but group of 5 is still a team, isn't it? For clarity, I didn't resign :).

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? It's my first time, I hope not last.

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've always thought of that. Some time ago I looked into joining OpenMW, but I didn't have enough time for that. GSoC gave me a big push.

2.5) Gaming experience - Are you a gamer? Is that question really here? I've played games since I was five. But recently, as I code more, I play less and both things enjoy equally.

2.5.1) What type of gamer are you? No rush, check everything. this way Morrowind took me a few months to finish (of course you can never say that this game is over). Moreover - I prefer indie games over AAA titles. If the game astonishes me with brilliant ideas, I'll not bother to look at the graphics.

2.5.2) What type of games? Puzzle, point'n'click, shooters, platformers, RPGs, strategies. Erm... every type of game. I play games, not genres.

2.5.3) What type of opponents do you prefer? Playing against (or cooperating with) humans is more attractive and

and feels genuine, but single player games allow the creators develop 
a story or setting impossible in any multiplayer world.

2.5.4) Are you more interested in story or gameplay? Both. But... Games, that are more like movies than interactive applications should be shown in cinemas, not sold in computer stores (Dreamfall, argh!).

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer. We do not plan to favor Wesnoth players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively. I played about half of the mainline campaigns and some hot seat games. Without any doubt, the multiplayer skirmish is an experience incomparable with anything, requires a lot of thinking and is like Heroes battle fought between two powerful heroes with huge armies. But unlike Heroes, it happens all the time, not once during whole scenario. Campaigns? I played them, when no real person around me felt like trying new game with 2D graphics (don't ask me how it that possible). The idea of recalls, while satisfying at first glance, becomes frustrating in the middle of long campaign. As far as I remember, South Guard hit the sweet spot, but it's still level lower than multiplayer.

If both of the AI project are finished, I'll replay campaigns to check how it changed them.

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 repository (during the evaluation period or earlier) please state so.

https://gna.org/patch/?3884

https://gna.org/patch/?3846 - not finished, I have to discuss it

https://gna.org/patch/?3905

As a training (and a proof that I can use Lua and write simple AI) I wrote recruitment routine, that mirrors enemy's army.

http://pastebin.com/J5DMXqtB

3) 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.

3.2) What spoken languages are you fluent in? No trouble in reading anything written in English, communicating on IRC or the forums wouldn't pose me a problem either.

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough. Honestly, I don't know what the question is about, but if somebody's friendly, I am so too. If somebody is rude (without any constructive claims), I just ignore him. that means: I'm not the flame war guy.

3.4) Do you give constructive advice? I try as hard as I can if I feel like I can help someone.

3.5) Do you receive advice well? Yes, it's somehow pleasant to find out how to do something better.

3.6) Are you good at sorting useful criticisms from useless ones? That's the whole point of using forums or other social services. You must be prepared for lots of mess flying around and must find any useful information inside.

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 stay in the middle - think a lot about the idea, structure, design, then try it out and change according to results. So I discuss the changes to some point, gather required information and start coding.

4) 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 chose defensive AI. I'd like to concentrate on estimating enemy response and maximining enemy_losses-my_losses during one turn.

4.2) If you have invented your own project, please describe the project and the scope. Sorry, I can't answer this question :(.

4.3) Why did you choose this project? AI sounds fascinating and is adequately thrilling, when I see the computer doing what I taught it. The changes this project offers can better the experience both for players and developers. Current AI for sure fits for the description 'good at killing, that's all' ;). Moreover, writing a server never sounds like fun.

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 wrote it in the timeline and milestones.

4.5) Include as much technical detail about your implementation as you can Again?

4.6) What do you expect to gain from this project? Money, money, money, money and money. Just kidding. Experience in LUA, C++. I'll be familiar with working on big project with many people. Joining wesnoth community. Joining open-source in a more meaningful way that installing Linux. And, what's best, I could show everyone: that's what I did for this game. Cool, isn't it?

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC? The correct answer is: What would prevent you from staying in the Wesnoth community after the conclusion of SOC? That'd be sad - improve AI a lot and then forget.

5) Practical considerations

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

• Git (used for all commits)

Novice level, I know the basics.

• C++ (language used for all the normal source code)

Is there anyone in the world that can say: I know C++? It has so many strange features, that for sure Bjarne Stroustrup forgot what he wrote years ago. But with enough time and internet I could write anything with it, and learning new tricks is always satisfying.

• STL, Boost, Sdl (C++ libraries used by Wesnoth)

I use first two in my game, and used SDL in a game written 2 years ago for an assignment. Though, I've seen only parts of Boost, seems powerful.

• Python (optional, mainly used for tools)

Nope, but people on the street keep talking that it's the most convenient language instead of going shopping, so if I need it, I'll learn it quickly.

• build environments (eg cmake/scons)

Compiled wesnoth using cmake, that's all. But internet is full of materials, and I can read ;).

• WML (the wesnoth specific scenario language)

I encountered it on my way to write this application. I don't know more than I know, but I'm familiar with the concept and can use it.

• Lua (used in combination with WML to create scenarios)

Apart from coding that mirror AI mentioned before, I have never used. But if I could write that AI during one or two hours, it must not be hard.

5.2) Which tools do you normally use for development? Why do you use them? Simple tasks (one few source files): Geany+Make. It's very simple, one button to compile, second to run, just the functionality I need and nothing more.

Anything bigger in compatible language: Netbeans. Very good autocompletion, formatting, managing big project, support for more than I need. (Once I tried Eclipse and didn't like it that much).

PS: I hope that vim is not required apart from generating infite random character sequences trying to quit it? :P

5.3) What programming languages are you fluent in? C/C++, Java, JavaScript. I used Prolog, Haskell and assembler but I don't remeber enough to say that I'm fluent in it.

And I don't know if that's just me or there is something in it, but despite Java being clearer, simpler and more convenient, C++ is my favourite.

5.4) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise! No problem.