SoC2014 vorobeez AI

This page is related to Summer of Code 2014

See the list of Summer of Code 2014 Ideas

This is a Summer of Code 2014 student page

AI Global strategy

High-level discription

Contents

• Definitions.
• Useful links.
• Main part.

Definitions

Following definitions will be used in the specification and project implementation.

Fact - simple statement. Can be of two types:

• Compares resources of player with the resources of another players.
• Tells about condition and resources of game.

For Instance:

• “The first player has less villages than a second player”.
• “The first player has less gold than a second player”.
• “The first player has more archers than a second player”.
• “Now day”.
• “Free villages are available”.
• etc.

Goal - a global decision about what actions we need to take in order to convert the highest number of negative facts in the positive.

Goals might be as follows:

• “Need to capture the village...X”.
• “Need to attack the point...X,Y”.
• “Need to step back to the point...X,Y”.
• “Need to move to the point...X,Y”.
• “Need to recruit units of type...X”.
• etc.

Useful links

To understand main part of the project you must understand some basics in probability theory.

Some basic knowledge(not mandatory):

Probability theory

Event

Main part

In this section we have a description of the basic steps of the algorithm and a simple example explaining how the algorithm works.

1. Getting data.

We obtain data about present condition of the game. Such as:

• Number of villages captured by the first side / second side /...
• Number of free villages
• Number of units in the first side / second side /...
• Number of units of a certain type in the first side /second side /…
• Amount of gold in the first side / second side /…
• Time of day.
• etc.

Expample

Suppose that we are playing for a first side and against us playing the second side. And suppose that we have such data:

Number of...	First side	Second side
villages	6	8
gold	40	56
fighters	2	5
archers	3	2
scouts	4	3
all units	9	10
Available 6 villages.
Now Day

2. Creating facts

We have received the needed data. Next step will be creating facts based on this data.

We have already seen an example of the facts, so let's get right to the example:

From the data we obtained the following facts:

• "The first player has less villages than a second player"

• "Free villages available"

• "The first player has less gold than a second player"

• "The first player has less fighters than a second player"

• "The first player has more archers than a second player"

• "The first player has more scouts than a second player"

• "The first player has less units than a second player"

• "Now day"

We give a graphical example in Figure:

For every facts we have corresponding color. For black points corresponds opposite facts for our derived facts.

3. Creating goal.

Next step will be creating goals from derived facts.

Suppose that for our set of facts corresponds just three goal:

• “Need to capture the village...X”.

• “Need to step back to the point...X,Y”.

• “Need to recruit warriors".

Another one graphical example in Figure:

Again for every goal we have corresponding color.

We now turn to the choice of goals. We have 8 facts. Suppose that probability of each fact = 1/|number of derive facts|. Consequently in our case we have probability of each fact = 1/8. Based on that rule we compute probabilities for our goals:

“Need to capture the village...X” = 4/8 = 1/2.

“Need to step back to the point...X,Y” = 3/8.

“Need to recruit warriors" = 2/8 = 1/4.

And we get goal with highest probability: “Need to capture the village...X”.

4. Formation of action to achieve the goal.

After we choose the goal, we need to define actions that will help us to achieve the goal. What that’s means?

• Determine the optimal number of turns (1-2 max)
• Determine the exact coordinates for the purpose.
• etc.

Example: We choose a target “Need to capture the village...X” Consequently we need to find a village that it would meet following criteria:

• Should be closest to the Scouts (maximum two turns).
• Should be farthest from the enemy.
• Should be free.

If we find the village to meet our criteria, we assert the goal. In another case, we choose a target with a lower probability of again and do the fourth step.

Low-level discription

Example of C++ code for first and second step of concept

I put here code for first and second step of concept to show how it should works in simplified form

class facts 
{
public:
 facts();
 facts(base_side, opposite_side);
 
 void compute_fact_villages();
 void compute_fact_gold();
 void compute_fact_archers();
 
private:
 int base_side_;
 int opposite_side_;
 const gamemap &map_;
 const std::vector<team> &teams_;
 const unit_map &u_map_;
 
 //set of facts
 //will be a vector or some another type of container.
 private:
 int villages_;
 int free_villages_;
 int gold_;
 int archers_;
};

facts::facts(): base_side_(1), opposite_side_(2), map_(resources::gamemap), 
   teams_(resources::teams), u_map_(resources::units),
   villages_(-1), free_villages_(-1), gold_(-1), archers_(-1)
{}

facts::facts(base_side, opposite_side): base_side_(base_side), opposite_side_(opposite_side), 
   map_(resources::gamemap), teams_(resources::teams), 
   u_map_(resources::units), villages_(-1), 
   free_villages_(-1), gold_(-1), archers_(-1)
{}

//Compute number of villages captured by the base_side and opposite_side
void facts::compute_fact_villages(){
 int count_for_base_side = 0;
 int count_for_opposite_side = 0;
 int count_for_free_villages = 0;

 const std::vector<map_location>& villages = map.villages(); 
 std::vector<map_location>::iterator it = villages.begin();

   for(; it != villages.end(); ++it)
   {
     int owner = resources::village_owner(it);

     if(owner == base_side_)
     {
       ++count_for_base_side;
     }
     else if(owner == opposite_side_ - 1)
     {
       ++count_for_opposite_side;
     }
     else if(owner == -1)
     {
       ++count_for_free_villages;
     }
   } 

   //creating facts
   //The first player has less villages than a second player == 0
   //The first player has more villages than a second player == 1
   villages_ = count_for_base_side > count_for_opposite_side ? 1 : 0;
   //Free villages available == 1
   //No free villages available == 0
   free_villages_ = count_for_free_villages > 0 ? 1 : 0;
}

//Compute amount of gold in the base_side and opposite_side
void facts::compute_fact_gold()
{
   int gold_base_side = teams_[base_side_ - 1].gold();
   int gold_opposite_side = teams_[opposite_side_ - 1].gold();

   //The first player has less gold than a second player == 0
   //The first player has more gold than a second player == 1
   gold_ = gold_base_side > gold_opposite_side ? 1 : 0;
}

I will crate unify function for all type of units. But until now only one type, to show how it should work. I will not put this code elsewhere :)

//Compute number of archer in the base_side and opposite_side
void facts::compute_fact_archers()
{
   int count_for_base_side = 0;
   int count_for_opposite_side = 0;

   unit_map::const_unit_iterator ui = u_map_.begin();

   for(; iu != u_map_.end(); ++iu)
   {
     int side = iu->side();
     std::string const &type_name = iu->type_name().str();

     if((side == base_side_) && (type_name == "archer"))
     {
       ++count_for_base_side;
     }
     else if((side == opposite_side_) && (type_name == "archer")){
       ++count_for_opposite_side;
     }
   }

 //The first player has less archers than a second player == 0
 //The first player has more archers than a second player == 1
 archers_ = count_for_base_side > count_for_opposite_side ? 1 : 0;
}

Timeline

Apr 21 - May 19	Create full set of facts, goals and actions for goals.
May 19 - June 2	Implementation the first and second step of the concept.
June 2 - June 9	Past all exams in University and move to Crimea.
June 9 - June 23	Implementation the third step of the concept.
June 23 - July 14	Implementation the fourth step of the concept. Binding of concept with Candidate Actions framework.
July 14 - July 21	Testing concept and it code. Identify weaknesses and shortcomings of the concept of sets of facts and goals.
July 21 - August 28	This week I want to visit Lviv.
August 28 - August 11	Error correction logic of facts and goals. Addition and correction of their sets.
August 11 - August 18	Final testing and write documentation.
Afterwards	Improve global-decision concept. (Markov chain, Bayesian network...)

With exams should have no problems. I was the fourth time successfully rent them for a week. And soon after I will have more free time to work on the project (6-10 hours).

Patches and commits

New cost_calculator and ai.find_path_with_avoid() function. #145

Сommunication

IRC

vorobeez

Email

vorobeez@gmail.com

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

I'm Andrew Firsov, second-year student of Ivanovo State Power University.

1.2) State your preferred email address.

vorobeez@gmail.com

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

vorobeez

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

I have to take experience with open source projects, improve programming skills and fun.

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

I'm studying math(combinatorics, probability theory, mathematical analysis, linear algebra...), computer science(algorithms, data structures, cryptography, compilers, C++, Lua, some libraries: SDL, crypto++, STL, boost), and a bit of game theory

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

I study at Ivanovo, Russia (UTC+04:00), but throughout the summer months i will live in the Simferopol (Crimea,Ukraine) (UTC+02:00).

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

I want to travel around the Crimea on the weekends and at one week visit Lviv, that's all.

2) Experience

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

i created small projects for my needs and games to learn how works SDL and for realizing my own ideas.

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

No, i haven't

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?

No, i haven't

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'm not. But i love open source and use it every day.

2.5) Gaming experience - Are you a gamer?

I was a gamer. Now I sometimes play wesnoth and FTL. I like games in which we must think.

2.5.1) What type of gamer are you?

Hardcore gamer.

2.5.2) What type of games?

Strategies and little bit of indie-games.

2.5.3) What type of opponents do you prefer?

Real players with wide experience.

2.5.4) Are you more interested in story or gameplay?

I love deep and great stories in games. But in order to the gamers could have fun all components of the game should be worked out at high level

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'm playing Wesnoth for 1.5 years. I prefer SP. But sometimes play in MP with other players.

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.

I'm good at written English. And i speak with English native speakers freely.

3.2) What spoken languages are you fluent in?

Russian (native), Ukrainian, 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.

Always ready to answer questions from players. I do not like being rude, but I can control myself and keep my level of intelligence (=

3.4) Do you give constructive advice?

I think i do, the problems with the logic I do not (=

3.5) Do you receive advice well?

I have not a very good level of English, but I try.

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

Yes, i am. I have my mind and my ideas for this.

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 guess I'm one of those people who think first, and then write code. But I love to take risks.

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 a project to develop a global decision-making for AI. I want especially concentrate at AI, theory of probability and C++ code.

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 love the kind of research projects where I can apply my knowledge of mathematics and can improve them.

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

see: Timeline

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

see: Project

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

I want to get experience in the development, improve the knowledge of mathematics and programming. Meet new and interesting people. Fun summer. Get earnings in the end.

Improve my communication skill in English (=

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

I want to continue to develop its concept after the summer. There are many theories and techniques for this (Markov chain, Bayesian network...). With Wesnoth developing i can improve and gain many-many skills interesting for me.

5) Practical considerations

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

• Git (used for all commits) I use basic functionality of git for my projects.
• C++ (language used for all the normal source code) I good at C++
• STL, Boost, Sdl (C++ libraries used by Wesnoth) I know STL, SDL 1.2 and a little SDL 2.0. And I learn boost, but not often use it. Also i'm fast learner
• Python (optional, mainly used for tools) No
• build environments (eg cmake/scons) basic knowledge and using
• WML (the wesnoth specific scenario language) In theory, but i don't use in it practice
• Lua (used in combination with WML to create scenarios) Yes

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

• git and github to commits and verify version of my project.
• gcc and make for compiling separate sources.
• vim or sublime for coding.

5.3) What programming languages are you fluent in?

C/C++ and Lua.

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!