New AI Design for Wesnoth 1.7

[teg]

I'm not sure for the AI to decide by itself to take or not your villages, it seems to me overcomplicated, moreover if an option is created for that :
You need to create the algorithm (so you need to define precisely the conditions in which the AI will take possession of the village and it is not simple), you will create situations in which the AI decide to take the village and you don't want it or you are the player, etc.

An idea to simplify the 'AI taking your villages' can be to have a check-box for each of your villages to allow the AI to take it. If you allow the AI to take the village, it is seen by it as an opponent village and so the AI will try to take it.
This way, you decide which village the AI can take so you will never have a situation to complain about it. You don't need to modify the AI for that which is more simple and it creates an interaction between the player and his AI teammate.

What do you think about it, is it a functionality that is desired?

[HalfThere]

I feel like a good approach for individual campaign maps would be iterated battle simulations, allowing the AI to self-tune some of its parameters, allowing it to perform even better than manually-determined settings would allow.

Can Wesnoth simulate battles directly, that is without graphics and other stuff that slows it down?

Of course, the ideal way to create an optimum AI would be to implement a learning-based approach that collects data from all single-player battles during the beta. Sadly, this might be quite difficult, and would probably make file size too large as well.

[Lizard]

Can Wesnoth simulate battles directly, that is without graphics and other stuff that slows it down?

Allefant made a script for that (not sure if it works with the current version of Wesnoth), but you can also look up how --nogui works

[Crab]

Can Wesnoth simulate battles directly, that is without graphics and other stuff that slows it down?

Yes. Example command-line:
./wesnoth-debug . --log-info=ai/testing --nogui --multiplayer --controller1=ai --controller2=ai --scenario=multiplayer_Weldyn_Channel --ai_config1=path/to/ai1.cfg --ai_config2=path/to/ai2.cfg

Also, in trunk, see ai batch testing script, written in python: http://svn.gna.org/viewcvs/wesnoth/trunk/utils/ai_test/

It uses a postgresql DB to store results (a small web frontend in also available in svn).

[AI]

Can Wesnoth simulate battles directly, that is without graphics and other stuff that slows it down?

Yes. Example command-line:
./wesnoth-debug . --log-info=ai/testing --nogui --multiplayer --controller1=ai --controller2=ai --scenario=multiplayer_Weldyn_Channel --ai_config1=path/to/ai1.cfg --ai_config2=path/to/ai2.cfg

If you don't want to profile the code or create good backtraces if it crashes, you're probably better off using the 'wesnoth' binary than 'wesnoth-debug'.

[Zakalwe]

I'm going to agree here with Yogibear about the concept of a 'strategy' phase that precedes all other phases that sets priorities for the AI to follow through the rest of the turn.

I've got a lot of ideas for how to give the AI an ability to think and make decisions 'strategically'.

EXAMPLE Multiplayer AI

for this example we will assume the AI ignores fog of war and that there are only two players on the map.

STEP 1.
AI does this process ONCE at the beginning of each game (maybe a once-off recalculation if the leader moves to a different keep):
Firstly, creates an array with a value (set at zero) for each hex on the map.
Then it simulates the path that each of it's race units would take from it's starting castle to each
i) keep
ii) village
on the map
during each pathfinding simulation every hex that is crossed is incremented +1 in the array.
Then it does the same thing with the opponent, starting from the opponent's starting castle and decrementing -1 on the array all the hexes crossed during those simulations of the opponent's race units.
Finally run some sort of algorithim that smears out the data in the array so that adjacent hexes will share values (think of it as a mathematical 'blur tool') - this may have to be done more than once (potentially)

Now you've got a sort of numeric topographic map that overlays the actual map in the AI's mind, it has the following features:
1. Hexes with positive values are on the AI's "side" of the map
2. The higher the value the deeper within the AI's territory that hex is. The higher the value the stronger the AI is to it's military 'center of gravity' or the shorter it's 'supply lines' are. This means that theoretically it will find it easiest to concentrate it's forces around those hexes.
3. The AI now has an easy way to identify which villages 'belong' to it - any that have a positive value should be captured because they are closer to the AI than to the opponent (or the AI is between the village and the opponent).
4. Hexes that have a value close to zero are the ones where paths between the AI and it's opponent cross - these are the areas of conflict. In fact, if you colour in all the hexes with a value close to zero you'd probably get what can be termed a 'border zone' or 'no man's land'. This is a concept that is easy for a human to grasp but difficult for a computer the handle.

Now this is part of the basic information the AI can use for later decision making.
For example if it wanted to prioritise some 'village stealing' with some scout units - it would just make a list of villages starting from the one with the most positive value to the one with the most negative value, then it will exclude any village with more than 1 or 2 enemy units within 1 turn's movement range. Leftover is a list of villages suitable for stealing.
Another example is if it does a ToD calculation (I will elaborate on this later) and decides to retreat, which way to go? towards hexes with a more positive value and away from ones with a lower value.

#######
I'm going to bed now but I will try to get back and type up more of my ideas about how the AI could perform strategic analysis and decision making.

If people really like my ideas I will try and come up with some pseudo-code to help figure out implementation.

Preview of other ideas:
* Terrain type analysis (I get the feeling the AI already does this for picking troop mix?)
* Force mix analysis - based on averaging out all damage types on one side against the resistance types on the other side. (using weighted averages)
* Fighting strength analysis (including ToD analysis) (calculating a number for each side based on the aggregate of all of one side's unit's best attacks against a weighted average of the opponent's defense and resistances (taking into account ToD) and then comparing the two
* Wholistic comparison analysis - AI compares each player's
i) villages/income/gold reserves (if known, otherwise smart guesstimate)
ii) unit count and strength (see strength analysis above)
iii) experience (totals of player's unit's exp.)
iv) other factors? (as people come up with them.

--- The AI will then formulate the 'grand strategy' for the turn based on the result of the Wholistic comparison.
Ripping off Lionel's translation of Sun Tzu's Art of War:

8. It is the rule in war, if our forces are ten
to the enemy's one, to surround him; if five to one,
to attack him; if twice as numerous, to divide our army
into two.

9. If equally matched, we can offer battle;
if slightly inferior in numbers, we can avoid the enemy;
if quite unequal in every way, we can flee from him.

the AI will use some sort of heurustic rule similar to the above to figure out it's grand strategy for each turn.

Okay, I'm going to bed now. Good night all.

Please let me know what you guys think.

[Crab]

Hi, Zakalve

for this example we will assume the AI ignores fog of war and that there are only two players on the map.

Yes, current AI fully ignores fog.

Now you've got a sort of numeric topographic map that overlays the actual map in the AI's mind

Dragonking has done something roughly similar in his new recruitment work (you can check it out via launching wesnoth in debug mode and
selecting "Formula AI dev' from the list of multiplayer AIs )

If people really like my ideas I will try and come up with some pseudo-code to help figure out implementation.

that is good.

* Terrain type analysis (I get the feeling the AI already does this for picking troop mix?)

yes, there are two different implementations of this, for recruitment. The problem with them is: "ok, map got water, we recruit fish. Ok, where is enemy ? on land ? ok, we move our fish to land"

* Force mix analysis - based on averaging out all damage types on one side against the resistance types on the other side. (using weighted averages)

yes, there are two different implementations of this, for recruitment.

* Fighting strength analysis (including ToD analysis) (calculating a number for each side based on the aggregate of all of one side's unit's best attacks against a weighted average of the opponent's defense and resistances (taking into account ToD) and then comparing the two
* Wholistic comparison analysis - AI compares each player's
i) villages/income/gold reserves (if known, otherwise smart guesstimate)
ii) unit count and strength (see strength analysis above)
iii) experience (totals of player's unit's exp.)
iv) other factors? (as people come up with them.
--- The AI will then formulate the 'grand strategy' for the turn based on the result of the Wholistic comparison.

Making this info available is easy, the harder question is what to do with it ?

Right now, the most important problem that needs to be solved for current AI, is 'where to move units when enemy is not near?'
Current implementation of 'move and targeting phase' is slow, scales poorly with the number of units/targets (try playing NR: Showdown with 100+ friendly units - orc turns can take *hours*), and is easy to misuse.

[Zakalwe]

Hi, Zakalve

yes, there are two different implementations of this, for recruitment. The problem with them is: "ok, map got water, we recruit fish. Ok, where is enemy ? on land ? ok, we move our fish to land"

Right now, the most important problem that needs to be solved for current AI, is 'where to move units when enemy is not near?'
Current implementation of 'move and targeting phase' is slow, scales poorly with the number of units/targets (try playing NR: Showdown with 100+ friendly units - orc turns can take *hours*), and is easy to misuse.

Hey Crab,

I'll just answer two of the key questions that you are posing:

Firstly by using the numerical measure generated by the "STEP 1" process I described above and integrating the results with a terrain analysis the AI will be able to figure out what kinds of units are best for the 'zero value' conflict area fighting, it will also be able to identify the AI's 'home base' (highest negative value) and if it's done well, it will finally be able to identify the units that will move fastest/get best defense along the 'key paths' across the map (the greatest rate of change in value between hexes). This will help it to build the right units.

Secondly 'what to do when the enemy is not near?' is a specific question - but what I think you mean is 'how do we get the AI to use planning? I think the best way to answer that is to create something that can generate reasonably effective overall strategies.

Possible strategies would include elements such as:
"Capture all villages on my side of the map"
"Move Leader to a different keep"
"Harrass opponent by stealing villages"
"Anti-harrassment routine (for preventing village raids)"
"Full retreat"/"Partial retreat"
"Advance"/"Occupy terrain"
"Full attack"/"Partial attack"
"Do scouting"
"Recruit Units"
"Assassinate opponent's leader"
"Hold ground/Consolidate - heal and rotate units"
"Pre-emptive raids"/"sacrificial speedhump tactics" (such as poisoning attacking units at bad ToD or putting up a screen of WCs to protect valuable units)
"Maximum casualty attack" (ignores risks and goes on full steam attack to kill opponent's units).
"Concentrate forces"/"Disperse forces" (usually coupled with attack or retreat, hold ground etc.).
"Protect high value units" (leaders and lvl2 and lvl3 units)

Each of those strategy elements would be able to be broken down into a formula for how to accomplish it.

Each turn the AI would run a 'wholistic analysis' at the start of turn and then choose something like 1-5 of the goals from the list above. It would then do a weighting of importance of each goal and assign them both a priority and a percentage of it's forces (with room for a fudge factor). There will obviously be a bunch of formulas and a small amount of dice rolling involved in this process.

Say an AI has 10 units (including leader) and picks the following 4 strategies:
1. Recruit units (1)
2. Steal villages (1)
3. Occupy terrain (6)
4. Protect high value units (2)

So first thing it does is move it's leader onto a keep (if it isn't already there) and then it moves to the next step - the AI will come back at the end of the round and actually recruit the units. Here it uses 1 unit - the leader.

Second thing it does is it identifies opponent's villages that can be stolen (safely). It has found 2 villages, it then looks at which units can be used to steal them by (1. Working out travel/pathfinding can it get there? 2. making a rough estimate of whether it can survive the next turn on that hex) it has found 2 or 3 suitable units. It decides to steal both villages and sends two units.

Third thing it does is run the occupy terrain strategy, now it first identifies which area(s) it wants to hold and then it picks 6 units. This step is really easy because the protect high value units strategy 'claims' the units it wants to protect and cuts them out of the list (so does the anything involving the leader). Because there are only 7 units left unused and one of them is the 'high value unit' the other six are picked and sent to occupy terrain.

Fourth the AI grabs the high value unit (say a wounded lvl2 unit) and runs it away from the opponent's units, towards healing and onto a high defense hex if possible. The second unit the algorithim originally requested is not available (it was used to steal a village instead) so the AI cannot further protect the high value unit by using ZoC/blocking/meatshield tactics with the second unit.

Finally the AI finishes it's turn by tying up loose ends like finishing the recuit process etc.

I'm not saying this sort of system would not make mistakes, nor would it be without weaknesses or downsides, but it would allow the AI to have a more humanlike ability to plan and play in a more challenging and less predictable fashion.

---
btw I'm glad that other people have already created systems for generating information. I will focus more on my ideas for how the AI will actually generate strategies. Thank you for point out to me the work that has already been done.

[pauxlo]

STEP 1.
AI does this process ONCE at the beginning of each game (maybe a once-off recalculation if the leader moves to a different keep):
Firstly, creates an array with a value (set at zero) for each hex on the map.
Then it simulates the path that each of it's race units would take from it's starting castle to each
i) keep
ii) village
on the map
during each pathfinding simulation every hex that is crossed is incremented +1 in the array.
Then it does the same thing with the opponent, starting from the opponent's starting castle and decrementing -1 on the array all the hexes crossed during those simulations of the opponent's race units.
Finally run some sort of algorithim that smears out the data in the array so that adjacent hexes will share values (think of it as a mathematical 'blur tool') - this may have to be done more than once (potentially)

Now you've got a sort of numeric topographic map that overlays the actual map in the AI's mind, it has the following features:
1. Hexes with positive values are on the AI's "side" of the map
2. The higher the value the deeper within the AI's territory that hex is. The higher the value the stronger the AI is to it's military 'center of gravity' or the shorter it's 'supply lines' are. This means that theoretically it will find it easiest to concentrate it's forces around those hexes.
3. The AI now has an easy way to identify which villages 'belong' to it - any that have a positive value should be captured because they are closer to the AI than to the opponent (or the AI is between the village and the opponent).
4. Hexes that have a value close to zero are the ones where paths between the AI and it's opponent cross - these are the areas of conflict. In fact, if you colour in all the hexes with a value close to zero you'd probably get what can be termed a 'border zone' or 'no man's land'. This is a concept that is easy for a human to grasp but difficult for a computer the handle.

Either I misunderstood your algorithm idea, or it won't work.
As I understand, villages completely on your side, but not on the way to any other village or keep (so maybe behind your castle, to the border/corner of the map), will be at level 0, since both your and the enemy's units don't cross it to go to any other village/keep.

What your algorithm does, is emphasizing (?) the "streets" used by you and not your enemy, and inversely. It does not really measure "short supply lines" or "close to my castle" (apart from the area really close to it, in the direction of most villages).

[Crab]

Secondly 'what to do when the enemy is not near?' is a specific question - but what I think you mean is 'how do we get the AI to use planning? I think the best way to answer that is to create something that can generate reasonably effective overall strategies.

Possible strategies would include elements such as:
"Capture all villages on my side of the map"
"Move Leader to a different keep"
"Harrass opponent by stealing villages"
"Anti-harrassment routine (for preventing village raids)"
"Full retreat"/"Partial retreat"
"Advance"/"Occupy terrain"
"Full attack"/"Partial attack"
"Do scouting"
"Recruit Units"
"Assassinate opponent's leader"
"Hold ground/Consolidate - heal and rotate units"
"Pre-emptive raids"/"sacrificial speedhump tactics" (such as poisoning attacking units at bad ToD or putting up a screen of WCs to protect valuable units)
"Maximum casualty attack" (ignores risks and goes on full steam attack to kill opponent's units).
"Concentrate forces"/"Disperse forces" (usually coupled with attack or retreat, hold ground etc.).
"Protect high value units" (leaders and lvl2 and lvl3 units)

thanks for the list, it will be useful.

Third thing it does is run the occupy terrain strategy, now it first identifies which area(s) it wants to hold and then it picks 6 units. This step is really easy because the protect high value units strategy 'claims' the units it wants to protect and cuts them out of the list (so does the anything involving the leader). Because there are only 7 units left unused and one of them is the 'high value unit' the other six are picked and sent to occupy terrain.

Can you explain in more detail how this part will work ? How we are dispatching 6 units to occupy terrain ? right now, our AI can only send units one-by-one (except when in 'grab villages' phase).
So, if we're sending our units one-by-one, then:
- how we'll avoid the "one unit reached the good terrain, other were not able to reach that terrain, so the first unit is left alone" situation ?
- how we'll speed up the evaluation of such moves ? (right now, targeting phase is slow because it dispatches units one-by-one, and recalculates 'find best unit for best target' a lot, which results in lots of A* calls)
Else, if we're sending them at the same time, then how "find best combination of units" is implemented ?

[bvanevery]

I think the current approach to capturing allied villages is too simplistic. While I can understand the "Bow before me, I am human" mentality, there are occasions when it is beneficial and even acceptable for an AI to take the player's villages.

This is the cart before the horse. The current AI is not good enough to serve as a useful ally. All an AI ally does is blunder into the enemy and weaken him a bit. He is never better at doing damage than you are, even with tremendous force advantages. Consequently, allied villages should all be your villages, so you can spend that gold properly and mount a proper defense or offense. Implementing any kind of allied village grab when the ally performs poorly is going to annoy players greatly. First fix the AI, to the point where it actually makes decent combat decisions. Then talk about empowering the AI to have more villages under its control.

[Zakalwe]

Hey pauxlo,

Thank you for your input.

I see what you are saying but I think you missed a bit at the end where I wrote:

Finally run some sort of algorithim that smears out the data in the array so that adjacent hexes will share values (think of it as a mathematical 'blur tool') - this may have to be done more than once (potentially)

Now I've been thinking about how to do this best and I think you are right about what sort of numbers you would get from running the algorithim. I think that the increments have to be higher than just +1/-1 to begin with - they will probably have to be weighted in an intelligent manner otherwise there will be a miscalculation if you have a matchup between a faction with 8 units like Loyalists against a faction with 6 units like Drakes.

As for the 'blur tool' I was talking about it my original post I think the best way might be to start by doubling (or multiplying by another number) the results generated by the first part of the process and then, starting from the hexes with the highest (+/-) values, incrementing the hexes nearby by +/-1 or +/-0.5 etc. maybe this process can be run more than once.

You made another point about not being able to establish 'sides'. I think one possible solution that would work in conjunction with the 'blur tool' is to start with a non-zero value for the starting keep, or keep where the leader is located.

I would like to hear more of your opinions and input: do you think my suggested solution with the 'blur tool' would work? Would it be necessary to start with a non-zero value for the starting keeps? Finally do you think there is a particular number of times the blur tool should be run or would it depend on the size of the map? Or some other factor?

----
Just to clarify how I imagine the STEP 1 algorithim to work picture this:

Take a piece of paper and draw a map on it, you will have two starting keeps and a bunch of villages all over the place. There will be different types of terrain (with different movement speeds) all around.
Now take a red crayon and a blue crayon.
With the red crayon draw lines from the player 1(rebel) starting keep to each village representing the quickest route for an elf fighter, now draw another set of lines for archers, mages, merman hunters etc. etc. The resulting image should look like the spokes of a very very lopsided wheel.
With the blue crayon do the same for player 2(drake, loyalist, undead, another elf etc.).
Now smudge the whole page using your fingers (or a brush etc). <<<<This is a key step

There should be about 6 types of colours on the page:
1. Strongly red - this is the 'home' of player 1
2. Pink - this is player 1's 'backyard'
3. Purple - this is the contested ground between the players
4. Sky blue - this is player 2's 'backyard'
5. Strongly blue - this is the 'home' of player 2
6. White - these are areas of the map that aren't really relevant to either player.

Having done this visual exercise you might notice that the algorithim I originally proposed does not effectively distinguish between Purple and White, nor does it handle more than 2 players. I think this could be addressed with a sort of 'colour based' system. Basically instead of P1 being positive numbers and P2 being negative numbers, every player side would have a positive number. A bunch of new options enter in at this point:
1. White vs. Colour - add up the totals for each player on each hex, the higher the 'total' number the more important that hex is likely to be and the more traffic it is likely to see. Should illustrate the 'relevant' portions of the map to the AI
2. Red vs. Blue - you can get the same result that the original idea for the algorithim would give you just by subtracting the opponent's number on each hex from the AI's number on that hex.
3. Team vs. Team - add up the numbers for each side and then do the 'Red vs. Blue' subtraction as above for a similar result, or to figure out which part of the map each AI is 'responsible' for you could get fancy/tricky (I will need to take some time to figure out concrete ideas that would work)
4. FFA - similar to Team vs. Team, this is significantly more complex because you can do Red vs. Blue calculations individually or a Red vs. Everyone else composite calculation but I'm concerned about what the results might look like.

----
Hey Crab,

I intend to expand out the list of strategies with more ideas/details on how to implement them in a few days time. I'm really glad that you are finding my ideas useful.

The way I see things (I'm probably not the first one to think of all this, but I'd like to elucidate on it) is like this:

There are two approaches to implementing a flexible 'game' AI (that can deal with 'unknown' situations)
1. Have the AI do brute force calculations, like a Chess AI does a tree search - go through all decent looking moves to come up with some candidates, find the best reply from the opponent, find the best reply to that and so on and so forth until memory, processor power or time limitations force the AI to stop its search and play the 'best' move it was able to find.
Now in this approach the AI's 'strategy' is an imergent phenomenon - if this was a question of ethical philosophies it would be considered consequentialist/utilitarian: "The action that arrives at the best result the is 'right' strategy"
This approach is not very good for Wesnoth because each move is a turn and each turn has a VERY VERY large number of combinations of possible moves.
2. On the other hand (to borrow from philosophical ethics again) there is the "proceduralist" approach which is to have a set of rules (or Heuristics) that identify the situation at hand and then take an action that is determined by some pre-written "laws" or "rules". The weaknesses of this approach are that firstly it can be difficult to correctly identify what rule you should be following at any given point in time and secondly depending on who wrote those rules they might not give you the best results. With this approach "The appropriate strategy determines the best action".
George Polya's "How to solve it" states:

1. First, you have to understand the problem.
2. After understanding, then make a plan.

The problem to be solved is "How do I win?" This problem can be worked out in reverse:
a) Kill the opponent's Leader
b) Get within attacking distance of the opponent's Leader with sufficient forces to kill it
c) Build sufficient forces to kill opponent's leader
d) Get sufficient gold/income to build sufficient forces
e) Move these forces towards the opponent's leader
f) Maintain sufficient forces by keeping units alive and replacing
g) Destroy/bypass opponent's forces blocking my forces from reaching the opponent's leader
h) Get a larger/better force than opponent's force
i) Prevent opponent from building more forces
j) Take away opponent's income
Now as a human I can figure this out pretty easily but the computer, not being sentient/sapient, cannot.
The goal of the AI programmer is to reduce a complex goal that the AI cannot solve into a series of simpler sub-goals that the AI can solve.
To this end you'll notice that a lot of the goals from the "List of strategies" are just the sub-goals in reverse order that I worked out above being written in a different form. Another benefit of sub-goals is that they can be less computationally intensive (hopefully) than the brute force method, even though there is the extra work of analysing the situation and choosing the strategy added to the computer's burden.

Can you explain in more detail how this part will work ? How we are dispatching 6 units to occupy terrain ? right now, our AI can only send units one-by-one (except when in 'grab villages' phase).
So, if we're sending our units one-by-one, then:
- how we'll avoid the "one unit reached the good terrain, other were not able to reach that terrain, so the first unit is left alone" situation ?
- how we'll speed up the evaluation of such moves ? (right now, targeting phase is slow because it dispatches units one-by-one, and recalculates 'find best unit for best target' a lot, which results in lots of A* calls)
Else, if we're sending them at the same time, then how "find best combination of units" is implemented ?

The "Occupy Terrain" strategy is listed beside the "Advance" strategy because they are quite similar.
The "Advance" strategy sums up to:
"Move towards the opponent's side of the map with the nominated units (only attack if a] it is necessary to kill an enemy unit to open the path or b] one of your units ends up near an enemy unit and the damage exchange ratio is good)"
The "Occupy Terrain" strategy is:
"Move towards the opponent's side of the map with the nominated units and end their movement on advantageous terrain (only attack if one of your units ends up near an enemy unit and the damage exchange ratio is good)"

Implementation for the "Occupy Terrain" strategy
As I said before the AI picks a 'pool' of nominated units.
The simplest implementation would be to start with the one with the highest cost/lowest hitpoints/etc. etc. and look at all the hexes that are 'enemywards' of that unit. find the hex that has the highest defense/highest relative defense (highest relative defense is the greatest difference between the defense value of the hex [high] and the adjacent hexes on the opponent's side [low] examples would be a village next to open ground or a mountain next to river tiles). Move that unit to the best hex found during the search. Then repeat the process down the line til you get to the point where the least valuable/most durable/most expendable unit is moved last. This approach sucks when it comes to unit co-ordination but has the benefit of working with ANY pool of units no matter where they are located.
More complex implementations would include other factors into consideration.
If you wanted to move units as a group you'd have to take a different approach, starting with identifying the group and then creating a little sub-map that shows the over-lap region of their movement possibilities (for each unit go through the map and increment by 1 all hexes that it can move to this turn). You then discard all hexes that are
1. Not incremented
2. Not on the enemyward side of the map
3. Occupied by Allied/Neutral(including stoned) units or otherwise effectively impassable
4. Occupied by opponent's units/blocked by opponent's units ZoC
5. Have crappy low-defense terrain or some other glaring problem (glaring problems yet to be defined or thought of)
At this point there are a few different ways to proceed:
*Method 1
try out all the different 'final' positions, this is the brute force combinatorial C(n,k) approach where you try out every combination of k units into n hexes of terrain. There will probably be a bucketload of calculations (mostly combat calcs) for each possibility - this is computationally expensive but certain to produce the best result.
*Method 2
where n is the number of units in the group:
find the n best pieces of terrain for each unit (in descending order).
search for terrain 'clumps' (do all hexes have to be adjacent to one another?) that include a 'favourite' from each of the units in the group. Now either assign each hex to each unit (according to its preference order) or do a combinatorial search as method 1 except this time you only need k units in k hexes of terrain ...

The amount of detail that goes into working this stuff out seems somewhat overwhelming. I am however consoled by the fact that many of the basic ideas/steps can be re-used to handle other situations.
I'm taking a break at this point because I need to go to bed. More to come later.

One final thought before I hit the sack is that when it comes to combats often the only things that the computer needs to know is "will my unit die if it's attacked?" and "will the opponent's unit die if it's attacked?" in the context of small tactical battles in localised areas. In Wesnoth most of the time there are no certainties - most of the time there is a non-zero chance of a unit dying in combat or getting killed next turn.
In a lot of situations the AI doesn't need to 'sim out' every possible outcome, it just needs to simulate a few combats between 1 unit and the units that are in range to attack it. At this point you get a probability that the unit in question will kark it. By fiddling with what % level of confidence the AI finds acceptable in a given situation you can make it make either timid or bold/reckless choices.

Post Scriptum final thought. Many of these strategies will need to be 'recalculated' if the AI 'discovers' a hidden unit in Ambush/Nightstalk etc. etc. It will be necessary to come up with a response for AI's when this occurs (it could be a %/% chance of either to continue running the strat/abandoning the strat and choosing a new one for those units left in the 'pool').

[pauxlo]

Hey pauxlo,

Thank you for your input.

I see what you are saying but I think you missed a bit at the end where I wrote:

Finally run some sort of algorithim that smears out the data in the array so that adjacent hexes will share values (think of it as a mathematical 'blur tool') - this may have to be done more than once (potentially)

No, I did'nt miss this.

Now I've been thinking about how to do this best and I think you are right about what sort of numbers you would get from running the algorithim. I think that the increments have to be higher than just +1/-1 to begin with - they will probably have to be weighted in an intelligent manner otherwise there will be a miscalculation if you have a matchup between a faction with 8 units like Loyalists against a faction with 6 units like Drakes.

Naturally. (And for loyalists the spearman movement is more important than fencer, for example.)

You made another point about not being able to establish 'sides'. I think one possible solution that would work in conjunction with the 'blur tool' is to start with a non-zero value for the starting keep, or keep where the leader is located.

Depending on the way the lines are drawn, the starting keep hex would start with a high positive/negative score, since all of your lines begin/end there. This would not be a problem.

Just to clarify how I imagine the STEP 1 algorithim to work picture this:

Take a piece of paper and draw a map on it, you will have two starting keeps and a bunch of villages all over the place. There will be different types of terrain (with different movement speeds) all around.
Now take a red crayon and a blue crayon.
With the red crayon draw lines from the player 1(rebel) starting keep to each village representing the quickest route for an elf fighter, now draw another set of lines for archers, mages, merman hunters etc. etc. The resulting image should look like the spokes of a very very lopsided wheel.
With the blue crayon do the same for player 2(drake, loyalist, undead, another elf etc.).
Now smudge the whole page using your fingers (or a brush etc). <<<<This is a key step

Yes, i imagined it this way (a bit more matematically, but essentially the same).

There should be about 6 types of colours on the page:
1. Strongly red - this is the 'home' of player 1
5. Strongly blue - this is the 'home' of player 2
6. White - these are areas of the map that aren't really relevant to either player.

OK.

2. Pink - this is player 1's 'backyard'
3. Purple - this is the contested ground between the players
4. Sky blue - this is player 2's 'backyard'

With this I don't really consent.
I think, both players "backyards" will be same "light purple".

Did you try this out with a map and some units?
(Could be really simplified, only 8 villages, 2 keeps, and each side with two units.)

Paŭlo

[Mooncalf]

some thoughts on the "big strategy"-discussion i'd like to share

As allready mentioned the current AI does a great job at the actuall fighting, but its general strategy can be described as : "stumble in the general direction of the enemy. When in range -> engage."
Which is a fairly inefficient way to do it. And while i totaly agree with most changes dave suggested, i think the new AI would suffer from the same basic flaw.

The problem, as i see it, is, that each turn the current AI looks at a single unit and then wonders where to place it. Daves intended change of looking at squads/groups instead of single units will greatly increase the effectiveness of the unit placing, but i think, it's still the wrong way around to do.

I think, the AI should first look at the map and try to identify and evaluate what i'd like to call "strong points". This should always be clusters/groups of hexes, that offer higher defensive capabilities then the surrounding hexes. That means hills/woods can be strong points or castle-hexes or the area around every village should be one, or even plain hexes next to water hexes. The tricky part would be writing an algorythm to identify those clusters and to asign a significant general value to each of those strong point. This value will of course be faction dependend.

The AI should then evaluate each turn what kind and number of units should be assigned to each strong point on the map. From a programming view i would make those strong points a class, each "knowing" how urgently it self need troops and how many units are needed to hold/take that point. Then have an arbiter over routine to do the assignment of units to those points accordingly. This would directly lead into the squad building Dave spoke about.

Again identifying how badly each strong point need troops, would be the tricky part. The general idea should be something basic like: the points were the fewest units make the highest impact should report the highest values.

And i think a second concept could help there. My thoughts go into a similar direction as Zakalwes. I think the AI should have a general idea where the front line is, or should be. Objectives of the AI should be:
1) secure all villages on its side of the frontline and
2) whenever possible push the frontline away from own castle and in direction of the enemys castle.

in difference to zakalwes approach i would not give every hex on the map a value, depending on distance to home. Instead i would concentrate on a single frontline. This frontline should be made up by a set of strong points, with all strongpoints in that set have to be connected, i.e. there can be no non-frontline-strongpoint between two strongpoints of the frontline. Only those strong points that are (at the current turn) member of the frontline-set should be take into consideration when assigning units.

At the start of each game the frontline should be roughly a line dividing the map into two areas of the same size (strong points in euqal distance distance to both castles). later in the game, the AI has to do a threat evaluation as first step. It has to look at each section of the frontline (i.e. strong point) and compare the own forces to adjacent enemy forces. Based on this evaluation (factoring in things like ToD) it has to decide where it should attack, defend or retreat at that section of the map.

With Attack, defend, retreat translateing into frontline-thinking:
Attack : replace one strongpoint occupied by my forces from the set with one or more adjacent strongpoints that are nearer to the enemys castle
Defend: keep the frontline as it is
Retreat: replace one strongpoint occupied by my forces from the set with one or more adjacent strongpoints that are nearer to my castle

And as an aditional bonus of this concept, you could increase recruiting efficiency by not considering the terrain mix of the whole map, but by considering the terain mix of only the hexes of the frontline strong points

So thats my basic idea. Still a lot of details i havent tackled yet, and of course i'm no pro-coder so it may turn out to be impracticable (or unKISS ) but i'd really like to hear/read your comments especially from the devs

Thx

Moony

[spir]

preliminary notes:

• Strategy & tactics are elaborated according to a main objective; AI's objective depends on opponent's (player's) one and/or story.
• Q: Where is the border between strategic & tactical levels?
• Whatever the answer, Wesnoth's game is far too complicated to even hope designing any strategy (even a very poor one, even for the simplest case). To be convinced of this, just compare the complexity of chess (or go!) to Wesnoth. Concretely, this complexity causes both infinite computing time and impossible algorithm design (for the humans).

I will use "strategy" to refer to any decision taking over lower-level ones such as whether a unit or "squad" should attack or not. This latter case beeing "technique" and decided according to the result of an evaluation function. I guess this more or less mirrors the human decision: basically rating a possible attack is purely technique once the game rules are mastered; but in the human case, this basic rating will be further pondered by tactical/strategical consideration. (It may surely also be pre-pondered by such consideration, actually often disgarded before any evaluation, but this is out of my concerns here).

I think that, in place of real strategy/tactics in the proper sense of the term (eg "diversion" or "divide and conquer"), we could rather easily & clearly introduce "trends". An example of what I mean already exists in the present AI, namely the agressivity key inside [ai], an overall weight factor that will affect all attack decisions. I consider this as a good example of strategic trend.
There may be several trends such as this one, all together building a kind of trend space. Each strategic trend beeing set by a "cursor" (value), analog to a coordinate on an axis, all together determine a precise point in this space. This point can thus be used to influence all decisions. Concretely, it would ponder ("weigh"? do not know the proper english word) action evaluation, in addition to factors specific to this kind of action (such as damage chance for an attack).

I have three factors in mind:

• risk/agressivity: from "prudence" to "temerity", this factor mainly weighs defense vs attack
• time/emergency: how urgent it is to concentrate on the most important tasks (eg killing as opposed to grabbing a village). This factor indeed also depends on the scenario probable length.
• space/area: first, one (or more) area(s) to control can be specified. Then, its importance is pondered by the space factor. Concretely, controlling an area simply means concentrating troops around there. (I think this is the only real tactics we may implement -- and probably it's enough). At the computing level, this means that any possible action will be overrated if it brings a unit closer to the area, and conversely.

These trend factors are indeed clearly related to unit action decision, but at the same time still rather independant. They build an over-layer on action evaluation. For instance, the risk trend will influence the evaluation of attack, but also of positioning or of reaching a village. The same for time: if the factor is low, the AI can for instance recruit more scouts, and later give more importance to grabbing villages; it can recruit weaker but faster fighter to try and kill isolated units. As of space, any action will be less likely undertaken if it drives a unit farther from the zone to be controlled.



As an example, let's imagine a scenario using a map that mainly consists of a mountain pass. The player's side (elves) are on their way to an important mission; they must absolutely crawl across the pass, while there are ennemies (AI side, orcs) on a mountain flank, closer to the narrowest point of the valley and also faster on the main terrain. The story states that the orcs are not mere raiders or elf haters, they know indeed about the elves' objective and may even be here precisely to counter it.
So that the scenario designer would try to set the strategic trend cursors so as to maximize the orcs' chances to block the elves there. Well, you see what I mean, don't you?



I guess that a small set of such (clear? easy?) strategic trend cursors made available to scenario designers (and properly introduced!) would provide for more pleasant and... challenging gameplay.