Improving multiplayer AI through the use of openings

[akratic]

Chess AI programs use a fixed opening playbook for the first few turns before serious interactions between the players has begun. I propose that this same idea could be applied to the Wesnoth AI in multiplayer, and that this would result in a significant improvement in the AI's strength at little development cost.

Currently at the beginning of a multiplayer game, the AI will recruit a mix of units, capture the villages *it can immediately see* and then stream its units at the opponent at whatever speed these units move. Imagine if instead, just like a real player, the AI spread its units out after different objectives like capturing side villages and key positions, and also recruited exactly the right mix to counter the faction it was playing against (if known).

I propose that this could actually be implemented fairly easily by capturing the replays of player vs player multiplayer matches. If a bank of player replays was collected (ideally automatically at a central repository at the end of each multiplayer match) then the AI could begin by searching this bank for a matching replay on the same map, using the same faction, and ideally against its opponent's faction. The AI could simply follow what the human player in a matching replay did *exactly* during the first few turns, in fact, until it encountered the enemy player in combat. If a proper replay did not yet exist, it could fall back on the existing behavior. It might also make sense to integrate this idea with the ladder, so that only winning replays from top players were used, or at least to prefer these.

One difficulty would be the random inclusion of the quick trait. A similar difficulty would be wanting to use replays that are exact matches except for having heroes with slightly different movement speeds. I'm not sure of an elegant way to handle slightly varying movement speeds, but I'm confident that this idea could succeed regardless.

I am new to the Wesnoth community, but I have been playing a lot of single-player and multi-player matches against the AI recently, and I believe this idea could significantly improve the multi-player AI. Thanks for considering it.

[Caphriel]

It's an interesting idea, and all observable games on the official server do in fact have their replays saved. I imagine it would only want to emulate the winning player, however, preferably the winning player whose luck was as bad as possible. I'm not sure how much this would help, however, because unlike chess, Wesnoth has no accepted opening sequences beyond maybe initial recruits. The player in Wesnoth has already committed significantly to some course of action before encountering the enemy, so anything the AI does has to be generalizable, and without knowing what plan the player it is emulating had in mind, it would probably fail miserably on contact with the enemy.

[Max]

even if the ai recruited what would be "exactly the right mix" doesn't mean it's a mix that would fit the ai best. just think of things like heal or backstab...

[Sapient]

I think some work has already been done in this area by DragonKing using the FormulaAI