Help with testing Fred - Freelands MP Custom AI v0.14.15

[Alarantalara]

One interesting surprise was his recruiting of naga during one particular match (replay: "fred_vs_courageous_fools") that I don't remember seeing him do before (or since).

The whole recruiting code was written by Alarantalara quite a while ago and has been in Fred (and Ron, in fact) pretty much unchanged since then. Since it seems to be doing pretty well overall (and yes, even throwing the occasional naga or other surprise at you), I am treating it as a black box for now and am simply using it as is.

I've tried to model the recruiting to be similar to how human players pick units, however there are a few differences.
1) Some of the very high risk/reward units don't get recruited as often as a human might use them (Horseman, Berserker). For the AIs written at the time, this is a good thing, since these units, while very powerful, also require the most work to protect because of their usually high cost. While this does not really affect the Northerners, who don't have such units, it's something to address for the other factions in the future.

2) There's no real model of what the opponent might recruit, all enemy units are considered equally likely to be recruited. Tracking the enemy's historical recruiting behaviour and looking at what it would do if it were the opponent should slightly improve the results.

As for the Naga, without looking at the match, I'd imagine that it was most likely recruited during either the second watch or dawn when your advanced units were easily reachable via one of the waterways as a way to quickly reinforce an existing situation during the day. I'll go take a look at the replay though.

[mattsc]

Thanks for the explanations, Alarantalara. I'm aware of the fact that we might have to look into the recruiting code at some point in the future. For now though, if everything else in Fred worked as well as the recruiting, I'd be super happy!

I have run several more sets of Fred vs. default AI games (1200 in total) to try to figure out whether there was a regression from 0.14.0 to 0.14.1.

Some rambling about the tests, skip if you just want to see the results

The problem with my previous tests, giving 100 gold to both Fred and the enemy, is that it is impossible to see any improvements. If Fred already wins pretty much all games, well, anything but a very dramatic change is simply not visible. So I first spent some time trying to find out at which enemy gold amount Fred wins about 50% of the games against Northerners (that faction being chosen because it is the one the default AI plays best).

Turns out that that is at about 160 gold in 0.14.1 and that it is very volatile around that value. As in, with 150 enemy gold, Fred still wins almost all the time. At 175, he loses pretty much all the time. So this is pretty ideal for the tests I want to do. The down side is, of course, that there's quite a bit of variation between different trials of the same test, so we shouldn't read too much into small differences. However, together with the results for the other factions, I think we can draw some conclusions from the results below.

Disclaimer: of course, this does not tell us how well Fred does against a human player, but if performance decreases against the AI, that's not a good thing.

The results:

Code: Select all

Fred's gold: 100, enemy gold : 160
300 games total per trial, 50 games against each faction

                v0.14.0   v0.14.0       v0.14.1   v0.14.1
                trial 1   trial 2       trial 1   trial 2
Drakes           23 46%    27 54%        14 28%    23 46%
Knalgans         34 68%    36 72%        32 64%    29 58%
Loyalists        38 76%    42 84%        30 60%    28 56%
Northerners      41 82%    30 60%        27 54%    30 60%
Rebels           41 82%    44 88%        42 84%    42 84%
Undead           43 86%    42 84%        39 78%    37 74%

Total           220 73%   221 73%       184 61%   189 63%

So I think the main conclusion is that Fred indeed is not playing as well in 0.14.1 as he did in 0.14.0. However, I am still certain that the changes I made will eventually lead to an improvement, I just need Fred to use them correctly.

Some secondary conclusions:

• I ran two sets of 300 games for both 0.14.0 and 0.14.1 in order to get a feeling for the repeatability of the results. There is indeed a lot of variation in the results (esp. for Northerners) and an individual 50-game set against one faction might not be enough to draw solid conclusions. However, the overall result of 300 games of each trial is pretty clear.
• I think the fact that Fred does so well against Rebels has nothing to do with Fred, but with the fact that the default AI is not very good at playing Rebels.
• By contrast, Fred doing so badly again Drakes (so we didn’t just imagine that, it's real!) and, to a lesser extent against Knalgans, is likely a problem with Fred.
• Interestingly, the performance against Loyalists also got quite a bit worse in 0.14.1.
• Overall, I am not unhappy with a 73% win rate against an opponent with 60% more gold, even if it's the default AI.

I'll make sure to run these tests occasionally to get a feeling for whether I am on the right track with things. From the next version on, I will also include the table in the first post of the thread.

[name]

[questionable feedback]

My suspicion is that Fred does less well in this version for two specific reasons.

The first one is he seems noticeably more aggressive, attacking sooner and more often and retreating a less dramatic distance out of harm's way to preserve his forces. Previous version Fred would do just about anything to keep his underlings alive until their numbers reached a horde and the time of day was favorable. This may be the best strategy Fred could ever use. If you know you are against a superior intellect, for example if you are an AI against a Human player, your best chance in wesnoth is usually to hang back defensively and let the enemy make the first move, unless you have an even greater advantage in numbers and time of day than you would need for launching an attack on an equally skilled opponent.

The second one is he maybe masses more forces in the center valley than he did before (I may remember incorrectly though). This tends to be a waste because there is only one village to take, a river to cross and the enemy castle nearby with constant reinforcements. The east and west valleys are much higher priorities for both attack and defense.

[/questionable feedback]

By the way, is it a bad idea to fight one version of an AI against an earlier version of itself? Like Fred's 0.14.1 dueling against 0.14.0 or against Ron? Also, would it make sense to release the current and previous versions of an AI together with each update, for side-by-side testing?

You might want to start giving Fred a little bit more gold than yourself and see how that goes.

Well here's a replay where he was given +18 income. "What can men do against such reckless hate?"

[mattsc]

Not questionable feedback at all!

My suspicion is that Fred does less well in this version for two specific reasons.

The first one is he seems noticeably more aggressive,
[...]

I think that is absolutely true and I will pick up with this one as soon as I a get back to Fred (I'm doing some other things for a few days, since I have spent almost all my Wesnoth time on Fred for a couple months now). The main change in 0.14.1 that I keep alluding to is that the attack/counter attack calculation is much more accurate now. So that cannot be a bad thing. What I don't know is whether I need to readjust some of the weighting parameters (because they are still optimized for the previous, not-as-accurate method), or whether I have introduced one or more bugs. I do know where to start looking though, so I am hopeful.

The second one is he maybe masses more forces in the center valley than he did before (I may remember incorrectly though). This tends to be a waste because there is only one village to take, a river to cross and the enemy castle nearby with constant reinforcements. The east and west valleys are much higher priorities for both attack and defense.

Hmm, that is interesting. I have not done anything to the code that would actively cause this, but it might be a side effect of one of the other changes. And in general, I do know that the way how Fred distributes units into the three valleys is far from ideal. It is on my list of things to look into, although not as high a priority as the previous problem.

By the way, is it a bad idea to fight one version of an AI against an earlier version of itself? Like Fred's 0.14.1 dueling against 0.14.0 or against Ron? Also, would it make sense to release the current and previous versions of an AI together with each update, for side-by-side testing?

On the contrary, that's a great idea. Fred vs. Ron should already be doable simply by selecting them in the MP menus -- although if I recall correctly, there was some bug "recently" that prevented that from working. I'll have to look into that. We used to do a lot of Fred vs. Ron matches in the "old days" and Ron usually doesn't stand a chance, so this might not be the most interesting test.

Now, Fred vs. previous version Fred, that's a very interesting idea, but it's also not trivial to do. Among other things, it requires Fred being able to play Side 2, so it's not going to happen right away. I like the idea though, so I'll add it to "the List".

You might want to start giving Fred a little bit more gold than yourself and see how that goes.

Well here's a replay where he was given +18 income. "What can men do against such reckless hate?"

Woohoo! But +18 income is not "a little" more gold, of course.

As always, thanks for the feedback and the replay!

[Horus2]

Hi, wesnoth veteral signing in. I have seen its development from the beginning and to be honest, this Fred AI is the best thing happened to wesnoth in the past 2 years, so i'm glad the project is still moving. Due to my very specific circumstances, i cannot really be a part of the online community, but testing this bot offline is not off the table. What makes me even more interested is that i probably will be involved in making an AI for another game anyway, so i may as well start to learn about their ways now.

I will send you my first impressions soon.

[mattsc]

Hi Horus2: thank you (and I am not sure if I would go that far myself, but the compliment is much appreciated!)

If you (or anybody else) want to test Fred right now and have not already checked out the previous version, you might want to get v0.14.0 from here instead of using the current version from the add-ons server (0.14.1).

As we discussed in this thread, 0.14.1 plays significantly worse than 0.14.0, but I don't want to revert back to the previous version because, as I have said, I am convinced that the changes I made really are improvements and are just not being used correctly by the current version. That will, I hope, be fixed in v0.14.2, but those are not quick fixes, so it might be a while until that version comes out.

Looking forward to your comments and good luck with the AI for your other game!

[nelson]

Hey mattsc, it's great to see that you're back!

I've been away for quite some time myself. Frankly I've been depressed by the state of the Wesnoth Ladder (there's like 25% of the activity that it used to have at its peak) and frustrated by how long it takes to play competitive games (maybe 2-3 hours for an evenly matched game, 1 hour if it's a stomp). I've been devoting my time to Dota 2 instead, where a competitive game takes 1.5 hours max, half an hour for a stomp. I posted in the subreddit about this a while back https://www.reddit.com/r/wesnoth/commen ... _too_long/ but received minimal feedback.

At any rate, after seeing the "Wesnoth needs your help" post a few months ago and seeing that you've returned to the game, maybe it's time for me to come back and do what I can to help. I'll try to hang out in the IRC channels again, and you can feel free to message me if you could use my help. Right now I'm just taking the first step of downloading and installing Wesnoth again

[mattsc]

Hey nelson, great to hear from you! I'm traveling at the moment with limited Internet access, so this is just a brief hello. I'll try to catch you on irc when I'm back in a week or so.

Just a few quick PSs:
1. I've not really been away from Wesnoth, only from Fred while working on other things (but I do have less time these days than I used to).
2. The time commitment needed for MP games is the main reason why I pretty much exclusively play SP.
3. I've made a bit of progress on the issues discussed since the release of 0.14.1, but not enough yet to justify another release.

TTYL!

[mattsc]

It's been a while, maybe I should give a brief update... I am working on it pretty continuously, but it's slow progress because I don't have as much time for it as I would like at the moment and a lot of the changes are not quite trivial (for me, at least) and I don't always know how to go about them. So they are both taking a lot of time and involve much trial and error.

Current status: the reason why Fred played worse in v0.14.1 than in 0.14.0 was that I had made the attack outcome calculation much more accurate than it was before. While that should result in better performance in the end, the problem was that the overall evaluation procedure was optimized for the approximate method used before. Also, I've found a few subtle but, in some situations, consequential bugs in the new code. As of a couple weeks ago, I seem to have recovered the 0.14.0 performance. Here are some recent stats of games vs. the default AI with 60% more resources than Fred:

Code: Select all

Fred's gold: 100
Enemy gold : 160
300 games total per trial, 50 games against each faction.
4 trials (1200 games total) for v0.14.0 and v0.14.1.

             v0.14.0                v0.14.1                 v0.14.1+dev
                                                            28 Oct  2 Nov   5 Nov
#/faction    200                    200                     50      50      50

Drakes       51% (46,54,42,62 20)   42% (28,46,56,36 28)    32%     48% x3  56%
Knalgans     76% (68,72,84,78 16)   63% (64,58,70,60 12)    74%     66%     70%
Loyalists    79% (76,84,86,70 16)   59% (60,56,60,58  4)    62%     86%     82%
Northerners  68% (82,60,62,66 22)   57% (54,60,52,60  8)    60%     60%     60%
Rebels       84% (82,88,86,78 10)   80% (84,84,80,72 12)    88%     94%     90%
Undead       85% (86,84,78,90 12)   71% (78,74,64,68 14)    84%     78%     90%

Total %      74% (73,74,73,74  1)   62% (61,63,64,59  5)    67%     72%     75%
Wins/set     (220,221,219,222  3)   (184,189,191,177 14)    200     216     224
Total #      882/1200               741/1200

Values of type "85% (86,84,78,90 12)" mean that there were 4 trials of 50 games against each faction,
with an average winning percentage of 85%, ranging from 78% to 90%, which is a spread of 12%.

So it looks like the Nov 2 and 5 versions do about as well as v0.14.0 did. I will nevertheless not release a new version right now, as there are still too many known and obvious problems, and there is no significant improvement over v0.14.0 yet. The limiting factor now is not attacks any more (although I still have a big todo list for those too), but defensive unit positioning. That's where I think the biggest improvement can be gained at the moment, so that's what I am currently working on.

If anybody wants to know what has been going on recently (or if you want to check whether development has stalled), you can always check the commit history of the AI-demos repository.

[sacredceltic]

Here is my twopence

[mattsc]

Here is my twopence

Thanks for the replay.

[name]

It is not surprising that he is stronger against RCA's Rebels and Undead than Northerners and Drakes, since RCA doesn't believe in defense. But it is interesting how much better; a solid 50%. Makes me curious about the distant future, when Fred can play against older versions of himself, to see how these more defensive play dependent factions hold up then.

[mattsc]

It is not surprising that he is stronger against RCA's Rebels and Undead than Northerners and Drakes.

Indeed. I should look up the original quote sometime, but I have been told by several people that Dave specifically designed the Northerners to make them "easy" to play by the AI. Just for kicks, I ran 100 games of the default AI playing both sides, with 100 gold each, of Northerners vs. Rebels on the Freelands map. The Northerners won 68 of those.

Btw, I have said that in the other thread, but not here yet. The more I work on AIs, the more I appreciate how good the default AI actually is. In spite of its shortcomings and "single mindedness", it is really amazing as a general AI that works on all maps.

Makes me curious about the distant future, when Fred can play against older versions of himself, to see how these more defensive play dependent factions hold up then.

Will be interesting but yes, it is way in the future. On the other hand, I have changed my mind on the next release and will probably publish one sooner rather than later. There's really no point in keeping a sub-par version as the latest release on the server. It's still going to be a couple weeks though, as I've made a real mess of the overall strategy layer that needs to be cleaned up again first. Either that or roll it back to v0.14.0.

[mattsc]

Fred (AI-demos) v0.14.2 is on the 1.12 add-ons server. This is an intermediate release with tons of small changes that fix bugs and build on top of the changes begun in the previous version. As a result, v0.14.2 restores and slightly surpasses the v0.14.0 performance (compared to the regression in v0.14.1) in games against the default AI:

Batch testing against default AI with 60% more gold than Fred:

Code: Select all

Fred's gold: 100
Enemy gold : 160

             v0.14.0                v0.14.1                 v0.14.2

#/faction    200 (4 sets of 50)     200 (4 sets of 50)      200 (4 sets of 50)

Drakes       51% (46,54,42,62 20)   42% (28,46,56,36 28)    56% (56,66,40,62 26)
Knalgans     76% (68,72,84,78 16)   63% (64,58,70,60 12)    82% (84,84,84,76  8)
Loyalists    79% (76,84,86,70 16)   59% (60,56,60,58  4)    84% (88,76,82,88 12)
Northerners  68% (82,60,62,66 22)   57% (54,60,52,60  8)    62% (70,56,64,56 14)
Rebels       84% (82,88,86,78 10)   80% (84,84,80,72 12)    86% (90,88,80,86 10)
Undead       85% (86,84,78,90 12)   71% (78,74,64,68 14)    87% (82,90,86,88  8)

Total %      74% (73,74,73,74  1)   62% (61,63,64,59  5)    76% (78,77,73,76)
Wins/set     (220,221,219,222  3)   (184,189,191,177 14)    (235,230,218,228 17)
Total #      882/1200               741/1200                911/1200

There are lots and lots more little changes to be made along those same lines, but all of those will only result in minor improvements at this point. Fred's performance is currently limited by the way how units are distributed and positioned on the map. Fixing this means completely redoing that part of Fred’s code. This will take a long time and, to be honest, I have no idea if I’ll be able to pull it off — but I am going to give it a shot. So I’ve decided to release Fred’s current state as v0.14.2, because at least it is not a regression compared to v.0.14.0. I will spend the next weeks/months working on the unit distribution problem and after that is done (or after I give up on it) I will come back to the other issues.

As such, this version might not be worth your time for significant testing, but if you want to play against Fred for fun, please use v0.14.2 as it fixes most of the problems introduced in v0.14.1. That said, I do, of course, always appreciate all feedback and replays. I’m just saying that my sole focus for the next release will be on addressing the issue above.

Note that the first post of this thread always shows Fred's current status. For the record, changes and progress with respect to the previous version are shown below.

Known bugs and issues of note introduced in v0.14.2

• Occasionally Fred does not move most or all units for a turn. I know, in principle, what causes this and thought I had it fixed, but I can see in the log output from the batch testing that it still happens from time to time. I need to catch this in the act in order to fix it, so if anybody come across this, please send me a replay of it.
• This version is slower than the previous ones. For the most part this just means Fred being a bit more sluggish from time to time, but it does sometimes cause very long wait times. One of my favorites was this one

  Code: Select all

  **** Fred 0.14.1+dev *******************************************************
  Beginning of Turn 19 (Dawn) stats	[ t = 128.302 ]
    Side 1: 23 Units (740 HP), 15/16 villages  (Orcish Crossbowman, 34 gold)
    Side 2: 1 Units (6 HP), 1/16 villages  (Fire Drake, 21 gold)
  ************************************************************************
  ====> Executing zone_control CA favorable_attacks: attack	[ t = 618.149, dt = 490.197 ]

  Fred had 23 units with 740 HP total, the enemy had one (its leader) with 6HP, and Fred took over 8 minutes (490 seconds) to think about his best move. Obviously I will fix that at some point, but I want to do the changes described above first as they will likely introduce new inefficiencies.
• Linked to the unit distribution issue mentioned above, Fred does not deal well with the enemy sending most units through the western part of the map. So if you want an easy victory, that’s the way to go in this version.

Previous and current known issues and future work (diff between v0.14.2 and v0.14.1)

Issues that will get worked on soon(ish):

• Moved to highest priority: Distribution of units between the three zones of the Freelands map, and in particular also re-distribution when the situation changes, is currently sub-ideal.
• New bug: Sometimes Fred does not move most or all units during a turn
• The order in which several AI units attack the same enemy is currently predetermined and then followed rigidly. Sometimes it is better to change the order or attack hexes of the units if things don't go as expected, or to abandon the remaining attacks altogether.
• In progress: Improve retreating of injured units, both when to retreat and where to
• New(ish): Protection of leader continues to be sub-ideal
• Bigger penalty for attacking from next to village
• Add preferred trapping of enemy leader when he's off keep.
• Add small bonus for attacking from/moving to keep hexes near enemy leader, to block him from moving there.
• When pulling units back to protect leader, prefer hexes between AI leader and enemies.
• If severely injured unit cannot run away, put up a last-stand fight
• If not all units planned in for an attack are needed (because the enemy is killed early), this might leave some of the attackers more exposed than planned

Issues that will probably get worked on sometime:

• Prefer attacks with fewer units, if expected outcome is similar to using more units
• Move injured units toward villages if those are out of reach
• Actively try to protect weak, valuable units
• Leader does not need to return to keep if there's not enough gold for recruiting (but he needs to be kept
• Refine current metrics of unit power and unit value
• Keep leader from wandering off if own keep hexes are blocked by enemy
• Well advanced: Continue refining how counter attack stats are calculated; current method has many issues; need to balance between accuracy and speed
• Enable trapping by means other than a unit on either side
• Enable Fred to play Side 2
• Enable Fred to play all factions
• Don't force fog to be turned off for player side
• Add more trash talk easter eggs
• Continue speeding up the code
• Clean up the code

Issues that might or might not ever get worked on: (because I don't have the time or patience or simply because I do not know how to do this)

• One of the things that Fred (or any AI, probably) has a really hard time with is coordinating different moves with each other. So he might block, or not block, an area that a later move then makes inaccessible to the enemy anyway. Or he does an (in principle good) attack that pulls units away from another area were they are needed. That's really hard to deal with for an AI and while I will continue to work on this, I don't know if I'll ever really solve that problem. [The state space of possible moves is simply too big in Wesnoth to evaluate all possible move combinations.]
• Enable Fred to play other maps

v0.14.2 complete changelog

Code: Select all

----- 0.14.2, 20 December 2015 -----

This release continues the refinements to Fred's evaluation functions that were
started in v0.14.1. It fixes bugs and builds on top of the changes begun in that
version to restore (and surpass) the v0.14.0 performance.

- Fred (Freelands AI for Northerners, Side 1):
  - Significant changes to the overall strategy layer, including:
    - Distribution of units into the different zones of the map
    - Force leader to return to keep if defensive actions are needed
    - Force recruiting to help protecting the leader
    - Move units out of the way for leader moving to keep and recruiting
  - Continued refinements to attack calculations, such as:
    - Several fixes of significant bugs introduced in v0.14.1
    - Combined attack and counter attack damage is used as rating
    - Corrected evaluation of level-up calculations in attack combinations (but
      not yet in attack / counter attack evaluations)
    - Use of non-linear rating functions
    - Disallow blocking of leader from all keep hexes by units used in attacks
    - Exclude enemy units from counter attacks if their chance to die too high
    - Prefer using fewer units if outcome is almost the same as with more units
    - Don't use too many units for favorable attacks
    - Limit acceptable risk in attacks by units without MP
    - Don't use leader bonus weighting on enemy leader
    - Lower the limit for aggression in attacks when having advantage
    - More stringent condition on when not to attack from next to a village
  - Improvements to holding and advancing evaluations:
    - Improved evaluation of where and when/if to hold
    - Add a "desparate hold" action
    - Add a secondary rating to force advancing/retreating when no acceptable
      hexes are found otherwise
    - Do not advance through the center zone, except when AI is clearly winning
    - Don't isolate individual units in enemy territory
    - Holding thresholds are now configurable and automatically adapt to the
      situation
  - Move-leader-to-keep CA:
    - Prevent leader from wandering toward enemy keep
    - Bug fix for rare crash
  - Enable partial moves by the zone_control CA
  - Unit dependent threshold for what constitutes 'good terrain'
  - Debug output: improvements to content and triggers
- Miscellaneous:
  - Remove Fast MAI testing code
  - ai_helper: new function movepartial_outofway_stopunit()

[virtue]

Gave 14.2 a try. Super impressed! Fred got +25 gold I'll try with more. I was a little surprised when Fred left a captured village undefended.