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

Shofixti - Smarter and more human recruitment algorithm

As I have come to understand it, the current RCA AI recruitment algorithm suffers from a few flaws and a general lack of complexity. Given the chance, i'd like to completely redo this algorithm to allow the AI to factor in more variables and generally behave more like a human opponent than it currently does.

Project Ideas

All of these are broad ideas for the goal of a new re-factored AI, not implementation strategies.

Purpose Driven Recruitment

In order to create the right tool for the right job, it's important the the AI be able to create units for a specific purpose. Scouts for capturing villages in early-game, Sea units for quickly accessing islands, Defensive specialists for when the pressure is on, and Support units when the need arises. The recruitment algorithm would need to assign each created unit a sort of purpose attribute, and perhaps one day down the road these purposes could be implemented by the AI in combat and movement phases.

Relevant Terrain Awareness

As far as I am aware currently the AI only factors in the typical terrain of the map as a whole. This can lead to problems like the AI deciding to produce mermen as foot soldiers in a ground war, only because lots of water happens to exist on the map. I believe that having the AI know, at least in a really general sense, the type of terrain the unit will need to eventually traverse will greatly aid the recruitment decision making process.

Multiple Leader Support

In order to facilitate multiple leaders, it may be necessary to rewrite the recruitment stage to be subdivided between leaders. I imagine that this would be done using a similar Candidate Action Value system, in order to determine which leader should produce when. This approach would allow leaders to work in concert and adapt to each-other, as well as deciding where is physically the better place to recruit at a given time.

Adaptability

It is of the utmost importance that a newly written AI be able to analyze the battle as a whole up to this point and adjust recruitment based on:

1: Heavy losses of a unit type (The AI must know when to fill in missing ranks, and when to take a different approach)

2: The type of unit being favored by the opponent(s)

3: Current need for support units

Limiting the AI

A good AI implementation wouldn't aim to simply improve the AI strategically but also to increase the sense that the player is fighting against a human opponent, not a predictable machine. I would suggest that, if it has not already been done, that this newly re-factored AI would be capable of the following:

1: In fog of war maps, the AI should only be able to decide what counter-units to produce based off the opposing units it has encountered. Otherwise the AI would appear to be omniscient.

2: As mentioned in the list of requirements, the AI should be capable of entering a gold conservation mode, so that it doesn't simply spend everything each chance it gets.

3: Take into account scenario definable unit limits.

Project Section of the Questionnaire

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?

Yes, AI: Refactor recruitment algorithm
The 7 points covered in the ideas page for this project would be my highest priority
My overarching theme in the development in a re-factoring of the AI would be "Smarter and more Human". I can think of a few very minor ideas to make the AI behave closer to a human than it currently is. These include purpose driven recruitment and use of limited knowledge in fog of war games.
It's also very important that the AI be very configurable (if that's even a word) by the scenario editor.

4.2) If you have invented your own project, please describe the project and the scope.

I did not. All of my own project ideas would likely be shot down. I'm too new here to think I know what this project needs more than you folks do.

4.3) Why did you choose this project?

Conversations on IRC with a few other development members really set my creative blood on fire for AI design. It made me remember how much I enjoyed experimenting with AI long ago when I used to experiment in 3D engines... It's something i'd love to tackle again.
Additionally, I believe that a smarter AI recruitment, especially a purpose driven one, could change the gameplay experience of single player scenarios to an extreme.

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

Please keep in mind that this is only the broadest of estimates:
Most of May: Work with whoever will help me in IRC to learn everything there is to know about development in Wesnoth. This way when coding starts i'm already ready to go! (Maybe even with some early prototypes)
Early-Mid June: Focus on creating the initial framework of a new AI based on the old. Allow for new systems such as Multi-Leader recruitment, Per-Leader recruitment tables and assigning a purpose to each unit. (Perhaps someday I can get around to making these purposes matter, gameplay wise, but that sounds outside the scope of this project)
Mid-Late June: Refine all of the terrible mistakes I made in the previous two weeks into a solid starting point for the new AI.
July: Examine each of the "Seven Points" the project should hit on, and find creative, elegant solutions for each.
August: Continue to refine work on the "Seven Points", AI recruitment should at this point be taking shape as a superior replacement to old AI
September: Finish work on AI recruitment for GSOC. In all likelihood, continue work on AI even after GSOC is over, in order to implement the "purpose driven recruitment" changes into actual gameplay

4.5) Include as much technical detail about your implementation as you can

Each unit created by an AI should receive a "purpose" attribute for later reference by the AI when issuing movement and combat commands.
Simple path-finding algorithms will be used to find likely routes to either hostile forces or capture targets. These algorithms will then build a data structure, likely a tree, containing the terrain types, which will then be reduced to averages and usable values in order to determine which unit types would work best. Performance may be a concern here, so I will refine my approach as needed. (I'm an adept Assembly programmer, so if need be I can reduce some algorithms to assembly code in order to promote optimization)
The recruitment stage will be subdivided into leader recruitment stages, using a similar system of CA values to determine which leader should produce in what order. This can take into account location of keep, gold distribution per leader, available unit types, etc.
A conservation mode flag will be added
In truth, I don't know much about the workings of the Wesnoth source to be confident enough to provide exact implementation details. I need more hands on experience first.

4.6) What do you expect to gain from this project?

Primarily I would like to get to better acquaint myself with the workings of an open-source community project.
Improving my proficiency with C++ is always a bonus (I'm pretty well versed, but this is a great opportunity to stay in practice over the summer)
I also want to take this time to learn how to use Visual Studio. So many jobs out there require experience with it that I think it's high time I moved out of Eclipse and got some.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?

I already mostly plan to. You folks seem almost weirdly nice in the IRC dev channel.

IRC

Shofixti

Questionnaire

Please see the following page for the questionnaire: User:Shofixti/Questionnaire

User:Shofixti/GSoC13/Proposal

Contents