GSoC Proposal - Position Evaluation - Revision history

Henning at 15:15, 9 April 2009

2009-04-09T15:15:50Z

Henning: /* Estimated timeline */

2009-04-08T10:59:12Z

‎Estimated timeline

Ivanovic: added category SoC

2009-04-03T21:58:35Z

added category SoC

Henning: /* Open questions */

2009-04-03T11:59:20Z

‎Open questions

Henning: /* Estimated timeline */

2009-04-03T11:58:54Z

‎Estimated timeline

Henning: /* Gaming experience */

2009-04-01T13:33:05Z

‎Gaming experience

Henning: /* Open questions */

2009-04-01T13:31:51Z

‎Open questions

Henning at 13:31, 1 April 2009

2009-04-01T13:31:26Z

Henning: /* Parameter definitions */

2009-04-01T11:00:45Z

‎Parameter definitions

Henning: /* Egocentric position evaluation */

2009-04-01T10:54:45Z

‎Egocentric position evaluation

← Older revision		Revision as of 15:15, 9 April 2009
Line 1:		Line 1:
−	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]).	+	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.		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.

@@ Line 61: / Line 61: @@
 In general the aims for the 3 phases are as following:
 {| border="1"
-! Time period !! Milestone
+! Time period !! Description
 |-
 ! 20 Apr - 23 May
@@ Line 72: / Line 72: @@
 | '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
 |}
 ====Phase 0====
@@ Line 96: / Line 103: @@
 ====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==

← Older revision		Revision as of 21:58, 3 April 2009
Line 112:		Line 112:
	==Practical considerations==		==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.		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]]

← Older revision		Revision as of 11:59, 3 April 2009
Line 97:		Line 97:
	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.		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==		==Programming experience==

@@ Line 59: / Line 59: @@
 ===Estimated timeline===
 {| border="1"
 ! Time period !! Milestone
 |-
 ! 20 Apr - 23 May
-| Start game database, prototyping using matlab, familiarization with code base
+| '''Phase 0''' - Create a dataset of games. Prototyping
 |-
 ! 23 May - 6 Jul
-| Prototyping with matlab and C++, parameter search and architecture evaluation using game database
+| '''Phase 1''' - Development of algorithm in C++ with implementation optimized for performance and simplicity.
 |-
 ! 6 Jul - 10 Aug
-| Final implementation in C++ and integration into code base
+| '''Phase 2''' - Integration of algorithm into code base. Collection of feedback.
 |}
 ===Open questions===

@@ Line 84: / Line 84: @@
 ==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.
+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.
 ==Communication skills==

@@ Line 75: / Line 75: @@
 ===Open questions===
 How can the move evaluation be combined with move planning?
 How can mission objectives be implemented by shaping network architecture?
 ==Programming experience==

@@ Line 1: / Line 1: @@
-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]).
+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 evaluation with move planning in order to allow for multi-move forward planning and evaluation.
+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==

@@ Line 23: / Line 23: @@
 * 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).
+'''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.
-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.
+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.
@@ Line 31: / Line 31: @@
 '''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.
+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===

@@ Line 38: / Line 38: @@
 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===