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)

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 'feeling under threat'?).

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

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

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

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

AT LEVEL 1 (top level, most abstract)

The AI carries out a global 'evaluation' of the current game position, based on a suitable set of parameters (extracted from the questionnaires mentioned in Part 1). And then chooses only 1 'action' out of the following 3 disjoint sets of decisions at a global level, choosing from either 'attack', 'hold' or 'defend' decisions. This will result in a decision made with respect to a probabilistic distribution - such as 80% likelihood to 'attack', 15% likelihood to 'defend', 5% likelihood to 'hold'. After this initial choice is made, a further probabilistic choice is made 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 booster 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

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

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.

ANSWERS TO QUESTIONS

(In progress ...)

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

2) 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)

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?

2.4) Open Source

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

2.5) Gaming experience - Are you a gamer?

2.5.1) What type of gamer are you?

2.5.2) What type of games?

2.5.3) What type of opponents do you prefer?

2.5.4) Are you more interested in story or gameplay?

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

We do not plan to favor Wesnoth players as such, but some particular projects require a good feeling for the game which is hard to get without having played intensively.

3) Communication skills

3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.

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

3.3) Do you give constructive advice?

3.4) Do you receive advice well?

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

4) Project

4.1) Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?

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

4.3) Why did you choose this project?

4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".

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

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

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

5) Practical considerations

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

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

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

5.3) What programming languages are you fluent in?

5.4) What spoken languages are you fluent in?

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

5.6) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail.