Aditya Pande Global AI

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

ATTENTION

Incomplete

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.

TODONo I have not contributed so far but plan on doing so as soon as my semester final exams complete in May beginning.

I have downloaded the source code for the game.

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

TODO

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.