Jchb AI Global Strat

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

Description

AI: Improve AI by implementing global attack/retreat decision

Page for the idea: SoC_Ideas_AI_Global_strategy

The Wesnoth AI works by making local decisions about moves and attacks. Teach it to determine if it's worth to fight offensively or defensively in a given situation.

There are 5 submitted student proposals for this idea

Aditya Pande - Global AI for Battle of Wesnoth

I propose to implement global AI using a combination of idea of Quiescence search on game tree with alpha beta pruning along with a few heuristics to make it possible to actually solve this complex game. Also this approach requires an evaluation scheme for the same.

The idea of using Quiescence search here is different than that in chess engines. Here my idea is to reduce the average branching factor for each choice made by considering the ones which do not affect the game drastically (hence called quiet moves). In this case the braching factor for a unit can be given by

braching factor=Number of attacking moves + Number of Acquire village moves + 2

The 2 represent all Quiet moves based on retreat or charging forward towards enemy. As the quiet moves above do not affect the game drastically they shall be decided based on heuristics and here I plan to only consider the greatest retreat/charge.

The idea behind my approach is based on "Wesnoth can be treated much like a continuous game, because many positions tend to be very similar to each other. Additionally, unlike discrete board games, it is not common that a very small wrong move in Wesnoth is disastrous."

The aim of the whole approach is to simplify the game complexity using few heuristics and then use approach of negamax to select a good overall global move(not the best because of the simplication done) . Also the number of attacking moves and number of acquire village moves has to be reduced to actually keep the problem solvable. (Read all the heuristics for the same in Technical description).

I also plan to divide the whole problem into independent parts whenever possible. Let me give an example, lets say that the AI is under attack on 2 fronts but there is (currently) no relation between the 2 as to say that the AI units involved can't interact(i.e they are too far and can't 'get close' to each other in next turn). My idea is that by doing such division and focusing on solving each problem individually sharply reduces the complexity of the problem.

Lastly I plan to adopt some ideas from Fuzzy Logic, FSM and Behaviour trees to improve the current model I propose.
See Aditya Pande Global AI for more information.

Vahen_Improve_AI

I would like to improve the AI by implementing Global attack / retreat decision.

Elements : Anything around the unit that can cause a change to the behavior

Behavior : Determine what the enemy is going to do based on the elements.

Deliberation : Does the best move depending on the behavior previously set .

To do so I will use probality theory to determine what is best move to do.
See Improve AI for more information.

Arveanor Global AI

Give an ai player a set of potential objectives to pursue such as taking a village, killing an enemy, defending a village etc. Also give each ai different behavior modes based on the information they have access to. i.e. fight aggressively, fight defensively, fight cautiously etc. The ai would, depending on it's current behavior mode pursue the objectives more or less rigorously depending on how they align with the current behavior.

The behaviors and objectives would not necessarily mix strongly with recruitment, however a similar system to what would analyze which behavior to be used would also be able to inform recruiting patterns. Obviously certain unit types and a large amount of certain terrain hexes give good reason to favor certain units in recruitment, of course gaining vision and taking outlying villages (i.e. AI global objectives) would play into recruitment in terms of recruiting faster units.
See SoC2014 arveanor ai for more information.

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

A rule-based expert system style solution utilizing dynamic programming to make decisions
See SoC2014 kevin AI for more information.


See SoC2014 vorobeez AI for more information.

IRC

jchb

Application template

This template is no longer asked for during the initial application. Listing it here so that we can still reference it later on.

Application Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

  I am a graduate student in Computer Science at the University of Missouri - Columbia. I've been programming and doing advanced math since my adolescence but just recently got around to graduate school. My undergraduate degree is in economics, and I have a special interest in Algorithmic Game Theory. I also gained exposure last semester to computational intelligence methods that can be used to build computer AI for games such as Wesnoth. With these in mind I am interested in building upon the existing computer AI to account for global strategy considerations. I would like to use a combination of fuzzy logic and game theory to give the AI a system with which to reason about what sorts of moves it should be performing globally based on the actions of other players.

1.2) State your preferred email address.

jcb638@mail.missouri.edu

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

jchb

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

Open source is how I got started with computers so I love the whole culture. There is nothing as exciting or prestigious to me as working with this formal mentoring program.

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

Computer Science M.S., first year, University of Missouri

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

United States - probably late night Central time, 9PM - 12AM

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

I am planning a 3 credit-hour research project with an economics professor relating to mechanism design. No plans yet to travel.

2) Experience

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

I work in a remote sensing laboratory. We have a large C++ code repository for high performance processing of large sets of digital imagery.

Last summer I worked on a project with an experimental Haskell VLSI compiler.

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

Yes, I have worked in my laboratory for two years now and am experienced working with teams and using repository and compilation toolchains

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?

 Not yet

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

2.5) Gaming experience - Are you a gamer?

 Yes. I used to play a lot, now I play whenever time allows

2.5.1) What type of gamer are you?

 Whatever is fun. I'm open-minded.

2.5.2) What type of games?

 My gaming passion is Real-time Strategy or Turn based strategy, especially team and co-op scenarios

2.5.3) What type of opponents do you prefer?

 I prefer playing human opponents

2.5.4) Are you more interested in story or gameplay?

 Gameplay. I'll read a book for the story

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've played Wesnoth off and on for at least 4 years. I usually play the AI.

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.

 completely fluent in English

3.2) What spoken languages are you fluent in?

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

   Having played DotA for a while, I am familiar with abusive criticism. I think it is inevitable as part of a passionate gaming fanbase, particularly complex strategy games. Perhaps not necessary, it is a way of enforcing standards of play and strategic concepts within a games' community.

3.4) Do you give constructive advice?

  Yes, I know how to communicate meaningful criticisms in an articulate and respectful manner

3.5) Do you receive advice well?

  I listen and don't take constructive criticism personally.

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 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 selected the global AI project

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 feel particularly qualified with my expertise in economics, computational intelligence, and general programming. It is also interesting to me.

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

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

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

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

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

• Python (optional, mainly used for tools)

no

• build environments (eg cmake/scons)

no

• WML (the wesnoth specific scenario language)

no

• Lua (used in combination with WML to create scenarios)

no

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

 gcc, vim, Make, git. I use them because they're always available. I can be at a coffee shop or at home and plug into a common environment with my code safe in the cloud.

5.3) What programming languages are you fluent in?

 C, C++, Haskell, PHP, Perl

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!

 please message me on IRC for my phone number

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