Nephro SoC2013 - Revision history

Nephro: /* Description */

2013-05-13T08:49:31Z

‎Description

Nephro at 08:46, 13 May 2013

2013-05-13T08:46:55Z

Nephro at 08:40, 13 May 2013

2013-05-13T08:40:24Z

Nephro: /* More complicated algorithms */

2013-05-12T21:28:36Z

‎More complicated algorithms

Nephro: /* Project timeline */

2013-05-12T21:27:33Z

‎Project timeline

Nephro: /* Description */

2013-05-12T20:56:30Z

‎Description

Nephro: Created page with '{{SoC2013Student}} Category:SoC_Ideas_Your_Own_Ideas2013 =Description=

Nephro - AI project SoC2013

Registered this as a placeholder. Currently under heavy exam load…'

2013-05-02T23:16:42Z

Created page with '{{SoC2013Student}} Category:SoC_Ideas_Your_Own_Ideas2013 =Description= <h4>Nephro - AI project SoC2013</h4> Registered this as a placeholder. Currently under heavy exam load…'

New page

{{SoC2013Student}}
[[Category:SoC_Ideas_Your_Own_Ideas2013]]

=Description=
<h4>Nephro - AI project SoC2013</h4>
Registered this as a placeholder. Currently under heavy exam load, page will be done till Saturday.

=IRC=
Nephro, neph

@@ Line 5: / Line 5: @@
 <h4>Nephro - AI project SoC2013</h4>
-<h3>Introduction</h3>
+=Introduction=
 I learnt a lot of things during the last two summers while participating in GSoC for Wesnoth. I did a lot of analysis of the results of my work and discovered my strengths and weaknesses. I was thinking way too much about AI for the game in general while working mostly on tools to allow other developers make the computer play stronger strategically and tactically.
@@ Line 13: / Line 13: @@
 There is no need to describe how difficult it is to create a strong AI player for a game like Wesnoth, capable of competing with experienced human players. While other GSoC ideas, like implementing a new recruitment algorithm or a defense strategy mechanism, will undoubtedly strenghten the AI, I want to propose an idea that can provide a completely new dimension for AI development for Wesnoth. I must also say that I only want to work and focus on the platform that will allow new possibilities for the AI, leaving the implementation of the actual AI algorithms to my free time and/or other developers that might now the strategic aspects of the game much better than me.
-<h3>The concurrent block</h3>
+=The concurrent block=
 My first year project idea was to create a parallel system that would impact the current AI's decision making by providing additional evaluation to candidate actions, since at that time(and maybe still, I am not sure), the CA evaluation results were statically defined. The problem with this approach, as I see it now, is that the system would be too complicated to implement and it would basically be another AI system with a different approach, not able to make decisions, but able to interfere with decisions made by the RCA AI loop.
@@ Line 22: / Line 22: @@
-<h3>What can it do</h3>
+=What can it do=
-<h4>The common AI structures</h4>
+'''The common AI structures'''
 * The movement maps: movement maps currently are recalculated on demand using a quadratic time algorithm. After moving a unit a movement map is invalidated and requires recalculation. Rewriting the algorithm in a way that concurrently calculates the movement maps would allow us to get constant time access to these structures. One might say that problems might occur, since if a player constantly makes moves, the movement map is recalculated each time. I am aware of this issue and will address it in the "Synchronization issues" section.
 * The attack vectors: same as for movement maps, the attack vectors can become accessible in constant time if the algorithms are moved out to a concurrent block.
-<h4>More complicated algorithms</h4>
+'''More complicated algorithms'''
 * Positional analysis: are we ahead or are we behind? The answer to this question can be derived in many different ways, from trivial(counting the number of units on each side) to really complicated(analysing the formation, grouping of the forces, estimating gold and expansion potential, calculating possible battle outcomes). A simple "yes" or "no" answer can tell us what to do next: attack or defend. An answer in the form of a floating point number(say, 0 <= x <= 1) can allow the RCA AI adjust the aspects of the AI. The possibilities and options are endless. The more power and precision we require from such an algorithm, the higher the complexity of it becomes. It will be up to the developer to decide how complex the algorithm can be and how often will it be able to finish in time. This might require some statistical work, but results can be very rewarding.
@@ Line 37: / Line 37: @@
 Note that these are only some examples of all the possible algorithms that the AI can make use of. I will repeat myself and say that implementing these algorithms is not part of my suggested project, but I will surely implement at least a couple(maybe even dummy) algorithms for testing and presentation purposes.
-<h3>Synchronization issues</h3>
+=Synchronization issues=
 There is a certain issue with a concurrent approach to the AI in Wesnoth - we might become out of sync. A simple example could be: (1) movement maps are recalculated while a human player takes his turn; (2) human players ends turn with a move of one of his units; (3) the RCA loop gains control and makes a request for a movement map, that hasn't been recalculated yet.
-It is obvious, that the concurrent approach does not seem to be too useful in a situation like this, and such a situation is not uncommon. The solution is to refactor the movement map calculation algorithm and instead of recalculation after each invalidation, we can recalculate the movements only for affected units. We can switch from a "destroy -> build new"
+It is obvious, that the concurrent approach does not seem to be too useful in a situation like this, and such a situation is not uncommon. The solution is to refactor the movement map calculation algorithm and instead of recalculation after each invalidation, we can recalculate the movements only for affected units. We can switch from a "destroy -> build new" to a "maintain the old one" approach. So, for the situation described above, if by any means the map was not yet calculated, the request will be a blocking call, but the wait time will not be long, since we only recalculate movements for one unit. This is a reduction from O(n^2) average, to O(n) worst-case and O(1) average. Same goes for attack vectors.

@@ Line 5: / Line 5: @@
 <h4>Nephro - AI project SoC2013</h4>
-==Introduction==
+<h3>Introduction</h3>
 I learnt a lot of things during the last two summers while participating in GSoC for Wesnoth. I did a lot of analysis of the results of my work and discovered my strengths and weaknesses. I was thinking way too much about AI for the game in general while working mostly on tools to allow other developers make the computer play stronger strategically and tactically.
@@ Line 13: / Line 13: @@
 There is no need to describe how difficult it is to create a strong AI player for a game like Wesnoth, capable of competing with experienced human players. While other GSoC ideas, like implementing a new recruitment algorithm or a defense strategy mechanism, will undoubtedly strenghten the AI, I want to propose an idea that can provide a completely new dimension for AI development for Wesnoth. I must also say that I only want to work and focus on the platform that will allow new possibilities for the AI, leaving the implementation of the actual AI algorithms to my free time and/or other developers that might now the strategic aspects of the game much better than me.
-==The concurrent block==
+<h3>The concurrent block</h3>
 My first year project idea was to create a parallel system that would impact the current AI's decision making by providing additional evaluation to candidate actions, since at that time(and maybe still, I am not sure), the CA evaluation results were statically defined. The problem with this approach, as I see it now, is that the system would be too complicated to implement and it would basically be another AI system with a different approach, not able to make decisions, but able to interfere with decisions made by the RCA AI loop.
@@ Line 22: / Line 22: @@
-==What can it do==
+<h3>What can it do</h3>
-===The common AI structures===
+<h4>The common AI structures</h4>
 * The movement maps: movement maps currently are recalculated on demand using a quadratic time algorithm. After moving a unit a movement map is invalidated and requires recalculation. Rewriting the algorithm in a way that concurrently calculates the movement maps would allow us to get constant time access to these structures. One might say that problems might occur, since if a player constantly makes moves, the movement map is recalculated each time. I am aware of this issue and will address it in the "Synchronization issues" section.
 * The attack vectors: same as for movement maps, the attack vectors can become accessible in constant time if the algorithms are moved out to a concurrent block.
-===More complicated algorithms===
+<h4>More complicated algorithms</h4>
 * Positional analysis: are we ahead or are we behind? The answer to this question can be derived in many different ways, from trivial(counting the number of units on each side) to really complicated(analysing the formation, grouping of the forces, estimating gold and expansion potential, calculating possible battle outcomes). A simple "yes" or "no" answer can tell us what to do next: attack or defend. An answer in the form of a floating point number(say, 0 <= x <= 1) can allow the RCA AI adjust the aspects of the AI. The possibilities and options are endless. The more power and precision we require from such an algorithm, the higher the complexity of it becomes. It will be up to the developer to decide how complex the algorithm can be and how often will it be able to finish in time. This might require some statistical work, but results can be very rewarding.
@@ Line 37: / Line 37: @@
 Note that these are only some examples of all the possible algorithms that the AI can make use of. I will repeat myself and say that implementing these algorithms is not part of my suggested project, but I will surely implement at least a couple(maybe even dummy) algorithms for testing and presentation purposes.
-==Synchronization issues==
+<h3>Synchronization issues</h3>
 There is a certain issue with a concurrent approach to the AI in Wesnoth - we might become out of sync. A simple example could be: (1) movement maps are recalculated while a human player takes his turn; (2) human players ends turn with a move of one of his units; (3) the RCA loop gains control and makes a request for a movement map, that hasn't been recalculated yet.
-It is obvious, that the concurrent approach does not seem to be too useful in a situation like this, and such a situation is not uncommon. The solution is to refactor the movement map calculation algorithm and instead of recalculation after each invalidation, we can recalculate the movements only for affected units. We can switch from a "destroy -> build new" to a "maintain the old one" approach. So, for the situation described above, if by any means the map was not yet calculated, the request will be a blocking call, but the wait time will not be long, since we only recalculate movements for one unit. This is a reduction from O(n^2) average, to O(n) worst-case and O(1) average. Same goes for attack vectors.
+It is obvious, that the concurrent approach does not seem to be too useful in a situation like this, and such a situation is not uncommon. The solution is to refactor the movement map calculation algorithm and instead of recalculation after each invalidation, we can recalculate the movements only for affected units. We can switch from a "destroy -> build new"

@@ Line 33: / Line 33: @@
 * Positional analysis: are we ahead or are we behind? The answer to this question can be derived in many different ways, from trivial(counting the number of units on each side) to really complicated(analysing the formation, grouping of the forces, estimating gold and expansion potential, calculating possible battle outcomes). A simple "yes" or "no" answer can tell us what to do next: attack or defend. An answer in the form of a floating point number(say, 0 <= x <= 1) can allow the RCA AI adjust the aspects of the AI. The possibilities and options are endless. The more power and precision we require from such an algorithm, the higher the complexity of it becomes. It will be up to the developer to decide how complex the algorithm can be and how often will it be able to finish in time. This might require some statistical work, but results can be very rewarding.
 * Map analysis: another idea from my first year project proposal. I strongly believe that thorough map analysis before the game can have enormous impact on the AI strength. Such analysis can take into account the factions on in the current game, terrain analysis, map regions where we can set a strong formation, map regions where the enemy can stand strong, possible formation suggestions that can be used by CA's that make movement decisions. A great thing about map analysis is that can be static, which means, in a concurrent context, it can have unlimited computation time. If the algorithm is well-written, it can be partitioned to produce incremental results.
-E.g. (1) simple terrain analysis - O(n), simple formation analysis - O(n), simple "strong/weak" point detection - O(n), (2) more complex terrain analysis - O(n^2), formation analysis - O(n^2), etc, etc. Such an approach might be useful, in order to produce some results(even if they are not too useful) for CA's to use on the first turns. Such an algorithm can work throughout the whole game, it can even be designed to never terminate, the AI will grow stronger and stronger as the time goes.
+:E.g. (1) simple terrain analysis - O(n), simple formation analysis - O(n), simple "strong/weak" point detection - O(n), (2) more complex terrain analysis - O(n^2), formation analysis - O(n^2), etc, etc. Such an approach might be useful, in order to produce some results(even if they are not too useful) for CA's to use on the first turns. Such an algorithm can work throughout the whole game, it can even be designed to never terminate, the AI will grow stronger and stronger as the time goes.
 Note that these are only some examples of all the possible algorithms that the AI can make use of. I will repeat myself and say that implementing these algorithms is not part of my suggested project, but I will surely implement at least a couple(maybe even dummy) algorithms for testing and presentation purposes.
 ==Synchronization issues==

@@ Line 71: / Line 71: @@
 Learning from previous years I will not separate tasks into mandatory and optional. Everything listed in the timeline is mandatory and I will allocate the most pessimistic time possible, to preserve staying on track. Also, the concurrency block project and the rest of the tasks(bugfixes, Lua CA improvements, enemy attacks, etc) will be done in parallel, 3 hours a day each at the very least, since I am free the whole summer and have no other commitments.
 =IRC=
 Nephro, neph

@@ Line 4: / Line 4: @@
 =Description=
 <h4>Nephro - AI project SoC2013</h4>
-Registered this as a placeholder. Currently under heavy exam load, page will be done till Saturday.
 =IRC=
 Nephro, neph