SummerOfCodeProposal LuaAI Improvement Nephro - Revision history

Egallager: more heading level cleanup

2023-05-04T00:50:49Z

more heading level cleanup

Egallager: link/heading cleanup

2023-05-04T00:47:19Z

link/heading cleanup

Esr: Hide historical references to Subversion from the wiki search function

2013-03-21T01:40:08Z

Hide historical references to Subversion from the wiki search function

Nephro at 21:50, 18 April 2011

2011-04-18T21:50:33Z

Nephro at 21:37, 18 April 2011

2011-04-18T21:37:08Z

Nephro at 21:06, 18 April 2011

2011-04-18T21:06:02Z

Nephro at 06:55, 17 April 2011

2011-04-17T06:55:26Z

Nephro: /* The Timeline */

2011-04-17T06:52:13Z

‎The Timeline

Nephro: /* The Timeline */

2011-04-17T06:47:45Z

‎The Timeline

Nephro at 14:35, 12 April 2011

2011-04-12T14:35:33Z

@@ Line 393: / Line 393: @@
 ==Questionnaire==
 <h3>Basics</h3>
 <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 />
@@ Line 417: / 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 />
+<h3>Experience</h3>
 <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 />
@@ Line 445: / Line 442: @@
 - 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 />
-<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
 is no fun to me, as well as dieing without a single chance to succeed against hardcore pros.<br />
@@ Line 453: / Line 450: @@
 <i>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><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 />
@@ Line 464: / Line 460: @@
 https://gna.org/patch/?2638
 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 />
 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 486: / 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 />
-<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 />
 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 />
@@ Line 499: / Line 493: @@
 The timeline is here: [[SummerOfCodeProposal_LuaAI_Improvement_Nephro#The_Timeline]]
 <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 />
@@ Line 515: / 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)
 <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 />
 * 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

@@ Line 1: / Line 1: @@
 {{SoC2011Student_2|Nephro|SoC_Ideas_LuaAI_2011}}
+==Description==
 <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 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 />
 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 )
-=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 />
@@ Line 57: / Line 56: @@
 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=
+==The Timeline==
 <table class=MsoTableGrid border=1 cellspacing=0 cellpadding=0
@@ Line 386: / Line 385: @@
 - After that I will travel back to home and will be perfectly free to work on the project
-=IRC=
+==IRC==
 Nephro, Nephx
-=SoC Application=
+==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>
@@ Line 490: / Line 489: @@
 <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 />
 <b>4.2) If you have invented your own project, please describe the project and the scope.</b><br />
@@ Line 499: / Line 498: @@
 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 />
@@ Line 507: / Line 506: @@
 <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 />
 <b>4.6) What do you expect to gain from this project?</b><br />

@@ Line 456: / Line 456: @@
-<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 />
+<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 />
 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 />
@@ Line 519: / Line 519: @@
 <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.
 * 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.

@@ Line 36: / Line 36: @@
 etc, etc...<br />
+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.<br />
-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.<br />
+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 />

@@ Line 24: / Line 24: @@
 =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.
+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 />
-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
+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 />
-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.
+ROUGH example:
-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.
+ manager to brain: EVAL MOVE x y TO dx dy WITH ATTACK xenemy yenemy WEAPON 1
-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.
+ brain to manager: 1.001(meaning that it almost doesn't change anything)
-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).
+ manager to ai:    1.001
   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 53: @@
   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
 =The Timeline=

@@ Line 426: / Line 426: @@
 <br />
 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)
-<br />
+<br /><br />
+Update: and yet another patch has been submitted by me.
 <h2>Communication skills</h2>

@@ Line 347: / Line 347: @@
   </tr>
 </table>
 =IRC=

@@ Line 41: / Line 41: @@
    <p class=MsoNormal style='margin-bottom:0in;margin-bottom:.0001pt;line-height:
    normal'><b style='mso-bidi-font-weight:normal'>Description</b></p>
    </td>
   </tr>
@@ Line 59: / Line 66: @@
    <p class=MsoNormal style='margin-bottom:0in;margin-bottom:.0001pt;line-height:
    normal'>University exam session(detailed description below)</p>
    </td>
   </tr>
@@ Line 77: / Line 91: @@
    <p class=MsoNormal style='margin-bottom:0in;margin-bottom:.0001pt;line-height:
    normal'>Travelling home and preparing for work</p>
    </td>
   </tr>
@@ Line 96: / Line 117: @@
    normal'>Work on the exposure of the simplest parts of C++ AI(aspects, goals,
    actions) to <span class=SpellE>Lua</span></p>
    </td>
   </tr>
@@ Line 115: / Line 143: @@
    normal'>Creation of the low-level <span class=SpellE>Lua</span> function
    library, code cleanup</p>
    </td>
   </tr>
@@ Line 135: / Line 170: @@
    into higher level function libraries<br />(e.g. move() -&gt; wait() -&gt; move() =
    patrol())</p>
    </td>
   </tr>
@@ Line 164: / Line 206: @@
    normal'>Beginning of the work on the “brain”, design of the communication
    system</p>
    </td>
   </tr>
@@ Line 183: / Line 232: @@
    normal'>Creation of the “brain’s” structures, design of the layer merging
    mechanism</p>
    </td>
   </tr>
@@ Line 202: / Line 258: @@
    normal'>Finalization of the main part of the brain, testing it in battle
    against the current AI</p>
    </td>
   </tr>
@@ Line 220: / Line 283: @@
    <p class=MsoNormal style='margin-bottom:0in;margin-bottom:.0001pt;line-height:
    normal'>Completion of work and polishing of the project</p>
    </td>
   </tr>
@@ Line 238: / Line 308: @@
    <p class=MsoNormal style='margin-bottom:0in;margin-bottom:.0001pt;line-height:
    normal'>Vacation time and travelling back to University</p>
    </td>
   </tr>
@@ Line 260: / Line 337: @@
    minor-latin;mso-char-type:symbol;mso-symbol-font-family:Wingdings'><span
    style='mso-char-type:symbol;mso-symbol-font-family:Wingdings'>J</span></span></p>
    </td>
   </tr>
 </table>
 =IRC=