Difference between revisions of "SummerOfCodeProposal Sparksteel"

From The Battle for Wesnoth Wiki
(OVERALL PROJECT OUTLINE (DRAFT))
(OVERALL PROJECT OUTLINE (DRAFT))
Line 19: Line 19:
  
 
At the beginning of each turn (not after each attack), go through these three steps in turn:
 
At the beginning of each turn (not after each attack), go through these three steps in turn:
 +
  
 
''AT LEVEL 1 (top level, most abstract)''
 
''AT LEVEL 1 (top level, most abstract)''
  
 
The AI carries out a global 'evaluation' of the current game position, based on a suitable set of parameters (extracted from the questionnaires mentioned in Part 1). And then chooses only 1 'action' out of the following 3 disjoint sets of decisions at a global level, choosing from either 'attack', 'hold' or 'defend' decisions. This will result in a decision made with respect to a probabilistic distribution - such as 80% likelihood to 'attack', 15% likelihood to 'defend', 5% likelihood to 'hold'.  After this initial choice is made, a further probabilistic choice is made between the elements/actions of the chosen set of actions, such as choosing within all the different available 'attack' actions at this level for example, either via direct visible actions (which at this level should be only coordinated actions requiring the entire army, such as a last ditch defence of a beleaguered leader for example), terminating the decision process for this turn, or via boosting the probabilities for the corresponding categories in the next level down ..  which is
 
The AI carries out a global 'evaluation' of the current game position, based on a suitable set of parameters (extracted from the questionnaires mentioned in Part 1). And then chooses only 1 'action' out of the following 3 disjoint sets of decisions at a global level, choosing from either 'attack', 'hold' or 'defend' decisions. This will result in a decision made with respect to a probabilistic distribution - such as 80% likelihood to 'attack', 15% likelihood to 'defend', 5% likelihood to 'hold'.  After this initial choice is made, a further probabilistic choice is made between the elements/actions of the chosen set of actions, such as choosing within all the different available 'attack' actions at this level for example, either via direct visible actions (which at this level should be only coordinated actions requiring the entire army, such as a last ditch defence of a beleaguered leader for example), terminating the decision process for this turn, or via boosting the probabilities for the corresponding categories in the next level down ..  which is
 +
  
 
''LEVEL 2 (squad-based, intermediate abstraction)''
 
''LEVEL 2 (squad-based, intermediate abstraction)''
  
 
The AI then groups all currently available units into 'squads' of various sizes, each of which again undertakes a probabilistic decision to choose one action out of the 'attack', 'hold', or 'defend' sets of actions after a squad-level evaluation (this level is mainly intended to allow for flexible behavior between different sub-groups or elements of the AI player’s army).  Again the AI will 'choose' from one of the 3 disjoint sets of actions, some of which will termination the decision process for this turn (due to them being squad-based coordinated actions), and some of which will boost the probability of the corresponding actions in ..
 
The AI then groups all currently available units into 'squads' of various sizes, each of which again undertakes a probabilistic decision to choose one action out of the 'attack', 'hold', or 'defend' sets of actions after a squad-level evaluation (this level is mainly intended to allow for flexible behavior between different sub-groups or elements of the AI player’s army).  Again the AI will 'choose' from one of the 3 disjoint sets of actions, some of which will termination the decision process for this turn (due to them being squad-based coordinated actions), and some of which will boost the probability of the corresponding actions in ..
 +
  
 
''LEVEL 3 (individual units)''
 
''LEVEL 3 (individual units)''
  
 
When the decision process gets to this point, the AI then undertakes a final individual unit-level evaluation and decides for each unit whether to 'attack', 'hold' or 'defend'.  Note that this is the level at which the majority of non-coordinated AI decisions are expected to be turned into visible actions.
 
When the decision process gets to this point, the AI then undertakes a final individual unit-level evaluation and decides for each unit whether to 'attack', 'hold' or 'defend'.  Note that this is the level at which the majority of non-coordinated AI decisions are expected to be turned into visible actions.
 +
  
 
''Notes for the design''
 
''Notes for the design''
Line 37: Line 41:
  
 
- 'attack' being a general sense of either pushing towards an enemy, or away from our AI leader;
 
- 'attack' being a general sense of either pushing towards an enemy, or away from our AI leader;
 +
 
- 'hold' being a general sense of not really pushing forwards or retreating, but performing fairly small adjustments (fortifying?) to solidify the current player's game position; and
 
- 'hold' being a general sense of not really pushing forwards or retreating, but performing fairly small adjustments (fortifying?) to solidify the current player's game position; and
 +
 
- 'defend' being more a sense of withdrawing into a more compact and mutually reinforcing position.
 
- 'defend' being more a sense of withdrawing into a more compact and mutually reinforcing position.
  

Revision as of 23:37, 24 March 2009

BRIEF INTRODUCTION

Hi, my name is Huayi. My nickname is 'Sparksteel' on both the Wesnoth forums and wiki, and Sparks_ on irc. I am a 2nd year Computer Science and AI student in the UK. Unfortunately, I am currently completely swamped with work on my course this month (as we bang in the middle of a large project for a client as part of our course this semester), so I won't be able to submit any code for consideration before the application deadline, but I hope that you guys will still take the time to consider my proposals carefully.

OVERALL PROJECT OUTLINE (DRAFT)

Part 1 – obtaining a comprehensive coverage of ALL the key game concepts and parameters which should be included in the next iteration of the Wesnoth AI.

I think that in order to make significant improvements on the current Wesnoth AI engine design, it is very important to arrive at an abstract design which takes into account of all the important game concepts and parameters (especially the less obvious ones), and is also as easily (architecturally) extendable as we can make it. With the recent release of Wesnoth 1.6, I think now would be an ideal time to conduct a series of comprehensive evaluations about the current Wesnoth AI implementation, via a number of short questionnaires for both players and developers to answer.

- The questionnaires for the players would allow us to tease out all perceived failings and limitations of the current AI (which is unlikely to be completely comprehensively covered by only a few designers), such the one mentioned by YogiHH on 'http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511' about the fact that AI leaders, or any AI units with interesting 'constant' support abilities like 'leadership' or 'illuminate' cannot currently effectively apply their support ability (by going right along the friendly frontline for example). This should enable us to gain a pretty comprehensive list of absolutely ALL important game concepts or parameters to keep in mind when evaluating a game position (and could include even very abstract ideas such as what to do when you 'feel under threat'?).

- The questionnaires for the developers on the other hand would hopefully prompt much useful discussion on different possible ways to structure the AI engine architecturally (examples could include being structured as a set of recursive functions, as a pipeline, or as a state-space based engine etc.)

Part 2 – a rough outline of my proposed AI engine design

I would like to start this section by briefly describing a high-level view of a potentially useful AI engine design for a new Wesnoth AI, as follows:

At the beginning of each turn (not after each attack), go through these three steps in turn:


AT LEVEL 1 (top level, most abstract)

The AI carries out a global 'evaluation' of the current game position, based on a suitable set of parameters (extracted from the questionnaires mentioned in Part 1). And then chooses only 1 'action' out of the following 3 disjoint sets of decisions at a global level, choosing from either 'attack', 'hold' or 'defend' decisions. This will result in a decision made with respect to a probabilistic distribution - such as 80% likelihood to 'attack', 15% likelihood to 'defend', 5% likelihood to 'hold'. After this initial choice is made, a further probabilistic choice is made between the elements/actions of the chosen set of actions, such as choosing within all the different available 'attack' actions at this level for example, either via direct visible actions (which at this level should be only coordinated actions requiring the entire army, such as a last ditch defence of a beleaguered leader for example), terminating the decision process for this turn, or via boosting the probabilities for the corresponding categories in the next level down .. which is


LEVEL 2 (squad-based, intermediate abstraction)

The AI then groups all currently available units into 'squads' of various sizes, each of which again undertakes a probabilistic decision to choose one action out of the 'attack', 'hold', or 'defend' sets of actions after a squad-level evaluation (this level is mainly intended to allow for flexible behavior between different sub-groups or elements of the AI player’s army). Again the AI will 'choose' from one of the 3 disjoint sets of actions, some of which will termination the decision process for this turn (due to them being squad-based coordinated actions), and some of which will boost the probability of the corresponding actions in ..


LEVEL 3 (individual units)

When the decision process gets to this point, the AI then undertakes a final individual unit-level evaluation and decides for each unit whether to 'attack', 'hold' or 'defend'. Note that this is the level at which the majority of non-coordinated AI decisions are expected to be turned into visible actions.


Notes for the design

The reason that I have chosen to categorize the entire set of actions which should be available to the AI during a turn all as either 'attack', 'hold', or 'defend' decisions is that all examples of maneuvers which I have thought about so far (or seen or used in games) can be sensibly interpreted as one of these 3 actions in a fairly general sense, if we apply the following interpretations:

- 'attack' being a general sense of either pushing towards an enemy, or away from our AI leader;

- 'hold' being a general sense of not really pushing forwards or retreating, but performing fairly small adjustments (fortifying?) to solidify the current player's game position; and

- 'defend' being more a sense of withdrawing into a more compact and mutually reinforcing position.

This way of approaching the AI engine design would give us conceptual extendability (ie. the basic concepts about the AI engine would not need to be revised for any new strategy or maneuver we might want to add in the future). And almost certainly lead to much more extendable code design.




To be filled out soon ...


1) Basics

1.1) Write a small introduction to yourself.

1.2) State your preferred email address.

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

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

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

1.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 Wesnoth. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.

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)

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?

2.4) Open Source

2.4.1) 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?

2.5.1) What type of gamer are you?

2.5.2) What type of games?

2.5.3) What type of opponents do you prefer?

2.5.4) Are you more interested in story or 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.

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.

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

3.3) Do you give constructive advice?

3.4) Do you receive advice well?

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

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?

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

4.3) Why did you choose this project?

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?

   * Subversion (used for all commits)
   * C++ (language used for all the normal source code)
   * Python (optional, mainly used for tools)
   * build environments (eg cmake/autotools/scons) 

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

5.3) What programming languages are you fluent in?

5.4) What spoken languages are you fluent in?

5.5) At what hours are you awake and when will you be able to be in IRC (please specify in UTC)

5.6) 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.