Latest revision as of 22:31, 22 May 2013

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

Description

Jeffrey Eldridge - AI: Implement a 'total defense' strategy

I believe that the defense of the AI can be improved by aiming to move units into the best position, instead of simply maximizing the number of losses the enemy takes. Assuming that the AI wants to actually hold and defend a position against the enemy (as opposed to just running away and minimizing its own losses), the best position would be the one that minimizes enemy presence in the defended area while also minimizing the amount of damage that can be done by the enemy to the AI's own units.

Detailed Description

Have tougher units protect more vulnerable units within the defended area

This would be done in 3 stages:

Minimize the number of enemy units that can get within attack range of vulnerable units.
Maximize space betwen vulnerable units and enemy units.
Move vulnerable units into a position that allows them maximum utility, provided that it is "safe".

The hope here is that these priorities would encourage the natural formation of "neat" battle lines. This would likely be best done with a Micro AI that represents several high scoring candidate actions, to perform these stages in the order that they are listed.

Identify "critical areas" within a total area that the AI wants to defend.

The idea here is that if the AI is supposed to defend a certain area, certain "critical areas", areas that the AI really does not want the enemy to enter (e.g. towns, choke points), can be identified within the total area to be defended. Once the "critical areas" are identified, vulnerable units can be moved into these critical areas, and tougher units can be evenly allocated in predefined formations around these critical areas. The formations could depend on what kind of "critical area" the units are defending, what kind of vulnerable units occupy the area and how many tough units are available to defend that area.

Take the entire area to be defended as a unit, and create set formations based on available units.

This would be similar to identifying "critical areas", except that instead of separating out areas to be defended and dividing up units to those areas, take the entire area to be defended as critical. Vulnerable units are moved to the interior of the area, tough units are placed in a formation along the perimeter of the area based on how many such units are available, the size of the area, the direction the enemy is known to be coming from, the terrain in the area, and what kind of vulnerable units are being defended (e.g. if healers are present, the formation should put as many units as possible within range of the healers).

Have the AI make an intelligent fallback when necessary.

This would be developed in parallel to each of the other ideas, because it could be applied to each of them. The idea here is to sort out whether defending a specific area is actually possible or worthwhile based on the kind of force an enemy is attacking with. Heuristics could be used to measure if it is worthwhile to stay and sacrifice units to delay the enemy, or to retreat to save units. If a Micro AI were used, parameters could be passed in to modify how "hopeless" a situation would need to be before the AI abandoned the position. This mechanic would also specify where the AI should retreat to, and possibly include a heuristic to pick another currently defended or defensible position to fall back to.

Rotate strong, undamaged units to replace damaged units.

This would also be used in parallel with any of the other ideas. Units that make up the defensive formation should be rotated out when they are likely to die in the next turn or two. This would only occur if it is possible to replace that unit with a unit that is likely to live in that spot for longer than the current unit. This may be best implemented as a stand-alone candidate action using the cpp engine since it would likely be used by multiple defense strategies.

Demo

I put together a Micro AI to demonstrate the kind of formation I have in mind to defend a specific area, in this case, the area around a village. The scenario I used to test the Micro AI is a modification of the one used to demonstrate the healer support Micro AI, and consists of two sides: the red total defense Micro AI in the north and the blue healer support Micro AI in the south. I chose to pit the total defense AI against the healer support AI because it generally uses the standard RCA AI candidate action loop, but uses healers a bit more intelligently.

In the scenario, I'm having the total defense Micro AI defend the area around the village just north of the river in the center of the map by positioning uninjured, non-healer units on the outside of the area facing the enemy, and injured or healer units on the inside just behind the defender line. Units that fall under 50% hp are considered "injured" and will fall back to the interior of the defense radius.

I also ran this scenario with just two healer support Micro AIs pitted against each other, with the northern team assigned a "protect_area" goal centered around the same village with a radius of 5 for comparison with the total defense Micro AI. In both scenarios the northern (defending) team was forced to stop recruiting after turn 4, so that the southern team would eventually overwhelm the northern team with the idea being to see how long each AI could keep the opponent from capturing the defended village. The performance of my total defense Micro AI in comparison to a simple protect_area goal was somewhat underwhelming. The team in general would last about the same amount of turns as the protect_area AI, though it is worth noting that the total defense Micro AI would never lose control of the village, while the protect_area AI would. Generally the leader would die due to not being a part of the defensive structure around the village in the total defense AI.

Included here is a picture of the formation created by the total defense Micro AI around the villiage it is assigned to defend: https://github.com/jleldridge/wesnoth-old/blob/totaldefensedemo/ the file is at the bottom of that directory: total_defense_of_village.png

Here is the commit for the demo. Every commit I made during the demo has been rebased into a single commit so that the related file diffs can be more easily viewed: https://github.com/jleldridge/wesnoth-old/commit/bb478407e29003a930a4cd395018adc7f36aa7c2

IRC

jleldridge

Questionnaire

Students wishing to participate in GSoC should copy the questions below to a new page and fill it with the answers.

Please note that we generally plan to meet potential students through our IRC channel. So beside just answering these questions, potential candidates consider visiting us in IRC: #wesnoth-dev on irc.freenode.net. This is where most of our work takes place and participating in IRC is mandatory for GSoC students participating with Wesnoth. Our experience is that this is the easiest way to communicate and solve problems that come up.

1) Basics

1.1) Write a small introduction to yourself.

My name is Jeffrey Eldridge. I am a senior studying computer science at the University of North Carolina at Greensboro. I am the current president of UNCG's chapter of the Association for Computing Machinery, and I'm also a member of the STARS Alliance, an organization intended to encourage high school and college students to pursue education and careers in computer science and IT.

1.2) State your preferred email address.

jleldridge27@gmail.com

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

jleldridge on both IRC and Wesnoth forums.

1.4) Why do you want to participate in summer of code?

I wish to participate in the Google summer of code in order to gain experience working with real code bases. I am particularly interested in working on open source projects when I graduate, as well as working with projects that are generally intended for open source operating systems such as Linux.

1.5) What are you studying, subject, level and school?

I am studying computer science at the University of North Carolina at Greensboro. I am a senior.

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

I am from Greensboro, North Carolina, USA. During the summer I can join the IRC at any time, but the most reasonable times will be between 8:00am and 11:00pm eastern standard time.

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

I have no other commitments, and I have no current plans to take a vacation.

2) Experience

2.1) What programs/software have you worked on before?

I have worked on several simple programs for classes, including programs for a challenge course designed to test my ability to write programs using limited resources and having quick execution time. I have also participated in 2 local and 2 regional ACM programming contests, which required quick problem solving with similar program constraints as the aforementioned challenge course.

I have also worked on a few side projects, mostly in java, for fun, which can be found at my github page: https://github.com/jleldridge

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

I have participated in team programming during ACM programming contests, and during a Software Engineering course. The Software Engineering project that I was a part of was intended to be used by a non-profit organization, Parent to Parent, to replace work that was generally done by hand and on paper. The entire class (roughly 20 students) participated in the project, my portion can be found here: https://github.com/jleldridge/CSC340Project/tree/master/CSC340Project/src/matchingAlgorithm

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 have not participated before.

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

I am not currently involved in an open source project.

2.5) Gaming experience - Are you a gamer?

I am a gamer, and have been since I owned an original NES system.

2.5.1) What type of gamer are you?

I like to play competitively when I can, though I'm not excellent at any particular game. I enjoy the challenge from games with clever AI or obstacle courses, and I love to play against other humans.

2.5.2) What type of games?

I mostly enjoy platformers, RPGs, and strategy games. A few of my favorites are Dark Souls, Starcraft II, and The Binding of Isaac.

2.5.3) What type of opponents do you prefer?

I prefer human opponents if possible. Barring that I enjoy AI that is either particularly clever, or obstacle course type levels/opponents. I do not enjoy fighting opponents that are simply stronger than the player character and require large amounts of grinding to overcome.

2.5.4) Are you more interested in story or gameplay?

I believe a good mix of story and fun gameplay mechanics is necessary for a good game, though fun mechanics can salvage a poor story, and a great story can salvage boring gameplay.

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 have only just started the tutorial, but plan to play much more.

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.

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.

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.

English is my native language.

3.2) What spoken languages are you fluent in?

English.

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 have played several MMORPGs and other online games, and I'm very familiar and comfortable with interacting with other players online.

3.4) Do you give constructive advice?

I work as a tutor in the computer science department at my school, so I feel that I am fairly good at giving advice without giving offense.

3.5) Do you receive advice well?

Having played a few MMORPGs, Starcraft II, and programmed in a team setting, I am capable of taking advice, even if it is highly critical, in stride.

3.6) Are you good at sorting useful criticisms from useless ones?

Yes.

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 wants?

I prefer to start coding and test things myself to see if the behavior created is desirable. I believe planning is necessary, but that code cannot be truly evaluated until it is realized.

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 the "AI: Implement a 'total defense' strategy" project. I want to concentrate on having the AI naturally form battle lines as the result of extra heuristics added to the "enemy losses - (1-aggression)*own losses" formula.

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 chose this project because I have just taken an AI course in school, and I would like to be able to apply what I have learned in a more complex setting.

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

May 3 - May 27:

Final exams on 5/3, 5/6, 5/8, and 5/9.
Get experience playing the game.
Become familiar with the parts of the code that I'll be working with.
Improve proposal.

May 28 - June 16:

Speak with mentor about possible strategies, which AI engine to use to apply them in the code, etc.
Begin coding simple forms of each idea in the different engines to see what obstacles each one presents, and which one seems to work the best.
Create test scenarios to allow the AIs to be easily compared to each other against human opponents and other AIs.

June 30:

Find a metric by which to measure the performance of the each AI defense strategy.
Start determining which idea in which engine seems to be most successful at achieving the desired behavior.

July 15:

Have more refined versions of the strategies, having determined which ideas work best in each engine.

June 30:

Have most of project done for intensive testing (hopefully against mostly human opponents) and debugging.

August 16:

Have project finished and as bug free as possible.

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

I plan to use the LUA engine and custom Micro AIs with high candidate action scores under certain conditions to exactly position units once they manage to get into the general area that is to be defended. Micro AIs allow for the grouping of several behaviors into one file, as well as the selection of units that will be affected by the Micro AI, so Micro AIs seem like the most flexible way to create total defense behavior.

To define the area that is to be defended, "protect_unit" and "protect_area" [goal] tags could be used to modify where the movement candidate actions send units. The "protect_unit" and "protect_area" goal tags use the number of enemy units within a radius of the thing to be protected as a heuristic; if this proves insufficient to get units into desired defensible positions, new goals can be created that use different heuristics to work in combination with the current goals. If goals are not flexible enough to get the desired movement behavior, a Micro AI can be used that explicitly ignores the movement candidate actions and takes care of moving units into defensible positions itself.

4.6) What do you expect to gain from this project?

I expect to gain experience working on a real world project with a large amount of code involved. I also want to gain experience working with other people's code, as well as working on open source projects.

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

I will stay with the project if I find the work enjoyable. I love gaming and creating games, and I would very much enjoy continuing to fine tune the AI for Wesnoth.

5) Practical considerations

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

Git (used for all commits) Yes.
C++ (language used for all the normal source code) Yes.
STL, Boost, Sdl (C++ libraries used by Wesnoth) Yes to the STL, not the other two.
Python (optional, mainly used for tools) Yes.
build environments (eg cmake/scons) I have used makefiles.
WML (the wesnoth specific scenario language) Yes, in the past two weeks I've had plenty of exposure to it.
Lua (used in combination with WML to create scenarios) Yes, in the past two weeks I've also learned a fair amount of LUA.

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

For development I usually use Vim and Git, and compile in a terminal on Linux Mint. I prefer to use Vim because it allows me to work on any language on any operating system without having to change my development environment. I prefer compiling on the command line so that I know exactly what's going on when I compile/run my projects.

5.3) What programming languages are you fluent in? Java, C++, C, Python.

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!

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

Difference between revisions of "User:Jleldridge"