SummerOfCodeProposal AI Improvement Crab

Hello

My name is Yurii, My nick on IRC is Crab_, my nick on forum/wiki is Crab, on gna - crab.

terraninfo АТ terraninfo.net

Proposal Summary

I would like to make the Wesnoth AI better.

I've looked through the trunk code (FormulaAI and regular AI)
Now, with a better understanding of the current Wesnoth implementations, I would like to share my thoughts and ideas regarding the AI

Firstly, I'll state something that may be considered self-evident: the AI must know the rules of the game. It should know: - what actions are allowed by the game engine. - what are the consequences of these actions. It may be self-evident, but it is the reason why the current direction of FormulaAI development is wrong. For example, it is plain wrong to teach the AI that 'directing poisoning attacks at not poisoned units is a good thing'. It may be not a good thing in certain situation - for example, if there is a better move available on this turn or where is a good opportunity that may be available on next turn. For example, it may be better to move to protect own healer, or it may be better to move to grab the village instead, or to wait for the attacks of own units and see if there any low-hp targets worth killing to level-up faster. Or just do nothing and wait for the night to come. There are too many possible circumstances. If you want to do it with a formula - It would not work. It all starts simple, then some glitches are found, the formula is expanded to take this into account, ..., and, in the end - there will be a large pile of hacks floating around with subtle glitches. Thats really bad. And that's hard to tune for a scenario designer - not many scenario designers are well-prepared to debug formulaAI formulas. Instead, the AI should know how to evaluate the position, know the consequences of poisoning, and figure out good moves in itself. That's quite similar to database query planning - "if the specific query is planned wrong, do not constrain the planner's hand - instead, figure out why that is happening, and improve the planner's logic". It is good to let the AI figure something for itself. It is bad to tell the AI what to do (unless that is necessary for scenario or fluff purposes, that is). For all such instructions are, in fact, constraints on AI behavior, and they actually decrease it's long-term potency and efficiency. AI must KNOW the rules, SEE the position, EVALUATE the situation, and DECIDE on it's actions and EXPECT the outcoes (and it may re-decide its actions if the consequences of it's first actions are far from expected - for example, if the holy RNG decides that all 4 70% Archmage attacks are to be missed, it is not what was expected, and the situation may require re-evaluation. Or, if 4 30% attacks hit, it may create a target of opportunity not available before.

Such an AI, that KNOWS, SEE, EVALUATES, DECIDES, an EXPECTS is very easy to fool control :))) - in a good way, for scenario and fluff purposes. For example, a scenario editor may:

- change what AI KNOWS: for example, a scenario editor may tell the Orcs the false impression that forests are evil and give -50% defence for AI's units in them. Such an AI would (without any instructions or restrictions) try to avoid stepping in forests. For example, it can be done with a simple string "my.forest.defence.bonus=-50%" in scenario config. I think that the scenario designers will be delighted to have such a tool. This 'false information' inplanted in the AI by the scenario designer will not break the AI's - that's because such is the power of Wesnoth randomness - "Less then optimal decisions still have a chance of success"

- change what the AI SEES: for example, a scenario editor may make the AI ignore players units when the time of day is night.

- change how the AI EVALUATES what it sees: for example, a scenario editor may make the AI value certain scenario-important positions more.

- force the AI's DECISIONS: for example, a scenario editor may control some of the AI's unit movements for several turns

- change what the AI EXPECTS: for example, a scenario editor may make the Undead AI overoptimisic (that will make it somewhat risk-taking and agressive) at night.

The AI which I am proposing to construct, will run as a extendable decision loop (SEE what the situation is -> EVALUATE it -> DECIDE what to do-> EXECUTE and EXPECT some results -> return to SEE what actually happened -> ...) during its turn.

The task will be slightly easier because many trivial parts of it can be copypasted from current codebase. I'm preparing a small demonstration of such an AI at the moment (I'm highly specializing it to make it quickly)

Patches

I've already contributed some patches to make debugging easier and to fix some crashes related with FormulaAI.
[Bug 13218] - I've spotted and fixed an infinite loop (which hangs the game) in the AI if it persistently tries to move unit to occupied square, with a hint from Sirp and some help from Dragonking
[Bug 13230] - I've implemented one of the FormulaAI debugging-related suggestions on the EasyCoding page, under the guidance of boucman.
[Bug 13229] - I've fixed two small 'past-end-of-collection-dereference' bug in FormulaAI
[Patch 1136] -I've submitted a patch to fix a segfault in FormulaAI formula parser.
[Patch 1137] I've implemented FormulaAI function run_file - which adds ability to run .fai file directly from in-game console, which allows efficient debugging of the .fai files

My immediate work plans:
- improve FormulaAI console (I've already implemented the ability to run .fai files from the console, and I'm going to implement history and 'repeat-last-command' capabilities

 create a way to easily test the AIs in specified situations (I already know what is to be done, and I am preparing the detailed implementation plan at the moment - I want it to be reviewed by other AI Team members before I start to hack some code.)

Answers to those questions

---

Basics

Write a small introduction to yourself.
Hello. My name is Yurii Chernyi. I am 23, and I live in Kiev, Ukraine. I study applied math at the Faculty of Cybernetics, Kiev University.

1.2) State your preferred email address.
terraninfo АТ terraninfo.net

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?
IRC: Crab_
Wesnoth forums: Crab
Wesnoth wiki: Crab
GNA: crab

1.4) Why do you want to participate in summer of code?
I would like to make the world better and I've got some free time for this. I think that GSoC is a good opportunity to try to solve interesting problems.

1.5) What are you studying, subject, level and school?
Applied Mathematics, 6th year, Faculty of Cybernetics, Kiev University, Ukraine.

1.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 Wesnoth. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
Yes, I've contributed some patches and fixed some bugs. See My Patches

Experience

good practical knowlegge of C++, Java, computer science concepts, networking, system and database administration.

2.1) What programs/software have you worked on before?
Mostly, I've done website development using Java EE. Also, I've done various C++ projects in regarding numeric computations (for example, in computational fluid dynamics)

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)
Yes, I'm familiar to team development, and, at present, I coordinate a team of student developers for a small university project.

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?
I haven't participated in the GSoC before. This is my first and last (I graduate this year) chance to participate.

2.4) Open Source

2.4.1) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
I use a lot of open source, but Wesnoth is the first open source project I am involved with.

2.5) Gaming experience - Are you a gamer?
Yes, I am a gamer )

2.5.1) What type of gamer are you?
I'm not really sure what this question is about, but I'll try to answer: I prefer to think out a plan, and then execute it. So, according to http://www.quizilla.com/quizzes/result/532090/375850/, I'm a 'strategic gamer'.

2.5.2) What type of games?
I prefer strategy games, both turn-based and realtime.

2.5.3) What type of opponents do you prefer?
Those who play well and are challenging to beat. Those can be both human or computer players.

2.5.4) Are you more interested in story or gameplay?
It depends on gameplay. Some games are worth playing once - to see the story unfold. Some games are interesting to play even without the story :)

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.
yes, I've played Wesnoth, from version 1.4.2. I've finished all single-player campaigns that were in the base install, some of them several times on different difficulty levels. I've played a bit of multiplayer in hot seat mode.

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 I can read and write English quite well. This wiki page can serve as an example :)

3.2) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
That is yet to be seen, but I expect no problems. Being a player myself, I understand their desires )

3.3) Do you give constructive advice?
Yes, I personally think that I can give constructive advice.

3.4) Do you receive advice well?
Yes, especially if it is constructive :)

3.5) Are you good at sorting useful criticisms from useless ones?
Yes, I am.

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?
Yes, I looked through that list and I think it will be really hard and interesting to improve the AI (and the AI needs that improvement :) ).

4.2) If you have invented your own project, please describe the project and the scope.
My project is within the scope of 'improving AI and making it easier to tune its behavior' idea.

4.3) Why did you choose this project?
I want to make the AI feel more intelligent and I want it to be more fun to compete with. I would be happy to see Wesnoth with a better AI and I think I could make it better. Also, I want tweaking AI for specific scenarios to be a fun job, not a nightmarish formula debugging experience for scenario developers without programming background.

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".

+	Mar 19 - Mar 22	Familiarize myself with important parts of current Wesnoth AI code and Wesnoth way of doing things.
now	Mar 23 - Mar 31	familiarize myself with mentor and discuss implementation ideas and details. Also, work towards gaining svn commit access by improving those current AI code parts I'll need later, in particular - improve debugging capabilities. Also, To prove that I am able to write AIs, I will write an interesting working demonstration of the AI ideas I am trying to implement. I've already started doing it.
	April 1 - April 10	Write extended proposed AI redesign description, and write basic parts of it as an additional demonstration that underlying principles that I am proposing will really work.
	April 11 - April 20	Write a stub modular AI implementation and organize a convenient way to test it's abilities.
	April 21 - June 10	Redesign current AI and FormulaAI code, split them into layers with defined responsibility, make the code cleaner, modular, and simpler.
	June 11 - July 10	Improve the AI and make sure it is better that current AI.
	July 11 - August 10	Reflect on what is done and see what needs improvement, tune the AI for specific situations and scenario designer needs.
	August 11	"'pencils down' date. Take a week to scrub code, write tests, improve documentation, etc." (c) google
	Afterwards	- continue to improve the AI

I've got an unique opportunity to improve Wesnoth because I am a last year student and my exams are already over (they were in February-09), and I have no lectures to attend and almost none university work to do - that means I am 90% free to improve Wesnoth (remaining 10% being my teaching practice, coordinating the work of several student developeres, and working towards my diploma). I'm able to work on improving Wesnoth 6 days a week (remaining day being my Sunday D&D session - I've been a D&D DM for 9+ years.), and hacking some code for 12+ hours per day is the thing I love:) So, I can easily devote 48+ hours to Wesnoth each week, even now.

I will need this time because AI is quite hard to do right. But I am confident in my abilities and my determination.

4.5) Include as much technical detail about your implementation as you can
See My proposal summary

4.6) What do you expect to gain from this project?
Knowlegge that I have done a good thing, satisfaction playing a better Wesnoth, and a bit of money from Google (I can probably earn more if I would work elsewhere as a full-time developer, but programming for Wesnoth is much more fun :) ).

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
I will stay and continue to improve the game.

Practical considerations

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

* Subversion (used for all commits)
yes, both with command-line and gui.
* C++ (language used for all the normal source code)
yes
* Python (optional, mainly used for tools)
no, although I've worked with python code on several occasions and I can read it quite well.
* build environments (eg cmake/autotools/scons)
'make' - yes, 'scons' - learned a bit while looking at Wesnoth build system. 'autotools' - no, but I know its purpose and I think it will be easy for me to learn to use it, if it becomes necessary. Using scons is all that I needed so far to compile Wesnoth.

5.2) Which tools do you normally use for development? Why do you use them?
vi, gdb, find, fgrep, small shell scripts, Eclipse under GNU/Linux; Visual Studio and Eclipse under Windows. My work machine is a notebook running Debian GNU/Linux.

5.3) What programming languages are you fluent in?
I am fluent in Java (4+ years of experience) and C/C++ (4+ years of experience) I know a bit of php/perl/sh/sed/awk/javascript/pascal

5.4) What spoken languages are you fluent in?
I can speak in Ukrainian (native), in Russian (native), English.

5.5) At what hours are you awake and when will you be able to be in IRC (please specify in UTC)
I'm in UTC+2 timezone. I am normally awake from +10 UTC to +02 UTC, and most of that time I'm at home, so I'm able to be in IRC.

5.6) 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.
Of course, we can talk by phone.