User:Arkist
| 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 |
Contents
Description
Arkist - AI: Implement a total defense strategy
When AI calculates how to attack don't consider what could happen in next turn. I want to change this, caulculating different possibilities without increasing the computation complexity (or increasing it slightly, not increasing the 'loading' time). Maybe I could use 'branch and bound' algorithm, trying different heuristics.
AI: Implement a total defense strategy - Details
As I said in description, I will use the next turn possibilities in order to improve the behaviour of the AI units. In addition, I have some different ideas that could help this strategy:
Total defense mode
Sometimes, the best strategy is run away from the opponent. This could be the best strategy when the player wants to defend something, or maybe when the player is clearly in disadvantage and wants to regroup and recruit more units. The AI could do the same. My experience as Wesnoth player tells me that one good way for doing this is sacrificing some units, covering the other units. I detail this in the next section.
Sacrifice units
As I explained before, I want to use the less useful units in order to cover the other units when they're running away. This could be implemented with a simple algorithm and a quick mathematical operation, using variables like unit position, toughness and opponent units able to attack.
Groups and units position
Sometimes the AI could try to maximize the number of alive units. For this purpose, the units who are together could defend the ones with less life in the moment, in order to heal the others before they die.
Safer attacks
"What can happen if I move this archer here?" AI will calculate the different options with a heuristic function. The AI wants to use a total defense strategy, but sometimes attack is the best defense. AI could do 'safe' attacks, I mean, AI could attack with a unit when there is a high probability of success in the attack, and the opponent can't attack (or kill) the AI unit in the next (or more) turn.
Defending villages
"I'm using a total defense strategy and is working fine, but the game continues and I'm constantly losing money!" In my opinion, total defense strategy should only be applied when AI only needs to defend, no matter the evolution of the game. Unlike human player, computer don't have to save money for the next game.
Technical considerations
I know that the algorithm complexity increases a lot using too much recursion in branch and bound or heuristic-based algorithms. I will use additional conditions in order to decrease the complexity.
I have to try different options, so I can't talk now about the exact values and code I'm going to use.
Branch and Bound
Three basic steps:
1- Selection: Select what new posibility is going to be explored.
2- Branching: Divide the posibility in sub-posibilities.
For example, I have an archer and a knight. I move my archer to the position (+1,-2), but I don't know what I'm going to do with my Knight, so I ramify the different possibilities. If the new possibility could be better than my heuristic, I add it to the posibilities queue.
3- Prune: There are a lot of ways for doing this, like using an opthimistic value(pruning the worse branches) or using a memory with intermediate values.
The algorithm uses some functions: isRealizable: Determines if the partial solution could be better than the optimal isComplete: Determines if the solution is complete
The algorithm work like this: Pick a solution from the queue. If the solution isComplete and better than the optimal, this solution is optimal. If the solution is not Complete but isRealizable, add the solution to the queue Branch it.
IRC
Arkist
Questionnaire
1) Basics
1.1) Write a small introduction to yourself.
My name is Álvaro Villena. I'm a 20 year old IT student from Spain. I'm into programming because I've always liked technology, especially the computation field. I'm an active student who always wants to participate in activities and projects, and I'm constantly trying to learn new things. I can speak and write in Spanish and English, and I'm learning German too.
1.2) State your preferred email address.
alvarovillenamg@gmail.com
1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?
Arkist
1.4) Why do you want to participate in summer of code?
I want to participate in this program because I think is a great opportunity for me to get introduced in how to work in a real project.
Last year I could not participate because I was very busy with work and travels, but this summer I'm completely free and I want to contribute in this program.
1.5) What are you studying, subject, level and school?
I'm studying IT (computation speciality) in Castilla la Mancha University, Spain. I'm ending the third course.
1.6) What country are you from, at what time are you most likely to be able to join IRC?
I'm from Spain. In summer I will be available anytime, so I can adapt my schedule for being able most of the time.
1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.
As I've said before, I don't have other commitments for this period. I will be available the whole summer.
I'm planning to do a short trip (5 days) in July.
2) Experience
2.1) What programs/software have you worked on before?
2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)
Yes, but only for a 4 month project in the university.
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've never 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.
No, but I usually try to find out information about this kind of projects.
2.5) Gaming experience - Are you a gamer?
2.5.1) What type of gamer are you?
I've always liked video games. When I was young I used to play everyday, but now I have to be more responsible. Even so, I try to play when I have the time.
2.5.2) What type of games?
I like almost all type of games, especially I like trying indie games. My favorite kind of games are RPG, strategy and turn-based games.
2.5.3) What type of opponents do you prefer?
Sometimes is great playing with other people, but I've always preferred palying against a good IA.
2.5.4) Are you more interested in story or gameplay?
It depend on the game, but I usually prefer story. Nonetheless, a good gameplay is very important for having a good experience, so I think it should be a compromise between story and 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.
I think my first time playing Wesnoth was in 2006. I prefer single player because I can play as long as I want, sometimes multiplayer games are very long.
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.
My English level is C1 in Common European Framework of Reference. I can understand and produce complex and technical text without help. It's obvious that my English is not perfect, but I think is good enough in order to communicate with other people without problems. Last summer I was in England for 3 weeks, and I was able to talk with anybody.
3.2) What spoken languages are you fluent in?
English and Spanish.
3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
That depends on the other players. If they are constantly disturbing or insulting, I avoid interacting with them.
3.4) Do you give constructive advice?
I always say that everyone was new before, so I try to help other players if they need help because when I'm new in a game I like receiving advice from experimented players.
3.5) Do you receive advice well?
Yes, as long as the advices are real advices and not mockery.
3.6) Are you good at sorting useful criticisms from useless ones?
Yes. If someone gives me a good idea, you can be sure that I'm going to think about this idea.
Related with this question, I play bass guitar in a band. Useful and useless criticisms are very usual when we play in a gig, but I only care about the useful 'advices'. If someone say me just: "your music is horrible!" i'm not going to change my music.
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 prefer having a plan when I start coding. When I'm developing a project in a team, I like to talk with all my team about what and how we are going to do something.
Coding and trying new things is not bad if you really know what you are doing, but if someone constantly do this could fail and delay the project.
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 want to work in one of these projects:
AI: Implement a 'total defense' strategy
AI: Refactor recruitment algorithm
I have played Wesnoth for a long time, and I always thought AI has sometimes some 'strange' behavior.
My goal is to modify this kind of behavior, modifying the currently code or making a completely new one. I have a bit of experience in AI problems, so I think I can solve it.
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'm studying IT, and I've realized that I love everything related with AI. In addition, I think I can improve the game if I work hard on this project. This is a great opportunity for me because I want to work in projects like this one in the future, so I'm sure I wouldn't waste this opportunity if you let me do it.
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".
My last exam is 30th May, so I would start with my project in June.
I can't make an accurate timeline until I know exactly my project, but here is an estimated schedule:
1st June – 9th June: Read information about how to do my project. Try tools I’ve never used. Talk with my mentor and the team for obtaining as much information as I can.
10th June – 14th July: Follow the planning I made with the information and start coding. Get used to all the tools and work method. I expect having half of the project finished for 14th July.
15th July – 19th July: Maybe holidays.
21st July – 25th August: Finishing the main part of the program.
25th August – 15th September: Documentation. Final testing of the code and fixing little bugs.
4.5) Include as much technical detail about your implementation as you can
I think I can use technics like branch and bound, including variables like next turns. I want to mix them with heuristic functions, allowing me to calculate the best movements.
4.6) What do you expect to gain from this project?
This is a real project, so I expect gaining a lot of experience that is going to be very useful for me in the future.
In addition, I expect learning how to use a lot of new software and tools.
Is obvious that money is a really good incentive in this kind of projects, but is not my main goal. If I can't get this project, I will try to contact with Wesnoth or other team to provide my free help in any interesting project.
4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
I've played Wesnoth before, so I'm sure I'm not going to leave the community by choice.
5) Practical considerations
5.1) Are you familiar with any of the following tools or languages?
- Git (used for all commits)
- C++ (language used for all the normal source code)
- STL, Boost, Sdl (C++ libraries used by Wesnoth)
- Python (optional, mainly used for tools)
- build environments (eg cmake/scons)
- WML (the wesnoth specific scenario language)
- Lua (used in combination with WML to create scenarios)
I've used Git and C++ in some projects, so I’m very familiar with them.
I'm studying and using Python since September.
I've never used the other tools, but if you accept my project I can get used to them shortly.
5.2) Which tools do you normally use for development? Why do you use them?
Mainly programming environments like Eclipse or NetBeans, with C, C++, C#, Java, or Python languages, and tools like Git or Subversion SVN. I've used other languages like Haskell and Pascal, and I know a little bit about HTML.
I use this tools because mainly because I need it in my studies, but i've studied languages like Python by myself.
5.3) What programming languages are you fluent in?
I've said a list of languages before, but I think i'm more fluent in C, C++, Java and 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!
Talking on telephone with my mentor wouldn't be a problem, I think is a good and quick way for communicating.
My mobile phone is [censored here :)]