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)

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