FormulaAI FSM

From Wesnoth

Contents 1 Introduction 2 Experience 3 Gaming experience 4 Project 5 Discussion 5.1 The Finite State Machine (FSM) Approach 5.2 Some Hypothetical States: 5.3 Calculating Relative Effectiveness 5.4 Using Relative Effectiveness operationally 5.5 Towards a better force mix 5.6 Grouping units 5.7 Proposed Timeline 5.8 Me & the Community 6 Communication skills 7 Practical considerations

Introduction

         o Write a small introduction to yourself.
         o State your preferred email address.
         o If you have chosen a nick for IRC and Wesnoth forums, what is it?
         o Why do you want to participate in summer of code?
         o What are you studying, subject, level and school?

• My name is Martin Bolanca and I’m a third-year Software Engineering student at ANU (Australian National University) who is extremely interested in game making and design. I also have a couple of years of credits in English, communications and politics units from the wreckage of an Arts Degree.

• I am interesting in making games for a living so this seems like a natural way to learn more about programming a game AI, in particular for a hex based game. Wesnoth is one of the most successful open-source gaming projects around and I quite frankly would like to absorb some of the knowledge and experience of the senior developers. I also believe that I have some knowledge, insights and experience (certainly opinions) that I can impart to the project. At the very least, I have a long interest and experience with hexmap games. I have played *a lot* of them, and am sure that experience will come in useful.

• My gmail address is tanuojin@gmail.com

• My IRC and Wesnoth nicks are Martinov

Experience

         o What programs/software have you worked on before?
         o Have you developed software in a team environment before? (As opposed to hacking on something on your own)
         o 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?
         o What development model would you use (e.g. keywords: V-model, XP programming, agile programming, iterative; with the help of prototyping, formal specifications, tests, etc).
         o Open Source: Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement. 

• My greatest programming achievement so far is my game “The Great War in Europe 1914-18”. This is an original, turn-based game which I hope illustrates some of the dilemmas which faced the opposing alliances in their conduct of the war.

The Great War is midway in complexity between Risk and an old-school wargame. It is written in Java and according to my log has taken me approximately 1,600 hours to make. It comprises about 20-25,000 lines of (much much rewritten) code which creates 560k of java with about 30 meg of graphics etc. Incidentally the same counter program reported Wesnoth having 262,000 lines of (more densely written) code.

I hope to convert “The Great War” into C++ later this year as the graphics are not quite fast enough for my liking. The game is not currently available for distribution, but I would be happy to provide code, screenshots etc if requested.

• My experience with team programming has been limited to university projects and assignments. I’m comfortable with working in teams but I have observed that two or three person teams seem most effective – I guess the trick is to break a big project into tasks that size.

• I haven’t participated in Google Summer of Code before.

• I would be reluctant to select a development model until I have discussed the matter with my mentor. At first glance an iterative approach seems appropriate as the creation process will require a cycle of regular publication followed by feedback and revision.

• I'm currently working in a 6 man team to develop an open source Linux robotics library for entry level hobbyists. The project is a year long university course nominally sponsered by Nias Digital, who report it here (http://www.niasdigital.com/blag/?blog=2&page=1&paged=2). The project hopes to create a self sustaining community to expand its pilot work.

While I’ve used a lot of open source programs and have looked at a lot of open source projects but I haven’t really contributed to any open source of my own. I’ve made quite a few game mods and have always made them and the knowledge that created them as available as possible.

Gaming experience

               o  Are you a gamer? If so...
               o  What type of gamer are you?
               o  What type of games?
               o  What type of opponents do you prefer?
               o  Are you more interested in story or gameplay?
               o  Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer. 

• I am a gamer, although I sometimes think I may actually be more of a game-maker, as I probably spend two or three hours tinkering with, modding or making my own games for every hour I spend playing. In any case, I’ve decided to use my GSoC essay arguing that these aspects are really two sides of the same creative coin!

• What kind of gamer am I? Any ‘good’ board or computer game (FPS, RTS, TBG, RPG, etc) appeals. And a historical or strongly-themed game will appeal more.

• Both story and gameplay are very important, but I think that once you have a certain amount of gameplay – let’s call it an enabling level - then story (or in a historical game, the feel of realism) becomes more important (at least in an adventure/wargame like Wesnoth). That’s why people (at least some of us) keep going back to classic games. A game with high gameplay and low story is in effect a parlor or arcade game, with low replay value for people like myself.

• I’ve been playing Wesnoth for about two years after discovering it as part of the Ubuntu suite on ANU’s lab computers (unfortunately this year the computing department has changed over to the Kubuntu Feisty suite which does not seem to include Wesnoth). My preference is for human opponents, or challenging myself by fighting several AI’s at once (I usually lose).

Project

         o Did you select a project from our list? If that is the case, what project did you select?
         o If you have invented your own project, please describe the project and the scope.
         o Why did you choose this project?
         o Include an estimated timeline for your work on the project
         o Include as much technical detail about your implementation as you can
         o What do you expect to gain from this project?
         o What would make you stay in the Wesnoth community after the conclusion of SOC?

I am essentially submitting to work along the lines proposed by the Wesnoth proposal. However I would like to expand upon my understanding of that proposal by making the following caveats, and then providing some examples of my reasoning and approach to show where it might differ from that proposal.

Firstly, I don’t think we should underestimate the task of constructing a good AI for Wesnoth (or possibly any game worth playing). Indeed, I think I can safely say that no-one has yet programmed a really good hex map playing (should I say wargame playing?) AI.

So I would refine the proposal to say that the goal is to:

• to create a significantly better AI than the existing one in terms of performance and flexibility of modification,
• to deepen and strengthen the FormulaAI framework,
• thus encouraging and enabling future members of the community to continue the process of improvement and refinement
• and allowing scenario makers to more easily customise it to suit their own requirements.

Of course, even rephrased this is still an ambitious task, and to succeed I will need to fully tap the knowledge of my mentor and the experiences of people who have played the old AI so long they intimately know what it does well and what it does badly.

While my application is as per the straight FormulaAI proposal, my approach does focus on ‘operational battle’ AI concepts and so might complement another applicants work on the general/campaign AI.

Discussion

So what techniques might my project use or need? I would like to digress to show a couple of examples of my approach to the subject, specifically.

• using a Finite State Machine (FSM) to allow AI strategy to respond to changing strategic situation
• creation of an index of relative effectiveness to allow the AI to judge the relative value of units in different situations
• allowing the AI to manage groups of units to improve their combat effectiveness through mutual support (read not being picked off one by and providing a range of counters to whatever unit is attacking)
• the need for a sufficiently wide range of functions to allow the above, in particular functions allowing the AI to evaluate the relative worth of a unit in a given situation, and whole (visible) map evaluation functions to allow the AI to select units and behaviours appropriate to the strategic situation

I realise that there is nothing blazingly new in these suggestions, I provide them though to show my reasoning process about where to start. I have not had a chance to study the ‘classic’ AI in detail yet, but I wouldn’t be surprised to find out it uses a FSM structure somewhere and I’ve certainly seen evidence of good tactical decision making which must use some evaluative technique similar to the one I describe.

The Finite State Machine (FSM) Approach

I might be in a minority here, but my belief is that in the micro-sense, the current AI fights quite well, it certainly irritates the hell out of me, but what it needs to become a truly dangerous opponent is a governing or coordinating body. I first encountered FSM’s while hacking Dark Reign and have been in love with them ever since. Each state can be considered to represent a different AI personality or operational strategy.

Use of a FSM will necessarily mean the introduction of new functions, for example, the AI will need a function to evaluate what proportion of the map it controls.

In effect each state is:

• encouraging (weighting) particular units (for example fast units might be favoured if the AI is in a ‘Expansionistic’ or ‘Consolidatory’ state)
• encouraging (weighting) a particular subset of behaviours.

When the scenario developer wishes to ensure scenario-specific behaviours occur it could set the raw weight of these behaviours sufficiently high to ensure they are selected regardless of the governing state, or simply resort to creating a special ‘Quixotic’ state for the AI which weights them accordingly.

I believe that the community could provide a lot of input to develop these personality ‘states’ and their substrategies.

Some Hypothetical States:

• Expansionistic

The AI might start in this state at the start of the game. In this state it might favour building recon units and capturing villages.

• Consolidatory

The AI might switch to this state once it has achieved roughly its proportion of cities on the board. In this state it might focus on behaviours such as garrisoning villages, garrisoning villages near enemy units & villages forming font lines to minimise the damage from enemy attacks. There might even be several consolidatory sub-states, for eg - an ‘early’ one, which gets fast units out to hold the front line, and - a ‘late’ one which prepares for the ‘offensive state’ by sending a stream of units out to the front line - there might even be an optional ‘middle’ sub-state, which sends slow units out early in order to rendezvous with subsequently built fast units

• Defensive (or Offensive – Cautious)

The AI might switch to this state if it perceives the situation is tightly balanced, or if it has a slight advantage and has plenty of time. It might seek to hold villages while attacking in an attempt to inflict the best ratio of casualties while its forces build up.

• Offensive – Aggressive

The AI might switch to this state if it perceives it is winning. In this state it might attack in an attempt to inflict the greatest number of casualties in order to break the enemy.

• Desperate

The AI might switch to this state if it has clear evidence that it is losing, for example (enemy units > friendly units) && (enemy cities > friendly cities for a certain number of turns). In this state it might favour a last burst of effort favouring high risk attacks in the hope of turning the tide before its too late, or going all out to kill the opposing leader.

Calculating Relative Effectiveness

In order for the AI to make effective decisions I think it needs to be able to judge the relative value of its units in the current situation. A simple measure of effectiveness might be to measure the average damage likely to be inflicted in a pair of combats (each gets to choose an attack mode on the other). We will assume ceritas paribus on lots of conditions like probability of hitting, terrain etc and consider only a couple of variables (attacks, damage, resistance, hit points, cost). This gives something like

• unit1(damage * bonus multiplier) vs unit2 (damage * bonus multiplier) = hp exchange ratio1

• unit2(damage * bonus multiplier) vs unit1 (damage * bonus multiplier) = hp exchange ratio2

• Relative effectiveness index for unit1 vis a vis unit 2 = ratio1/ratio2

For example with a Human Bowman vs an Elf Scout

• (6*2*1.0) vs (7*3) = 12/21
• (6*3*1.2) vs (9*2*1.0) = 21.6/18

Or a Human Heavy Infantry vs an Elf Scout

• (11*2*1.0) vs (7*3*0.5) = 22/10.5
• (0) vs (9*2*0.6) = 0/10.8

Of course each unit has a different cost and a different quantity of hitpoints so we will factor this in by expressing the damage in terms of hitpoint dollars.

So in a pair of combats we might expect:

The Bowman to inflict damage (in hitpoint/dollars) in a proportion of:

• (33.6 * 33/15) / (39.0 * 46/31) = 1.27

The Heavy Infantry would inflict damage in a proportion of:

• (22 * 38/19) / (21.3 * 46/31) = 1.39

So we can see from this comparison that the Heavy Infantry is more efficient at despatching Elf Scouts (ceritas paribus, ie once in combat). Send for more Heavy Infantry!

Using Relative Effectiveness operationally

However several strategic modifiers might apply to this effectiveness index.

Obviously Bowmen are significantly faster than Heavy Infantry, so if the overall situation (as expressed by the governing state) calls for rapid deployment the index should be modified. It is also clear that combat between bowmen and scouts will be 50% more bloody, or in other words it will be more decisive – not what you want if you are in a defensive posture waiting for your production to overpower the enemy. On the other hand certain strategies (or FSM states), for example the aggressive state, or even the desperate state might be seeking to increase the intensity of the fighting in order to break the enemy quickly.

For discussion’s sake, let’s express the difference in capabilities as a ratio and use the square root of the ratio as the weighting multiplier to the effectiveness index.

• So in the case of a state placing a premium on movement, the modifier might be bowman move of 6 over Heavy Infantry move of 4 yields sqrt(6/4) giving a 1.2 multiplier to the Bowman’s effectiveness index, enough I think to favour its construction.

• The gross damage proportion is also about 33:39 bowman/rider and 22/21 heavy/rider so 3:2 more deadly if bowman are deployed, yielding a similar multiplier.

• So if the state felt that rapid movement and bloody combat were required the bowman might be re-valued at 1.27 * 1.2 * 1.2 = 1.83 making it a clear preference over the Heavy Infantry in this situation. Of course map size would probably be another multiplier.

Towards a better force mix

Using a FSM in conjunction with effectiveness indexes will allow the AI to make more informed (and hopefully better) choices in its selection of units.

It will do this by synthesising these values with its existing units and all known enemy units in an attempt to optimise its ‘ultimate’ index (I made that term up) which would effectively express the degree to which ‘I have the best mix of units to inflict damage, conduct the battle at the intensity I wish and move, based on my current personality’).

Our goal would be for the AI to construct units in proportion to their effectiveness (for example if it has been identified that the opponent has a lot of cavalry, a consolidatory or cautious state might construct a lot of spearmen in response, while an aggressive state might construct a lot of horsemen.

I suspect that matrices could be used to represent the possible friendly and enemy units, their current numbers and relative effectiveness given the ruling state and calculate (maybe the determinant of the product matrix will express) the ‘ultimate index’ of the AI’s army based on its opponents known composition.

Units would be constructed that would increase the ‘ultimate index’. This would ensure that the AI would have the best range of units to counter its opponent’s selection – then we only have to get it to use them wisely!

It’s true that this will involve a fair bit of number crunching but I doubt it will impact in real time, in any case an easier method will be for the process to generate a list of units to be built in order of desirability and simply move down that list, then regenerate the list next turn.

Grouping units

How to get the AI to use its new army more wisely? One way might be to introduce the concept of a group.

A group is simply a group of units that the AI will attempt to assemble together, march together (staying no more than a hex or two apart say) and fight together. Groups might be predefined (eg ‘two grunts, two archers and two goblins’) or they might be calculated by the AI in mid-play in response to the current perceived situation.

Grouping will:

• reduce the human ability to pickoff stray AI units, especially those in transit after being produced
• improve the group’s effectiveness as it is more likely that appropriate counter units will be available to respond to an attack on a member of the group
• possibly allow functions like shielding the weakest member of the group

One thing I really like about this approach is that it would put a much greater emphasis on concealing your forces from the AI as long as possible to minimise it responding with countermeasures.

Proposed Timeline

I suggest that the project have six stages, of which the first three and the second two can and should be perfomed concurrently.

Initial Stages (April 21 - May 14)

1a) "Preparation"//

Discussions with mentor to finalise scope of project and to plan needed functions and functionality.

1b) "Learning"

Subject to the mentor's advice, I think I should attempt to convert the existing AI to FormulaAI. I think this would be a useful exercise for me as:

• it will accelerate my experience with the FormulaAI methodology
• the translation process is bound to be a fertile source of ideas
• many functions developed for it are bound to be needed later

1c) "Research"

Simultaneously to study the forums and harness the power of the Wesnoth community to gather data on the requirements of the new AI. I think the project will require a written summary of my findings, the problems encountered and the decisions I took to with regard to them.

Development Stages (May 14 - July 25)

2a) "Development & Feedback" Work on the proposed AI, releasing editions fortnightly, June 13, June 27, July 14, July 25. Each edition would then be subject to scrutiny by the community, resulting in revisions for the next edition

2b) "Documentation" Expand and document the FormulaAI library functions in a user guide as well as inline comments, explaining what they do and what they might be useful for.

Finalisation Stage (July 25 - Aug 18)

3) Complete documentation. Write summary report. Create and publish final (Aug 11) version.

Me & the Community

I am very comfortable with Wesnoth as a game, and depending on my experiences, expect to remain involved in the community after the project – not necessarily as a developer though – possibly as an editor! I’ve been playing some of the campaigns and I think I see some room for helping scenario makers with grammar, narration, advice on plot and so on, in order to make them even better.

Communication skills

         o Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.
         o Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.
         o Do you give constructive advice?
         o Do you receive advice well?
         o Are you good at sorting useful criticisms from useless ones? 

• English is my first language. I’m fairly fluent, though I did dropout of my English degree in second year!

• I think I’m quite good at interacting with other players. I’ve participated on many forums and have never had any trouble communicating or getting along with my fellows.

• I think I have a good eye for innovation and improvements and weighing up the positives and negatives of a system, so I think that, yes, I do give good, constructive, advice. My delivery method varies and depends on how well I know the person -sometimes you need to be blunt - sometimes it pays to be tactful. But I believe you should always be respectful.

• won’t say I’m perfect at receiving advice - sometimes I have difficulty understanding what the other guy is going on about! But I will say that I am very good in responding to criticism - once I have been persuaded of the need for change I often become its most ardent advocate! I think it’s worth noting that I am, in a sense, participating in the project in order to be criticised, and to learn from that criticism.

Practical considerations

         o Are you familiar with any of the following tools?
               + Subversion
               + C++
               + Python 
         o Which tools do you normally use for development? Why do you use them?
         o What programming languages are you fluent in?
         o What spoken languages are you fluent in?
         o At what hours are you awake (please specify in UTC)
         o Would you mind talking with your mentor on telephone / internet phone? 

• My recreational programming has mainly involved Java but I am familiar with C/C++ and SVN through coursework, and these will be my primary languages in courses and hobby work this year. I also have experience with functional programming (in Haskell) and have done a course in Python.

• My waking hours vary, but I’m invariably up until 3-4am in the morning so I will describe my waking hours as 5pm – 10am UCT. I’m happy with chatting on the phone.

Copyright © 2003-2008 The Battle for Wesnoth

Powered by MediaWiki