New AI Design for Wesnoth 1.7
Moderator: Forum Moderators
New AI Design for Wesnoth 1.7
The state of the AI in 1.6 is somewhat embarrassing. I've put together the following design proposal for how we can make a better AI in 1.7. Comments are welcome.
INTRODUCTION
The current default AI for Wesnoth is based on work I started in 2002. It has evolved since then, but as time wears on, its limitations become clearer and clearer. Patch after patch has been made to it, and it has become complicated enough to become difficult to understand easily. This has led to many forms of odd behavior which are difficult to understand and correct.
One alternative which featured prominently in Wesnoth's Google Summer of Code program in 2008 was to develop a 'formula AI'. This 'formula AI' would, in fact, be a system that allowed anyone to write their own AI using a simple functional programming language. While there have been some useful results from this effort, this approach has been too general to be successful. It attempts to allow specification of any possible AI behavior, and by doing so, puts the burden on the formula writer to design and develop their own AI.
I think that it is time for us to try to develop a new AI system. This AI system should be composed of interchangeable parts, so that one can tweak or replace one part of the AI, leaving other parts in tact. The overall design will, however, enforce what the different parts are and the interfaces between them.
Enforcing the overall parts in an AI will place some constraints on what the AI can do. It will place some limitations, and ensure that the AI will not be able to behave optimally in every possible situation. However, I think if we choose well, and create a good design, we can still create a very flexible AI with interchangeable parts. This document intends to outline the design of such an AI framework.
THE CURRENT AI
It is useful to understand how the current AI works. The current AI uses what I will call a "phase based approach". That is to say, it has several phases in its logic, and when one phase has been considered, it proceeds to the next phase, and so forth.
The original basic design was as follows:
The first phase it has is the combat phase. During the combat phase it analyzes all enemy units that may be attacked, and then calculates whether it should attack them or not, based on different heuristics, which can be modified by some of the AI parameters.
The second phase is the village grabbing phase, where it sees if any villages are immediately able to be captured. It then calculates whether capturing these villages should be done, based on more heuristics. This phase also involves a phse to calculate whether units should move onto a village for healing.
Then is a "targetting" phase. The AI has now decided that there are no more units that are "in range" of something attainable this turn, so instead it concentrates on moving units so that they will be able to attain various goals on future turns. It draws up various targets -- by default all enemy/unowned villages and the enemy leader, though configurable by parameters -- and assigns value to them. Then it assigns units to pursue targets based on the distance to the targets and the value of the targets. Units move in the direction of targets.
Finally, there is a recruitment phase, where units are recruited.
Unfortunately, there are numerous defects in this design, some of which have had attempts made to correect them. The biggest defect is that this "phase based" system does not consider opportunity costs. One might choose to attack a unit based on a very marginal advantage it gains, without getting down to the phase which considers that instead of attacking, the unit could have captured a village in an opportune location.
Likewise, and even worse, a unit may choose not to attack in the attack phase, but then after moving through all the other phases, we find that the unit is cornered and doesn't really have any other options. For a long time this led to bizarre behavior where a unit would move up next to an enemy unit but not attack. Eventually this was 'patched' by adding an additional 'mini attack' phase at the end.
There were also many other attempts to improve AI behavior. This included trying to 'group' units together during the target phase, trying to make units 'support' each other in an additional phase, and so forth. Unfortunately these changes tend to have unexpected consequences, and are ultimately just patches of a fundamentally limited system.
A BETTER WAY
Instead of having 'phases' as described above, an AI should consider possible 'candidate' moves, and compare moves to each other, based on their merits, choosing the best possible move. It should compare not only one attack option to another, but it should compare the possibility of attacking a unit with the possibility of moving to capture a village, valuing each against one another, choosing the best option.
However, choosing a move shouldn't necessarily be done on a unit-by-unit basis. If you have five units together, you probably want most or all of them to do something similar. You don't want to send two of them forward to fight and be slaughtered, while the other three stand in a defensive formation, or go off capturing villages.
So, it should be possible to group units into 'squads'. These squads should compare different approaches and choose the best approach for the squad.
COMPONENTS
The AI should have the following components:
- Squad Selection: This is run at the start of the AI's turn, and breaks the AI into squads. The simplest possible approaches, both of which are legitimate in some cases, are to put each unit in its own squad, or to put all of the AI's units into one squad.
There are many other conceivable approaches, such as grouping into squads based on units being able to attack the same enemy, or units having movement possibilities that allow them to end the turn adjacent to each other. The time complexity of an AI will increase exponentially with squad size, so it will likely be a good idea for any approach to limit the number of units in a squad.
- Candidate Move Selection: This component is given a unit, and returns a list of 'candidate moves' for the unit. Attached to a candidate move is attached an 'analysis report' -- a data structure explaining the goals this move fulfills.
The simplest possible Candidate Move Selection algorithm is simply to return all possible moves a unit can make. This approach could actually be sensible, depending on the configuration of the other components.
- Candidate Attack Selection: Attacking in Wesnoth is important enough for it to be given a different component from the Candidate Moves Selection. The Candidate Attack Selection is given a squad of units, and should return candidate attack plans. The attack plans should use some or all of the units in the squad to perform an attack on an enemy unit. Attached to each candidate attack is an analysis report -- a data structure which contains analysis data about the benefits and risks of undertaking the attack.
- Position Evaluator: This component is given a Wesnoth game position and evaluates the strength of the position.
- Recruiter: This component selects which units should be recruited, based on the game position and available gold.
ALGORITHM
The Wesnoth AI Framework will use an algorithm to combine these components to make AI moves every turn:
- All AI units will be divided into squads, by the Squad Selector.
- Each unit will have a list of candidate moves generated
- Each squad will have a list of candidate attacks generated
- Each squad will have possible combinations of moves and attacks simulated, and then the outcomes evaluated using the Position Evaluator. For attacks, the possible outcomes will be determined, and then the chance of each outcome will be multiplied by the evaluation, and these evaluations summed to give an overall evaluation.
It may be too expensive to simulate and evaluate every possible combination of candidate moves and attacks as well as evaluate all possible battle outcomes. The framework may be tuned to use a 'monte carlo' style algorithm to only evaluate some of the possible combinations of candidate moves/attacks. It may also only evaluate some of the possible battle outcomes, since there would be many similar ones.
- After any non-deterministic move takes place (i.e. an attack), the entire algorithm starts from scratch.
BENEFITS
Each different component would be represented by an abstract class in C++. One could write their own classes that derive from these classes, and put them together to make an AI. One could make their classes heavily configurable using WML, or could make them call formulas to make decisions.
This would make the AI very configurable, and would allow one to fairly dramatically control AI behavior by tweaking the different components.
The approach should also be very flexible. One should be able to, for instance, make an AI that can 'guard' against an enemy approach by making an Evaluator that rewards cutting down the possible movement the enemy can make into one's territory, as well as placing one's units on defensive terrain, and so forth.
Naturally there would be many trade offs, and some combinations of components would not work well together. For instance, having a Candidate Move Selector that selects every possible move, and having a Squad Selector that puts all units into the same squad would result in a prohibitively large combination of possible moves a squad could make.
There are also some details to work out, like how AI leaders would fit into this framework, and when recruiting would take place. Possibly it would simply be the job of the Squad Selector to decide if the leader goes in a squad with other units, and the Candidate Move Selector to decide if the leader can move off the keep and the Evaluator to decide if moving off the keep is actually a good idea. But perhaps we could work out a way to add better support for leaders and recruiting to this framework.
CONCLUSION
We need to come up with a better AI solution for Wesnoth. I think this design is fairly solid, and we should try to come up with a proof-of-concept for it.
INTRODUCTION
The current default AI for Wesnoth is based on work I started in 2002. It has evolved since then, but as time wears on, its limitations become clearer and clearer. Patch after patch has been made to it, and it has become complicated enough to become difficult to understand easily. This has led to many forms of odd behavior which are difficult to understand and correct.
One alternative which featured prominently in Wesnoth's Google Summer of Code program in 2008 was to develop a 'formula AI'. This 'formula AI' would, in fact, be a system that allowed anyone to write their own AI using a simple functional programming language. While there have been some useful results from this effort, this approach has been too general to be successful. It attempts to allow specification of any possible AI behavior, and by doing so, puts the burden on the formula writer to design and develop their own AI.
I think that it is time for us to try to develop a new AI system. This AI system should be composed of interchangeable parts, so that one can tweak or replace one part of the AI, leaving other parts in tact. The overall design will, however, enforce what the different parts are and the interfaces between them.
Enforcing the overall parts in an AI will place some constraints on what the AI can do. It will place some limitations, and ensure that the AI will not be able to behave optimally in every possible situation. However, I think if we choose well, and create a good design, we can still create a very flexible AI with interchangeable parts. This document intends to outline the design of such an AI framework.
THE CURRENT AI
It is useful to understand how the current AI works. The current AI uses what I will call a "phase based approach". That is to say, it has several phases in its logic, and when one phase has been considered, it proceeds to the next phase, and so forth.
The original basic design was as follows:
The first phase it has is the combat phase. During the combat phase it analyzes all enemy units that may be attacked, and then calculates whether it should attack them or not, based on different heuristics, which can be modified by some of the AI parameters.
The second phase is the village grabbing phase, where it sees if any villages are immediately able to be captured. It then calculates whether capturing these villages should be done, based on more heuristics. This phase also involves a phse to calculate whether units should move onto a village for healing.
Then is a "targetting" phase. The AI has now decided that there are no more units that are "in range" of something attainable this turn, so instead it concentrates on moving units so that they will be able to attain various goals on future turns. It draws up various targets -- by default all enemy/unowned villages and the enemy leader, though configurable by parameters -- and assigns value to them. Then it assigns units to pursue targets based on the distance to the targets and the value of the targets. Units move in the direction of targets.
Finally, there is a recruitment phase, where units are recruited.
Unfortunately, there are numerous defects in this design, some of which have had attempts made to correect them. The biggest defect is that this "phase based" system does not consider opportunity costs. One might choose to attack a unit based on a very marginal advantage it gains, without getting down to the phase which considers that instead of attacking, the unit could have captured a village in an opportune location.
Likewise, and even worse, a unit may choose not to attack in the attack phase, but then after moving through all the other phases, we find that the unit is cornered and doesn't really have any other options. For a long time this led to bizarre behavior where a unit would move up next to an enemy unit but not attack. Eventually this was 'patched' by adding an additional 'mini attack' phase at the end.
There were also many other attempts to improve AI behavior. This included trying to 'group' units together during the target phase, trying to make units 'support' each other in an additional phase, and so forth. Unfortunately these changes tend to have unexpected consequences, and are ultimately just patches of a fundamentally limited system.
A BETTER WAY
Instead of having 'phases' as described above, an AI should consider possible 'candidate' moves, and compare moves to each other, based on their merits, choosing the best possible move. It should compare not only one attack option to another, but it should compare the possibility of attacking a unit with the possibility of moving to capture a village, valuing each against one another, choosing the best option.
However, choosing a move shouldn't necessarily be done on a unit-by-unit basis. If you have five units together, you probably want most or all of them to do something similar. You don't want to send two of them forward to fight and be slaughtered, while the other three stand in a defensive formation, or go off capturing villages.
So, it should be possible to group units into 'squads'. These squads should compare different approaches and choose the best approach for the squad.
COMPONENTS
The AI should have the following components:
- Squad Selection: This is run at the start of the AI's turn, and breaks the AI into squads. The simplest possible approaches, both of which are legitimate in some cases, are to put each unit in its own squad, or to put all of the AI's units into one squad.
There are many other conceivable approaches, such as grouping into squads based on units being able to attack the same enemy, or units having movement possibilities that allow them to end the turn adjacent to each other. The time complexity of an AI will increase exponentially with squad size, so it will likely be a good idea for any approach to limit the number of units in a squad.
- Candidate Move Selection: This component is given a unit, and returns a list of 'candidate moves' for the unit. Attached to a candidate move is attached an 'analysis report' -- a data structure explaining the goals this move fulfills.
The simplest possible Candidate Move Selection algorithm is simply to return all possible moves a unit can make. This approach could actually be sensible, depending on the configuration of the other components.
- Candidate Attack Selection: Attacking in Wesnoth is important enough for it to be given a different component from the Candidate Moves Selection. The Candidate Attack Selection is given a squad of units, and should return candidate attack plans. The attack plans should use some or all of the units in the squad to perform an attack on an enemy unit. Attached to each candidate attack is an analysis report -- a data structure which contains analysis data about the benefits and risks of undertaking the attack.
- Position Evaluator: This component is given a Wesnoth game position and evaluates the strength of the position.
- Recruiter: This component selects which units should be recruited, based on the game position and available gold.
ALGORITHM
The Wesnoth AI Framework will use an algorithm to combine these components to make AI moves every turn:
- All AI units will be divided into squads, by the Squad Selector.
- Each unit will have a list of candidate moves generated
- Each squad will have a list of candidate attacks generated
- Each squad will have possible combinations of moves and attacks simulated, and then the outcomes evaluated using the Position Evaluator. For attacks, the possible outcomes will be determined, and then the chance of each outcome will be multiplied by the evaluation, and these evaluations summed to give an overall evaluation.
It may be too expensive to simulate and evaluate every possible combination of candidate moves and attacks as well as evaluate all possible battle outcomes. The framework may be tuned to use a 'monte carlo' style algorithm to only evaluate some of the possible combinations of candidate moves/attacks. It may also only evaluate some of the possible battle outcomes, since there would be many similar ones.
- After any non-deterministic move takes place (i.e. an attack), the entire algorithm starts from scratch.
BENEFITS
Each different component would be represented by an abstract class in C++. One could write their own classes that derive from these classes, and put them together to make an AI. One could make their classes heavily configurable using WML, or could make them call formulas to make decisions.
This would make the AI very configurable, and would allow one to fairly dramatically control AI behavior by tweaking the different components.
The approach should also be very flexible. One should be able to, for instance, make an AI that can 'guard' against an enemy approach by making an Evaluator that rewards cutting down the possible movement the enemy can make into one's territory, as well as placing one's units on defensive terrain, and so forth.
Naturally there would be many trade offs, and some combinations of components would not work well together. For instance, having a Candidate Move Selector that selects every possible move, and having a Squad Selector that puts all units into the same squad would result in a prohibitively large combination of possible moves a squad could make.
There are also some details to work out, like how AI leaders would fit into this framework, and when recruiting would take place. Possibly it would simply be the job of the Squad Selector to decide if the leader goes in a squad with other units, and the Candidate Move Selector to decide if the leader can move off the keep and the Evaluator to decide if moving off the keep is actually a good idea. But perhaps we could work out a way to add better support for leaders and recruiting to this framework.
CONCLUSION
We need to come up with a better AI solution for Wesnoth. I think this design is fairly solid, and we should try to come up with a proof-of-concept for it.
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
Yogibear
- Retired Developer
- Posts: 1086
- Joined: September 16th, 2005, 5:44 am
- Location: Hamburg, Germany
Re: New AI Design for Wesnoth 1.7
Well, we had a lot of discussions about the AI and its behaviour on FOSDEM. Although i didn't take part in much of it, here are some thoughts of mine.
First of all, i think the component approach is a very good one. It will make the AI more structured (code-wise, mainly) and it will add a lot to understanding its behaviour.
I am also with you about the squad approach.
But i think what is really missing badly is a strategy evaluation. This should be done before everything else. For example a simple strategy could be "if i am weaker (by whatever measurement) i retreat, otherwise i attack". There are also countless possibilites to make this configurable. I am not sure if that goes along with your Evaluator, by i think it has a more global approach.
Depending on the chosen strategy, every unit gets assigned a certain role. A mage for example is a front line linebreaker if attacking and a unit to be guarded if defending. Tanks are either front line heavy hitters or village holders. A shaman or a saurian augur might become a valuable attacker (due to slow / cold) during offense and concentrates on healing during defense. Things like that.
According to the role the unit gets assigned, certain actions are rated. Attacking for example becomes lower priority if defending, healing might be more important here. I also believe that this eliminates a lot of possible actions (especially moves) upfront, making the AI faster overall.
Again, some of your ideas sounded very similar, but i am not sure about the details. I got the feeling that your approach concentrates more on the individual unit, whereas my idea evaluates the strategy first and coming from there does the rest.
Btw, i think the current default AI would be considerably better if we introduce "do_strategy" as the first phase. However, the component approach is superior in my opinion and a lot less maintenance for sure in the long run.
First of all, i think the component approach is a very good one. It will make the AI more structured (code-wise, mainly) and it will add a lot to understanding its behaviour.
I am also with you about the squad approach.
But i think what is really missing badly is a strategy evaluation. This should be done before everything else. For example a simple strategy could be "if i am weaker (by whatever measurement) i retreat, otherwise i attack". There are also countless possibilites to make this configurable. I am not sure if that goes along with your Evaluator, by i think it has a more global approach.
Depending on the chosen strategy, every unit gets assigned a certain role. A mage for example is a front line linebreaker if attacking and a unit to be guarded if defending. Tanks are either front line heavy hitters or village holders. A shaman or a saurian augur might become a valuable attacker (due to slow / cold) during offense and concentrates on healing during defense. Things like that.
According to the role the unit gets assigned, certain actions are rated. Attacking for example becomes lower priority if defending, healing might be more important here. I also believe that this eliminates a lot of possible actions (especially moves) upfront, making the AI faster overall.
Again, some of your ideas sounded very similar, but i am not sure about the details. I got the feeling that your approach concentrates more on the individual unit, whereas my idea evaluates the strategy first and coming from there does the rest.
Btw, i think the current default AI would be considerably better if we introduce "do_strategy" as the first phase. However, the component approach is superior in my opinion and a lot less maintenance for sure in the long run.
Smart persons learn out of their mistakes, wise persons learn out of others mistakes!
Re: New AI Design for Wesnoth 1.7
This is exactly what the squad selection is needed for because retreat or attack is not global. You may retreat at one front but at the same time attack at another.Yogibear wrote:I am also with you about the squad approach.
But i think what is really missing badly is a strategy evaluation. This should be done before everything else. For example a simple strategy could be "if i am weaker (by whatever measurement) i retreat, otherwise i attack". There are also countless possibilites to make this configurable. I am not sure if that goes along with your Evaluator, by i think it has a more global approach.
"If gameplay requires it, they can be made to live on Venus." -- scott
Re: New AI Design for Wesnoth 1.7
As Soliton said, I don't think that a "global strategy decision" is something we want to make a fundamental part of all AI's. I used to think this was perhaps a good idea, but after analyzing many games, I saw that most of the time things don't fit neatly into strategies like "attack/defend/regroup/capture villages/etc". A game of Wesnoth is much more chaotic and skirmish-like than that.Yogibear wrote: But i think what is really missing badly is a strategy evaluation. This should be done before everything else. For example a simple strategy could be "if i am weaker (by whatever measurement) i retreat, otherwise i attack". There are also countless possibilites to make this configurable. I am not sure if that goes along with your Evaluator, by i think it has a more global approach.
I don't think that making "roles" a fundamental part of the AI framework is necessary. It can be implied and handled by the Candidate Move Selector and the Evaluator.Yogibear wrote: Depending on the chosen strategy, every unit gets assigned a certain role. A mage for example is a front line linebreaker if attacking and a unit to be guarded if defending. Tanks are either front line heavy hitters or village holders. A shaman or a saurian augur might become a valuable attacker (due to slow / cold) during offense and concentrates on healing during defense. Things like that.
When you write the components, make the Candidate Move Selector select candidate moves appropriate to a unit's role. Make the Evaluator prefer positions where Heavy Infantry is in the front lines and Mages are protected.
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
Darth Fool
- Retired Developer
- Posts: 2633
- Joined: March 22nd, 2004, 11:22 pm
- Location: An Earl's Roadstead
Re: New AI Design for Wesnoth 1.7
Dave,
What you are describing is very similar to the project I started with the dfool AI. For details, see http://www.wesnoth.org/wiki/User:Darth_Fool. My ideas on AI have evolved a bit since I wrote that, but I think fundamentally the concept of an AI based upon WML defined orders is a good way to go. Unfortunately, it was abandoned because of real world issues that forced me to stop devoting time to wesnoth coding. Now that I again have some time that can be allocated to coding wesnoth, I have started looking at the AI again. I just sent an email to wesnoth-dev detailing a basic plan to redevelop the order based AI using formula AI as a basis. I kind of wish I had checked out this forum first.
I guess my big concern here is having both of us devote a significant chunk of time developing similar AI frameworks. Is there instead a good way to divide the work?
What you are describing is very similar to the project I started with the dfool AI. For details, see http://www.wesnoth.org/wiki/User:Darth_Fool. My ideas on AI have evolved a bit since I wrote that, but I think fundamentally the concept of an AI based upon WML defined orders is a good way to go. Unfortunately, it was abandoned because of real world issues that forced me to stop devoting time to wesnoth coding. Now that I again have some time that can be allocated to coding wesnoth, I have started looking at the AI again. I just sent an email to wesnoth-dev detailing a basic plan to redevelop the order based AI using formula AI as a basis. I kind of wish I had checked out this forum first.
I guess my big concern here is having both of us devote a significant chunk of time developing similar AI frameworks. Is there instead a good way to divide the work?
"you can already do that with WML"
Fight Creeeping Biggerism!
http://www.wesnoth.org/forum/viewtopic. ... 760#131760
http://www.wesnoth.org/forum/viewtopic. ... 1358#11358
Re: New AI Design for Wesnoth 1.7
Personally I think it's okay -- for now -- to have several people work on different ideas. Hopefully people will get their ideas to a "proof of concept" stage where they have a decent AI working. After that, the best concept will hopefully prove itself, and other developers will leap on and help.Darth Fool wrote: I guess my big concern here is having both of us devote a significant chunk of time developing similar AI frameworks. Is there instead a good way to divide the work?
I think it's very difficult to collaborate so early on with the design of an AI. I think it's best to develop things separately and then see what ideas work out best.
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
Re: New AI Design for Wesnoth 1.7
Hm-
So, I have an idea I thought I'd throw out. It's in some sense similar to what Dave suggested.
1. First thing that is done is we generate a bunch of goals. This could be anything that we could want, kill a unit, take villages, defend something, advance towards something, etc.
2. Then for every pair of unit and goal, we generate all the moves that the unit could do and assign them a score determined in part by the goal. That is, for example if the goal is to kill a unit, the score is mostly based on the expected damage to the target but also should take into account other factors like expected damage to itself and how "strong" of a position the unit is stopped in. At this point we would want to throw away many of the unit-move-goal tuples. That is, a lot of a unit's possible moves don't help towards a given goal so we cull them out here.
3. Then, for each of these goals we would generate a set of squads for that goal. For example, if the goal is to take a village then each squad could just be a single unit that could move to that village... if the goal is to kill a unit, then there could be a lot of different combinations that form the squad. For a given goal we would probably want to throw out some squads via some fast check before the next step.
4. For each of these goal-squad pairs, we want to determine the best set of moves. Basically we can use the scores generated in step 2 and find the maximum value pairing of units to locations. This can be done via max-flow. Once the best moves are determined we will want to assign the goal-squad pair a score based on the end-state after the moves are made, this could simply be the sum of the scores of the pairings. Or for something a bit more complicated it could be similar to the position evaluator that Dave mentioned. That is we could just score it based on the change in position strength. We again want to throw out "bad" pairs -- say, those with negative score and probably some lowest percentage of the remaining ones too.
5. Once that is done, we need to actually assign our units to squads. I doubt that there is a fast way to do this perfectly, but there are techniques to get an approximate solution quickly.
6. We must now determine what move to do first. We could, for example, choose to start with the highest scored goal-squad pair and do the highest scored unit-move pair in that.
7. As in Dave's suggestion, after any non-deterministic move we will have to restart from the beginning. Maybe a bit better would be to only recalculate if the expected value of the just moved goal-squad pair has changed.
One of the things that I like about this is that it can actually be built up from very simple components. That is, we only need a way to select goals and a way to assign a score to a unit-move-goal tuple. Once we have those, we can do everything else with no game-specific knowledge.
One thing that this wouldn't explicitly consider is how moves work together. That is, say a goal is to defend an area. Then with two units the best move may not be to move the units to their own best spots but to move them both to spots that would be not as good without the other unit. This is because when we find the "best" moves for a given goal-squad pair we aren't really considering how each unit's move affects the other units other than that they can't move to the same location. The problem with considering how the moves affect each other is that it is much slower. This could be overcome by requiring smaller squads. Another possibility that could help is to actual recalculate after every move. In this way the second unit to move could actually move into position to help the previous one.
So, I have an idea I thought I'd throw out. It's in some sense similar to what Dave suggested.
1. First thing that is done is we generate a bunch of goals. This could be anything that we could want, kill a unit, take villages, defend something, advance towards something, etc.
2. Then for every pair of unit and goal, we generate all the moves that the unit could do and assign them a score determined in part by the goal. That is, for example if the goal is to kill a unit, the score is mostly based on the expected damage to the target but also should take into account other factors like expected damage to itself and how "strong" of a position the unit is stopped in. At this point we would want to throw away many of the unit-move-goal tuples. That is, a lot of a unit's possible moves don't help towards a given goal so we cull them out here.
3. Then, for each of these goals we would generate a set of squads for that goal. For example, if the goal is to take a village then each squad could just be a single unit that could move to that village... if the goal is to kill a unit, then there could be a lot of different combinations that form the squad. For a given goal we would probably want to throw out some squads via some fast check before the next step.
4. For each of these goal-squad pairs, we want to determine the best set of moves. Basically we can use the scores generated in step 2 and find the maximum value pairing of units to locations. This can be done via max-flow. Once the best moves are determined we will want to assign the goal-squad pair a score based on the end-state after the moves are made, this could simply be the sum of the scores of the pairings. Or for something a bit more complicated it could be similar to the position evaluator that Dave mentioned. That is we could just score it based on the change in position strength. We again want to throw out "bad" pairs -- say, those with negative score and probably some lowest percentage of the remaining ones too.
5. Once that is done, we need to actually assign our units to squads. I doubt that there is a fast way to do this perfectly, but there are techniques to get an approximate solution quickly.
6. We must now determine what move to do first. We could, for example, choose to start with the highest scored goal-squad pair and do the highest scored unit-move pair in that.
7. As in Dave's suggestion, after any non-deterministic move we will have to restart from the beginning. Maybe a bit better would be to only recalculate if the expected value of the just moved goal-squad pair has changed.
One of the things that I like about this is that it can actually be built up from very simple components. That is, we only need a way to select goals and a way to assign a score to a unit-move-goal tuple. Once we have those, we can do everything else with no game-specific knowledge.
One thing that this wouldn't explicitly consider is how moves work together. That is, say a goal is to defend an area. Then with two units the best move may not be to move the units to their own best spots but to move them both to spots that would be not as good without the other unit. This is because when we find the "best" moves for a given goal-squad pair we aren't really considering how each unit's move affects the other units other than that they can't move to the same location. The problem with considering how the moves affect each other is that it is much slower. This could be overcome by requiring smaller squads. Another possibility that could help is to actual recalculate after every move. In this way the second unit to move could actually move into position to help the previous one.
Re: New AI Design for Wesnoth 1.7
Designing a new AI and all is fine. But before the old one is burnt to the ground, I would like us to expose what we liked and didn't like about the old one, so that we can keep it in mind when designing the new one. Because modularity, code rewrite, and so on, are only means; in the end, we want an AI that is more fun. So here are a few points:
- I like how obstinate the AI is in killing my units. During a turn, it doesn't scratch each of my units; it focuses on a few ones and slaughter them. Technically, it selects an enemy unit and then tries to hit it with up to 6 units (the actual bound is set by the campaign designer depending on the difficulty) starting with units with "slow" (in fact, it doesn't start with them due to a small bug in the AI, but that doesn't make it a bad idea). Once it has evaluated all the enemy units, it chooses the one which leads to biggest change in economy balance and it starts the actual attack on it. Then it starts its evaluation phase again.
I have noticed two bad points about this approach in the implementation.- Favoring money is good, but sometimes the AI should just decide to free one of its units (in other words, a surrounded unit should be good/bad for global economy).
- Since a dead unit is not a poisoned unit, the AI just underestimates poison attacks; this is typically the situation where scratching as many units as you can makes sense (again, a poisoned yet alive unit should be good/bad for economy).
- I like how team-friendly the AI is. If there are two allied leaders for a single keep, they will leave the keep once they have recruited so that the other one can recruit too. This behavior is really neat, especially once you notice it is done on purpose.
- I don't like the way allied villages are handled. The AI never steps on an allied village, even if it is about to be lost; it prefers it to forsake it to the enemy rather than to defend it. So while the AI should not deliberately hunt the villages of its allies, it should not hesitate to step on them if they are about to be lost.
Re: New AI Design for Wesnoth 1.7
Completely agree. With all your observations as well. Here are some more:silene wrote:Designing a new AI and all is fine. But before the old one is burnt to the ground, I would like us to expose what we liked and didn't like about the old one, so that we can keep it in mind when designing the new one.
1. AI doesn't do half-moves. For example, human players will move leadership units less than its full mp to give a bonus to one unit, then move it again for another bonus elsewhere, while the AI simply moves its leadership unit once.
2. AI isn't very good at backstab because it doesn't set up for it. Moving one unit to give another the opportunity to use backstab would involve sequencing, so that it moves set-up units first, but calculates where they should go based on where the backstabber could go next.
3. Combining both of the above should also greatly increase the effective use of skirmishers.
Hope this helps.
-
grzywacz
- Inactive Developer
- Posts: 303
- Joined: January 29th, 2005, 9:03 pm
- Location: Krakow, Poland
- Contact:
Re: New AI Design for Wesnoth 1.7
Interesting. I saw an exactly opposite behavior while playing 1.6rc two weeks ago. I was playing against 3 AI players and one of the leaders ended up in the other one's castle. The other leader didn't bother to move away - he just stood there blocking his ally from recruiting.silene wrote: [*] I like how team-friendly the AI is. If there are two allied leaders for a single keep, they will leave the keep once they have recruited so that the other one can recruit too. This behavior is really neat, especially once you notice it is done on purpose.
I haven't looked into this case, but maybe it was like that because every turn there was enough money to get at least one more unit?
ORCS WIN!
User:Grzywacz Wiki Site
User:Grzywacz Wiki Site
Re: New AI Design for Wesnoth 1.7
Actually, it's even worse than that in practice. It takes backstab into account, but only with respect to the current positions. Which means that if the first unit to move is already near the enemy but it decides to move to the tile next to it because it has a better defense there, then the second unit to move, which has backstab, will move at the opposite tile from the old position of the first unit, hence completely messing with the predictions (since backstab no longer applies, contrarily to what the AI expected). To summarize, the AI not being good at backstab is not by design, it is by sheer bug. Fixing the way computations are done would automagically fix backstab handling.Barsoom wrote:AI isn't very good at backstab because it doesn't set up for it. Moving one unit to give another the opportunity to use backstab would involve sequencing, so that it moves set-up units first, but calculates where they should go based on where the backstabber could go next.
Yes, unfortunately the AI for leaders is utterly broken in 1.6. At least it was working fine in 1.0; the code is still there in 1.6, but some other bug elsewhere must be preventing it from working.grzywacz wrote:Interesting. I saw an exactly opposite behavior while playing 1.6rc two weeks ago.
Re: New AI Design for Wesnoth 1.7
Here is my ideas about improving AI,im up for comments 
http://www.wesnoth.org/wiki/SummerOfCodeProposal_Velory
http://www.wesnoth.org/wiki/SummerOfCodeProposal_Velory
-
Yogibear
- Retired Developer
- Posts: 1086
- Joined: September 16th, 2005, 5:44 am
- Location: Hamburg, Germany
Re: New AI Design for Wesnoth 1.7
Should be caused by this: https://gna.org/bugs/index.php?13165.silene wrote:Yes, unfortunately the AI for leaders is utterly broken in 1.6. At least it was working fine in 1.0; the code is still there in 1.6, but some other bug elsewhere must be preventing it from working.grzywacz wrote:Interesting. I saw an exactly opposite behavior while playing 1.6rc two weeks ago.
And should be fixed as well.
Smart persons learn out of their mistakes, wise persons learn out of others mistakes!
Re: New AI Design for Wesnoth 1.7
I agree completely. We should try to grow on the current AI. I am planning to re-use plenty of code in any re-write.silene wrote:Designing a new AI and all is fine. But before the old one is burnt to the ground, I would like us to expose what we liked and didn't like about the old one,
Yes! I plan to keep the 'attack analysis' code very very similar, and the design I placed around "candidate attacks" was specifically to allow this. I think the AI is very very good at analyzing attacks and choosing the best way to kill units.silene wrote:I like how obstinate the AI is in killing my units.
I would say this is the only thing the current AI is really really good at (and even this not so much anymore perhaps since some problematic code was added).
I agree with this. It needs to know more about special abilities in general, and poison should be low hanging fruit for this. (As opposed to, say, healing or leadership which is pretty damn hard to teach an AI to do effectively)silene wrote: [*] Since a dead unit is not a poisoned unit, the AI just underestimates poison attacks; this is typically the situation where scratching as many units as you can makes sense (again, a poisoned yet alive unit should be good/bad for economy).
I agree that this is a nice feature and should be maintained.silene wrote: I like how team-friendly the AI is. If there are two allied leaders for a single keep, they will leave the keep once they have recruited so that the other one can recruit too. This behavior is really neat, especially once you notice it is done on purpose.
This kind of thing is quite hard since it's always subjective. The current approach is used because so many people yelled at me with how much they hated the AI getting their villages and insisted "it should never get my villages under any circumstances!!!!!!!" (with that many exclamation points.silene wrote: I don't like the way allied villages are handled. The AI never steps on an allied village, even if it is about to be lost; it prefers it to forsake it to the enemy rather than to defend it. So while the AI should not deliberately hunt the villages of its allies, it should not hesitate to step on them if they are about to be lost.
)I tend to agree though, if we could come up with a very good heuristic. I don't think this is a big deal in the scheme of things, though.
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
Re: New AI Design for Wesnoth 1.7
I'd personally prefer the current system of AI not taking my villages under any circumstances, ever. Yes, it can be annoying at times, but I don't want to have to rely on AI to decide for me when it's intelligent to steal my villages. I'm the player.