Difference between revisions of "SummerOfCodeProposal LuaAI Improvement Nephro"

From The Battle for Wesnoth Wiki
m (more heading level cleanup)
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{SoC2011Student_2|Nephro|SoC_Ideas_LuaAI_2011}}
 
{{SoC2011Student_2|Nephro|SoC_Ideas_LuaAI_2011}}
 
+
==Description==
=Description=
 
 
<h4>Nephro - Improving and extending LuaAI</h4>
 
<h4>Nephro - Improving and extending LuaAI</h4>
 
The artificial intelligence module of Battle for Wesnoth is written in C++ and is pretty complicated for scenario developers to configure. That's why Wesnoth developers decided to extend it and allow users to write AI configurations in Lua, which is not possible at the moment.
 
The artificial intelligence module of Battle for Wesnoth is written in C++ and is pretty complicated for scenario developers to configure. That's why Wesnoth developers decided to extend it and allow users to write AI configurations in Lua, which is not possible at the moment.
  
=The Project=
+
==The Project==
It is no secret that the artificial opponents in Battle for Wesnoth are not the strongest out there. As stated in http://wiki.wesnoth.org/WhyWritingAWesnothAIIsHard, “discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.” If we let the computer analyze a situation using discrete methods, it will not only last forever to calculate a good set of moves (with all the units, recruiting and recalling), it will also suffer failure when the factor of randomness comes in. <br /><br />
+
It is no secret that the artificial opponents in Battle for Wesnoth are not the strongest out there. As stated in [[WhyWritingAWesnothAIIsHard]], “discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.” If we let the computer analyze a situation using discrete methods, it will not only last forever to calculate a good set of moves (with all the units, recruiting and recalling), it will also suffer failure when the factor of randomness comes in. <br /><br />
 
Imagine an AI (after long calculations) has discovered a perfect combination of moves, which relies on the success of the attacks of some units. The first warrior’s attacks do not reach its target. The AI has foreseen that and sends the next fighter to battle, but he fails too, even though, he had high probabilities to strike the enemy. This can last forever, and at some point the AI would be forced to recalculate its moves again and again.<br /><br />
 
Imagine an AI (after long calculations) has discovered a perfect combination of moves, which relies on the success of the attacks of some units. The first warrior’s attacks do not reach its target. The AI has foreseen that and sends the next fighter to battle, but he fails too, even though, he had high probabilities to strike the enemy. This can last forever, and at some point the AI would be forced to recalculate its moves again and again.<br /><br />
 
After thinking about this problem I’ve decided to analyze, how a human mind makes its decisions. It is obvious that we do not do a lot of calculations during the game. But what do we do, when we play? First of all, we have a plan, which might be simple or complicated, depending on our skills, knowledge of the opponent and experience. It is hard to give an AI a plan, especially a flexible one, but this problem will be partially solved later on. Second, we take a look at the map, to get a comprehensive view on, where is a good place for us to fight, where is a good place for us to defend, where is a good place for us to flee, etc. After this I almost instantly came to a mobility and battle map concept. This could serve as a foundation for an AI “brain”. If we know all the types of units we can recruit at the beginning of the game, these maps would be calculated only once. What we can do next is generate such maps for the opponent. <br /><br />
 
After thinking about this problem I’ve decided to analyze, how a human mind makes its decisions. It is obvious that we do not do a lot of calculations during the game. But what do we do, when we play? First of all, we have a plan, which might be simple or complicated, depending on our skills, knowledge of the opponent and experience. It is hard to give an AI a plan, especially a flexible one, but this problem will be partially solved later on. Second, we take a look at the map, to get a comprehensive view on, where is a good place for us to fight, where is a good place for us to defend, where is a good place for us to flee, etc. After this I almost instantly came to a mobility and battle map concept. This could serve as a foundation for an AI “brain”. If we know all the types of units we can recruit at the beginning of the game, these maps would be calculated only once. What we can do next is generate such maps for the opponent. <br /><br />
Line 22: Line 21:
 
This is how I see the very end-product. How it should perform? The most optimistic goal I can set, is that it should be able to beat the AI Wesnoth has now and should challenge newcomers by the end of the summer. Who knows, maybe in a year or so, people will search for ways to beat it using their own AI implementations(too bad Wesnoth is open-source and anyone can look in the very depths of the "brain" :D )
 
This is how I see the very end-product. How it should perform? The most optimistic goal I can set, is that it should be able to beat the AI Wesnoth has now and should challenge newcomers by the end of the summer. Who knows, maybe in a year or so, people will search for ways to beat it using their own AI implementations(too bad Wesnoth is open-source and anyone can look in the very depths of the "brain" :D )
  
=Tech corner=
+
==Tech corner==
 +
 
 +
Before starting the work on the “brain” itself, a manager class must be created, in order to enable communication between the existing AI system and the “brain”. The RCA AI loop will enquire the manager, passing the information about the action to be evaluated.<br />
 +
The manager will implement a protocol to talk with the brain, enabling people to write their own "brains" if they consider that Nephro's brain isn't good enough(you can interpret this anyway you want, it'll still be tru :) ).<br />
 +
ROUGH example:
 +
manager to brain: EVAL MOVE x y TO dx dy WITH ATTACK xenemy yenemy WEAPON 1
 +
brain to manager: 1.001(meaning that it almost doesn't change anything)
 +
manager to ai:    1.001
 +
 
 +
ai multiplies the RCA evaluation the 1.001(this is the simplest way to use the evaluation obviously)
 +
ai tells manager that move has been made
  
Before starting the work on the “brain” itself, a manager class must be created, in order to enable communication between the existing AI system and the “brain”. The RCA AI loop will enquire the manager, passing the information about the action to be evaluated.
+
etc, etc...<br />
These are basically the only two functions that would have to be used in the existing AI code(except for the code that decides what to do with the evaluation). The RCA AI loop can do whatever it wants with the evaluation, but it should
+
 
Since our “brain” consists from many layers, we have to get a structure that keeps the layers. A good structure for that could be a priority queue, because we can decide that some layers are more important that others and we have to give them a chance to be merged faster.
+
The manager will also handle errors and restart the "brain" if it crashes down. Error handling will mostly result in the manager replying "1" to the AI system(1 = neutral, if we consider it a multiplier of the RCA evaluation score) while the structures are rebuilt from scratch.
The simplest structure of the “brain” would be nothing but a two-dimensional array(a vectors of vectors probably). We know all the movement speeds of our units(and units) on all of the terrains, so we can build a simple mobility map using some formula(it isn’t designed yet). Still it will have to be wrapped in a layer type, which will allow the layers be of different implementation.
+
The most interesting thing(at least for me) are the formation graphs. I don’t know yet, how am I going to merge graphs with sequential containers, but I know that it will be fun to do. Vertices of the graph will represent the strength of the position. The graph will most probably be stretched and layered over the quadratic maps.
+
There are basically the only two functions(evaluate() and moveExecuted()) that would have to be used in the existing AI code(except for the code that decides what to do with the evaluation). The RCA AI loop can do whatever it wants with the evaluation.<br />
The “brain will work in two” threads, where one will work on the production and generation of maps and the second will merge and un-merge the resulting structure(since when we receive an updated mobility map, for example, we have to get the old one out).
+
Since our “brain” consists from many layers, we have to get a structure that keeps the layers. A good structure for that could be a priority queue, because we can decide that some layers are more important that others and we have to give them a chance to be merged faster. Merging will just be taking values of corresponding elements in arrays and storing the result of some function f() in the final map, from which the evaluation for a move will be calculated. Merging formulas are yet to be discovered, but this is not the main part of the project(the main part is to actually implement this beast and making it at least somehow improve the existing strength of the AI and to teach it how to defend). Self balancing formulas could also be an idea in perspective(not this summer of course)<br />
 +
The simplest structure of the “brain” would be nothing but a two-dimensional array(a vectors of vectors probably). We know all the movement speeds of our units(and units) on all of the terrains, so we can build a simple mobility map using some formula(it isn’t designed yet). Still it will have to be wrapped in a layer type, which will allow the layers be of different implementation.<br />
 +
The most interesting thing(at least for me) are the formation graphs. I don’t know yet, how am I going to merge graphs with sequential containers, but I know that it will be fun to do. Vertices of the graph will represent the strength of the position. The graph will most probably be stretched and layered over the quadratic maps.<br />
 +
The “brain will work in two” threads, where one will work on the production and generation of maps and the second will merge and un-merge the resulting structure(since when we receive an updated mobility map, for example, we have to get the old one out).<br />
 +
While discussing this with one of my friends, he told me that he read a book called "Programming Pearls" and there was a chapter describing some sort of tree structure, that was able to handle dynamics of many objects moving at once. Since we have no predefined character move sequence, we may try considering that all of the units move at once and experimentally find out, whether it's a good idea to do so.
  
 
  20110416 15:21:46< fendrin> I have understood that the brain lives in a separate thread where it does constantly update a database, right?
 
  20110416 15:21:46< fendrin> I have understood that the brain lives in a separate thread where it does constantly update a database, right?
Line 39: Line 52:
 
  20110416 15:33:21< Nephro> fendrin, it may also be able to take over control at some point, that will be time consuming too, since it will transform from an evaluator, to a generator, but I don't think that is possible to achieve by the end of the summer, I plan to work on that during autumn/winter, since the university programm bores me to death
 
  20110416 15:33:21< Nephro> fendrin, it may also be able to take over control at some point, that will be time consuming too, since it will transform from an evaluator, to a generator, but I don't think that is possible to achieve by the end of the summer, I plan to work on that during autumn/winter, since the university programm bores me to death
  
 +
As you can see from the chat log, the request complexity be O(1), that is it will respond in constant time and the AI will not start thinking longer(as someone might have seen in chess, where the move computations might last forever). The structures on the other hand will take their time to generate themselves, since good decisions don’t come from air.<br / >
  
=The Timeline=
+
P.S.: It is hard for me to write this section, because the idea is constantly in my head, growing and changing, and although the overview stays the same, technical details change all the time. If you have any further questions about really specific details, please ask me on IRC, Mail or forums. Sample code is irrelevant here, since we are dealing mostly with data structures and algorithms, and the code itself will not be used, but writing the exact way, how will I generate graphs and search them with BFS seems more like an implementation, rather than description. Thanks
 +
 
 +
==The Timeline==
  
 
<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
 
<table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
Line 369: Line 385:
 
- After that I will travel back to home and will be perfectly free to work on the project
 
- After that I will travel back to home and will be perfectly free to work on the project
  
=IRC=
+
==IRC==
 
Nephro, Nephx
 
Nephro, Nephx
  
=SoC Application=
+
==SoC Application==
 
[http://www.google-melange.com/gsoc/proposal/review/google/gsoc2011/nephro/1 SoC Application]
 
[http://www.google-melange.com/gsoc/proposal/review/google/gsoc2011/nephro/1 SoC Application]
  
=Questionnaire=
+
==Questionnaire==
<h2>Basics</h2>
+
<h3>Basics</h3>
 
 
 
<b>1.1) Write a small introduction to yourself.</b>
 
<b>1.1) Write a small introduction to yourself.</b>
 
Hello! My name is Dmitry Kovalenko and I am a candidate student for GSoC 2011. I study computing science and hope to become a game developer, because, in my opinion, it is one of the rare industries, where programming is still interesting. I am fond of algorithms and data structures, which combines to an interest in the field of artificial intelligence for games. It's common for the top chess players of the world to play against computer opponents, but who knows, maybe in 5 years, computers will challenge the big names in the computer gaming community.<br />
 
Hello! My name is Dmitry Kovalenko and I am a candidate student for GSoC 2011. I study computing science and hope to become a game developer, because, in my opinion, it is one of the rare industries, where programming is still interesting. I am fond of algorithms and data structures, which combines to an interest in the field of artificial intelligence for games. It's common for the top chess players of the world to play against computer opponents, but who knows, maybe in 5 years, computers will challenge the big names in the computer gaming community.<br />
Line 401: Line 416:
 
No, I don't have any commitments at all, except for weekly ballgame matches, but they take place on weekends, so will not affect my work.<br />
 
No, I don't have any commitments at all, except for weekly ballgame matches, but they take place on weekends, so will not affect my work.<br />
  
 
+
<h3>Experience</h3>
<h2>Experience</h2>
 
 
 
 
<b>2.1) What programs/software have you worked on before?</b><br />
 
<b>2.1) What programs/software have you worked on before?</b><br />
 
Most of the time I developed software for various contests, never had a chance to do my own projects, but I don't regret that, because my "career" was not only challenging and fun, it also provided a wide range of sophisticated tasks, which I had to implement using set technologies and languages, often unsuitable ones. From that I learnt, which languages are good/bad and where can I use them efficiently.<br />
 
Most of the time I developed software for various contests, never had a chance to do my own projects, but I don't regret that, because my "career" was not only challenging and fun, it also provided a wide range of sophisticated tasks, which I had to implement using set technologies and languages, often unsuitable ones. From that I learnt, which languages are good/bad and where can I use them efficiently.<br />
Line 429: Line 442:
 
- LoL: League of Legends, game similar to DotA, but running on its own engine<br />
 
- LoL: League of Legends, game similar to DotA, but running on its own engine<br />
 
- HoN: Heroes of Newerth, another similae to DotA and LoL game<br />
 
- HoN: Heroes of Newerth, another similae to DotA and LoL game<br />
<i>2.5.3) What type of opponents do you prefer?<br />
+
<i>2.5.3) What type of opponents do you prefer?</i><br />
 
I prefer opponents that are slightly stronger than I am, mostly because beating up young(bad?) players  
 
I prefer opponents that are slightly stronger than I am, mostly because beating up young(bad?) players  
 
is no fun to me, as well as dieing without a single chance to succeed against hardcore pros.<br />
 
is no fun to me, as well as dieing without a single chance to succeed against hardcore pros.<br />
Line 438: Line 451:
 
I've found Wesnoth in summer of 2009, when I was working in an office, used to play it during lunch breaks. In autumn, I played it in the train, while travelling to school. My friend noticed that and showed interest, so we started battling each other every morning. Although most of the play time I played single player scenarios, I certainly lean towards multiplayer games, PvP or versus AI.<br />
 
I've found Wesnoth in summer of 2009, when I was working in an office, used to play it during lunch breaks. In autumn, I played it in the train, while travelling to school. My friend noticed that and showed interest, so we started battling each other every morning. Although most of the play time I played single player scenarios, I certainly lean towards multiplayer games, PvP or versus AI.<br />
  
 
+
<b>2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our S&shy;&shy;V&shy;&shy;N (during the evaluation period or earlier) please state so.</b><br />
<b>2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.</b><br />
 
 
At the moment of writing(28/3/11) I submitted only one patch, the purpose of which was only to get to know the codebase better, experiment with Lua and C++ and just to mark my existence at GNA :)<br />
 
At the moment of writing(28/3/11) I submitted only one patch, the purpose of which was only to get to know the codebase better, experiment with Lua and C++ and just to mark my existence at GNA :)<br />
 
The patch itself: https://gna.org/patch/?2599<br />
 
The patch itself: https://gna.org/patch/?2599<br />
Line 448: Line 460:
 
https://gna.org/patch/?2638
 
https://gna.org/patch/?2638
 
The patch received some feedback from Crab_, so I will probably have to work on it further.
 
The patch received some feedback from Crab_, so I will probably have to work on it further.
<h2>Communication skills</h2>
+
<h3>Communication skills</h3>
 
 
 
<b>3.1) Though most of our developers are not native English speakers, English is the project's working language.  Describe your fluency level in written English.</b><br />
 
<b>3.1) Though most of our developers are not native English speakers, English is the project's working language.  Describe your fluency level in written English.</b><br />
 
I think my knowledge of English is sufficient to work on and contribute to Wesnoth. I passed the IELTS test with overall band of 7.5 and study in Scotland, where everything takes place in English.<br />
 
I think my knowledge of English is sufficient to work on and contribute to Wesnoth. I passed the IELTS test with overall band of 7.5 and study in Scotland, where everything takes place in English.<br />
Line 470: Line 481:
 
I do not like the "see how it turns out" approach, because that led me to tons of refactoring of my code(and code of other people). I'd rather spend 5 minutes of a more experienced programmer to find out what I am asked to do, then spend 20 minutes of him explaining to me what have I done wrong and why, and how to fix it now. Time investments before starting the work will almost always lead to time economy later.<br />
 
I do not like the "see how it turns out" approach, because that led me to tons of refactoring of my code(and code of other people). I'd rather spend 5 minutes of a more experienced programmer to find out what I am asked to do, then spend 20 minutes of him explaining to me what have I done wrong and why, and how to fix it now. Time investments before starting the work will almost always lead to time economy later.<br />
  
<h2>Project</h2>
+
<h3>Project</h3>
 
 
 
<b>4.1)Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?</b><br />
 
<b>4.1)Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?</b><br />
I selected Crab's project on improving and extending the AI of BfW(http://wiki.wesnoth.org/SoC_Ideas_LuaAI_2011), since AI is one of my fields of interest and this is the perfect opportunity to learn, how real AIs actually work. The experience on developing and investigating the current AI will let me not make mistakes in the future. in my opinion, game AI is one of the most fun programming spheres out there.<br />
+
I selected Crab's project on improving and extending the AI of BfW ([[SoC_Ideas_LuaAI_2011]]), since AI is one of my fields of interest and this is the perfect opportunity to learn, how real AIs actually work. The experience on developing and investigating the current AI will let me not make mistakes in the future. in my opinion, game AI is one of the most fun programming spheres out there.<br />
 
I want to concentrate on the last part of the idea: the interaction between the AI teams. That seems very challenging and even more fun, but to get there, of course, I will have to work efficiently to complete the other tasks in time.<br />
 
I want to concentrate on the last part of the idea: the interaction between the AI teams. That seems very challenging and even more fun, but to get there, of course, I will have to work efficiently to complete the other tasks in time.<br />
 
<b>4.2) If you have invented your own project, please describe the project and the scope.</b><br />
 
<b>4.2) If you have invented your own project, please describe the project and the scope.</b><br />
Line 482: Line 492:
 
I don't have any significant plans for the summer. I have two trainings a week, both in the evenings and some matches that always take place on Saturdays and Sundays.<br />
 
I don't have any significant plans for the summer. I have two trainings a week, both in the evenings and some matches that always take place on Saturdays and Sundays.<br />
  
The timeline is here: http://wiki.wesnoth.org/index.php?title=SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Timeline
+
The timeline is here: [[SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Timeline]]
 
 
 
<br />
 
<br />
  
 
<i>AI improvement:</i> there are some AI improvements proposed by Crab_ in his idea page, but those are not obligatory to be done. Instead, he said he welcomes discussion about interesting ideas in the AI field.<br />
 
<i>AI improvement:</i> there are some AI improvements proposed by Crab_ in his idea page, but those are not obligatory to be done. Instead, he said he welcomes discussion about interesting ideas in the AI field.<br />
 
  
 
<b>4.5) Include as much technical detail about your implementation as you can</b><br />
 
<b>4.5) Include as much technical detail about your implementation as you can</b><br />
The "Brain": http://wiki.wesnoth.org/index.php?title=SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Project<br />
+
The "Brain": [[SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Project]]<br />
 
One of the ideas I wanted to implement myself, was creating a "brain" for Wesnoth. The "brain" would be a horribly sophisticated data structure that could help the RCA AI evaluate candidate moves. The "brain" would "think" in a different thread and answer to RCA requests depending on the current state. While the player makes his moves, the "brain" would constantly rebalance itself by doing positional and discrete analysis. The positional analysis would allow the AI to have a plan, and that would make it much more stronger than it is now. Discrete analysis is a bad solution for Wesnoth, because it would take forever to calculate even a small part of the possible moves, but if we have a pre-planned position the discrete analysis would boost it, find the holes in it and patch them up.<br />
 
One of the ideas I wanted to implement myself, was creating a "brain" for Wesnoth. The "brain" would be a horribly sophisticated data structure that could help the RCA AI evaluate candidate moves. The "brain" would "think" in a different thread and answer to RCA requests depending on the current state. While the player makes his moves, the "brain" would constantly rebalance itself by doing positional and discrete analysis. The positional analysis would allow the AI to have a plan, and that would make it much more stronger than it is now. Discrete analysis is a bad solution for Wesnoth, because it would take forever to calculate even a small part of the possible moves, but if we have a pre-planned position the discrete analysis would boost it, find the holes in it and patch them up.<br />
 
<b>4.6) What do you expect to gain from this project?</b><br />
 
<b>4.6) What do you expect to gain from this project?</b><br />
Line 499: Line 507:
 
Instead of answering this question directly, I will tell you what would make me leave the Wesnoth community :) I would leave if senior devs would reject my ideas and proposals. Wesnoth is a perfect project for aspiring developers to try out their skills. My numerous ideas for the AI are impossible to implement during one summer, and since I have a lot of free time during my studies at University, I will most certainly continue making the AI more powerful than it is at the moment in autumn, winter and spring(or even this summer, if I don't get accepted :D)
 
Instead of answering this question directly, I will tell you what would make me leave the Wesnoth community :) I would leave if senior devs would reject my ideas and proposals. Wesnoth is a perfect project for aspiring developers to try out their skills. My numerous ideas for the AI are impossible to implement during one summer, and since I have a lot of free time during my studies at University, I will most certainly continue making the AI more powerful than it is at the moment in autumn, winter and spring(or even this summer, if I don't get accepted :D)
 
<br />
 
<br />
<h2>Practical considerations</h2>
+
<h3>Practical considerations</h3>
 
 
 
<b>5.1) Are you familiar with any of the following tools or languages?</b><br />
 
<b>5.1) Are you familiar with any of the following tools or languages?</b><br />
* Subversion (used for all commits) -- I have used Mercurial for my work and I doubt that I will not be able to use SVN after reading the manual
+
* Sub&shy;&shy;version (used for all commits) -- I have used Mercurial for my work and I doubt that I will not be able to use S&shy;&shy;V&shy;&shy;N after reading the manual
 
* C++ (language used for all the normal source code) -- I took a course on C++, read books on it and still have a lot to learn there. My favorite language.
 
* C++ (language used for all the normal source code) -- I took a course on C++, read books on it and still have a lot to learn there. My favorite language.
 
* STL, Boost, Sdl (C++ libraries used by Wesnoth) -- STL is used in all my projects, therefore I can find my way around it. I haven't used Boost a lot, but remember refactoring a peace of code that used it extensively. Again, nothing is impossible, while we have the manuals. I used SDL only once, for a simple ping-pong game, know the basic concepts, but don't think that this library is at all relevant to AI development.
 
* STL, Boost, Sdl (C++ libraries used by Wesnoth) -- STL is used in all my projects, therefore I can find my way around it. I haven't used Boost a lot, but remember refactoring a peace of code that used it extensively. Again, nothing is impossible, while we have the manuals. I used SDL only once, for a simple ping-pong game, know the basic concepts, but don't think that this library is at all relevant to AI development.

Latest revision as of 00:50, 4 May 2023


This page is related to Summer of Code 2011
See the list of Summer of Code 2011 Ideas



This is a Summer of Code 2011 student page
Project: SoC_Ideas_LuaAI_2011


Description

Nephro - Improving and extending LuaAI

The artificial intelligence module of Battle for Wesnoth is written in C++ and is pretty complicated for scenario developers to configure. That's why Wesnoth developers decided to extend it and allow users to write AI configurations in Lua, which is not possible at the moment.

The Project

It is no secret that the artificial opponents in Battle for Wesnoth are not the strongest out there. As stated in WhyWritingAWesnothAIIsHard, “discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.” If we let the computer analyze a situation using discrete methods, it will not only last forever to calculate a good set of moves (with all the units, recruiting and recalling), it will also suffer failure when the factor of randomness comes in.

Imagine an AI (after long calculations) has discovered a perfect combination of moves, which relies on the success of the attacks of some units. The first warrior’s attacks do not reach its target. The AI has foreseen that and sends the next fighter to battle, but he fails too, even though, he had high probabilities to strike the enemy. This can last forever, and at some point the AI would be forced to recalculate its moves again and again.

After thinking about this problem I’ve decided to analyze, how a human mind makes its decisions. It is obvious that we do not do a lot of calculations during the game. But what do we do, when we play? First of all, we have a plan, which might be simple or complicated, depending on our skills, knowledge of the opponent and experience. It is hard to give an AI a plan, especially a flexible one, but this problem will be partially solved later on. Second, we take a look at the map, to get a comprehensive view on, where is a good place for us to fight, where is a good place for us to defend, where is a good place for us to flee, etc. After this I almost instantly came to a mobility and battle map concept. This could serve as a foundation for an AI “brain”. If we know all the types of units we can recruit at the beginning of the game, these maps would be calculated only once. What we can do next is generate such maps for the opponent.

At first, I thought that the existing system the RCA AI will ask these maps for an opinion on the move, but that seemed weird, since each map could give different evaluations and the RCA loop would have to make decisions (and what if we add more maps to the “brain”)? I found the solution to this problem in layering all maps together using some formula (will discuss this later). The end product could show us the key positions on the map, the capture of which are essential to win. “Wait, Nephro, isn’t this discrete analysis all over again?” It is not, note that the “brain” doesn’t produce move suggestions(yet), it just tells its opinion. Also, note that the “brain” is like an observer; it sits there and thinks all the time, taking a look on the game, when something happens there. In the beginning, when it hasn’t generated much, it stays neutral, but while the game goes on it becomes “smarter” and at some point might even take over control and start telling RCA AI what to do, instead of evaluating suggested by the RCA AI moves. This is all very optimistic, but possible, and it fits perfectly with the existing AI system.
examplesx.png
This is a very simplified example, only to illustrate the idea of the maps and layering. Colors represent numerical values: dark green = good, red = bad, other colors are something in between. On the layered map, black = horrible spot, blue = good spots. Consider the RCA AI wants to move the leader to the cell, which is black on the layered map(the example is extreme, but illustrates the idea well), in this case, the "brain" will give a horrible evaluation to a move and toss the RCA loop an idea to move the leader to the blue spot.

The next concept I want to introduce is the formation graph. This complex data structure would represent the current position of all the units on the map. Again, the “brain” will not generate good formations (at least in the beginnings), it will look for weak spots in the existing ones and tell the RCA AI, whether the suggested move improves the formation or not. The next logical decision would be, of course, layer this graph with the mobility, battle and the rest of the maps. As you can see, closer to mid-game, we receive a heavy object that lives its own life and gives opinions. Closer to late-game it is expected to start giving move suggestions instead of opinions.
start1n.jpg
The example is again very simple and it's main purpose is the illustration of the idea. The colored circles represent the strength of the position of a single unit. Green dots represent strong positions: the leader is well defended and at decent health, the fighter is ready to level-up and is also on safe distance. The red dotted unit is in trouble: not only is he at dangerously low-health, he is also a potential victim of the two enemies nearby. The colored lines represent the links between the units, representing, how fast could the neighbors come to the rescue, how safe will they be if they come, how much help can they bring, etc...

The design of such structures, in my opinion, is pure art. Each one is sophisticated by itself, but their merge must be a real challenge. As I already said, at first, the structures will be simple, they will not take into consideration a lot of the factors, aspects of the game, but it will constantly grow, like a snowball, taking more and more information into account with each step. The extension of the structure code can also be endless, everybody can add their own maps and tell the "brain", how to merge them with the others.

This design involves some fun facts, for example, the faster the opponents make their moves, the less time the “brain” is given to think, and the worse its performance will be. It is hard to evaluate the actual speed of this “thinking” process, but it is obvious, that the it will continue throughout the whole game.
This is how I see the very end-product. How it should perform? The most optimistic goal I can set, is that it should be able to beat the AI Wesnoth has now and should challenge newcomers by the end of the summer. Who knows, maybe in a year or so, people will search for ways to beat it using their own AI implementations(too bad Wesnoth is open-source and anyone can look in the very depths of the "brain" :D )

Tech corner

Before starting the work on the “brain” itself, a manager class must be created, in order to enable communication between the existing AI system and the “brain”. The RCA AI loop will enquire the manager, passing the information about the action to be evaluated.
The manager will implement a protocol to talk with the brain, enabling people to write their own "brains" if they consider that Nephro's brain isn't good enough(you can interpret this anyway you want, it'll still be tru :) ).
ROUGH example:

manager to brain: EVAL MOVE x y TO dx dy WITH ATTACK xenemy yenemy WEAPON 1
brain to manager: 1.001(meaning that it almost doesn't change anything)
manager to ai:    1.001
ai multiplies the RCA evaluation the 1.001(this is the simplest way to use the evaluation obviously)
ai tells manager that move has been made

etc, etc...

The manager will also handle errors and restart the "brain" if it crashes down. Error handling will mostly result in the manager replying "1" to the AI system(1 = neutral, if we consider it a multiplier of the RCA evaluation score) while the structures are rebuilt from scratch.

There are basically the only two functions(evaluate() and moveExecuted()) that would have to be used in the existing AI code(except for the code that decides what to do with the evaluation). The RCA AI loop can do whatever it wants with the evaluation.
Since our “brain” consists from many layers, we have to get a structure that keeps the layers. A good structure for that could be a priority queue, because we can decide that some layers are more important that others and we have to give them a chance to be merged faster. Merging will just be taking values of corresponding elements in arrays and storing the result of some function f() in the final map, from which the evaluation for a move will be calculated. Merging formulas are yet to be discovered, but this is not the main part of the project(the main part is to actually implement this beast and making it at least somehow improve the existing strength of the AI and to teach it how to defend). Self balancing formulas could also be an idea in perspective(not this summer of course)
The simplest structure of the “brain” would be nothing but a two-dimensional array(a vectors of vectors probably). We know all the movement speeds of our units(and units) on all of the terrains, so we can build a simple mobility map using some formula(it isn’t designed yet). Still it will have to be wrapped in a layer type, which will allow the layers be of different implementation.
The most interesting thing(at least for me) are the formation graphs. I don’t know yet, how am I going to merge graphs with sequential containers, but I know that it will be fun to do. Vertices of the graph will represent the strength of the position. The graph will most probably be stretched and layered over the quadratic maps.
The “brain will work in two” threads, where one will work on the production and generation of maps and the second will merge and un-merge the resulting structure(since when we receive an updated mobility map, for example, we have to get the old one out).
While discussing this with one of my friends, he told me that he read a book called "Programming Pearls" and there was a chapter describing some sort of tree structure, that was able to handle dynamics of many objects moving at once. Since we have no predefined character move sequence, we may try considering that all of the units move at once and experimentally find out, whether it's a good idea to do so.

20110416 15:21:46< fendrin> I have understood that the brain lives in a separate thread where it does constantly update a database, right?
20110416 15:22:18< fendrin> A single request from the brain is delivered out of the database in O(1)?
20110416 15:24:11< Nephro> fendrin, Indeed, and it not only updates the information known to it, it also builds new and new structures on itself. The request will hopefully be in constant time always, the simplest structures(the ones generated in the beginning of the game) will have O(n) complexity, but the each next one will be more sophisticated
20110416 15:25:40< Nephro> fendrin, as I maybe written in the description(don't remember), the "brain" might stay neutral sometimes, if it hasn't built much yet
20110416 15:30:26< Nephro> fendrin, I haven't thought about that, yet, since I wanted to discuss this matter with someone more experienced. It will certainly depend on the level chosen by the player(easy, med, hard etc)... I figured that it could be progressive, or dynamic, it will need lots of power in the beginning to start up, then it could "calm down", and progressively increase later on. 
20110416 15:32:48< fendrin> Nephro: I think it is okay to consume cpu. Realtime 3D games usually waste a complete core for rendering as best as possible. I can't see why Wesnoth should not do the same for the ai.
20110416 15:33:21< Nephro> fendrin, it may also be able to take over control at some point, that will be time consuming too, since it will transform from an evaluator, to a generator, but I don't think that is possible to achieve by the end of the summer, I plan to work on that during autumn/winter, since the university programm bores me to death

As you can see from the chat log, the request complexity be O(1), that is it will respond in constant time and the AI will not start thinking longer(as someone might have seen in chess, where the move computations might last forever). The structures on the other hand will take their time to generate themselves, since good decisions don’t come from air.

P.S.: It is hard for me to write this section, because the idea is constantly in my head, growing and changing, and although the overview stays the same, technical details change all the time. If you have any further questions about really specific details, please ask me on IRC, Mail or forums. Sample code is irrelevant here, since we are dealing mostly with data structures and algorithms, and the code itself will not be used, but writing the exact way, how will I generate graphs and search them with BFS seems more like an implementation, rather than description. Thanks

The Timeline

Date

Description

Importance level

April 17 – May 17

University exam session(detailed description below)

-

May 18 – May 22

Travelling home and preparing for work

-

May 23 – June 1

Work on the exposure of the simplest parts of C++ AI(aspects, goals, actions) to Lua

Compulsory

June 2 – June 10

Creation of the low-level Lua function library, code cleanup

Compulsory

June 11 – July 11

Gather low-level Lua function sequences into higher level function libraries
(e.g. move() -> wait() -> move() = patrol())

High

End of the compulsory part of the project

July 12 – July 15

Beginning of the work on the “brain”, design of the communication system

Compulsory

July 16 – August 1

Creation of the “brain’s” structures, design of the layer merging mechanism

High

August 2 – August 15

Finalization of the main part of the brain, testing it in battle against the current AI

Medium

August 16 – August 22

Completion of work and polishing of the project

Compulsory

August 22 – September **

Vacation time and travelling back to University

-

October - …

Further work on the “brain”, making the thing become more angry and unbeatable J

Low(no priority for the GSoC)

- I have 4 exams during the period from 18th of April to 16th of May, I will probably spend a lot of time preparing, but will be able to investigate further the AI and get an even better understanding - After that I will travel back to home and will be perfectly free to work on the project

IRC

Nephro, Nephx

SoC Application

SoC Application

Questionnaire

Basics

1.1) Write a small introduction to yourself. Hello! My name is Dmitry Kovalenko and I am a candidate student for GSoC 2011. I study computing science and hope to become a game developer, because, in my opinion, it is one of the rare industries, where programming is still interesting. I am fond of algorithms and data structures, which combines to an interest in the field of artificial intelligence for games. It's common for the top chess players of the world to play against computer opponents, but who knows, maybe in 5 years, computers will challenge the big names in the computer gaming community.

1.2) State your preferred email address.
nephro dot wes at gmail dot com.
1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?
IRC: Nephro, nephx(alternative)
Wiki, forums, GNA: Nephro

1.4) Why do you want to participate in summer of code?
I am intending to become a software developer and know the difference between a good and a bad one. It's practice and experience! It isn't possible to become a good programmer by just reading a book and finishing a University, that's why I always take the opportunities to participate in projects, do somebody's homework or just help random people on the net.
Lately I was looking for something more serious to do, even wrote a letter to some lecturers in the Uni, but no one seemed to be interested in my help. I looked up the list of Open Source projects and skimmed through it. Somewhere near the end I noticed BfW and remembered how I used to play the game when travelling to school. I went to the developer channel at freenode and started asking about chances to work on the AI(one of my fields of interest). Someone told me that GSoC is coming and that Crab_ has an AI idea for it and the next thing I know, I am writing answers to this questionnaire.

1.5) What are you studying, subject, level and school?
I am a first year student of Computing Science in the University of Glasgow. Besides programming and general computing topics(information management, HCI, systems) I study Maths and Electronics Engineering.

1.6) What country are you from, at what time are you most likely to be able to join IRC?
During summer I will stay in Latvia, which is my home country, but during term time I live in Glasgow, Scotland. Most likely I turn on my computer in the morning and the IRC client is on for the whole day. If I am programming I am available all the time, from 10 o'clock in the morning till late night, depends on how much do I want to accomplish and when did I start.
The timezone in Latvia is GMT+2, so the European community member should have no difficulties contacting me during daytime.

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.
No, I don't have any commitments at all, except for weekly ballgame matches, but they take place on weekends, so will not affect my work.

Experience

2.1) What programs/software have you worked on before?
Most of the time I developed software for various contests, never had a chance to do my own projects, but I don't regret that, because my "career" was not only challenging and fun, it also provided a wide range of sophisticated tasks, which I had to implement using set technologies and languages, often unsuitable ones. From that I learnt, which languages are good/bad and where can I use them efficiently.
I also had the opportunity to work on a large social network in a real company when I was 17, which I am proud of.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)
Two of the contests I participated in 12th grade were nationwide team contests. After winning the first one, I got invited to the same team to win the second one. This experience was probably very valuable, I had a chance to learn to evaluate tasks, decide how to distribute the tasks between the team and, of course, complete them in fixed time.
Aside from the contests, I had the experience to work in a professional team(social network mentioned in 2.1). There I learn the importance of documentation, responsibility and of course cleaning up the mess made by bad programmers before us(we received the half made project in a horrible condition). As the youngest member of the team I got to do lots of refactoring, which I started to hate by the end of the summer, but it was still valuable, since i learnt to write reusable generic code from the start, evading the need to refactor later.

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?
This is my first year in university, therefore my first attempt at GSoC.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
No, I haven't contributed to any open source projects yet, since I was always busy working or participating in contests.

2.5) Gaming experience - Are you a gamer?
I can't say that I am a gamer. Maybe I was earlier, when I had tons of free time and cared less about programming. Games were always a big part of my life, but those were not always computer games... Maybe the questions below will clear that out.
2.5.1) What type of gamer are you?
Googling "types of gamers" didn't help me :) I don't have a type, I just play when I want and what I want. The game itself doesn't mean a lot to me, I enjoy the challenge, the chance to outplay weaker players or lose to stronger ones.
2.5.2) What type of games?
When I was younger the games changed almost every week, but had the tendency to strategic gameplay. I was keen on Warcraft III TFT, played it competitively, until I understood that at some point your thinking abilities, strategy and tactics don't matter as much as microcontrol(the ability to control single units and small groups in a fight). I like thinking more than clicking the mouse 300 times per minute. Then I moved to WoW, which bored me to death with the quests that are all the same. When I spent ages to level up my character and then understood that I don't like this class, instead of creating a new char I just quit the game.
Then came the DotA family(that's what I call DotA, HoN, LoL and the rest). These games don't need hours of leveling up, don't need 300 clicks per minute, give a chance to think. After travelling between the games of this family I stopped at LoL, the engine of which provides me with what I want: dynamics, speed, flexibility.
Abbreviations:
- DotA: Defence of the Ancients, a custom Warcraft III map, where two team of 5 heroes fight each other
- LoL: League of Legends, game similar to DotA, but running on its own engine
- HoN: Heroes of Newerth, another similae to DotA and LoL game
2.5.3) What type of opponents do you prefer?
I prefer opponents that are slightly stronger than I am, mostly because beating up young(bad?) players is no fun to me, as well as dieing without a single chance to succeed against hardcore pros.
2.5.4) Are you more interested in story or gameplay?
The short answer would be: gameplay.
In PvP games the story has almost no value, because players concentrate on winning each other. Despite that, a beautiful storyline behind the characters and the world itself can certainly add to the pleasure gained while playing
2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
I've found Wesnoth in summer of 2009, when I was working in an office, used to play it during lunch breaks. In autumn, I played it in the train, while travelling to school. My friend noticed that and showed interest, so we started battling each other every morning. Although most of the play time I played single player scenarios, I certainly lean towards multiplayer games, PvP or versus AI.

2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our S­­V­­N (during the evaluation period or earlier) please state so.
At the moment of writing(28/3/11) I submitted only one patch, the purpose of which was only to get to know the codebase better, experiment with Lua and C++ and just to mark my existence at GNA :)
The patch itself: https://gna.org/patch/?2599

Update: I have submitted another patch, which is significantly bigger, but still incomplete. http://gna.org/patch/?2626 This patch will not be committed as it the work is still in progress and I intend to finish it before April 14th(it would be done faster, but I was unable to work due to illness from April 8 till April 11)

Update: and yet another patch has been submitted by me. https://gna.org/patch/?2638 The patch received some feedback from Crab_, so I will probably have to work on it further.

Communication skills

3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
I think my knowledge of English is sufficient to work on and contribute to Wesnoth. I passed the IELTS test with overall band of 7.5 and study in Scotland, where everything takes place in English.

3.2) What spoken languages are you fluent in?
Russian(native)
Latvian(as good as native)
English(fluent)

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
I am good at interacting with players, who are good at interacting with players :) If the team is passive I usually try to start some tactical discussions, give advice to players, who aren't doing too good. If they are active and polite we manage to interact pretty well, but people, who start insulting others usually get punished by not receiving help from me(which is very important in teamplay games like LoL). The enemies, well, I always admire people, who outplay me with style and beauty, and I always tell them that, but most of the time I hear bad things in my address and I may sometimes verbally fight back, using this as a psychological weapon to make the enemies more unstable and willing to punish me.

3.4) Do you give constructive advice?
I usually try to help people with constructive advice if I feel that they want to hear it, but as practice shows, not everybody is interested in argumented and constructive advice as much as they want to hear a plain answer to their question.
3.5) Do you receive advice well?
I think that I do, I learnt that from my other hobby, electronic music production, where the first steps were very tough, and the criticism received - as rough as it can get. But I managed to get through that point and now I will never ask for an answer, I'll ask for the reason.
3.6) Are you good at sorting useful criticisms from useless ones?
It can sometimes get tricky, but I usually find respected people in the community and listen to them first, since they are less likely to give obviously bad advice. My experience in programming also allows me to understand, whether the given advice is a good idea or not.
3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want
I do not like the "see how it turns out" approach, because that led me to tons of refactoring of my code(and code of other people). I'd rather spend 5 minutes of a more experienced programmer to find out what I am asked to do, then spend 20 minutes of him explaining to me what have I done wrong and why, and how to fix it now. Time investments before starting the work will almost always lead to time economy later.

Project

4.1)Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?
I selected Crab's project on improving and extending the AI of BfW (SoC_Ideas_LuaAI_2011), since AI is one of my fields of interest and this is the perfect opportunity to learn, how real AIs actually work. The experience on developing and investigating the current AI will let me not make mistakes in the future. in my opinion, game AI is one of the most fun programming spheres out there.
I want to concentrate on the last part of the idea: the interaction between the AI teams. That seems very challenging and even more fun, but to get there, of course, I will have to work efficiently to complete the other tasks in time.
4.2) If you have invented your own project, please describe the project and the scope.
-- not relevant --
4.3) Why did you choose this project?
AI(as I stated many times before) is a very fun programming topic, in my opinion, but I never really had a chance to try myself out in it. Wesnoth is a complicated positional strategy, where discrete analysis fails and any AI solution that can fight against a human mind must be a peace of art.
4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".
I don't have any significant plans for the summer. I have two trainings a week, both in the evenings and some matches that always take place on Saturdays and Sundays.

The timeline is here: SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Timeline

AI improvement: there are some AI improvements proposed by Crab_ in his idea page, but those are not obligatory to be done. Instead, he said he welcomes discussion about interesting ideas in the AI field.

4.5) Include as much technical detail about your implementation as you can
The "Brain": SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Project
One of the ideas I wanted to implement myself, was creating a "brain" for Wesnoth. The "brain" would be a horribly sophisticated data structure that could help the RCA AI evaluate candidate moves. The "brain" would "think" in a different thread and answer to RCA requests depending on the current state. While the player makes his moves, the "brain" would constantly rebalance itself by doing positional and discrete analysis. The positional analysis would allow the AI to have a plan, and that would make it much more stronger than it is now. Discrete analysis is a bad solution for Wesnoth, because it would take forever to calculate even a small part of the possible moves, but if we have a pre-planned position the discrete analysis would boost it, find the holes in it and patch them up.
4.6) What do you expect to gain from this project?
Tons of experience, friends and confidence in my programming skills. The stipend is also very tempting, since I study abroad and life in Glasgow is much more expensive that in Latvia. It would help me concentrate on my studies and think less about part time jobs and other money matters.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?
Instead of answering this question directly, I will tell you what would make me leave the Wesnoth community :) I would leave if senior devs would reject my ideas and proposals. Wesnoth is a perfect project for aspiring developers to try out their skills. My numerous ideas for the AI are impossible to implement during one summer, and since I have a lot of free time during my studies at University, I will most certainly continue making the AI more powerful than it is at the moment in autumn, winter and spring(or even this summer, if I don't get accepted :D)

Practical considerations

5.1) Are you familiar with any of the following tools or languages?

  • Sub­­version (used for all commits) -- I have used Mercurial for my work and I doubt that I will not be able to use S­­V­­N after reading the manual
  • C++ (language used for all the normal source code) -- I took a course on C++, read books on it and still have a lot to learn there. My favorite language.
  • STL, Boost, Sdl (C++ libraries used by Wesnoth) -- STL is used in all my projects, therefore I can find my way around it. I haven't used Boost a lot, but remember refactoring a peace of code that used it extensively. Again, nothing is impossible, while we have the manuals. I used SDL only once, for a simple ping-pong game, know the basic concepts, but don't think that this library is at all relevant to AI development.
  • Python (optional, mainly used for tools) -- took a course on python and currently finished studying it at university. Not a fan of it, but it's very useful in some cases, when you have to write something small, fast, inefficient, insecure...(j.k. everything depends on the developer)
  • build environments (eg cmake/scons) -- didn't have experience with such before, but successfully compiled Wesnoth in Linux and Windows(windows was a pain, but the solution was out there)...
  • WML (the wesnoth specific scenario language) -- not at all, yet. Hopefully it isn't a big problem, there still is time to learn.
  • Lua (used in combination with WML to create scenarios) -- learnt Lua in the beginning of March, after talking with Wesnoth's crew for the first time.

5.2) Which tools do you normally use for development? Why do you use them?
I like to use simple IDE's, not overstuffed with tools. I used Dev-C++ for a long time, but it had problems, that's why I transfered to Code::Blocks, which seems like a fine IDE to me atm. For Wesnoth I use MSVC9, because it is easy to compile Wesnoth in it and it also seems comfortable. I prefer Linux for development, but don't have a possibility to use a Linux machine.

5.3) What programming languages are you fluent in?
C/C++ - constantly use them and try to deepen my knowledge on every occasion.
Pascal - my first language, which I was taught to program in.
Python - fluent, but not a fan.
Java - basic knowledge, am able to create small simple applications, with a simple GUI.
PHP - used for work on a social network, don't like it, though.
Other languages are not worth mentioning.


5.4) Would you mind talking with your mentor on telephone / internet phone?
No, not at all. I do not have a phone number in Latvia at the moment, but I will post one here as soon as I get one.

This page was last edited on 4 May 2023, at 00:50.