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.
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
- fix current FormulaAI recruitment bugs

What I intend to to with the code:
I've looked through the trunk code (FormulaAI and regular AI) and I think there is a large room for improvement
Firstly, the current code doesn't have a clear separation of responsibilities between the core c++ ai engine, and between various FormulaAI parts. This leads to situation where incorrect AI desision can easily hang up or segfault the game (for example, I've recently found and patched an infinite loop in the AI if it persistently tried to move unit to occupied square). In my opinion, nothing that AI does, no matter how rare or stupid, should be able to lock up the game like this. Therefore, to ensure that such bugs don't sneak in, and to make a good and extensible AI, we must cleanly separate the following layers:

1) game rules library: decisions about what moves are allowed, what path will the unit take if it moves. Functions in this library should have no side effect.
2) game engine library: actually moving units, handling special cases like 'ambush', etc. this lib must delegate all rules decisions (eg. 'can I move there?') to [1]
3) core AI (should be rewritten in modular way in c++): core AI tasks. these must be modular and allow override using FormulaAI, this lib must delegate all rules decisions to [1], all actions - to [2]
4) AI extension library (formulaAI will be very good here): allow scenario creators to override and make *hints* to the core AI.

In current code those functions are interleaved together with some ugly hacks, and a clean-up is needed to make the current code more robust and extensible, and pave a road for further improvements. I believe that such a cleanup/refactoring/layering is well within the scope of a GSoC project. There will be enough time to do this, and, as a result, the AI subsystem will become simpler, easier to develop and debug, and more robust.

AI Part: What do I want to do about core AI tasks:
Firsty, Wesnoth is about tactical combat. Tactical combat involves skirmishes between small squads of units which work towards achieving small tactical goals, albeit chaotically (thanks to randomness of combat and the huge number of possible positions). A good AI must know how to achieve it's goals, which may be set by the scenario creator, using (to the best of its ability) forces already in the field and forces it may recruit. To do this we need the following:

1) the ability for the AI to intelligently select its tactical goals. Those goals may be overridden by scenario creators using FormulaAI.

2) the ability for the AI to intelligently form/recruit tactical squads to achieve those goals. A squad is a small group of units which will work towards a single goal. Squad composition may be overridden by scenario creators using FormulaAI.

3) the ability for the AI to move its squads into 'good enough' positions. Movement may be overridden by scenario creators using FormulaAI.

4) the ability for the AI to fight its battles well. Specific combat actions may be overridden by scenario creators using FormulaAI.

Additional requirements:

5) Scenario creators need the ability to specify\override AI using an easy-to-learn domain specific language.

6) AI must be modular with pluggable modules, to make enhancement and parallel development of the AI possible.

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

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,

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.

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.
No, not yet. I use a lot of open source, but I'm yet to contribute back.

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.

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.

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

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.

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.

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 - April 1 : Familiarize myself with current Wesnoth AI code, familiarize myself with mentor and discuss implementation ideas and details.
April 1 - April 10: Write proposed AI redesign description, and write basic function library
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

4.5) Include as much technical detail about your implementation as you can
I'm yet to study the current implementation in more detail, but I thint that Dave http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 has proposed a design that will be a good start.

4.6) What do you expect to gain from this project?
Knowlegge that I have done a good thing, satisfaction from playing a better Wesnoth, and a bit of money from Google.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
I will most probably stay.

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, 'autotools/scons' - no, but I know their purpose and I think it will be easy for me to learn to use them.

5.2) Which tools do you normally use for development? Why do you use them?
Eclipse under GNU/Linux, Visual Studio under Windows.

5.3) What programming languages are you fluent in?
I am fluent in Java and C/C++. I know a bit of php/perl/sh/javascript

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.