Difference between revisions of "User:Zazweda"

From The Battle for Wesnoth Wiki
(Project split)
(Project split)
 
(4 intermediate revisions by the same user not shown)
Line 36: Line 36:
 
<h4>Refactoring of the attack algorithm</h4>
 
<h4>Refactoring of the attack algorithm</h4>
  
Modificating the attack algorithm is useful mainly to defend important AIs unit or zone. This would go through the "good position" detection (detailed in the section of the same name) and defending experimented unit or usefull units against the enemy(ies).
+
Modificating the attack algorithm is useful mainly to defend important AIs unit or zone. This would go through the "good position" detection (detailed in the section of the same name) and defending experimented unit or useful units against the enemy(ies) taking its own "value" into account.
  
 
This would allow to check if there is an attack move that is good enough in term of "future" anticipation. If there is no good attack move, it would go to defense algorithm
 
This would allow to check if there is an attack move that is good enough in term of "future" anticipation. If there is no good attack move, it would go to defense algorithm
Line 42: Line 42:
 
<h4>Defense algorithm</h4>
 
<h4>Defense algorithm</h4>
  
 +
The defense algorithm would allow the AI to think about the future actions.
 +
If no good attack move is found it goes defending. This would be done by moving to "good position" or in front of important unit. The good position for defense is detailed in the section good position algo.
 +
If there is no way to protect efficiently a very important unit (through a line of blocking unit per exemple) it would simply try to kill or weaken the highest threat level enemy (detected by the risk detection algorithm).
 +
 
<h4>Estimation algorithm</h4>
 
<h4>Estimation algorithm</h4>
 +
 +
This algorithm estimates the next turn possibilities according to given CAs.
 +
It would take each CA and run a risk detection on it. It would then pick the one with the lowest RISK-DEFENSE_Possibilites. Defense possiblities represents a good position or for example a home (which would heal next turn) or a high defense terrain.
 +
 +
It would finally return the CAs it estimates best for the unit.
  
 
<h4>Risk detection algorithm</h4>
 
<h4>Risk detection algorithm</h4>
 +
 +
Risk detection would simply simulate next turn and take some criteria into account. This could be improved using the markov chains to predict the next steps.
 +
Criterias could be : Number of possible attacks, risk of death, risk of losing an important terrain, risk of having an important target attacked.
 +
It would finally returns a value representing the "risk" of the CA
  
 
<h4>Good position detection algorithm</h4>
 
<h4>Good position detection algorithm</h4>
 +
 +
A good position may be 2 things. For attack it is where your defense score is the best and enemy's the lowest. For defense it is a little different. If AI anticipates next turn it has to take into attack where its own defense will be the best, but also where enemy defense will be the lowest. It will then try to find the terrain with the highest defense for him and with hex around it which have low defense score for the enemy.
 +
 +
The terrain value would be calculated through the enemy kind in the first place an improvement could be to take the current threatening unit into account.
 +
 +
Then other "good position" may be more dangerous but valuable position : control of a castle, control of a house or even a bridge.
  
 
<h4>High priority unit algorithm</h4>
 
<h4>High priority unit algorithm</h4>
 +
 +
The AI high priority unit would be its own leader, high exp unit, or powerful units against enemy kind (improvement could take into account the current threatening units). It may also be depending on the number of house per exemple, its fast moving units (when it needs more money).
 +
 +
The enemy highest priority unit are pretty much the same but reversed for the quick units (if I have a lot of house I don't want some horse to steal them.) and powerful unit against my kind (which would be attacked by counter unit).
  
 
<h4>Detection of the next turn potential actions</h4>
 
<h4>Detection of the next turn potential actions</h4>
  
The detection of the next turn actions has a big part in the AI CAs. It would be done through 2 a 2 steps algorithm :  
+
The detection of the next turn actions has a big part in the AI CAs. It would be done through a 2 steps algorithm :  
  
 
Estimate the best CAs according to the refactored estimation algorithm (attack or defense move), this would select the N best CAs (1 2 3 or more according to tests).
 
Estimate the best CAs according to the refactored estimation algorithm (attack or defense move), this would select the N best CAs (1 2 3 or more according to tests).
  
 
For each of this CAs it would try to estimate the risks that the enemy move could provoke on next turn. This risk is defined in the "risk detection" algorithm.
 
For each of this CAs it would try to estimate the risks that the enemy move could provoke on next turn. This risk is defined in the "risk detection" algorithm.
 +
 +
<h4> MAIs and extCAs </h4>
 +
I would like to implement MAIs so that user can specify a little deeper which kind of AI is used. For example it could be interesting to specify that you want the AI to give more importance to the defense of a castle, or some special units,...
 +
 +
==Schedule==
  
 
=Description=
 
=Description=

Latest revision as of 06:23, 14 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


Overview

The Total defense Strategy Google summer of code has for purpose to propose an AI that would take more variable into account before attacking. It would also make decision to move through a defensive algorithm if no "good" attack is found.

Attacking algorithm

The new attack algorithm may choose its target according to a different formula, which would take into account next round fight with the attacked unit (will it kill the AI unit instantly because it used a different attack ?) for exemple. Ideas of things to take into account on top of current ones : -Some might already be taken into account and I missed it, if so please tell me-

  • Possibility of escaping (is there a possibility to block him, or to make him slower -water?- or is he extra slow/ too fast)
  • Firepower right next to him (how many units and power compared to AI's)
  • Next round fight(distance and close attack have different outcome) ponderated by the %age of chance to kill him first
  • Threatening important units or position(almost lvl up for examples, castel, houses or good cases -like mountain for dwarfs- not only the leader)
  • Ratio number of house controlled by the AI and speed of the enemy (kill fast first to avoid quick invasion if AI starts having less house)

Defense Algorithm

On the other hand, sometime attacking is not the best way, sometime defending is better : you can pick best position for fighting (like forest for elves and stuff). This algorithm would take place if no good or few attack option are found. Stuff I would like the defense algorithm take into account :

  • Moving to a nice position for future fight, taking into account what is arround (the more bad cases for the enemy, the best).
  • Defending an important target (same as for attacking), by placing around it so it can't be reach, or on a bad land.
  • Backing to houses which no or few enemy can reach.
  • Move the leader to the best location (ratio between safe and close enough to recruit efficiently)

Micro AIs for defense and on the fly mods

The Micro AI system may be very interesting for the algorithms accentuating the aggressivity through bigger strength given to some variables.

On the fly modifications would be useful to determine in which case attacking or defending is better according to the current state of the game (for exemple if AI has advantage with more unit or more house it can be more aggressive).

Project split

Refactoring of the attack algorithm

Modificating the attack algorithm is useful mainly to defend important AIs unit or zone. This would go through the "good position" detection (detailed in the section of the same name) and defending experimented unit or useful units against the enemy(ies) taking its own "value" into account.

This would allow to check if there is an attack move that is good enough in term of "future" anticipation. If there is no good attack move, it would go to defense algorithm

Defense algorithm

The defense algorithm would allow the AI to think about the future actions. If no good attack move is found it goes defending. This would be done by moving to "good position" or in front of important unit. The good position for defense is detailed in the section good position algo. If there is no way to protect efficiently a very important unit (through a line of blocking unit per exemple) it would simply try to kill or weaken the highest threat level enemy (detected by the risk detection algorithm).

Estimation algorithm

This algorithm estimates the next turn possibilities according to given CAs. It would take each CA and run a risk detection on it. It would then pick the one with the lowest RISK-DEFENSE_Possibilites. Defense possiblities represents a good position or for example a home (which would heal next turn) or a high defense terrain.

It would finally return the CAs it estimates best for the unit.

Risk detection algorithm

Risk detection would simply simulate next turn and take some criteria into account. This could be improved using the markov chains to predict the next steps. Criterias could be : Number of possible attacks, risk of death, risk of losing an important terrain, risk of having an important target attacked. It would finally returns a value representing the "risk" of the CA

Good position detection algorithm

A good position may be 2 things. For attack it is where your defense score is the best and enemy's the lowest. For defense it is a little different. If AI anticipates next turn it has to take into attack where its own defense will be the best, but also where enemy defense will be the lowest. It will then try to find the terrain with the highest defense for him and with hex around it which have low defense score for the enemy.

The terrain value would be calculated through the enemy kind in the first place an improvement could be to take the current threatening unit into account.

Then other "good position" may be more dangerous but valuable position : control of a castle, control of a house or even a bridge.

High priority unit algorithm

The AI high priority unit would be its own leader, high exp unit, or powerful units against enemy kind (improvement could take into account the current threatening units). It may also be depending on the number of house per exemple, its fast moving units (when it needs more money).

The enemy highest priority unit are pretty much the same but reversed for the quick units (if I have a lot of house I don't want some horse to steal them.) and powerful unit against my kind (which would be attacked by counter unit).

Detection of the next turn potential actions

The detection of the next turn actions has a big part in the AI CAs. It would be done through a 2 steps algorithm :

Estimate the best CAs according to the refactored estimation algorithm (attack or defense move), this would select the N best CAs (1 2 3 or more according to tests).

For each of this CAs it would try to estimate the risks that the enemy move could provoke on next turn. This risk is defined in the "risk detection" algorithm.

MAIs and extCAs

I would like to implement MAIs so that user can specify a little deeper which kind of AI is used. For example it could be interesting to specify that you want the AI to give more importance to the defense of a castle, or some special units,...

Schedule

Description

Zazweda - Total defense Strategy

The defense project would include taking more information and probabilities into account (next turn for example).

IRC

Zazweda, ValentinD

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

I am a 21 yo french student in a Computer Science Engineering school in Belfort (North East). I am currently in the Image Interaction and virtual reality part of the Computer Science department and this is my last year. In the computer science field I love AI, Virtual reality, big data, videogame and I am very enthousiast about the open source principle ! For the rest of my life I like reading, playing any kind of game (board, role, cards, videogames,...) and finally I play Badminton.

1.2) State your preferred email address.

valentin[dot]deschaintre[at]gmail.com

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

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

The GSoc is an amazing possibility to discover a complete new world and start involving myself in it. I want to be part of some evolution with my knowledges and I hope that I finally have the skills to achieve this !

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

I am studying Computer Science in the UTBM (French North East Engineering school). I am currently in the last year of study (school is in 5 years) and am specialised in the Image Interaction and virtual reality field.

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

I am from France (GMT+2 right now), I would mostly be on IRC between 11 am and 11 pm during the GSOC. Before that I try to be on as much as possible, it would mainly be present at night.

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

My exams will be over at the end of June. I would then be fully available until mid August, then a little bit less since school starts again in september (but the beginning is light).

2) Experience

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

I have worked on different projects at school such as a little Angry Birds like game and also an AI for a "Rasend Roboter" board game. I am currently working on animating a 3D character and a "World war simulation between Ants and termites. On my side I developped a little Space Invader in Python.

I also did a 6 months Internship in a startup Company called "GumGum". I could work on a lot of different projects including a C++ HTTP server or JAVA data handling through ditributed technology such as hadoop.

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

All my school projects are in team from 2 to 4 and I also worked with the others engineers in the company I was in (they were 6)

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?

It would be my first experience in the GSoc.

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 involved yet in an open source development project but I am willing to now that I have a little bit more experience !

2.5) Gaming experience - Are you a gamer?/

Yes !

2.5.1) What type of gamer are you?

I like to play, I can be really fond of different types of games. I can be really passionated about some !

2.5.2) What type of games?

I played to a lot of different types : Rts (Age of empires, Warcraft), but also some Moba (LoL), or RPGs (FFX would be the the most played), I also like to play some "old" games such as Magical Drop 3 or DoDonPachi(we have an arcade machine at school).

2.5.3) What type of opponents do you prefer?

Depends of what I expect from the game, I like AIs because of the technological progress it represents. But in the end playing with or against other real player is often more challenging .

2.5.4) Are you more interested in story or gameplay?

Story is very important when I play against AI, it often represents what the AI fights for or what it is. The gameplay is the first aspect you see of the game and the one that will follow you until the end, so I would say 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.

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 played a few games before mostly multiplayer and a few campaigns, I haven't played intensively but my roommate is willing to fix this "issue" ;).


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.

I created (not commited yet, still improving) a MIAs for the guardians that "guards" a zone.

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 followed European cursus and spent 6 months in California, I would describe my level as "fluent".

3.2) What spoken languages are you fluent in?

French, English, not bad in German

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

When I play a game I always try to make it as cool as possible. I am not perfect either, but I try to keep calm and "play the game" ! I have been some kind of Community Manager for the website "www.kraland.org" before my internship (then it became a little complicated with the new life and schedule :( ).

3.4) Do you give constructive advice?

I try not to troll for free ;). More seriously when I give an advice I try to explain why I give it, it might not be a general rule, but I know an unexplained advice is almost "useless".

3.5) Do you receive advice well?

I try to stay open to any advice as long as people don't start by "omfg u r 2 stupid !" ^^"

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

That was part of my job as Community manager, and it currently is as president of my school association. I try to be as fair as possible and take the maximum of criticisms into account, eventhough it's sometime hard.

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 am more the kind of "I want to try my idea coded", of course I think about what I want to code first but I like to prove it's going to work and do what I want.

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 liked multiple projects, mainly the ones about the AIs. The defense AI and recruiting algorithm look really nice !

4.2) If you have invented your own project, please describe the project and the scope. -- 4.3) Why did you choose this project?

The AI projects are very interesting to me because, well it's AI and I love everything related to it, I think of it as the next big step in computer evolution ! Implementing an AI for a game on top of all would be a great plus for me since it is a world I know and love.

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

I could work from 1st july to 15 august aprox and then a little less from 25 august to end of september (back to school). Before July I have to give all my school projects back and have my final exams for the semester é_è.

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

I think that the easiest way to implement easy to use and update AI would be to create one in C++ with all the basic defense behaviour. And add in LUA different MIAs detailing this general behaviour. A little bit like its done now with the "guardian" behaviour and MIAs.

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

I expect to gain an experience in open source projects, games, improve and learn new AI algorithm. And of course meet new awesome people !

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

I would say the community itself ! Simply the atmosphere around the game I guess. I am willing to involve on a long time and I hope this GSoc could give a head start to it.

5) Practical considerations

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

   Sub­­version (used for all commits)
     Used it during the entire internship, pretty familiar
   Git (I put it as bfw is migrating to it if I understood well)
     Used it multiple times for different projects (mainly school ones)
   C++ (language used for all the normal source code)
     Learned it and used it for different purpose (working with it on my 3D animation project)
   STL, Boost, Sdl (C++ libraries used by Wesnoth)
     I used Boost to implement the HTTP server in C++ and am Using the SDL for the animation project. I am willing to learn it further !
   Python (optional, mainly used for tools)
     Worked with it multiple times, mostly on personnal projects (a little pokemon and space invader with pygame)
   build environments (eg cmake/scons)
    Not very familiar but willing to learn
   WML (the wesnoth specific scenario language)
    Getting more familiar with it
   Lua (used in combination with WML to create scenarios) 
     Trying to use it right now modifying and adding some MIAs

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

I like eclipse for Java, I have no preferences for C++ developping, I recently tried the eclipse for C++ and the QT IDE, both were nice eventhough I prefered eclipse since I already know its architecture through the Java part. Gedit is useful too sometimes ;).

5.3) What programming languages are you fluent in?

  Java, Groovy, C++ are the main languages I know really well.

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!

I wouldn't mind, if I need to be contacted in any way I would answer the phone ! (I will add it to the Gsoc application!)

This page was last edited on 14 May 2013, at 06:23.