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.
See Aditya Pande Global AI for more information.

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.
See Improve AI for more information.

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.
See SoC2014 arveanor ai for more information.

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

A rule-based expert system style solution utilizing dynamic programming to make decisions
See SoC2014 kevin AI for more information.


See SoC2014 vorobeez AI for more information.

Additional Information

Wesnoth has time of day cycles (...-day-day-dusk-night-night-morning-... ), with certain times of day heavily favoring units depending on their alignment. Moreover, new units are constantly trained - so, sometimes the best decision would be to defend and wait or fall back, other times the best decision would be to attack (e.g. with the aim of holding a strategic village until morning, and counter-attacking during morning and day, then falling back with dusk). The AI should learn to adapt its strategy depending on the balance of forces and the current time of day.

Good first steps

Read http://wiki.wesnoth.org/Customizing_AI_in_Wesnoth_1.8#how_AI_works.2C_a_short_developer-oriented_overview. Read http://wiki.wesnoth.org/Customizing_AI_in_Wesnoth_1.8#Customizing_AI_turn_sequence Take a look at some of the 'candidate actions', for example here - https://github.com/wesnoth/wesnoth/blob/master/src/ai/testing/ca.cpp The goal is to understand the AI turn structure, without going far into details of how each individual action works. Ask questions, if you'll have any. it's better to ask on IRC since it'll benefit other students asking the same. During the course of the project, you'll most likely have to add new candidate actions ("IF this DO that WITH PRIORITY such") and modify existing ones.

Whom to ask about this

Crab_ on irc.