The Battle for Wesnoth Wiki - User contributions [en]

GSoC Proposal - Position Evaluation

2009-04-09T15:15:50Z

Henning:

For this year's summer of code season I would like to develop a position evaluator.

The idea is to provide a feedback mechanism for instant evaluation of game positions. For this project I propose this mechanism to be one way - the algorithm will not try to suggest moves to the function caller.

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]). The algorithm can be used to allow for a test of previously calculated candidate moves for their strategical viability.
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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
In general the aims for the 3 phases are as following:
{| border="1"
! Time period !! Description
|-
! 20 Apr - 23 May
| '''Phase 0''' - Create a dataset of games. Prototyping
|-
! 23 May - 6 Jul
| '''Phase 1''' - Development of algorithm in C++ with implementation optimized for performance and simplicity.
|-
! 6 Jul - 10 Aug
| '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
|}

There are two main milestones to be achieved during this project:
#The algorithm needs to be developed so that it converges towards the end of the game as one side begins to gain advantage. At the very least the algorithm should have more predictive power than an evaluation based on material in the game alone. I plan to measure the prediction of the algorithm at every stage of the game. If my algorithm is able to predict the outcome of the game either earlier or more reliable than the control then this part of the project will have succeeded.
#Secondly, if milestone one has been achieved the algorithm needs to be implemented in a fashion that is intuitive and useful to both users and developers:
#*I will make both the algorithm and test database accessible to the public
#*I will write a function to provide in-game feedback to the players (if they so wish).
#*Most importantly, I will create an interface between the algorithm and formula AI providing a function that can calculate evaluations during move planning.

====Phase 0====
*20-26 Apr: Compile wesnoth. Create game export function.
*27 Apr-3 May: Create database scenarios and collect data. Start implementing prototype algorithm.
*4-10 May: Add complexity - fighting. Come up with solution for probability distributions and make algorithm understand ''chance to kill''.
*11-17 May: Add complexity - special abilities.
*18-23 May: Add complexity - terrain.

All through phase 0 I will familiarize myself further with the code base in order to be up to speed for phase 1.

====Phase 1====
*25-31 May: Develop specification for interface between algorithm and codebase.
*1-21 Jun: Implement algorithm in C++
*22-28 Jun: Benchmark algorithm.
*29 Jun-5 Jul: Write report.

====Phase 2====
*6-19 Jul: Integrate algorithm into code base.
*20-26 Jul: Collect feedback from community
*27 Jul-2 Aug: Update algorithm according to feedback.
*3-9 Aug: Write final report.

====Phase 3====
After the summer of code, if the project has been successful I would like to continue by looking at move generation in combination with the position evaluation algorithm.

==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. Getting back on the saddle has proved to be quite easy.

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

[[Category:Summer of Code]]

GSoC Proposal - Position Evaluation

2009-04-08T10:59:12Z

Henning: /* Estimated timeline */

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
In general the aims for the 3 phases are as following:
{| border="1"
! Time period !! Description
|-
! 20 Apr - 23 May
| '''Phase 0''' - Create a dataset of games. Prototyping
|-
! 23 May - 6 Jul
| '''Phase 1''' - Development of algorithm in C++ with implementation optimized for performance and simplicity.
|-
! 6 Jul - 10 Aug
| '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
|}

There are two main milestones to be achieved during this project:
#The algorithm needs to be developed so that it converges towards the end of the game as one side begins to gain advantage. At the very least the algorithm should have more predictive power than an evaluation based on material in the game alone. I plan to measure the prediction of the algorithm at every stage of the game. If my algorithm is able to predict the outcome of the game either earlier or more reliable than the control then this part of the project will have succeeded.
#Secondly, if milestone one has been achieved the algorithm needs to be implemented in a fashion that is intuitive and useful to both users and developers:
#*I will make both the algorithm and test database accessible to the public
#*I will write a function to provide in-game feedback to the players (if they so wish).
#*Most importantly, I will create an interface between the algorithm and formula AI providing a function that can calculate evaluations during move planning.

====Phase 0====
*20-26 Apr: Compile wesnoth. Create game export function.
*27 Apr-3 May: Create database scenarios and collect data. Start implementing prototype algorithm.
*4-10 May: Add complexity - fighting. Come up with solution for probability distributions and make algorithm understand ''chance to kill''.
*11-17 May: Add complexity - special abilities.
*18-23 May: Add complexity - terrain.

All through phase 0 I will familiarize myself further with the code base in order to be up to speed for phase 1.

====Phase 1====
*25-31 May: Develop specification for interface between algorithm and codebase.
*1-21 Jun: Implement algorithm in C++
*22-28 Jun: Benchmark algorithm.
*29 Jun-5 Jul: Write report.

====Phase 2====
*6-19 Jul: Integrate algorithm into code base.
*20-26 Jul: Collect feedback from community
*27 Jul-2 Aug: Update algorithm according to feedback.
*3-9 Aug: Write final report.

====Phase 3====
After the summer of code, if the project has been successful I would like to continue by looking at move generation in combination with the position evaluation algorithm.

==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. Getting back on the saddle has proved to be quite easy.

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

[[Category:Summer of Code]]

GSoC Proposal - Position Evaluation

2009-04-03T11:59:20Z

Henning: /* Open questions */

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
In general the aims for the 3 phases are as following:
{| border="1"
! Time period !! Milestone
|-
! 20 Apr - 23 May
| '''Phase 0''' - Create a dataset of games. Prototyping
|-
! 23 May - 6 Jul
| '''Phase 1''' - Development of algorithm in C++ with implementation optimized for performance and simplicity.
|-
! 6 Jul - 10 Aug
| '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
|}

====Phase 0====
*20-26 Apr: Compile wesnoth. Create game export function.
*27 Apr-3 May: Create database scenarios and collect data. Start implementing prototype algorithm.
*4-10 May: Add complexity - fighting. Come up with solution for probability distributions and make algorithm understand ''chance to kill''.
*11-17 May: Add complexity - special abilities.
*18-23 May: Add complexity - terrain.

All through phase 0 I will familiarize myself further with the code base in order to be up to speed for phase 1.

====Phase 1====
*25-31 May: Develop specification for interface between algorithm and codebase.
*1-21 Jun: Implement algorithm in C++
*22-28 Jun: Benchmark algorithm.
*29 Jun-5 Jul: Write report.

====Phase 2====
*6-19 Jul: Integrate algorithm into code base.
*20-26 Jul: Collect feedback from community
*27 Jul-2 Aug: Update algorithm according to feedback.
*3-9 Aug: Write final report.

====Phase 3====
After the summer of code, if the project has been successful I would like to continue by looking at move generation in combination with the position evaluation algorithm.

==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. Getting back on the saddle has proved to be quite easy.

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

GSoC Proposal - Position Evaluation

2009-04-03T11:58:54Z

Henning: /* Estimated timeline */

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
In general the aims for the 3 phases are as following:
{| border="1"
! Time period !! Milestone
|-
! 20 Apr - 23 May
| '''Phase 0''' - Create a dataset of games. Prototyping
|-
! 23 May - 6 Jul
| '''Phase 1''' - Development of algorithm in C++ with implementation optimized for performance and simplicity.
|-
! 6 Jul - 10 Aug
| '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
|}

====Phase 0====
*20-26 Apr: Compile wesnoth. Create game export function.
*27 Apr-3 May: Create database scenarios and collect data. Start implementing prototype algorithm.
*4-10 May: Add complexity - fighting. Come up with solution for probability distributions and make algorithm understand ''chance to kill''.
*11-17 May: Add complexity - special abilities.
*18-23 May: Add complexity - terrain.

All through phase 0 I will familiarize myself further with the code base in order to be up to speed for phase 1.

====Phase 1====
*25-31 May: Develop specification for interface between algorithm and codebase.
*1-21 Jun: Implement algorithm in C++
*22-28 Jun: Benchmark algorithm.
*29 Jun-5 Jul: Write report.

====Phase 2====
*6-19 Jul: Integrate algorithm into code base.
*20-26 Jul: Collect feedback from community
*27 Jul-2 Aug: Update algorithm according to feedback.
*3-9 Aug: Write final report.

====Phase 3====
After the summer of code, if the project has been successful I would like to continue by looking at move generation in combination with the position evaluation algorithm.

===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. Getting back on the saddle has proved to be quite easy.

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

GSoC Proposal - Position Evaluation

2009-04-01T13:33:05Z

Henning: /* Gaming experience */

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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. Getting back on the saddle has proved to be quite easy.

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

GSoC Proposal - Position Evaluation

2009-04-01T13:31:51Z

Henning: /* Open questions */

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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.

GSoC Proposal - Position Evaluation

2009-04-01T13:31:26Z

Henning:

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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T11:00:45Z

Henning: /* Parameter definitions */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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 [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T10:54:45Z

Henning: /* Egocentric position evaluation */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|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 [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T10:54:02Z

Henning: /* Example */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|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.

===Example===
Check out [http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T10:53:43Z

Henning: /* Example */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|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.

===Example===
Check out [[http://www.ini.uzh.ch/~henning/wesnoth-algorithm.html this example]] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T10:53:14Z

Henning: /* Example */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|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.

===Example===
Check out [[https://www.ini.uzh.ch/~henning/wesnoth-algorithm.html | this example]] that will hopefully shed some light on my rather cryptic description above.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-04-01T10:45:10Z

Henning: /* Egocentric position evaluation */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|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.

===Example===
''currently preparing the figures''

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-03-31T11:21:13Z

Henning: /* Contact details */

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|here]]) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor.

I therefore 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. If we assume that units have a certain internal activity value (roughly corresponding to the unit's strength) then interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. The strength of connections will depend on the probabilities involved in mediating the units effect.
The overall energy of a players network of material is then a correlate of the strength of his position.

===Example===
''currently preparing the figures''

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

SummerOfCodeIdeas

2009-03-31T11:18:51Z

Henning: /* AI */

This is a compilation of ideas from ML. Needs to be refined (more detailed description, deliverables, workload estimation?):

== I want to be one of your Google Summer of Code students, what should I do... ==

Here is a quick list of things to do to get you started
* Create an account on gna.org
* Create an account on the wesnoth forum, and tell an admin on the IRC channel to mark is as a GSoC Student account (Admins are boucman, Ivanovic, mordante, Shadow_Master, Sirp and Turuk)
* Join the irc channel (#wesnoth-dev on irc.freenode.net) and introduce yourself. We will not give formal interviews, but we will clearly favor people we have learned to know during the selection process (basically communication via IRC is mandatory for our project! it is the main way of "every day communication" for Wesnoth. For the same reason, it's also a good idea to regularly read the [http://wesnoth.debian.net/?C=M;O=A IRC logs].).

* Start a wiki page about your idea, add a link on the bottom of this page and add this information on it:
** List your account names (gna, forum, irc nick) so that we can recognize you
** Fill the questionnaire on this page: [[SoC_Information_for_Google#Does_your_organization_have_an_application_template_you_would_like_to_see_students_use.3F_If_so.2C_please_provide_it_now.| List of questions to answer]]
** Detail your idea as much as possible, look at other students pages, and please give milestones and studies you've done
** Add a link to the page at the bottom of this page

* Though not mandatory, it is highly advisable to go to the [[EasyCoding]] and [[NotSoEasyCoding]] pages and implement one of these ideas (or any idea of similar scope) so we have an idea how you work. Be sure to use your gna account when submitting these patches so we know who it is coming from. You can also implement some features from our feature request database at gna. When you implement something, also list it on your own page with a reference to the patch.

* For working on Wesnoth you have to be able to compile trunk. To do so you should have a look at the [[WesnothSVN|page about svn]] and afterwards [[CompilingWesnoth|compile Wesnoth svn]].

* Once you have everything done here and think your idea is okay, go to [http://groups.google.com/group/google-summer-of-code-announce/web/guide-to-the-gsoc-web-app-for-student-applicants page at google] to submit your application. You have to submit it before '''Date to be supplied later''' or you have no chance to get in!

== List of Ideas for the Project (Suggestions from the wesnoth developers) ==

Here is only a short description of possible Ideas we have, each has a page of its own with a more detailed version on it.

=== Optimize implementation of WML for memory usage ===

Based on this idea: [http://dave.wesnoth.org/?p=9] optimize WML to minimize its memory usage. High memory usage has been a problem for Wesnoth, and this project will aim to reduce it.

=== Implement campaign statistics reports on stats.wesnoth.org ===

Wesnoth has an infrastructure which records details of campaigns that players play into a centralized MySQL database. However, we only have rudimentary reports based on this MySQL database available at this time, at [http://stats.wesnoth.org].

This project would involve writing a stats reporting web site which would take the data from the MySQL database and produce reports in chart and table form. Campaign designers would be able to use these reports to gather feedback on their campaigns and get ideas for improvements.

A student could largely make their choice of infrastructure for creating the Website -- whether they prefer Python, Perl, Ruby, PHP, etc. This is a great opportunity for someone who doesn't want to dive into hardcore C++ to make a valuable contribution to Wesnoth.

[[SoC Ideas Stats Server]] - Full Version of the idea, with detailed information

=== Extending the Multiplayer server ===

Our multiplayer community is generally strong and healthy, but we believe its growth is limited by some problems in the interface of the multiplayer lobby.

[[SoC Ideas Multiplayer server]] - Full version of the idea, with detailed information

=== Addon server ===
Wesnoth has an addon server which offers users to upload user
made content (UMC). This allows all other users of Wesnoth
to easily download and install this content. The server was
originally written for user-made campaigns but contains a lot
more types of addons nowadays. Both the server side and the
client side need to be improved.

[[SoC Ideas Addon Server]] - Full version of the idea, with detailed information

=== WML validation schemes ===
Wesnoth uses WML as basic data structure. Over the years
this language has evolved and got more complex. At the
moment the WML is validated at runtime and in case of a
problem the engine stops. With schemes these problems can
be validated when loading the WML, making it easier to find
problems before running into them.

[[SoC Ideas Schemes]] - Full version of the idea, with detailed information

=== Write a primitive library for Formula AI ===

Wesnoth has always had a simple C++ based AI. David (our lead developer) has been working on a simple language to write AI in Wesnoth: [[FormulaAI]]

The Wesnoth AI is used as an opponent in most campaigns, and as such is an important piece of code for the Wesnoth project. Unfortunately, because the skills required to understand and modify it are rather arcane, it is also one of the most neglected parts of the Wesnoth code. This is a place where a lot of research and useful work could be done. But keep in mind that [[WhyWritingAWesnothAIIsHard|writing an AI for Wesnoth is difficult]].

Writing a whole AI is so complicated that we believe it can't be done in a single Summer of code. All proposals should keep that in mind and try to identify an interesting subset that would be workable in the limited time of a summer of code

[[SoC Ideas FormulaAI]] - Full version of the idea, with detailed information

=== Savegame reorganization ===
The savegame formats of Wesnoth for single player campaigns
and multiplayer differ from each other. And they are processed
differently as well. Now there is an additional request coming
up: Multiplayer campaigns. The task will be to unify the savegames
for all types of scenarios in order to provide a maintainable code
again.

[[SoC Ideas Savegame]] - Full version of the idea, with detailed information

=== Other possible ideas to be fleshed out ===
A MapGenerator rewrite - better scalable for outdoor maps, plus the possibility to define areas (similar to the caverns in the cave generator) etc.

=== Make your own ideas ===
If you have your own idea the best thing is to join IRC wesnoth-dev at irc.freenode.net and discuss the idea with the developers there. If the developers think your idea is interesting and like the feature you can start to turn it into a full proposal. Once done discuss it again on IRC so the developers can accept your idea.

== Information about our Project ==
The information we provided google with about our project can be looked up at the site [[SoC Information for Google]].

Also see the [[DeveloperResources]] link (from the [[Project]] page).

== People to bug on IRC ==
We have prepared a list of people with their "area of competence". This is to give you an idea on which areas those people can be of help for you. Of course you should always just ask in the IRC chan, but those are the most likely ones to answer questions in the respective area. And here is the list:

[[SoC People to bug on IRC]]

== GSoC Student pages ==

Please add a link to your wiki page below

==== AI ====

[[SummerOfCodeProposal_Velory| Velory - SoC Proposal]]

[[SummerOfCodeProposal_AI_Improvement_Crab| Crab - SoC Proposal - AI Improvement]]

[[SummerOfCodeProposal_Sparksteel | Sparksteel - Improving the AI engine design]]

[[FormulaAISoC2009Dragonking | Dragonking - Improving the formula AI ]]

[[GSoC_Proposal_-_Position_Evaluation | henning - Position Evaluation ]]

==== Savegame reorganization ====

[[SummerOfCodeProposal_Euschn | Euschn - Savegame reorganization]]

[[SummerOfCodeProposal_lmg| lmg - Savegame reorganization]]

[[SummerOfCodeProposal_grantwu| grantwu - Savegame reorganization]]

==== Extending the Multiplayer server ====

[[SummerOfCodeProposal_rubend | rubend - Extending the Multiplayer server]]

[[SummerOfCodeProposal_IneQuation | IneQuation - Extending the Multiplayer server]]

[[MP Server Ilor | Ilor - Extending the Multiplayer server]]

==== Addon server ====

[[SummerOfCodeProposal_Ryochan7| Ryochan7 - Addon server]]

[[SummerOfCodeProposal_iyonius| iyonius - Addon server]]

==== Optimize implementation of WML for memory usage ====

[[SummerOfCodeProposal_res| res - Optimize implementation of WML for memory usage ]]

[[SummerOfCodeProposal_jdmunro| jdmunro - Optimize implementation of WML for memory usage ]]

[[SummerOfCodeProposal_Ryanc| ryanc - Optimize implementation of WML for memory usage ]]

==== WML validation schemes ====

[[SummerOfCodeProposal_orian| orian - WML validation schemes ]]

==== Implement campaign statistics reports on stats.wesnoth.org ====

[[SummerOfCodeProposal_Elbin| Elbin - New campaign statistics page]]

[[SummerOfCodeProposal_Munk| Munk - New campaign stats page]]

[[SummerOfCodeProposal_carlestyle| carlestyle - New campaign stats page]]

[[SummerOfCodeProposal_nerwa| NeRwa - New campaign stats page]]

[[SummerOfCodeProposal_mrfinch| mrfinch - New Campaign Statistics Page]]

[[SummerOfCodeProposal_corn| corn - New Campaign Statistics Page]]

[[SummerOfCodeProposal_csaunders | csaunders - SoC Proposal - Stats Server]]

[[Category:Summer of Code|*]]

GSoC Proposal - Position Evaluation

2009-03-31T11:18:11Z

Henning:

For this year's summer of code season I would like to develop a position evaluator. While this is not technically related to the improvement of formula AI, 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 [http://www.wesnoth.org/forum/viewtopic.php?f=10&t=24511 Dave's forum post]).
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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: jp0186
* 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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|here]]) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor.

I therefore 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. If we assume that units have a certain internal activity value (roughly corresponding to the unit's strength) then interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. The strength of connections will depend on the probabilities involved in mediating the units effect.
The overall energy of a players network of material is then a correlate of the strength of his position.

===Example===
''currently preparing the figures''

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-03-31T11:13:13Z

Henning: /* Contact details */

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.
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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: jp0186
* 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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|here]]) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor.

I therefore 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. If we assume that units have a certain internal activity value (roughly corresponding to the unit's strength) then interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. The strength of connections will depend on the probabilities involved in mediating the units effect.
The overall energy of a players network of material is then a correlate of the strength of his position.

===Example===
''currently preparing the figures''

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-03-31T11:10:37Z

Henning: /* Project proposal */ added example stub

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.
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|here]]) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor.

I therefore 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. If we assume that units have a certain internal activity value (roughly corresponding to the unit's strength) then interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. The strength of connections will depend on the probabilities involved in mediating the units effect.
The overall energy of a players network of material is then a correlate of the strength of his position.

===Example===
''currently preparing the figures''

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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

GSoC Proposal - Position Evaluation

2009-03-31T11:04:59Z

Henning: Initial commit

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.
In the long run, it might be possible to couple the evaluation with move planning in order to allow for multi-move forward planning and evaluation.

==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).
In a similar sense, villages can also count towards the material evaluation as they enable a player to gather resources in order to increase his material strength in the future.

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

All of these factors should be taken into account for the evaluation.

===Egocentric position evaluation===
The 10^10000 possible positions in a typical game of wesnoth (as discussed [[WhyWritingAWesnothAIIsHard|here]]) do not lend themselves well to a classical tree-search approach with material as the main evaluation factor.

I therefore 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. If we assume that units have a certain internal activity value (roughly corresponding to the unit's strength) then interactions between units can be expressed in terms of excitatory or inhibitory connections that either increase or decrease a units activity. The strength of connections will depend on the probabilities involved in mediating the units effect.
The overall energy of a players network of material is then a correlate of the strength of his position.

===General considerations===
This scheme has the following advantages:

# It massively simplifies the space of possible moves and provides a simplified context in which moves can be represented.
# It takes into account the overall structure of the position making use of synergetic effects between units.
# It will be able to account for half-moves to maximize network energy.
# It can take into account special abilities by shaping a units areas of influence.
# 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.
# 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===
{| border="1"
! 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 is such a system solved numerically in an efficient manner?

How can the move evaluation be combined with move planning?

How can mission objectives be implemented by shaping network architecture?

How can mission designers influence the ''character'' of the AI by changing network parameters?

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