Difference between revisions of "SummerOfCodeProposal Sparksteel"
Sparksteel (talk | contribs) (New page: 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, w...) |
m (Hide historical references to Subversion from the wiki search function) |
||
(107 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | + | ==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. | ||
+ | '''PS. I have uploaded a small java program which I did last summer in support of my GSoC application as I haven't had time to submit any Wesnoth Code before the deadline.. it is at the following address:''' | ||
− | + | '''address: http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24783''' | |
− | + | ==OVERALL PROJECT OUTLINE== | |
− | + | (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... please see the section below.) | |
− | + | ===WHAT THE PROOF OF CONCEPT SHOULD INCLUDE=== | |
− | |||
− | + | Currently, I am thinking that it should demonstrate the following: | |
− | 1. | + | 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) | + | 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, and just within a very restricted scenario for GSoC, say with 2-3 units on each side..), | |
− | + | 5. Also not to just rush at opponents at top speed when attacking (displays better 'stalemateish'/'holding' behaviour). | |
− | + | ===A DETAILED EXAMPLE OF MY DESIGN IN ACTION IN A PROOF-OF-CONCEPT TEST SCENARIO=== | |
− | |||
− | + | '''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. | |
− | 2. | + | If any ideas seem ambiguous or unclear, please refer to the next 2 sections (2.3 and 2.4) for details. |
− | |||
− | + | '''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 only a few days to think about some precise implementation details so far, as a response to some concerns people had about the ambitiousness of this project, so there could be one or two small details missing (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 | ||
− | 5) | + | 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: | |
− | 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. | + | //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'. | ||
+ | |||
+ | ===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 involve other 'action' classes). | ||
+ | |||
+ | |||
+ | '''''I'd just like to also emphasis here that this way of approaching the problem of constructing a more powerful AI framework, where there is a more 1-to-1 correspondence between natural ways of expressing actions and the programming, should minimize the typical problems relating to unforeseen implications elsewhere when changing 1 small part of the AI code so often faced by AI developers.''''' | ||
+ | |||
+ | |||
+ | 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). It is also very important that 'parameters' are small enough in granularity to be reusable in many different contexts, and are as independent of each other as possible (ie. they shouldn't overlap too much in the actual game-concepts which they are representing). | ||
+ | |||
+ | ==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== | ||
+ | |||
+ | |||
+ | '''April 20th to May 22nd - estimated 5*5 = 25 working days - cautious/lower estimate''' | ||
+ | (I have still exams, coursework etc. during this time..) | ||
+ | |||
+ | 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'). | ||
+ | |||
+ | - the final number of actions and parameters implemented for this GSoC is likely to be at least around 7-15 'parameters', of varying complexity, 3 of which have already been outlined above in the 'EXAMPLE OF PROOF OF CONCEPT SECTION'; And at least '6-9' actions, depending on the precise parameters chosen; 'actions' will be spread across the 3 categories ('attack/hold/defend') and cover at least 2 out of the 3 levels of abstraction (probably levels 1 and 2, as level 3 is probably the level which corresponds to many of the current Wesnoth AI actions). | ||
+ | |||
+ | '''''More detailed timing breakdown''''' | ||
+ | |||
+ | 5 days - for designing suitable questions for both players and developers (though I am less sure about the immediate impact the developer questionnaire will have on the project... That will depend upon how many people are particularly interested in Wesnoth AI part?), | ||
+ | |||
+ | 8 days - for compiling results from questionnaires and finalizing general implementation details, | ||
+ | (both general architecture and 'parameters' to include in GSoC project). | ||
+ | |||
+ | 2 days - to decide which set of 'actions' to include in the proof of concept and which 2 'mini-armies' to work with for this project. | ||
+ | |||
+ | 10 days - for starting to get a very general feel for Wesnoth framework, asking lots of questions about it in IRC, and in particular identifying the 'interfaces' between AI module and other parts of the code. | ||
+ | |||
+ | |||
+ | '''May 23rd to July 5th(official start date for coding) - estimated 6*5 + 4 = 34 working days - cautious/lower estimate''' | ||
+ | (up to early June 4-5th I will have exams, but after that it will be full steam ahead... hence +4 days in estimate) | ||
+ | |||
+ | At the end of this period, the majority of my proof-of-concept AI should be completed - implementing a restricted set of 'actions' and 'parameters' only, and using a restricted scenario, say with only 2-3 different units on each side. | ||
+ | |||
+ | '''''More detailed timing breakdown''''' | ||
+ | |||
+ | Roughly 14 days - to finalize formula for all the 7-15 'parameters'. | ||
+ | |||
+ | Roughly 14 days - to implement all 6-9 'actions'. | ||
+ | |||
+ | 6 days - 'spare', for unexpected problems etc. :) | ||
+ | |||
+ | |||
+ | '''July 6th to July 27th - estimated 3*6 = 18 working days''' | ||
+ | (mid-holidays.. much more time available..) | ||
+ | |||
+ | 3 weeks or so to both finish off the proof-of-concept implementations and test out the new AI against the current default AI. | ||
+ | |||
+ | '''''More detailed timing breakdown''''' | ||
+ | |||
+ | 4 days - together with spare days from last section.. finish proof-of-concept implementation. | ||
+ | |||
+ | 6 days - setting up required code for first test of default AI 'VS' my AI :) | ||
+ | |||
+ | 3 days - do some extensive testing (ie. multiple runs on a randomly generated small map) | ||
+ | |||
+ | 5 days - time for any bug fixing, correcting etc. | ||
+ | |||
+ | |||
+ | '''July 28th to August 17th - estimated 3*6 = 18 working days''' | ||
+ | |||
+ | More comprehensive testing, tidy up code etc. | ||
+ | |||
+ | '''''More detailed timing breakdown''''' | ||
+ | |||
+ | 3 days - second batch of runs (maybe on a slightly bigger map, depending on how the first batch of tests went) | ||
+ | |||
+ | 6 days - general release to interested developers, getting their opinions, as well as continuing with my own test games. | ||
+ | |||
+ | 9 days - 'spare' for any problems encountered previously, if all went earlier than planned (very tentatively hopefully.. :P) maybe starting final writeup/evaluation etc. | ||
+ | |||
+ | |||
+ | '''August 17th (end of actual progress on project)''' | ||
+ | (THE END... almost anyways..) | ||
+ | |||
+ | |||
+ | '''Note about testing''' | ||
+ | |||
+ | I have a feeling that activities such as extensive unit testing etc. will be unlikely to be particularly useful in the context of this particular project, as it will be both handled by just 1 main programmer (me) and also will concentrate on a relatively small number of functionalities. However, the more abstract and difficult 'integration testing' bit (ie. testing the behavior/effectiveness of my AI under actual game conditions) will probably be both far more important and time-consuming. This is why I have added liberal sprinkles of 'spare' time allowance in... in order to ensure on-schedule delivery at the end of the summer. | ||
+ | |||
+ | ==ANSWERS TO QUESTIONS== | ||
+ | |||
+ | ===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 S­­V­­N (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?''' | ||
+ | |||
+ | * Sub­­version (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; Basic c++. | ||
+ | |||
+ | '''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..) | ||
+ | |||
+ | |||
+ | [[Category:Summer of Code]] |
Latest revision as of 00:08, 21 March 2013
Contents
- 1 BRIEF INTRODUCTION
- 2 OVERALL PROJECT OUTLINE
- 2.1 WHAT THE PROOF OF CONCEPT SHOULD INCLUDE
- 2.2 A DETAILED EXAMPLE OF MY DESIGN IN ACTION IN A PROOF-OF-CONCEPT TEST SCENARIO
- 2.3 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.
- 2.4 Part 2 – a rough outline of my proposed AI engine design
- 2.5 Notes for the design outlined in Part 2
- 2.6 A notes on the role of parameters in this design
- 3 ANSWERS TO POSSIBLE OBJECTIONS OR LIMITATIONS
- 4 PROJECT TIMELINE
- 5 ANSWERS TO QUESTIONS
- 6 COMMENTS
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.
PS. I have uploaded a small java program which I did last summer in support of my GSoC application as I haven't had time to submit any Wesnoth Code before the deadline.. it is at the following address:
address: http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24783
OVERALL PROJECT OUTLINE
(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... please see the section below.)
WHAT THE PROOF OF CONCEPT SHOULD INCLUDE
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, and just within a very restricted scenario for GSoC, say with 2-3 units on each side..),
5. Also not to just rush at opponents at top speed when attacking (displays better 'stalemateish'/'holding' behaviour).
A DETAILED EXAMPLE OF MY DESIGN IN ACTION IN A PROOF-OF-CONCEPT TEST SCENARIO
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.
If any ideas seem ambiguous or unclear, please refer to the next 2 sections (2.3 and 2.4) for details.
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 only a few days to think about some precise implementation details so far, as a response to some concerns people had about the ambitiousness of this project, so there could be one or two small details missing (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'.
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 involve other 'action' classes).
I'd just like to also emphasis here that this way of approaching the problem of constructing a more powerful AI framework, where there is a more 1-to-1 correspondence between natural ways of expressing actions and the programming, should minimize the typical problems relating to unforeseen implications elsewhere when changing 1 small part of the AI code so often faced by AI developers.
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). It is also very important that 'parameters' are small enough in granularity to be reusable in many different contexts, and are as independent of each other as possible (ie. they shouldn't overlap too much in the actual game-concepts which they are representing).
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
April 20th to May 22nd - estimated 5*5 = 25 working days - cautious/lower estimate (I have still exams, coursework etc. during this time..)
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').
- the final number of actions and parameters implemented for this GSoC is likely to be at least around 7-15 'parameters', of varying complexity, 3 of which have already been outlined above in the 'EXAMPLE OF PROOF OF CONCEPT SECTION'; And at least '6-9' actions, depending on the precise parameters chosen; 'actions' will be spread across the 3 categories ('attack/hold/defend') and cover at least 2 out of the 3 levels of abstraction (probably levels 1 and 2, as level 3 is probably the level which corresponds to many of the current Wesnoth AI actions).
More detailed timing breakdown
5 days - for designing suitable questions for both players and developers (though I am less sure about the immediate impact the developer questionnaire will have on the project... That will depend upon how many people are particularly interested in Wesnoth AI part?),
8 days - for compiling results from questionnaires and finalizing general implementation details, (both general architecture and 'parameters' to include in GSoC project).
2 days - to decide which set of 'actions' to include in the proof of concept and which 2 'mini-armies' to work with for this project.
10 days - for starting to get a very general feel for Wesnoth framework, asking lots of questions about it in IRC, and in particular identifying the 'interfaces' between AI module and other parts of the code.
May 23rd to July 5th(official start date for coding) - estimated 6*5 + 4 = 34 working days - cautious/lower estimate
(up to early June 4-5th I will have exams, but after that it will be full steam ahead... hence +4 days in estimate)
At the end of this period, the majority of my proof-of-concept AI should be completed - implementing a restricted set of 'actions' and 'parameters' only, and using a restricted scenario, say with only 2-3 different units on each side.
More detailed timing breakdown
Roughly 14 days - to finalize formula for all the 7-15 'parameters'.
Roughly 14 days - to implement all 6-9 'actions'.
6 days - 'spare', for unexpected problems etc. :)
July 6th to July 27th - estimated 3*6 = 18 working days
(mid-holidays.. much more time available..)
3 weeks or so to both finish off the proof-of-concept implementations and test out the new AI against the current default AI.
More detailed timing breakdown
4 days - together with spare days from last section.. finish proof-of-concept implementation.
6 days - setting up required code for first test of default AI 'VS' my AI :)
3 days - do some extensive testing (ie. multiple runs on a randomly generated small map)
5 days - time for any bug fixing, correcting etc.
July 28th to August 17th - estimated 3*6 = 18 working days
More comprehensive testing, tidy up code etc.
More detailed timing breakdown
3 days - second batch of runs (maybe on a slightly bigger map, depending on how the first batch of tests went)
6 days - general release to interested developers, getting their opinions, as well as continuing with my own test games.
9 days - 'spare' for any problems encountered previously, if all went earlier than planned (very tentatively hopefully.. :P) maybe starting final writeup/evaluation etc.
August 17th (end of actual progress on project)
(THE END... almost anyways..)
Note about testing
I have a feeling that activities such as extensive unit testing etc. will be unlikely to be particularly useful in the context of this particular project, as it will be both handled by just 1 main programmer (me) and also will concentrate on a relatively small number of functionalities. However, the more abstract and difficult 'integration testing' bit (ie. testing the behavior/effectiveness of my AI under actual game conditions) will probably be both far more important and time-consuming. This is why I have added liberal sprinkles of 'spare' time allowance in... in order to ensure on-schedule delivery at the end of the summer.
ANSWERS TO QUESTIONS
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; Basic c++.
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..)