SummerOfCodeProposal Sparksteel

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 want to take the time to consider my proposals carefully.

OVERALL PROJECT OUTLINE (DRAFT)

(please note that I do NOT intend to do a whole AI in 3 months, but instead only to do a proof-of-concept on a fairly strictly restricted set of functionalities using my AI design... see 'WHAT THE PROOF OF CONCEPT SHOULD INCLUDE' section)

WHAT THE PROOF OF CONCEPT SHOULD INCLUDE

(in progress...)

Currently, I am thinking that it should demonstrate the following:

1. Show that my design allows the easy insertion/deletion of further 'actions' (roughly corresponding to ideas or strategic concepts real people have and can verbalize when playing),

2. Include one or two 'special' abilities which the current AI cannot utilize properly (like utilizing 'illuminate' properly),

3. Demonstrate significantly less predictability than the current AI (whilst still doing reasonable moves),

4. Usually beat the current AI consistently (with fairly even starting resources on both sides),

5. Also not to just rush at opponents at top speed when attacking (displays better 'stalemateish'/'holding' behaviour).

AN EXAMPLE OF MY DESIGN IN ACTION IN A PROOF-OF-CONCEPT TEST SCENARIO

(in progress...)

Motivation:

After conversations with both Boucman and YogiHH at length yesterday (30/3/2009), as well as others in the Wesnoth IRC, I got the impression that there is a distinct aversion to proposals which sound a bit like 'pie-in-the-sky' ones (ie. an AI overhaul :) ), and with good reasons too (as this is certainly a very difficult and complex proposal to embark on). However, the AI in Wesnoth definitely does have plenty of room for improvement...

So in order to persuade you that this proposal is not a 'pie-in-the-sky' one, I have decided to outline some precise details of a limited-scope scenario (kind of a slightly reduced version of the sort of scenario for my eventual proof-of-concept). At this point I'd just like to reiterate that I do NOT intend to do the whole new AI design within GSoC, but simply deliver a proof-of-concept design for a more powerful AI design during GSoC, with a view to continue this work together with the Wesnoth community after this summer.

Important definitions

an 'action' - these are all supposed to be subclasses of the action superclass. Each action should correspond roughly with something a human player might say they are 'doing' whilst playing a game of Wesnoth. They might look something like this:

   class RecruitAction extends Action {...}

The action superclass might be something like this:

   abstract class Action
   {
     double probOfBeingTaken;
     abstract void execute(){}  //this actualizes an action
   }

a 'parameter' - these are concepts which should be considered in the context of a particular action in order to adjust the probabilities associated with an action, because these parameters are intended to be reusable within multiple actions, they should be as small in granularity as possible. It is also a good idea for the entire set of parameters used to be formed of disjoint elements as far as possible (ie. 2 or more parameters should not usually overlap in the actual real concepts they are representing).

Worked Example

In the explanation below, I will be using some pseudo-code, with Javaish syntax (which is largely not so different from C++ for the most part). I will also draw attention to points which show how this example directly relates to my proposed design. Also, I would be quite grateful if you could bear in mind that I have had rather little time to think about the precise details so far, so there's bound to be a few holes in the detailed design here and there (though hopefully not many..). I will also be introducing new 'parameters' and 'actions' as we need them. Here we go..

A general pattern for decision making in my design, throughout levels 1, 2 and 3 will be as follows:

   //1. manipulate the probabilities of all actions available at this level via evaluating
   //   different relevant parameters relating to each possible action,
   while(an action not yet chosen at this level)
   {
     //2. randomise the queue containing all possible actions,
     //3. chose an action to consider, if action taken, follow the process specified within the
     //   action taken, else repeat while loop.
   }

For example, lets pretend we are in a scenario where we have the following specifications (partial list only):

   All actions available at level 1 (most abstract):

   -  RecruitOnlyAction        //this only recruits units, then ends turn
   -  RecruitAndAttackAction   //this recruits units, then takes an 'attack' action
   -  AttackOnlyAction         //this does not recruit any units, but only chooses an 'attack' action
   -  GrabVillagesAction       //this action tries to boost the probability of all actions which
                               //involve grabbing villages at the squad and singleton levels (levels
                               //2 and 3)
   -  AssaultLeaderSuicidallyAction    //this would be ideal for situations where there is a great
                                       //opportunity to kill off an enemy leader

Each one of these action subclasses above would have an associated probability of been taken, using the general pattern (with the while loop) specified just above this section. These 5 actions would also appear within each of the 3 categories of actions ('attack'/'hold'/'defend') as follows:

   Attack actions:
   -  RecruitAndAttackAction
   -  AttackOnlyAction
   -  GrabVillagesAction
   -  AssaultLeaderSuicidallyAction

   Holding actions:
   -  RecruitOnlyAction
   -  RecruitAndAttackAction
   -  AttackOnlyAction
   -  GrabVillagesAction

   Defending actions:
   -  RecruitOnlyAction
   -  RecruitAndAttackAction
   -  AttackOnlyAction
   -  AssaultLeaderSuicidallyAction

It is important to note that each action can appear in more than 1 category, as long as that action (corresponding to how a person might express their choice of action) is suitable for the category.

For the purposes of this example, I will choose to expand on what happens when the 'RecruitOnlyAction' is taken.

If the 'RecruitOnlyAction' is taken, then the decision process stops for this turn, and the move is actualised, ie. the 'RecruitOnlyAction.execute()' method might look something like this:

   //set all action.probOfBeingTaken to 50% for all 'Recruit(<unit>)' type actions
   while( (still enough space on keep) & (enough money) )
   {
     for(each 'Recruit(<unit>)' type action 'ru')  //ie. Recruit(BloodBat), Recruit(Draug) ...
     {
       if(a turn limit exists)
       {
         if(unit is a scout)
           ru.setProbOfBeingTaken() =
             ru.getProbOfBeingTaken() + (-2*((current turn number) / (maximum turns) - 0.5)) * 0.2 ;
                                       //this modifier above is a 'parameter' representation, which
                                       //will initially boost, then gradually reduce the probability
                                       //of a particular 'Recruit(<unit>)' action being taken forall
                                       //'Recruit(<unit>)' type actions where the unit is tagged as
                                       //a good scout (to be explained below..).
         if(unit is a fighter)
           ru.setprobOfBeingTaken() =
             ru.getProbOfBeingTaken() + ... ;  //ie. plus some other modifier which relates the part
                                               //of the game we are in with whether the unit is a
                                               //fighter or not
         //and so on... until all parameters which need to be considered have been for the case where
         //there is a turn limit
       }
       else if(no turn limit)
       {
         ...  //do similar manipulations of the probability of each action being taken based on
              //relevant probabilities..
       }
     }
     //....
     //after all parameter-based probability manipulations have taken place,
     //use the general pattern mentioned above to chose a particular unit to recruit
     //then repeat while loop
   }

The short snippet above uses 2 further parameters (ie. whether the unit being considered is tagged as a 'scout', or a 'fighter', or both) which need to be clarified below:

The decision about whether to tag a unit as a scout might be based on the formula below:

   The unit is only tagged as a scout iff:
   -  its 'actual movement' (calculated by unit mv-pts / cost per move over majority terrain) is
      larger or equal to the value of
        (maximum  units' 'actual movement' - 6/(30 integer divide (units' 'actual movement'))
        //this should evaluate to within 1-3 'actual movement' moves of the fastest unit on the
        //players' side

And the decision about whether to tag a unit as a fighter might be based on the following:

   The unit is only tagged as a fighter iff:
   -  its 'total damage' (obtained by multiplying the damage/hit by the number of hits) is no lower
      than
        AvMaxDamage (average of maxDamage for all units for current player) - 0.15 * AvMaxDamage

A few points about the details so far..

I don't know whether these parameters are already present in Wesnoth in the form I have specified, but if so I didn't plagiarize :)

The couple of evaluations regarding whether to tag a unit as a good fighter/scout which I have just mentioned are good examples of what I see as 'parameters' to be considered by the system when modifying probabilities in the context of different 'actions'.

(to be continued..)

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 encoding the AI to be able to hypothesis about the opponents' current 'intent'?).

- 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 (possible alternatives to the current phases-based approach 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 set/category of 'actions' to consider 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 within the actions available within the chosen set of actions, such as choosing within all the different available 'attack' actions at this level for example. Actions will be either directly 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 indirect actions which boost/reduce 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 variable 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). Note that the actual actions at this level will be different to the actions at level 1, and be set against a squad-based context. 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 outlined in Part 2

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

A central concept for my design is that at each level (1,2,3), the actual 'decision' or action taken by the AI could only effect the moves taken by

- either indirectly influencing the actual moves taken this turn by boosting or subduing the probabilities of choosing various categories of actions (or maybe even individual actions themselves) at the next lowest level (ie. an indirect 'defend' decision at level 1 would boost the probabilities of all available defending 'actions' at level 2);

- or directly influencing the actual moves taken this turn by choosing an action which is actualised at the current level (essentially bypassing the lower levels), which would also terminate the AI decision process for this turn.

It is also important to note that the 'attack' / 'hold' / 'defend' decisions at each level could range from very simple actions, such as "attack the nearest enemy" (a typical level 3 action), or to more complex code which does something more abstract such as "set-up a strong defence around point x,y on the map" (this might be a level 2 decision).

In this AI engine, I envision that all actual actions available to the AI will be hardcoded subclasses of an 'action' superclass, inheriting some common members variables and functions - such as an associated probability for the action to be actualised, and an 'execute action' method/function. These hardcoded 'action' subclasses should roughly correspond to all actions which a person might imagine the AI would take, which could range from simple (level 3) actions like 'attack the nearest weakest enemy unit' to more abstract (level 1) actions like 'surround the enemy leader, but don't attack until we have at least X many units within the region nearby'. This is where the questionnaire given to the players (mentioned in Part 1) will be very helpful in ensuring that we cover the entire set of actions which would need to be implemented, as each reasonable 'action' proposed by players should have a 1-to-1 correspondence to 'action' subclasses (which may or may not involve other 'action' classes).

One part which I am currently undecided on is how to decide on the particular 'action' to be chosen from the set of available actions at any stage. I currently see two alternative ways of dealing with this:

- either via a range-based approach, where we have a particular range (say from integers 1 to 2000) which is partitioned unevenly to correspond to the 'probability distributions' of available actions within that set, for example if our randomly generated integer falls (inclusively) between 1 to 999, then we take 'Action A', if falling between 1000 to 1701 then we take 'Action B', and if falling between 1702 to 2000 then we take 'Action C', OR

- via a queue mechanism, where each action has a probability of being taken or not (for example, say 'Action A' has 75% chance of being taken, and 25% chance of not been taken), and actions are considered in turn until one is taken; where we could probably use the same decision mechanism as for determining whether a unit hits successfully or not in Wesnoth for this approach. It is important to note that in this approach, indirect actions (propagating to the next lowest level) would work by manipulating both the probability, and also the position in the queue of the actions at the lower level..

Currently I'm not sure which approach would be more appropriate.. And any other alternative approaches would be very welcome also.

A notes on the role of parameters in this design

The role of parameters in this design is essentially to represent all the concepts which need to be taken into consideration when evaluating a given board position. From simpler concepts such as the defensibility of a single square to more abstract concepts such as defensibility of a wide area near a river, to even more abstract concepts such as having both a representation of a self-generated 'intent'/'goal' and a hypothesis for an opponents' intent; the entire set of parameters encoded in the program should approach an exhaustive partitioning of the entire concept-space of both explicit and implicit factors considered when playing a game of Wesnoth. These same parameters are used in game position evaluations to ultimately produce a probability for that decision (probably by using weighted sums) and/or changes in the order of consideration for a particular decision (see previous section). The primary way of manipulating the behaviour of the Wesnoth AI (for example to 'make it more aggressive') will be through manipulating the way in which these parameters are evaluated (via their associated formulae).

ANSWERS TO POSSIBLE OBJECTIONS OR LIMITATIONS

You might think that this proposed engine design seems somewhat unsuitable for actions such as attacking and defending on multiple fronts at a time, or long range (lone) scouting for example; but this is where the propagation from a more abstract level (1) to the more fine-grained layers (2,3) come in. Essentially, most of the time, the 'decisions' at the global level (level 1 of algorithm) will not actually be expressed directly as an actual visible AI action, but they will feed into the lower layers (levels 2 and 3) as an increase or decrease in the probability of a particular action category (or sometimes individual actions) being chosen. And the use of the Global, then Squad, then Individual level divisions (together with an entirely probability-based decision system) should generate plenty of interesting emergent behaviors whilst retaining a sense of the AI carrying out some coherent and human-like strategic actions.

PROJECT TIMELINE

(in progress..)

April 20th to May 22nd

Activities will include:

- obtaining a good grasp of the overall structure of the Wesnoth source files (particularly the files relating to Wesnoth AI).

- designing a small set of suitable questions to ask players, and also another set of questions about possible other code architectures for fellow Wesnoth AI developers (see 'OVERALL PROJECT OUTLINE' -> 'Part 1').

- settling on all the small details about the final abstract design for the new AI engine, such as deciding whether to implement indirect 'actions' using queue-order adjustments or not (see 'OVERALL PROJECT OUTLINE' -> 'Notes for the design outlined in Part 2').

May 23rd (official start date for coding)

July 6th

August 17th (end of actual progress on project)

ANSWERS TO QUESTIONS

(done)

Basics

1.1) Write a small introduction to yourself.

(please see 'BRIEF INTRODUCTION' section)

1.2) State your preferred email address.

minihuang2004@yahoo.co.uk

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

(please see 'BRIEF INTRODUCTION' section)

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

It seems like a great opportunity to contribute something to the Wesnoth community (of which I have been a part of for just over 2 years approx. as a player), whilst putting theory into practice from my university course. And I get paid too of course.. :)

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

Computer Science and AI @

University of Sheffield, UK

Year 2, Undergraduate

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.

None yet..

Experience

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

A number of team projects for a variety of clients (as part of my course):

Project 1 - We developed a functional theater booking system (in Semester 1, Year 1 of my course).

Project 2 - We developed an interface for a testing API developed by one of our lecturers (in Semester 1, Year 2 of my course).

Project 3 - We are currently in the middle of developing an extensive Workload Allocation System for the university (now ongoing, as part of my course).

My own projects:

Project 4 - A program for visualizing an n by n chessboard displaying both pieces and their threat ranges (this was not a university project, but something which I did last summer for fun).

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

Yes, many times.. (See projects 1-3 in section 2.1)

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?

Haven't participated before..

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.

Not currently.

2.5) Gaming experience - Are you a gamer?

Yes.

2.5.1) What type of gamer are you?

Though I haven't currently got time to play many games, I have played many many games in the past across most of the major genres (apart from 'sports' games).

2.5.2) What type of games?

Strategy (both real-time and turn-based), RPGs, First-person adventure/shooters, 'Sneak' games (such as the Thief series), Squad-tactics (such as Ground Control series and Nexus The Jupiter Incident)..

2.5.3) What type of opponents do you prefer?

Any (as long as they are not rude..), the unpredictability of facing human opponents is what makes multiplayer so exciting.

2.5.4) Are you more interested in story or gameplay?

For singleplayer, storyline; But for multiplayer, definitely gameplay. Though if either side is too poor in singleplayer I tend to put the game right back on the shelf.

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

Yes, I have played for about 2-3 years. I tend to lean towards the singleplayer (simply because I like a good story) but have also played multiplayer on numerous occasions.

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.

Complete fluency.

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

No problem :)

3.3) Do you give constructive advice?

Yes.

3.4) Do you receive advice well?

Yes.

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

Yes.

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 - The AI project. I want to concentrate on producing an architectural design for the AI subsystem in Wesnoth which will be easily adaptable and suitable for all our future needs in that area (ie. both conceptually and concretely highly flexible/extendable). For the scope of the GSoC 2009, I am planning on producing a proof of concept implementation for my proposed design.

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

Not applicable.

4.3) Why did you choose this project?

Seemed a perfect opportunity for me to put theory into practise. Also, if this project goes well, one of the ideas I am considering doing my 3rd year dissertation on includes testing some other 'Strong AI' ideas I have using the Wesnoth platform. But due to the fact that those 'strong AI' ideas are currently still somewhat fuzzy, I have chosen to go with a 'weak AI' approach for my design for GSoC.

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 have decided to start a serious AI project (independent from course work) this summer anyways, and developing Wesnoth seemed like a great community to be involved in; but if I were selected to participate in GSoC, I would have much more time to dedicate to it. See 'PROJECT TIMELINE' section for more details.

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

(please see 'OVERALL PROJECT OUTLINE' section)

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

Practical experience of implementing an intelligent game AI, with possible follow-on projects being in the vein of replacing the current Wesnoth AI engine completely with a much more powerful design.

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

If I was selected, I think I would definitely stay as part of the Wesnoth development community afterwards.. As I have a feeling that this project should go quite well.

Practical considerations

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

   * Subversion (used for all commits),                     yes
   * C++ (language used for all the normal source code)     currently basic knowledge
   * Python (optional, mainly used for tools)               no
   * build environments (eg cmake/autotools/scons)          some experience

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

- A large variety of simple (coloured) text-editors, simply due to the 'hand-crafted' feeling, as well as the way this forces you to have a pretty complete understanding of every line of code you are writing (which makes debugging a much less painful process).

- Netbeans and Eclipse, for times when I need more speed in development..

5.3) What programming languages are you fluent in?

Java, Haskell and Prolog.

5.4) What spoken languages are you fluent in?

English and Chinese.

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

Much of the time everyday between 1000 to 0000 UTC (UK time) during summer holidays.

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.

Fine.

COMMENTS

(please put any questions/comments regarding my proposal under this section..)