# SoC Ideas AI Global strategy

 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 Idea

## Description

### AI: Improve AI by implementing global attack/retreat decision

Page for the idea: SoC_Ideas_AI_Global_strategy

The Wesnoth AI works by making local decisions about moves and attacks. Teach it to determine if it's worth to fight offensively or defensively in a given situation.

There are 5 submitted student proposals for this idea

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

#### Vahen_Improve_AI

I would like to improve the AI by implementing Global attack / retreat decision.

Elements : Anything around the unit that can cause a change to the behavior

Behavior : Determine what the enemy is going to do based on the elements.

Deliberation : Does the best move depending on the behavior previously set .

To do so I will use probality theory to determine what is best move to do.

#### Arveanor Global AI

Give an ai player a set of potential objectives to pursue such as taking a village, killing an enemy, defending a village etc. Also give each ai different behavior modes based on the information they have access to. i.e. fight aggressively, fight defensively, fight cautiously etc. The ai would, depending on it's current behavior mode pursue the objectives more or less rigorously depending on how they align with the current behavior.

The behaviors and objectives would not necessarily mix strongly with recruitment, however a similar system to what would analyze which behavior to be used would also be able to inform recruiting patterns. Obviously certain unit types and a large amount of certain terrain hexes give good reason to favor certain units in recruitment, of course gaining vision and taking outlying villages (i.e. AI global objectives) would play into recruitment in terms of recruiting faster units.

#### Kevin Xi - AI: Improve AI by implementing global attack/retreat decision

A rule-based expert system style solution utilizing dynamic programming to make decisions