GSoC Proposal Evolutionary AI

Note: Please be aware that this is still a work in progress. I am currently working to remedy this.

Questionnaire

• Basics
  • Write a small introduction about yourself.
    • My name is Micah Heineck, and I'm a senior Computer Science and Philosophy double-major at Lafayette College in Pennsylvania. I have a passion for programming, video games, and Ultimate Frisbee. I plan on pursuing evolutionary programming either in the video game industry or academically after I graduate. And my favorite beer is XIII by Weyerbacher.
  • State your preferred email address.
    • heineckm@lafayette.edu
  • If you have chosen a nick for IRC and Wesnoth forums, what is it?
    • My nickname is heineckm on everything.
  • Why do you want to participate in summer of code?
    • I am determined to find a niche for evolutionary programming in video games, and I am hoping that participating in GSoC will help me in determining how feasible this actually is.

• Experience
  • What programs/software have you worked on before?
    • As a Bachelor of Science in Computer Science, there have been innumerable projects that I have completed, in a variety of languages (specifically Python, Java, C++, and C). The project most relevant to this application is my ongoing Senior Thesis. For my thesis I designed and implemented a video game and then built an evolutionary algorithm to produce the AI to play it.
  • Have you developed software in a team environment before? (As opposed to hacking on something on your own)
    • Yes, we work in groups quite often. In fact, in 3 of my classes we have worked almost exclusively with a large group (4-5 people).
  • Have you participated in the Google Summer of Code before?
    • I applied previously, but was rejected. Apparently I was the fourth best candidate, and the organization was given only three slots.
  • Open Source
    • Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.
      • I am not already involved with any open source projects.
  • Gaming experience - Are you a gamer?
    • Yes, I am a very passionate promoter and player of video games.
  • What type of gamer are you?
    • A good one.
  • What type of games?
    • Mostly turn-based strategy games. i enjoy RPGs also, but usually only if they have a strong strategy element (like Baldur's Gate).
  • What type of opponents do you prefer?
    • Challenging opponents. I don't like games that are too easy.
  • Are you more interested in story or gameplay?
    • Gameplay is of utmost importance. A good story is nice, though.
  • Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.
    • I downloaded and played Wesnoth for a few days not too long ago. Although I'm no expert at the game, I got a good feel for it anyway. I almost always lean towards single player, in any game.

• Communication skills
  • 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 would hope that my fluency level is apparent based on the responses I've given in this questionnaire. I am a native English speaker.
  • Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
    • As I said, I'm usually a single-player gamer, and so I generally don't have to deal with other players.
  • Do you give constructive advice?
    • Yes, unless I know the recipient won't take it well.
  • Do you receive advice well?
    • I don't take well to people who come across as condescending. Regardless, though, I'm always open for advice, especially from those who have more experience than I.
  • Are you good at sorting useful criticisms from useless ones?
    • Criticisms that are general ("Everything is bad") and lack specific details or examples are usually useless criticisms. I also tend to ignore criticisms directed at my mother or my manliness.

• Project
  • 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 have come up with my own project idea.
  • If you have invented your own project, please describe the project and the scope.
    • The project I propose is to create an AI for Wesnoth that is based on an evolutionary algorithm. Please see below for further details.
  • Why did you choose this project?
    • I have previously worked on evolutionary algorithms and I am planning on incorporating them in my career. I am very confident in the ability of evolutionary algorithms to provide better AI, overall, than traditional game AI. An evolutionary AI can come up with solutions that are at least as good as traditional results, and are more dynamic, more challenging, and have substantial replay value. Additionally, evolutionary algorithms are usually less intensive to code (they are much more conceptually difficult, though). Overall, I think evolutionary algorithms are the next step for game AI, and I am hoping that developing a project to that extent will prove that these benefits are actually true.
  • 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".
    • A detailed timeline is provided below. As for special things, I would like to take a trip to Germany this summer, but that is not set in stone by any means, and GSoC will definitely take priority.
  • What do you expect to gain from this project?
    • I expect to gain a better understanding of what it's like to work in Open Source, and what it's like to have a "telecommuting" job. I also expect to learn much more about Wesnoth. I hope to gain a better insight into exactly what evolutionary algorithms in game AI are capable of.
  • What would make you stay in the Wesnoth community after the conclusion of SOC?
    • If staying with Wesnoth could possibly see the fruition of an AI based on evolutionary algorithm, then I will almost certainly stay in the community.

• Practical considerations
  • Are you familiar with any of the following tools or languages?
    • I am quite familiar with all of the mentioned tools and languages.
  • Which tools do you normally use for development? Why do you use them?
    • We use makefiles to make compilation much easier, and svn to make getting access to the group's files much more straightforward. While coding, I usually use a simple Emacs, as it ensures I know what I'm doing (and partially out of habit). I have on occasion used tools like DrJava.
  • What programming languages are you fluent in?
    • In descending order of fluency: Python, Java, C++, C
  • What spoken languages are you fluent in?
    • English
  • At what hours are you awake and when will you be able to be in IRC (please specify in UTC)
    • Usually, 3PM to 5AM UTC (10AM to 12AM EST), and from about 3:30PM to 10PM UTC on IRC (that can be extended if necessary, I'm flexible).
  • Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail.
    • I wouldn't mind at all. I have Skype and I'm not afraid to use it.

Theory

The basic theory behind an evolutionary algorithm is that if nature was able to produce such complicated creatures as humans, then why don't we mimic that process? Through the very simple processes in evolution extremely complex forms of life have arisen, so why must we use very complicated algorithms and formulas to try to solve problems when the mechanisms of evolution are so much easier and just as powerful? The reason we don't is simply because we don't have millions of years to spend waiting around for digital humans to arise. Evolutionary algorithms use operations that involve at least some randomness, and so the result can be unpredictable. However, when an evolutionary algorithm is set up the right way it can be "contained", if you will, in order to produce good results a reasonable amount of the time (say, 95%). I think that utilizing evolutionary algorithms is the best direction that game AI (and AI in general, but I'll focus on game AI) can go at this point. Most traditional game AI is hard-coded into the system as essentially a complicated serious of if-statements. There are many problems with this approach, some of which are: the AI is inflexible and can be exploited if the formula is discovered; the coder is human and will include bias in determining what he thinks is a good actions in certain situations, which may actually be suboptimal actions; the amount of time and effort it can take to code some AIs is tremendous. On the other hand, evolutionary AIs are learning programs and much more flexible; they don't have any pre-determined bias against apparently dumb actions, and so it they can come up with solutions never even imagined by humans; the amount of code necessary to write them isn't all that much compared to the potential power of the results. All in all, I think evolutionary AIs are superior to traditional AIs in many ways and should be implemented in games.

Details

The basic evolutionary algorithm is a very simple process. You begin with a population of solutions, which, in a game, essentially means that the solutions determines what the AI will do in a given situation. You must first evaluate each of the solutions in the population to determine exactly how "fit" they are. This can simply be a number describing how well they play the game, with better solutions getting higher scores. Then, with higher preference given to the more fit solutions of population, solutions are chosen that will pass on parts of their solution to the next generation of solutions. For example, in a genetic algorithm two solutions are chosen that will "mate" with each other; their solutions will mixed at a certain point, and two new solutions will be created, each that have part of each parent solution in their own. Also, mutation can occur in any of the new solutions, that is, small parts of the solution will be randomly altered. This process of producing new offspring solutions will continue until there is are a full set of new solutions, which will then undergo the same process that their parents did. The idea is that the best solutions of a generation will combine to form even better solutions. This process will continue until either a solution that is sufficiently good is produced, or a maximum number of generations have been tried. Mutation acts as a noise operator to ensure that the solutions to not converge too quickly on local optima.

The actual details of this particular implementation are, unfortunately, not completely realized to me yet. This will come with further exploration of exactly how Wesnoth works and discussion with mentors to determine what would be most useful and beneficial for the organization. Specifically, the parts of the project that are still open to interpretation are in regard to exactly when the process is applied, either in-game or in between games. I don't have a particular preference, but I think that both options are feasible and have their own respective pros and cons. I will briefly discuss these here:

In-Game Application

This was suggested to me by Sirp. The idea here is that the evolutionary algorithm would be applied on every turn the AI gets, and the solutions map a particular AI unit to a valid action, for each of the units an AI controls. The evaluation function would be a function that looks at a particular position on the board and evaluates it. So, to evaluate a particular solution, the program would take the position of the board that would most likely result if the actions suggested by the solution were taken and evaluate it. The rest of the algorithm would follow accordingly, with new solutions being created from the best solutions of the previous generation, until a particular solution evaluates to a high enough score (in which case that solution would be used) or too many generations have been produced (in which case the highest evaluated score at that point would be used).

Pros:

It would be fairly straightforward to implement, especially since the evaluation function would most likely be passed in as a parameter and needn't be optimized in the program. The representation of solutions is pretty easy, as it's simply a multi-dimensional matrix based on the number of units and the moves available to them. Also, having the AI come up with solutions on the fly has the potential to be very dynamic, reacting to the human player mid-game.

Cons:

The biggest problem I can see with this implementation is the potential to create very contrived solutions. That is, because the evaluation function will most likely be very discrete and based on what the programmer deems as good or bad, there is the potential for a lot of bias in the results. That is, I'm afraid that the evaluation function will push the AI in one direction or another too much, so that the results will always be contrived in a sense. This may not actually be the case, but it is my intuition.

In Between Games Application

This is the original idea of mine regarding the implementation of the algorithm. The idea here is that the solutions themselves contain all the information necessary for an AI to play the game. That is, by examining the solution set, one can determine what the AI will do in any particular situation. Thus, the evaluation portion of the program will take the solution and have it play against a standard good AI. Most likely, the beginning generations of solutions will lose, and so the evaluation function will assign scores based on the number of units lost, how quickly the AI lost, etc. Then, the usual selection and reproduction operators create a new generation, and they once again play against the standard opponent. An alternative implementation could be to take a pre-made good AI and make it the basis of the first generation (apply mutation to all of the offspring). Then these offspring would play against each other with the evaluation function being something simple, like those who win get a positive score and those who lose get 0. This would be a good way to come up with even better AIs than what is already considered good.

Pros:

The best thing about this implementation (especially the alternative) is the lack of human involvement in the evaluation function. This means that the AIs have the opportunity to produce unexpected and challenging results because they're not biased against any particular move that would appear inane to a human.

Cons:

The worst part about this implementation is the representation function. Like I said, it would need to produce a result for every unit for every situation the AI could face. With a game as complicated as Wesnoth, such a representation could be very difficult, if at all possible, to come up with. One possible solution to this could be something like the following: the representation for a unit's actions are represented by a string of numbers, like "10212". Each index in the string stands for a different characteristic, for instance "Aggressiveness" or "Wealthiness", and the number associated with that variable determines the degree to which the AI uses that variable. For example, suppose "Aggressiveness" is the first index in the representation string. A value of 0 means that this unit will attack only when it has a clear advantage. A value of 1 means that it will sometimes (say, 50% of the time) attack when it has a slight disadvantage. And a value of 2 means that it will always attack when it can. So this particular unit will sometimes attack when it has a slight disadvantage, because it has a 1 in the first index of the string. "Wealthiness" could be associated with the priority it gives to capturing villages. The string for a single unit would be as long as there are characteristics. Thus, a complete representation would be a matrix in this form:

102121
002101
202011
111111
   .
   .
   .

Where the first string could be for a fighter, the second could be for an archer, etc.

Another con is the fact that getting the algorithm to produce consistently good results is a difficult task and would require much fine-tuned optimization of the system (especially of the representation function), something I don't propose I would be able to do in just three months.

With the above considerations taken into account, it becomes apparent that the first implementation is a much more feasible project for GSoC. Although I would still like to implement the second procedure, I will continue on the assumption that the In-Game Application will be more beneficial to Wesnoth.

Timeline

The following timeline is split up on the basis of the various components of the evolutionary algorithm. I do this because I believe the architecture can be implemented in a logical and straightforward manner like this, and I will give the estimated deadline for each of the tasks. Note that I have implemented evolutionary algorithms before and have a good idea of about how long it takes.

0) Proof of Concept - April 14

As suggested by Sirp, I will provide some code for Wesnoth in the form of the architecture I plan to use for the project by April 14th. This task won't be very difficult, but as I am deep in the academic semester, my time is at a premium and it may take me the entire week and a half to find enough time to accomplish it.

1) Representation - June 13

This will mostly involve my getting used to the current Wesnoth framework and determining exactly how I will implement the rest of the project. Then I need to implement a function that takes the possible moves for each unit and translates them into representative form. Also, it should be able to accept a candidate moves function that will allow the possible moves to be narrowed and focused. This should take a total of about 3 weeks.

2) Evaluation - July 4

This is another large bulk of the project. It must take in a representative solution and be able to produce the position of the board that would result if the solution were carried through. It must also accept the evaluation function and use it to determine the evaluative score of each solution. This will also take about 3 weeks.

3) Selection - July 8

This is very straightforward. The selection process simply takes in the evaluated scores for the set of solutions and determines (with slight randomness) which ones will be used in the Reproduction phase. This should take only two days, at most.

4) Reproduction - July 15

If the Representation portion is done correctly, then this phase should be straightforward as well. The process will be to take in the selected solutions, modify them using the operators of recombination and mutation, and produce a new generation of solutions. This process will take about a week.

5) Generations and Termination - July 18

This is essentially just a while loop that will continue to perform the previous 3 steps until the evaluative score of a solution is higher than a predetermined amount, and that solution will be returned, or a maximum number of generations have been utilized, at which point the highest scoring solution will be returned. The final solution will be used as the action for the AI for that move.

6) Implementation and Optimization - August 10

As of this stage in the project, the program should run as intended and it should be fairly straightforward to implement it into a scenario or campaign. Then, tests can be run to see exactly how effective the program is, and minor changes can be made to optimize the program with regard to efficiency and results. As coding a large project like this will undoubtedly suffer from unexpected difficulties, the optimization phase will be of secondary importance to the completion and implementation of the general framework.

7) Final Documentation and Submission - August 17

Although documenting will be an ongoing process during the project, there will undoubtedly be sections of the code that can be cleaned up, better documented, etc. This final week will also be spent recording exactly what progress has been made and where the project can go from there.

I am sorry to admit that I am running very short on time and need to submit this application immediately. I will continue to update this wiki as time goes on. Hopefully I will be discussing this with you all soon!

Thanks for considering my application, ~Micah Heineck