User:Dragos/GsoC 2013/AI: Implement a 'total defense' strategy

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

Note

This application is a draft and it will be subject to changes.

Description

Dragos Ristache: Implement a total defense strategy

I intend to implement a total defense strategy for the Wesnoth AI. Currently the Wesnoth AI is really good at doing attacks but it's not that good at defending. The AI currently tries to maximize the formula (enemy losses - aggression*own_losses), which can't generate a defending behavior making it easy to defeat in certain situation.

IRC

dragos

Project

Make the AI do a ‘full retreat’

One idea that would make the AI defend better is to make a good method for the AI to retreat in certain situations (bad time of day and so on). This can be implemented as a candidate action or a stage action.

Analyzing the next turn

Taking into account what the enemy can do in their next turn (the enemy counter-attack) when the AI decides where and what to attack can help the defense.

This change can go as far as refactoring the combat evaluation code so it will be easier to change how the attacks are rated.

Grouping the units

Currently when the aggression ( in the attack formula that maximizes (enemy losses - aggression*own_losses)) is set to 0 the AI only makes ‘good attacks’. We could force the units when they cannot find a good attack to group with the other units on the front line and stand united. Grouping the units has simple advantages, such as less overall surface area the enemy can attack from and stronger attacks.

Using support units

We can start using the support units more in the attack. If they do not have good attacks we should use them to help the weakest points of the defensive wall.

Testing

The changes will need extensive tests. We will need tests against AI and against real players so we can be sure the AI improves overall effectiveness and to be 100% sure we leave no loopholes that will make the AI easy to trick/defeat.

Note: Implementing even only a couple of these ideas can solve the problem so we will make the aggression close to 0. Also in the development of the defense, it will be possible to find other ( even more useful) way of making the defense better.

Questionnaire

Basics

Write a small introduction to yourself.

My name is Dragos Florian Ristache, and I am 20 years old. I have been a Computer Science student for a semester at Jacobs University Bremen, and starting this fall, I will study Computer Science at the University of Southampton. I have been working in C++ and participating in numerous competitions since the 9th grade (so for around 5 years).

In the later years I started working with other languages and technologies (Python/C#).

State your preferred email address.

drasisu [at] yahoo [dot] com

or

ristachedragos [at] gmail [dot] com

If you have chosen a nick for IRC and Wesnoth forums, what is it?

dragos on the forum and the IRC.

Why do you want to participate in summer of code?

I think summer of code is the perfect way to gain a lot of practical experience. In addition, working at big project will also help my programming and thinkings skills.

Because I’ve been participating and training for many competitions in high school I haven’t had the chance to focus on the practical part of Computer Science and I think this would be the perfect chance to do so.

What are you studying, subject, level and school?

I will be studying Computer Science, starting this fall at University of Southampton.

(note* This year, I’ve studied a semester at Jacobs University Bremen. I have also had the chance to take many online courses during the ‘gap’ semester. The two most important I would like to mention would be: Berkley’s Introduction to Artificial Intelligence and Caltech’s Machine Learning course)

What country are you from, at what time are you most likely to be able to join IRC?

I’m from Romania and will mostly be available from 7 am to 7 pm GMT.

Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

I do not have any commitments or vacations planned so far.

Experience

What programs/software have you worked on before?

I’ve only worked at small individual projects.

Have you developed software in a team environment before? (As opposed to hacking on something on your own)

I haven’t developed software on my own, but on numerous occasions I’ve worked in team environments at Computer Science competitions. This competitions ranged between 5 hours to months and this is one of the main reasons I believe I work well in a team environment.

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?

No, I haven’t participated before.

Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

No, this would be my first open source development project.

Gaming experience - Are you a gamer?

Yes, I do consider myself a gamer. I also think that this is one of the main reasons I chose this project (and even why I started studying computer science)

What type of gamer are you?

I consider myself a competitive gamer in some regards. When I find a game that is at the same time challenging and fun I usually invest a lot of time at getting really good at the said game.

What type of games?

I generally play all types of games. I really like strategy games ( I constantly play Starcraft 2 for example). RPG are one of my favorite types, the same can be said about shooters and puzzle games.

What type of opponents do you prefer?

I usually prefer challenging opponents and I like it when the game has a high difficulty.

Are you more interested in story or gameplay?

When I’m playing a game I’m usually interested in both, with a little inclination to story, but when I analyze a game and decide if I should keep playing or not, the gameplay is the biggest factor.

Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

I’ve been playing Wesnoth for a couple of weeks. I’m inclined to play the single player mainly because of the AI.

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.

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.

I’ve worked on 3 “demo-patches” as instructed by Crab_.

1. I’ve created a lua function to display a label over each hex.

2. I’ve also created a mirror recruit for the AI in C++. This is in case the AI is playing a 1v1 against the same race. Using this function the AI will recruit the exact units the enemy recruited.

3. I’ve created a naive retreat function. When used the AI units will start retreating away from the enemies and to the safest positions on the map.

Communication skills

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 studied one year at an international high school and semester at an international university (where the teaching and working language was English). I also scored a 110 (out of 120) on the TOEFL iBT. Those are the main reasons I consider myself good at written english.

What spoken languages are you fluent in?

Romanian and English.

Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.

I occasionally spend the time on internet forums discussing strategies or other game related information so yes, I would consider myself good at interacting with other players.

Do you give constructive advice?

When I have the necessary knowledge to give someone advice, I do.

Do you receive advice well?

Yes! I think advice from other people is one of the best ways to grow as a programmer and as a person.

Are you good at sorting useful criticisms from useless ones?

When I reach a high enough level at something to have an outline on what areas I need improving and what areas I reached a ‘good enough’ level for my task I am able to sort useful from useless criticism.

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

This depends on what stage I am at learning the code base. When I just want to learn how everything works and how everything is structured I will probably just code a proof of concept, but when I gained enough information about the project I think well ahead of the code I write, as to not waste time.

Project

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’ve selected improving the AI, more specifically implementing a ‘total defense’ strategy.

Why did you choose this project?

This project combines thinking of a solution (and I consider that this will probably be the hardest part in this project) with working at a good implementation. I think that this mix of practical and theoretical work is perfect for my skills.

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

Time Frame	Milestone
14 June - 23 June (10 days)	Implementing the full retreat function and testing formulas for the positions
24 June - 27 June (4 days)	Testing the full retreat and analyzing the available formulas to choose the best one
28 June - 10 July (14 days)	Writing an algorithm to make the units group themselves when necessary
11 July - 14 July (4 days)	Testing the grouping algorithm
15 July - 4 August (21 days)	Refactoring combat evaluation code and working to take into account the next turn. (In this period I will also prepare for the midterm evaluation)
5 August- 8 August (4 days)	Testing the next turn and the modifications to the combat evaluation
9 August- 23 August (15 days)	Adding better usage for support units
24 August - 24 August (1 day)	Testing the support units individually and all together
25 August - 10 September (17 days)	Implementing ideas that may come during the time I work on the project. If there aren’t any new ideas I will reallocate the time as necessary (See notes 1 and 3)
11 September - 23 September (13 days)	Extensive testing of all the ideas applied together, with help from Wesnoth players (if possible), preparing for the final evaluation, writing necessary documentation
After SOC (PLAN)	Continue working for Wesnoth

Notes:

1. I’ve allocated some time from 25 August to 10 September to implement new ideas if they come. In the case that I have no other ideas, I will reallocate the time for the ideas that need it more and/or I will have an after midterm testing phase, like the one at the end of the project (Note 3).

2. After each implementation, I will use a couple of days to test the implementation formula and to search for bugs. The last testing phase, that takes a week, will test all the combined ideas working together to see how the AI behaves. This testing phase will (hopefully) be done by me and other people from the Wesnoth community. I hope the last testing phase will help tweak the existing ideas, to make them perform even better.

3. There is a possibility to add a similar testing phase after the midterm evaluation, to see if we need to focus more time on some aspects of the project. I emphasized so much on testing because I believe that it’s hard to predict how the AI will act while developing it.

What do you expect to gain from this project?

Working at a project like Wesnoth will provide invaluable experience. Working at this will also expand my practical knowledge of AI and algorithms. Also, I’m sure that this Summer of Code will prepare me for working in the future for open-source organisations and programs. (I always felt that I wanted to work for an open-source project, but lacked the guidance and a clear goal)

What would make you stay in the Wesnoth community after the conclusion of SOC?

I plan to continue coding for Wesnoth after the SOC. I believe that continually working for an open-source project offers both individual benefits and, especially, benefits for the community.

Practical considerations

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

   Git (used for all commits)

I’ve used Git a couple of times and I am somewhat familiar

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

I’ve been working in C++ for around 5 years, so I would consider myself good at it

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

I’ve been using STL for a long time but I only have minimal experience with Boost and Sdl/

  Python (optional, mainly used for tools)

I’ve worked with Python numerous types so I find myself familiar with the language

   build environments (eg cmake/scons)

I used scons and cmake in the weeks before the applications

   WML (the wesnoth specific scenario language)

Minimal experience

   Lua (used in combination with WML to create scenarios)

While working on a demo-patch for wesnoth I learned a bit of Lua and LuaAI

Which tools do you normally use for development? Why do you use them?

I mainly use Code::Blocks and Eclipse. I use Code::Blocks because it suited my needs in high school while programming for competitions and I started using Eclipse because it helped me in some projects I worked on. (But for Wesnoth I only used Code::Blocks)

What programming languages are you fluent in?

I worked in C/C++,C# and Python. I consider that I know C/C++ at a high level and Python/C# at a medium-level.

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!

In general, students should be as verbose as possible in their answers and feel free to elaborate.

I agree and will add my phone number in the google application.