Aditya Pande Global AI

This page is a candidate for deletion. Someone has decided that this article does not (or no longer) serve a purpose. It may be deleted once suitable time has elapsed for others to contest the deletion on its discussion page.

This page is related to Summer of Code 2014

See the list of Summer of Code 2014 Ideas

This is a Summer of Code 2014 student page

Description

Aditya Pande - Global AI for Battle of Wesnoth

I propose to implement global AI using a combination of idea of Quiescence search on game tree with alpha beta pruning along with a few heuristics to make it possible to actually solve this complex game. Also this approach requires an evaluation scheme for the same.

The idea of using Quiescence search here is different than that in chess engines. Here my idea is to reduce the average branching factor for each choice made by considering the ones which do not affect the game drastically (hence called quiet moves). In this case the braching factor for a unit can be given by

braching factor=Number of attacking moves + Number of Acquire village moves + 2

The 2 represent all Quiet moves based on retreat or charging forward towards enemy. As the quiet moves above do not affect the game drastically they shall be decided based on heuristics and here I plan to only consider the greatest retreat/charge.

The idea behind my approach is based on "Wesnoth can be treated much like a continuous game, because many positions tend to be very similar to each other. Additionally, unlike discrete board games, it is not common that a very small wrong move in Wesnoth is disastrous."

The aim of the whole approach is to simplify the game complexity using few heuristics and then use approach of negamax to select a good overall global move(not the best because of the simplication done) . Also the number of attacking moves and number of acquire village moves has to be reduced to actually keep the problem solvable. (Read all the heuristics for the same in Technical description).

I also plan to divide the whole problem into independent parts whenever possible. Let me give an example, lets say that the AI is under attack on 2 fronts but there is (currently) no relation between the 2 as to say that the AI units involved can't interact(i.e they are too far and can't 'get close' to each other in next turn). My idea is that by doing such division and focusing on solving each problem individually sharply reduces the complexity of the problem.

Lastly I plan to adopt some ideas from Fuzzy Logic, FSM and Behaviour trees to improve the current model I propose.

IRC

adityapande

Questionnaire

1) Basics

1.1) Write a small introduction to yourself.

Myself Aditya Pande,a third year Bachelor of Engineering in Mechanical Engineer in BITS Pilani India. I am very interested in programming, chess, games, artificial intelligence, game development and machine learning. I am part of the college chess team and I regularly participate in coding competitions to test my skill mainly on SPOJ (http://www.spoj.com/users/adityapande/ )and Codechef(http://www.codechef.com/users/adityapande).

1.2) State your preferred email address.

pandeaditya7@gmail.com

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?

adityapande

1.4) Why do you want to participate in summer of code?

I want to participate in summer of code this year because:

i) I like programming, solving design problems

ii) I am interested in game development and AI (which this project will allow me to pursue)

iii) I want to do something significant in my summer

iv) I hope that working on an open source project will help me become a professional

v) I want to learn and get an opportunity to get hands on experience

1.5) What are you studying, subject, level and school?

Currently, I am studying B.E. Mechanical Engineering in BITS Pilani. Apart from that I have studied linear algebra, probability and statistics., dicrete optimization, data structures and algoritms, machine learning, design and analysis of algorithms, game trees and related chess engine theory(negamax, alpha-beta search and pruning etc).

1.6) What country are you from, at what time are you most likely to be able to join IRC?

I am from India and I would be able to be online on IRC between 10 am to 6 pm IST

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

I have no other summer commitments

2) Experience

2.1) What programs/software have you worked on before?

Computer Languages: C(Expert),C++ (Proficient), Python (Proficient), Java, Ruby(Familiar), Django (Proficient), AWK(Familiar), HTML(Proficient), CSS(Proficient), PHP(Basic), CUDA(Basic)

Tools and Systems: Linux, Windows, Codeskulptor( game development IDE for Python), Eclipse, Pygame, Android, MS Visual Studio 2010, OpenGL, Microsoft XNA game engine, Blender and Unity3d game engine

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)

I have worked on a few projects in teams before:

i) Castle – a Chess Engine(2012)

ii) Smart Media Player(2013)

iii) Parallel implementation of Smith waterman algorithm(2013)

iv) Developed a web site to facilitate data handling and automating the process of the monthly report generation required by CPWD, Mussoorie (2013)

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?

No because I only came to know of it last year from a college senior but I had pre-occupations mainly because of my CPWD internship

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

So far I have not been involved in any open source projects

2.5) Gaming experience - Are you a gamer?

Yes I am a gamer and I am a member of my college chess team and I am fond of games be it playing or developing

2.5.1) What type of gamer are you?

I mainly like RPGs, Strategy games (chess and AOE) and a few other sports and racing games.

2.5.2) What type of games?

My favorite games would include chess, AOE, Dragon Age, Lionheart, Assassins Creed, Slay, Cricket etc and by the looks of it Battle of Wesnoth would also join my list(stuck on scenario 9 though)

2.5.3) What type of opponents do you prefer?

I like tough and competitive opponents as I like facing challenges

2.5.4) Are you more interested in story or gameplay?

Mainly gameplay but the story should not be too bad either.

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 have and kind of disliked it for 15 minutes but I kept going as I started to understand the game better but after that I kind of got a hang for it. I played upto scenario 5 in first campaign in about 5 hours and then had to restart due to lack of high level units. I have played for about 10 days and am currently finding my way through at the Valley of Death level.

So far I lean towards the single player as I am having fun with the campaign 1 scenarios. This may change though once I complete the campaign and become better at the game.

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 repository (during the evaluation period or earlier) please state so.

No I have not contributed so far but plan on doing so as soon as I am free. So far I have downloaded the source code for the game and compiled it using Codeblocks and tweaked around with the code a bit. I have also generated new campaigns and scenarios and switched AIs using aiWML.

3) 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.

Proficient English speaker.

3.2) What spoken languages are you fluent in?

English and Hindi

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 and I can say this based on my experience with Voobly AOE community

3.4) Do you give constructive advice?

Yes I do

3.5) Do you receive advice well?

Yes

3.6) Are you good at sorting useful criticisms from useless ones?

Yes I generally try to strengthen my weaknesses based on other’s critique and opinion

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 am mostly of the code it and see the result type but I guess it would be helpful for me to learn to discuss with people a bit more to be more productive with respect to open source development

4) 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 did select the “AI: Improve AI by implementing global attack/retreat decision”

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

[Not applicable]

4.3) Why did you choose this project?

I have selected the project as it interests me the most (my interests include ai, game development and designing algos and heuristics) and I believe it would be challenging and fun for me at the same time. Also I have worked on chess engine development 2 years back and I would love to take this bigger challenge.

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

1. Preparation: (before 19 May)

Going through the AI and developersHome wiki blog, reading up on AI practices including Fuzzy Logic and FSM, reading and implementing the EasyCoding and NotSoEasyCoding tutorial pages, try Boost and SDL. Also going through current AI implementations to look for ideas missing in my proposal

Community bonding(talk to the developers and ask them to help me with my doubts)

2. Improve my model: (19 May - 26 May)

Improve it by trying to incorporate ideas from Fuzzy Logic and perhaps Finite State Machines. Also I shall re-evaluate the proposed heuristics.

3. Evaluation: (26 May-2 June) Write an evaluation function for the game positions based on numerous factors. I know it is not required as there evaluation function is already implemented but I want to own attempt it myself first and use it in testing. I plan on using the default evaluation function later.

4. Start writing my own AI: (2 June -7 July )

I shall implement the model I propose as a .cpp file with the required functions (play_turn() ,attack_enemy(),move_unit(),recruit()). Use my AI by updating the ai.cpp file

5. Testing and Debugging: (7 July - 21 July)

I shall now test my AI looking for possible bugs and AI weaknesses. I shall simultaneously working to remove the bugs found.

6. Improvements: (21 July - 4 August)

Based on the weaknesses found I shall try to improve it further by removing the weaknesses. Re-evaluation of AI heuristics and 'weights' used in evaluation method for better performance

7. Testing with default evaluation method: (4 August - 11 August)

This time I shall use the default evaluation and try and see how the ai plays. Also I shall compare it with my own evaluation model. Based on the discrepencies in performance of the 2 schemes I would be able to improve the weaker evaluation scheme with respect to a given scenario/position. Finally a more refined evaluation scheme shall be used

8. Improving my AI by using ML Recruiter:(11 August - 18 August) I plan on using the ML Recruiter to further improve my AI performance.

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

I plan on using game trees and applying the choice based on the best evaluation found in the trees. I plan on using an evaluation scheme like

E(side) = w1*Income + w2*Health of (AI boss) or crowned unit + foreach_other_unit(w14*unit_type + w3*health + w4*experience + w5*level + w5*defence_at_unit_position - w13*unit_on_recruiting square) + w6*unit_is_in_village + w7*unit_is_near_healing_unit + w8*protection_by_nearby_units) + w9*number of units commanded + w10*money_left + w11*revenue_per_turn + w12*total_mobility

here total_mobility is the number of hexes at least one of the units in the side can go to. It has to be included in the model with a small weight so that at least when there is no battle going on the AI shall explore the map further and acquire some villages to help the economy

Evaluation_pos = E(AI)-E(human or opponent)

This could be easily programmed like (i won't do it in Python when I actually implement it, it would be in C++)

def eval_side(side):
	#not writing weights to keep the code clean here
	e = side.income
	for crowned_unit in side.crowned_units:
		e+=crowned_unit.health
		if crowned_unit.health>0:
			e+= weight3
		#and similarly for all the other factors

`

I plan to write my own AI as a new cpp file with a class deriving the ai_interface in ai.cpp and write the functions play_turn() using the interface functions attack_enemy(), move_unit() and recruit(). Then I will get the state of the game using some utility functions like calculate_possible_moves() and other map location based utilities defined in pathfind.hpp. Also I plan to use the other utility functions provided by map and team header files.

Recruiter:

First I plan to write a very simple random recruiter with weights assigned to each unit type available for the team. I plan on using the MLRecruiter results(these results shall initially be hard-coded) for a start. The idea behind not focusing on recruiting is that there is already a very good project going on in that field. My purpose of writing my own recruiter is to allow me to focus on the main task at hand, while not having to worry about integrating it with the other frameworks as yet. For the same purpose I shall start by writing my own evaluation method. Later however I shall work in the direction of integrating my AI with the current RCA AI model with Formula_AI evaluation.

Also the recruiting shall be based on a heuristic that whenever possible recruit units so that the AI always has a larger army which serves both defensive and offensive causes. (Note: This is unlike other strategy games where economy might be important like in AOE.)

Based on the last heuristic, in my evaluation model the unit_on_recruiting square has a negative weight attached so that units don't stay back and block new units from being recruited

Practical considerations in game tree construction:

First main idea is to divide the choices into distinct independent sets whenever possible. As explained in the project idea description this is a very powerful idea which can easily reduce the combinatorial complexity exponentially. This makes it possible to solve many different battle fronts more efficiently without relying as much on heuristics. This may also allow to solve small battlefronts as accurately as possible.

The game tree expands very fast because each unit has many choices. If we construct a game tree based on all the choices for a unit then it will have a very large branching factor. So I plan to use an idea similar to that used in chess engines to remove the horizon effect, i.e the idea of Quiescence search. However, I am using it for a different purpose -reducing branching factor- and I am not exactly ignoring the quiet moves. Now each units moves can be categorized as

i) Attacking moves

ii) Village acquiring moves

iii) Special abilities (like healing (as in shamans, mages(level2+) and paladins) and leadership(as in warriors anc champions)

iv) Quiet moves(just movement)

Now in a set of units (lets call it a company of an army) we are considering right now. (As we shall build few independent game trees). Start from considering the units in increasing % of hp left. This helps the cause that in this case normally the units which require healing more would acquire the villages. This should be a good heuristic to achieve unit safety with less problems.

Implementation Note: Once one unit acquires a village no other unit can acquire the same. Same actually goes for any square and it should always be checked.

Let me now simplify and reduce these using few heuristics so that I can come up with a global strategy and not just local strategy. For (i) I propose the following heuristics:

a) first try attacking the crowned opponent units if it is in this units range and it is not futile to attack.

Implementation Note: Primitive futility check : Attack is futile if this unit dies or loses hit-points more than a threshold (say 60%) without killing any unit or doing a threshold percent of opponent's hp damage

b) try attacking higher level enemies if it is not futile (This heuristic shall be very powerful with a human opponent in case of a campaign as it aims to kill off higher level human units)

Implementation Note: for each fight choice take the expected value of the end result based on the sum of product of the possibilities and their probabilities given by the damage_calculations that is already implemented in Wesnoth. (I am yet to figure how to call it though)

c) then try attacking all other units unless futile

d) if there are any fight choices that are not futile choose the one based on the priority a>b>c

e) from where to attack shall be based on 2 heuristics:

i) try attacking from most favorable tile type (based on its protection and healing abilities in case of villages)

ii) try attacking from such a spot so that other units which can reach there in this move can assist (ignore this heuristic if it is very likely that this attack will kill the enemy unit by a threshold probability(lets say 85%))

Based on the above heuristics we will get only one attack type choice for unit or none if it can't reach any other enemy unit or if all attacks are futile.

for ii) Village acquiring moves

If there are many such choices for a unit only consider the one such that as many villages can be acquired as possible This is a simple dynamic (knapsack) problem and should be easily solved.

So now this is also reduced to upto only a single choice for each unit.

for iii) Special abilities (like healing (as in shamans, mages(level2+) and paladins) and leadership(as in warriors anc champions)

This would be incorporated automatically by the simple movements of the units with such abilities. However the movement of such special power units should be based on a heuristic that when just moving these pieces around try to place them next to wounded units(for healers) and next to fighting units(for leaders).

for iv) Quiet moves:

I plan to just consider at most 3 possible cases:

a) charge (charge towards the enemy as much as possible (but also consider terrain favoribility for the particular tile)). This can be achieved by adding a weight function to both movement towards enemy(in terms of tiles) and the defence offered at the particular tile(can get this using map.hpp).

b) retreat (move away from enemy as much as possible)

c) special abilities (mentioned in iii above)

So I now have a total of at most 5 moves per unit(would generally be less). So I can safely construct a tree with n units which will have at most 5^n end nodes. Actually branching factor would generally be much less than 5 but even in worst case we can easily solve exactly for at least n=8 having 390625 end nodes.

Considering that futility pruning would also be applied so we would be able to solve it for larger company size (n) upto 20. Also the 'company of army' shall be selected dynamically until the tree end nodes become greater than threshold. Threshold shall be selected such that the whole tree can be constructed and evaluated in less than a few seconds. Also we should directly play the move in the case when a unit has only 1 move (i.e after our categorization and simplification of possible moves).

The problem with above is that we should also consider the enemy moves so the above numbers would be about halved to maintain efficient game trees. I will also consider the enemy moves into the construction of game tree. (Only the enemy interacting with the 'AI company' shall be considered here).

To solve the above complexity problem I propose to use an idea similar to alpha-beta pruning to avoid bad branches which have a bad evaluation. (It would simply reject the moves that are much worse than the current best move we have found)It would certainly reduce the branching factor further.

The tree shall be generated dynamically by first locally restricting the moves to consider according to the above ideas proposed. The tree shall be generated as we dfs through the moves of different units and add them in the tree. Apply modified alpha beta pruning, which is different from standard alpha beta search as it shall not be alternating as in chess but it will depend on whose move we are considering. I plan to consider the AI choices first and then the player choices. Hashes may also be used to deal with transpostions. (Exact transpositions shall not be possible though so this would be 'lossy' but helpful in reducing complexity nonetheless)

For many AI v one human, we can also add the heuristic to attack the human when the other AI of our team can also attack.

I shall also try to improve the current model proposed to incorporate ideas from Fuzzy logic and FSM.

Game tree storage details: A class Node with the game state including the side choice we are considering, a vector of type Node to store its child nodes, evaluation score and vector of class Unit (storing info like unit_identifier, unit_type, hp, position) and a variable of some class storing the choice we have made to come from parent to child so far.

Lastly I want to implement the whole idea with the RCA AI framework also using Formula AI evaluation scheme and ML Recruiter shall also be integrated to my AI

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

I expect to gain:

i) open source development skills

ii) better understanding of articial intelligence and designing ai and heuristics

iii) understanding and experience with boost and sdl libraries

iv) possibly experience in Lua

v) possibly application of machine learning concepts

vi) experience in game development and general programming

vii) something cool for my Resume to get jobs in fields similar to my interests

viii) professional connections with the Wesnoth developer community

ix) satisfaction at having done something cool and big

x) a paycheck from Google

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

I would like to continue working for the community as long as I am free and the organization allows me to work on interesting projects I can learn something from.

Some monetary benefits maybe an additional incentive.

5) Practical considerations

5.1) Are you familiar with any of the following tools or languages?Git (used for all commits)

Yes (the basics)

C++ (language used for all the normal source code)

Proficient(5 years experience)

STL, Boost, Sdl (C++ libraries used by Wesnoth)

Yes (only with STL). However I have worked on Matlab for linear algebra,etc. I hope to learn the 2 fairly quickly because I already know something with similar purpose. I have worked on Maple, Matlab and Octave and also on OpenGl, Unity3d, Pygame and Codeskulptor. Furthermore I am looking forward to work on boost and SDL in the near future.

Python (optional, mainly used for tools)

Yes I have worked in Python for about 3 years and have also made few simple 2d games In it using codeskulptor and Pygame

build environments (eg cmake/scons)

Not familiar with cmake or Scons

WML (the wesnoth specific scenario language)

No

Lua (used in combination with WML to create scenarios)

No but I would be able to learn it fairly quickly

5.2) Which tools do you normally use for development? Why do you use them?

I generally prefer C++ and Python as the programming language because of my experience in them. I use Visual Studio and Bloodshed IDE for C++ and Idle for Python.

5.3) What programming languages are you fluent in?

C++, Java and Python

5.4) 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. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!

In general, students should be as verbose as possible in their answers and feel free to elaborate.

I would like to talk with the mentors at phone. My phone number is +91 9799363378.