Nephro SoC2013

This page is related to Summer of Code 2013

See the list of Summer of Code 2013 Ideas

This is a Summer of Code 2013 student page

Description

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.

My first year project was overly optimistic, I was not aware of the actual complexity and never even got to implementing it, since I was really behind on the mandatory tasks. Looking back to the project proposed by me in 2011 I can't say I am still excited about it in general, but it has a few very good points I would like to emphasize.

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

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.

One of the good points I see in that project is the idea of a concurrent system. The RCA AI does a great job of separating the turn into logical sections, but is really limited in time, since it starts computation only after the AI system receives control. Tens of seconds and sometimes even minutes of CPU time is left without utilization, while human players(or even other AI players) make decisions and execute them. Even the animation time of movement, combat, recruiting, healing, etc., can be used for calculation. Modern CPU's can allow flawless execution of the game. On my PC wesnoth barely reaches 40% of CPU load at peak times. I really think the free time can be used for AI calculations.

Another reason why I think this idea is good, is that AI developers that I discussed it with stated that they have algorithms implemented that do not meet reasonable time limits for termination. These algorithms might be used for testing the finished project and/or deployment into mainline. These algorithms are typically variants of exhaustive searches and are of exponential complexity, but can be reduced to polynomial complexity using heuristics and constraints.

What can it do

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.

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

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

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.

The whole idea is that almost any out-of-sync problem can be mitigated with minimal damage with a linear algorithm. Even without complex analysis algorithms, concurrency can at least speed up the current AI. Also, complex algorithms that go out-of-sync, can be used "as is" in some situations. E.g. we are trying to determine our current position(whether we are winning or not) using some complex algorithm. It does not terminate for the current game state before the user ends his turn and some CA is requesting the positional coefficient. Usually 1-2 moves can not change the situation dramatically, for this reason, the error in coefficient can be treated as insignificant and used for decision making. Decisions might not be optimal, but will still be much better and stronger.

Research and investigation

It is still unclear to me, how Lua fits in with concurrency, but I will do the needed research on the matter throughout the remainder of May. Even if it becomes clear that it is not possible to implement concurrent Lua support, the AI can still use all of the benefits that concurrent C++ algorithms can provide.

Research on the currently used concurrency libraries and paradigms in Wesnoth will also be done.

Intended outcomes

• fully completed concurrent block with clear interfaces and usage manuals
• all pre-gsoc tasks completed
• attack vectors refactored and enemy attacks vector available
• any other bugfixes and/or usage problem solution

Pre-GSoC tasks

• reimplement persistent storage system for Lua AI engines - complete
• implement support for parameterized candidate actions
• investigation on concurrency in Wesnoth and Lua in particular
• candidate action unit filtering
• begin work on refactoring attack vector calculation and providing an enemy attacks vector

Project timeline

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.

The part of the timeline after the midterm evaluation period is not really clear, due to the fact that research on the matter has not been carried out yet and I am not certain about some aspects of the project(like support for Lua). Also, experience shows that things tend to go wrong, fall behind and just simply not work, so the time after midterm evaluations is very valuable for buffering any undone tasks. Tasks not associated with the concurrent block do not show up after August the 1st, but it does not mean that all of the time is going to be used for the concurrent block development, these tasks are not yet identified, but there is lots to be done for the AI, e.g. Lua AI's core.cpp got slightly out of hand and can use lots of refactoring, since it contains code duplication, functional inconsistencies and maybe even memory leaks(about 50% of the problems is introduced in my code, that I've done during my first GSoC).

I am constantly in touch with active AI developers and LuaAI users, so I am always up-to-date on problems with the systems and suggestions for new features and functionality. Therefore, the timeline for the non-concurrency tasks may be altered.

Task	Date	Status
Lua engine/CA/extCA storage system	Week starting on May 6th	Completed
Parameterized candidate actions support	Week starting on May 13th	Incomplete
Investigation of concurrency systems used in Wesnoth	May 13th - June 1st	In progress
CA Filters	Week starting on May 20th	Incomplete
Investigation of C++/Lua support for concurrency	Week starting on June 3rd	Incomplete
Refactoring attacks vector calculation functions	Week starting on June 3rd till end of June	Incomplete
Creating a specification for the concurrent block	Week starting on June 10th	Incomplete
Providing enemy attacks vector	Week starting on July 1st	Incomplete
Implementing concurrency block interfaces and creating needed backend and statistical tools	From week starting on June 17th till the end of June	Incomplete
Implementation of the concurrency block and dummy algorithms for testing purposes	July - August	Incomplete
Assessment of progress, discussion with potential developers, testing/bugfixing, determining usability problems	First half of August	Incomplete
Stage of refactoring, attempts to translate and move existing algorithms into the concurrent block	2nd half of August till mid September	Incomplete
Finishing and cleaning up	Mid September - September 27th	Incomplete

IRC

Nephro, neph