My own AI, where to start?

[SymbolicFrank]

Hi,

I recently discovered Wesnoth, and it's great. But I think the AI can use some serious improvements, which seems like a nice project. (The ultimate goal would be to have the AI determine the difficulty, instead of the quality and quantity of the resources. Very hard to do, I know )

So, I was wondering what the easiest way is, to disable the current AI and make my own.

It seems (from reading the wiki), that there are many levels, bits and pieces of AI scattered everywhere throughout the code and configuration files. Phew! Is it possible to have a single lua function somewhere to make all the moves, with some global storage and an interface for things like path calculations and unit / terrain values? And where can I find a description of the lua API?



From playing many RTS games, I have some ideas and observations about AI behavior in general, and some specific for RTS AI's. They tend to be aggressive, and default to sending all units produced to the enemy, as soon as they're ready.

The first thing can be good, as the best way to win tends to be a decapitating strike, as soon as possible. Harassing and taking economic resources (villages) is good as well. But "winning" is a twofold thing: it either requires fulfilling the conditions yourself, OR keeing the opponent from doing so.

In Wesnoth campaigns, where there is a strict turn limit and early finish bonus, an early strike and harassing are good, but after that the most important goal becomes keeping the enemy (player) from fulfilling his/her goals. Generally that means: turtle.

Another observation is the use of teams/battle groups, or rather the lack thereof: build a defensive force, and when it becomes larger than required, split it and try to take out wandering enemy groups. If you have fielded multiple of those, use all of them for a coordinated attack.

Also, when units become much better with experience, try and have the ones closest to leveling from each group give the finishing blow.



I think the main problem with most AI's is, that they try to do everything from the top level, and try to calculate all moves in advance. I want to take the opposite approach: a very light strategic level, some coordination on the tactical level, but most of the intelligence in the AI for the individual units, who are only interested in their own, direct surroundings.

Like: a terrain, opponents and goals analysis up front, some (one or two) very broad strategic goals (which can change) and mostly steered by recruiting the right kind of units, some officers (units with leadership, high damage, slow and/or healing) who try to fulfill those goals, and opportunistic soldiers (all the other units).

Those soldiers would roam around fully independent.

If they have a high mobility on the terrain and no enemy units would be present, they would scout and go for opportunistic kills and village captures. And trying to stay away from other allied units. But if they see a strong and fast enemy (force) approaching, they would revert to their generic soldier role.

Soldiers like to bunch together, and look for the closest officer that has the smallest escort. They try to protect that officer (and their comrades), by forming a defensive line and ganging up on enemies, and retreating/looking for healing when needed.

Officers (mages, healers, knights, etc) are the only units that actively try to execute the strategic goals, by gathering a force and going out to accomplish it. If there are more than a few, they try to bunch up as well, to limit the amount of independent groups.

The strategic level would then mostly consist of recruiting the right unit types, and changing the goals when required.


Anyway, that's the idea.

[SymbolicFrank]

Ok, let's forget about the coding for now (and I understand the need for scenario builders to influence the way the AI plays).

But what do you think about the plan? Might this result in a better AI, or does it sound pretty stupid?

And in either case, why?

[Speedbrain]

This might be why no one has responded yet.
And those with any related ability might be too busy to have seen this thread since you started it.

[SymbolicFrank]

Ok, I'll tackle those points.

I'm largely writing this in response to the number of people who have historically wanted to write a Wesnoth AI, as well as the number of students who are interested in developing an AI for Wesnoth as part of Summer of Code.

I have been programming just about anything for 29 years, in many different languages (I prefer Delphi, and I dislike C++), and I also design digital hardware. I think I do have a fairly good grasp about the subject matter.

Many people think that a very powerful AI for Wesnoth should be fairly easy. After all, computers can beat the world's best players in chess and backgammon, both of which are turned based games, so why not Wesnoth?

AI's are HARD. Their main problems are, that they have no spatial awareness and don't want to survive/win.

Wesnoth's flexibility hurts us

Wesnoth is very flexible. There are many different maps, of different sizes, and different units. Players can even add their own units. This makes it much more difficult to make a general AI.

Computers are very good at chess because chess is played on a relatively small board, that is always the same, and the pieces always start in the same position.
...

Definitely, if you want to calculate all possibilities in advance, then simply forget about it. It won't work, especially as, unlike chess, there is a serious random factor involved.

The computational complexity of Wesnoth is immense compared to board games such as chess, backgammon, shogi, and go.

Discrete analysis fails badly on Wesnoth because, though technically Wesnoth is a discrete game, there are so many positions that discrete analysis techniques fail.

So, don't use the brute force method, it won't work, come up with something better.

Fortunately, Wesnoth can be treated much like a continuous game, because many positions tend to be very similar to each other.

Exactly. Now start thinking in "positions" and their good and bad points.

Additionally, unlike discrete board games, it is not common that a very small wrong move in Wesnoth is disastrous.

That depends: yes, if every move counts. And they do, but most often, it's better for the AI to play to increase the amount of moves. Which you don't do by giving him a suicidal attitude.

There are alternatives, like the one I sketched.

Most traditional AI methods cannot be applied to Wesnoth, so it is necessary to use highly innovative solutions.

Exactly.


Actually, the main reason I want to do it, is because it's considered hard. Not impossible, just hard. A challenge.


Edit: posting such a wiki article discourages people to come up with something better or even respond to a new idea. Explain that it's hard, yes, but don't try to give the impression that it cannot be done.

[SymbolicFrank]

I would really want to hear all the ideas everyone has about how to improve the AI. I'll think about how to implement it as soon as one of the core developers responds about how to do it.

For that, we need a decent API. But we need to know the requirements first: what makes a good AI?

[Crab]

Hi,

hi

I recently discovered Wesnoth, and it's great. But I think the AI can use some serious improvements, which seems like a nice project. (The ultimate goal would be to have the AI determine the difficulty, instead of the quality and quantity of the resources. Very hard to do, I know )

it's good project indeed

So, I was wondering what the easiest way is, to disable the current AI and make my own.
It seems (from reading the wiki), that there are many levels, bits and pieces of AI scattered everywhere throughout the code and configuration files. Phew! Is it possible to have a single lua function somewhere to make all the moves, with some global storage and an interface for things like path calculations and unit / terrain values? And where can I find a description of the lua API?

take a look at that wiki page - http://wiki.wesnoth.org/Customizing_AI_in_Wesnoth_1.8
and http://wiki.wesnoth.org/AI_Module
you can write an 'ai config file which will include 1 part of the turn - a 'stage', backed up 'lua engine' and referencing external lua code. you can even mix lua/c++/formula_ai code in a single ai. See data/ai/scenarios/scenario-lua-ai.cfg for some examples of lua AI integration. Currently, lua AI is not complete, but it's usable - you can move/attack/recruit/recall and you can access all the great 'lua for wml' stuff, giving you access to the game state like units, teams, terrain.

You can ask questions here or at #wesnoth-dev IRC channel at freenode. I'm usually online in IRC during the 'day in europe', and I can answer all your questions about current code in src/ai and current problems and weak points of the Wesnoth AI.

[SymbolicFrank]

Thanks, Crab!

I'll look into it and see how far I'll get. I'll post here when I have something interesting.

[Crab]

ok. Let me know if you need some examples/information.

p.s. also check http://wiki.wesnoth.org/LuaWML page for 'lua support in wesnoth', in general - it all can be used from within lua ai [stage] or [candidate_action]

p.p.s: we have a python script ( utils/ai_test ) which allows to run multiple ai-vs-ai battles and store results to postgresql database - it can be used to test 'how good the ai A is against other ai B on predetermined maps, with all possible factions'

[SymbolicFrank]

Thanks for the encouragement!

I'll start my research this weekend, and post my observations as soon as they're ready.

[bassPenguin]

I have been working on an RTS AI research project at my university this Summer. We deal with complex, dynamic, simultaneous, real-time state spaces (more complex than Wesnoth's). We are developing an agent that does not rely on scripts or domain-specific unit types/spells, etc. Based on my experience so far, I think that machine learning techniques with Monty Carlo based planning could be effectively employed in the Wesnoth domain to generate dynamic scripts. There has been a lot of recent research in the field and some cool techniques have emerged. I would say it is definitely within grasp to create a better, more generalized Wesnoth AI. It would take a lot of work though.

I think I might look into this a little myself.

Good luck.