SoC2014 kevin AI

From The Battle for Wesnoth Wiki
Revision as of 18:31, 20 March 2014 by KevinXi (talk | contribs) (gsoc2014 kevin's proposal on improve AI)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


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


Attention

This page will be continuously modified and updated.

Description

Kevin Xi - AI: Improve AI by implementing global attack/retreat decision

A way to analyse status of times, terrains, arms, special abilities of units and many other aspects to change the behavior modes of AI, with fuzzy logic to describe the AI rules and Combs method to prevent combinatorial explosion

Idea

Following is my idea on how to analyse status of times, terrains, arms, special abilities of units and many other aspects to change the behavior modes of AI, with the help of fuzzy logic, combs method(to deal with combinatorial explosion) and defuzzification.

I start from a naive idea: If it is day, let lawful units fight offensively and chaotic units retreat; If it is night, let chaotic units attack and lawful units fight defensively.

Two problems should be discussed: Defination of "offensively/defensively" and the factors that influence decisions.

First the defination: To be specific, AI play offensively means it tend to attack when there is a chance, tend to claim the villages and recruit new units to the battlefield. In contrast, AI play defensively means it tend to retreat, it think the units is valuable and only attack when it is quite sure, it may give up villages when the time of day is not right for its unit. But how much does an AI want to retreat? Does retreating five hexes and retreating six hexes make any difference? It seems that the output is fuzzy, so may be we could apply fuzzy logic on it. For example, if it is night and enemies is "very close(a fuzzy set)" and terrain is "a kind of bad(another fuzzy set)", the merman warrior "badly(fuzzy output)" want to retreat.

Second the factors: The factors that influence decisions are far more beyond time of day. For example, if a merman warrior should cross flat to retreat at night, it would be better to rush into the river ahead. Even we just consider terrain for now: According to the acient Chinese book The Art of War by Sun Tzu(I really like this book and it really help me a lot in Wesnoth battlefield), there are six kinds of terrain(the 16 types of Wesnoth can classified in a category for a specific unit): accessible, enmeshes, disadvantageous to both side, narrow and precipitous, hazardous, distant. In each kind of terrain we should decide in different way. So the complexity of situation bring us combinatorial explosion of AI rules. But if we use fuzzy logic, there is a way called "Combs method(http://en.wikipedia.org/wiki/Combs_method)" can prevent this problem.

To sum up, use fuzzy logic to describe the AI rules and Combs method to prevent combinatorial explosion, I believe we can teach AI to make global attack/retreat decision.

IRC

Kevin_Xi

Questionnaire

1) Basics

1.1) Write a small introduction to yourself. Hi, I am Kevin, a junior Software Engineering student in Beihang University. I love open source, I use and learn from it all the time. I played The Battle of Wesnoth for about a year. In my free time(besides coding), I like taking some MOOC course about computer, game design, music and thinking. I also like watching Star Trek and enjoying Jazz, the great works of Horace Sliver make me feel relaxed.

1.2) State your preferred email address.

kevin.xgr [at] gmail.com

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

Kevin_Xi on IRC, FAKevin on forum.

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

I think become part of something bigger than you(open source) is a kind of intrinsic motivation of human being and my heart is always vibrated to the great moment that a software come to life. I believe "Learning by Doing" and want to improve my skills, both on coding and communicating, by participate in a real-life project. The GSoC project is a good trigger for me to get my hands dirty.

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

I am a third year student on Software Engineering, Beihang University. The course I have finished are: Object-oriented programming with C++, Principles of Computer Organization and Architecture, Software Engineering, Database System Concepts, Network, Operating System, Compiler, System Analysis and Design and so on.

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

China. 8:30~10:00am, 1:30~12:00pm UTC+8.

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

I would like to take this as a full time job, so I don't arrange other things.

2) Experience

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

Part of my individual project is available here: https://github.com/Kevin-Xi?tab=repositories. Many of them are tools for my daily life. For teamwork, the latest project I am working on is a Raspberry Pi based smart home system. I develop web server use Django on Raspberry Pi.

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

Yes, I teamed up with my classmates on C++, C#, Java, Django project several times. We often follow agile development methods and use git to manage our project.

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 just know it this year from my RSS reader

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 want to get involved. Sometimes I modify Linux kernel and re-compile it to learn it.

2.5) Gaming experience - Are you a gamer?

Yes. I play a lot, enjoy it and feel there are many things to learn from it, so I taked gamification course at Coursera. I do well in class and get a 10 out of 10 in a recently design work.

2.5.1) What type of gamer are you?

According to the Bartle Player Type Model, I am an archiver who like complete all levels and explorer who like finding out all possibilities in game.

2.5.2) What type of games?

Role-playing, Alternate reality, Educational, Puzzles, Strategy.

2.5.3) What type of opponents do you prefer?

Clever and polite. The most important is I can learn from my opponents.

2.5.4) Are you more interested in story or gameplay?

It depends on the type of game. I like fantasy background in RPG, gameplay in puzzles.

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 played it for about 1 year. I played all official campaigns and like to be a observer of online battles.

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.

No. But I forked wesnoth on github and write a toy AI recently.

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.

There are four kinds of abilities one should develop when learning languages: Listening, Speaking, Reading and Writing. For listening, I am able to understand MOOC class videos without subtitles. For Speaking, although I do not have so much chances to talk directly to a native speaker, I sometimes practice my speaking skills by read after some English podcast online. For Reading, I choose origin English version textbook and read technical papers for information I want. For Writing, I write programming log as diary in English.

3.2) What spoken languages are you fluent in?

Chinese, 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.

Yes, I am a rational and friendly person.

3.4) Do you give constructive advice?

Yes. Sometimes I also give simple ideas to begin brainstorm among team members.

3.5) Do you receive advice well?

I have a systematic approach to take advice and learn from it .

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

I think this depend how deep I understand the system. For wesnoth, since I don't familiar now, I wouldn't say I can. But I will try to ask developers and get familiar on it.

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

As a Software Engineering student, I consider both. But the way I like most is develop a prototype(that allow you to test your idea and fail quickly if it don't work) and test it.


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?

Yes, I choose "Improve AI by implementing global attack/retreat decision". I want to concentrate on figuring out in what situation the AI should change its strategy, in a quantifiable way with the help of fuzzy logic(to be efficient, economic) and other mathematical principles.

4.2) If you have invented your own project, please describe the project and the scope.

No.

4.3) Why did you choose this project?

I like AI since I was a freshman, I have some experiences on AI and got a 100 out of 100 in my Machine Learning course on MOOC. Since AI of wesnoth should include strategy analysis on terrain, time, arms, special abilities of units and many other aspects, I read the famous ancient Chinese book The Art of War by Sun Tzu since I was young, so I like and good at analysing these elements.

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

Time Tasks
Week 1
  • familiar with the overall structure of Wesnoth project
  • familiar with the AI part
Week 2
  • design algorithm into detail
  • learn useful interfaces
Week 3
  • implement prototypes
  • test prototypes
Week 4
  • analyse feedbacks
  • refine algorithm
Week 5
  • to be updated

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

This will be updated later.

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

Familiar with the workflow of an open source community and keep working as a part of community. Improve my skill on programming and communication. The joy of accomplishment of the project.

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

Creative, smart and friendly people in the community. Working as a part of something bigger than me.


5) Practical considerations

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

Git (used for all commits)
I manage almost all of my code, either individual or team work, on git
C++ (language used for all the normal source code)
I feel comfortable with the basic and the advanced features of C++, and code a lot.
STL, Boost, Sdl (C++ libraries used by Wesnoth)
I use STL, but don't familiar with Boost and Sdl
Python (optional, mainly used for tools)
Python is my daily life tool. I catch podcast and process text file with it. And I use Django to set up my web server.
build environments (eg cmake/scons)
I use g++ and make
WML (the wesnoth specific scenario language)
It "make coding accessible"
Lua (used in combination with WML to create scenarios)
No, I don't have experience on Lua. But I can be a fast learner with the experience of C++, python, Common Lisp, Java and so on.

5.2) Which tools do you normally use for development? Why do you use them? Vim, g++, gdb, make, git. Because these tools are build-in and powerful, and I can learn and modify them since open source. I will use IDE for some big project.

5.3) What programming languages are you fluent in?

C++, Java, Python, basic part of Common Lisp

5.4) Would you mind talking with your mentor on telephone / internet phone? Not at all, I will send my phone number to my mentor if I am accepted.