GSoC Proposal - Position Evaluation

For this year's summer of code season I would like to develop a position evaluator. Reliable position evaluation will improve the current AI in two different ways: In the short term it will be an important tool for developers in order to test their own move planning algorithms. As such it is part of the proposed AI changes for 1.7 (see Dave's forum post). In the long run, it might be possible to couple the position evaluation with move evaluation in order to allow for multi-move forward planning.

About myself

My name is Henning and I am a 27 year-old PhD student from Zurich, Switzerland. I am currently in my final year of post-graduate study at the Institute of Neuroinformatics where I model biological neural networks and study them theoretically.

The brain has some unique solutions in dealing with complexity in the environment and my aim for the near future is to try to apply some of those principles in real-world applications. Summer of code gives me a great opportunity to test out some of my ideas in a friendly environment.

Contact details

• Email: henning at ini dot phys dot ethz dot ch
• Forums: henning
• gna: henning
• IRC: henning__
• skype: jp0186

Project proposal

Parameter definitions

The factors determining the value of a given position in wesnoth are

• Material
• Development
• Synergy

Material is the basic element determining the value of a wesnoth position and also the most easy to evaluate. The player with more units will have an advantage over the player with less units (if the units are comparable in strength). Similarly, the player with an experienced unit will generally have an advantage over the player with a weaker unit (again, only if the number of units is comparable). Similarly the health of the units under a player's control has a direct influence on the value of his material. Another important factor determining a player's material is gold, both present and future (in the sense of current income).

Development refers to the position of material on the battlefield. It is easily imaginable that a player with a material advantage is in an inferior game position because he hasn't utilized his material to be useful for his purposes. This utilization can involve reaching a strategically valuable position, maneuvering close to a village that can potentially be captured, being able to attack an enemy unit, or blocking the way against an enemy attack. Evaluating this utilization is non-trivial as it depends on overall strategical considerations as well as complex interactions between units.

Synergy refers to the interactions between some friendly units that are not directly captured by the concept of Development. This can refer both to directly to special abilities or indirectly to some desirable combinations of unit specialities. For example, a healing unit in combination with a high damage, low health unit. As with Development these connections are difficult to evaluate within a classical approach.

While Material is certainly very important in determining the strength of a position in wesnoth it has one major flaw in its predictive power - it is not deterministic. Development and Synergy on the other hand can be predicted well with the exception of units being killed.

Egocentric position evaluation

The 10^10000 possible positions in a typical game of wesnoth (as discussed here) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor. Furthermore, the outcome of each move is undeterministic due to the chance involved in fighting between units.

I propose to represent each position in a massively simplified state space which is based on egocentric representation of each piece of material and corresponding areas of influence. This can be done efficiently and intuitively by representing material as nodes in a network. Connections between nodes represent units having a direct beneficial or detrimental influence on each other. Units have a certain internal activity value (roughly corresponding to the unit's HP). Interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. This can evaluate the strength of a players position in terms of development and synergy. The overall energy of a players network consisting of material, development and synergy values is then a correlate of the strength of his position. Evaluating the development and synergy values has the added advantage of providing deterministic position evaluation before any fighting has been done, potentially warning the AI that a certain move weakens the structure of ones units significantly.

I have compiled some example formulae for this in the example below.

Example

Check out this example that will hopefully shed some light on my rather cryptic description above.

General considerations

This scheme has the following advantages:

1. It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
2. It takes into account the overall structure of the position making use of synergetic effects between units.
3. It will be able to account for half-moves to maximize network energy.
4. It can take into account special abilities by shaping a units areas of influence.
5. It could potentially lead to more advanced strategical considerations by identifying the value of each unit in the context of its position in the game.
6. A modular position evaluator can either be implemented statically into the current AI or serve as a tool within formula AI, depending on how successful the approach proves to be.

Benchmarking and parameter search

In order to test an evaluation algorithm empirically as well as search for suitable parameter combinations of the network connections, I propose to first build a database of games between two human players (if these players so consent). Armed with this it will be possible to cycle through the games and evaluate each move with a prototype of my move evaluator. The predictive power of an evaluator can be tested by measuring convergence of evaluations. Alternatively data about single-player campaigns could be used. In any case a large database of played games will yield more accurate results in evaluating the position evaluator.

Estimated timeline

Time period	Milestone
20 Apr - 23 May	Start game database, prototyping using matlab, familiarization with code base
23 May - 6 Jul	Prototyping with matlab and C++, parameter search and architecture evaluation using game database
6 Jul - 10 Aug	Final implementation in C++ and integration into code base

Open questions

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

Programming experience

Although I do not have a classical engineering background I consider myself a decent self-taught programmer. My languages are C++, perl and matlab. I know how to use build-tools and SVN. Since only half of this proposal is concerned with the actual implementation I am sure I will have enough time to familiarize myself with the code base before having to commit actual changes.

Gaming experience

I am an enthusiastic gamer both on my computer as well as my PS3. I generally, enjoy games that either push the boundaries of what is technologically possible, or surprise me in some way or other. Games I have enjoyed recently are Fallout3, World of Warcraft, and Grand Theft Auto 4. I used to play a lot of Wesnoth back in what must have been 2005. It is impressive to see how much the game has matured and developed since then.

Communication skills

I am a native German speaker and speak English fluently (I studied in the UK for 4 years).

Practical considerations

I am mostly done with my thesis and expect to be working on this full-time during the Summer of Code period. I am awake 7 - 23 UTC and should be available on IRC from 7 - 17.