1.5 request

[Dave]

In all, if you count a unit move as one 'ply', this analysis goes very deep. It starts at the mage's move and attack, goes through the analysis of all the fighter moves, and then possible counter-attacks and so forth. Not to mention analyzing potential reinforcements from either side, and so forth.

Does the current AI (is it chesslike?) really branch on possible enemy moves when evaluating each of the unit moves that makes up the turn? That would be very interesting! I can't think, offhand, how I would go about constructing such an algorithm that wouldn't very wastefully reevalute the same enemy moves over and over again.

No, it doesn't do this, precisely because of the problems you describe. That is a big reason it's so weak.

[CarpeGuitarrem]

A good approach to AI would probably be working at "tactics", little mini-strategies that can be applied to multiple but similar situations on the battlefield. Things like evaluating how to protect a weakened unit with the surrounding units.

[mowerpower]

I can't think, offhand, how I would go about constructing such an algorithm that wouldn't very wastefully reevalute the same enemy moves over and over again.

No, it doesn't do this, precisely because of the problems you describe. That is a big reason it's so weak.

Now you have me thinking! A night's sleep has given me only one partly-formed idea that would only limit, not avoid, unit move reevaluation. We can call this the "Turn search composition problem": how to compose a search to determine a good set of moves for a sides turn out of searches for got moves for each of its units, with minimal reevaluation.

It does rather look like I was right to doubt that Wesnoth presents so much harder an AI problem than Go, though. Thinking more about the problem only illustrates how different the kinds of difficulty are in the two cases. A convincing case that one is harder than the other looks like it would be pretty technical.

[Soliton]

It does rather look like I was right to doubt that Wesnoth presents so much harder an AI problem than Go, though. Thinking more about the problem only illustrates how different the kinds of difficulty are in the two cases. A convincing case that one is harder than the other looks like it would be pretty technical.

Did I miss something or did you provide no arguments for this funny conclusion what so ever?

[mowerpower]

Did I miss something or did you provide no arguments for this funny conclusion what so ever?

Yesterday I made the argument [1] that go has much higher per-turn depth complexity than Wesnoth, and that high depth-complexity will generally dominate high breadth-complexity (which Wesnoth certainly has in spades).

Dave made the point that something like per-unit lookahead would be best for Wesnoth, which may allow the high breadth complexity of per-turn lookahead for Wesnoth to be broken up into smaller subproblems with lower breadth complexity, but with increased depth complexity.

That's an idea I find very interesting as a question about designing a game AI, but since it doesn't appear that anyone has yet figured out how to make it work, it's not really a storming counterargument.

[1]: http://www.wesnoth.org/forum/viewtopic. ... 95#p289195

[Dave]

Did I miss something or did you provide no arguments for this funny conclusion what so ever?

Yesterday I made the argument [1] that go has much higher per-turn depth complexity than Wesnoth, and that high depth-complexity will generally dominate high breadth-complexity (which Wesnoth certainly has in spades).

Dave made the point that something like per-unit lookahead would be best for Wesnoth, which may allow the high breadth complexity of per-turn lookahead for Wesnoth to be broken up into smaller subproblems with lower breadth complexity

Huh? I made the point that Wesnoth does have high depth complexity, since you essentially have to count a unit's movement as a 'ply'.

David

[mowerpower]

Huh? I made the point that Wesnoth does have high depth complexity, since you essentially have to count a unit's movement as a 'ply'.

Well, OK, but I don't see it that way. You can do a traditional per-turn analysis, so you don't have to count a unit's movement as ply: it is just that you can in principle do it this way.

[Dave]

Huh? I made the point that Wesnoth does have high depth complexity, since you essentially have to count a unit's movement as a 'ply'.

Well, OK, but I don't see it that way. You can do a traditional per-turn analysis, so you don't have to count a unit's movement as ply: it is just that you can in principle do it this way.

Doing a traditional per-turn analysis isn't completely possible. One unit's moves are dependent on another unit's battle outcomes, but even if we ignore that and do it like this, the branching factor is huge. Let's look at the complexity of Go, analyzing a breadth of 300, with a depth of 20 ply, with your B^D formula:

300^20 = 34867844010000000000000000000000000000000000000000

Now, in Wesnoth let's say each team has 10 units. These units each have 20 possible moves. I think both very typical, especially if you count different attacks, and different battle outcomes. This means the different movement possibilities are around 20^10. Now let's say you want to think just 4 ply ahead. (Not very deep -- I think a good Wesnoth player thinks at least 4 ply ahead) This is the number we're looking at:

(20^10)^4 = 10995116277760000000000000000000000000000000000000000

i.e. several orders of magnitude greater than the Go example. And this analysis ignores many of the complexities of Wesnoth, and the much greater difficulty in writing an eval() function for Wesnoth vs Go.

David

[mowerpower]

i.e. several orders of magnitude greater than the Go example. And this analysis ignores many of the complexities of Wesnoth, ...

Yes, I agree, and I'm pleased to see those numbers. But I take away from this calculation that the two look to live in something like the same complexity neighbourhood, and we need to look at the details of what pruning is possible to be able to say more.

I really don't mean to be obtuse here, and I am aware that my grasp of the details of Wesnoth AI design is fairly superficial, but my intuitions are not wholly unformed, and I have a gut feeling that there are certain features of go that make pruning hard, that don't seem to me to me to have similarly complex analogues in Wesnoth.

...and the much greater difficulty in writing an eval() function for Wesnoth vs Go.

Yes, indeed. And I should emphasise that I am impressed by some of what I have seen the Wesnoth AI do. I'm particularly impressed by how it uses information about opponents past moves to guess where hidden units might be. Making smart guesses about unknowns determined by an adversary is very much nontrivial

[Dave]

i.e. several orders of magnitude greater than the Go example. And this analysis ignores many of the complexities of Wesnoth, ...

Yes, I agree, and I'm pleased to see those numbers. But I take away from this calculation that the two look to live in something like the same complexity neighbourhood, and we need to look at the details of what pruning is possible to be able to say more.

Well, if we are talking about to play a decent game against a strong human, I would say if you take a fairly small Wesnoth map, perhaps in the region of 20x20 (same size as a Go board) and want a computer to just play on that map, with a certain set of factions, with no fog of war, it might be reasonably close.

If you're talking about the more general problem of making an AI play well on any Wesnoth map (or simply any map below a certain size such as 50x50) I would say that Wesnoth is substantially more complicated.

And if you're talking about solving Wesnoth (as in, making an AI that will always guarantee the highest % possible of a win) then I would say there is no comparison between that and solving Go. (though each is completely infeasible to solve with current technology).

I have a gut feeling that there are certain features of go that make pruning hard, that don't seem to me to me to have similarly complex analogues in Wesnoth.

I think though that there are also certain features of Wesnoth which can also make pruning hard. Additionally, I think writing an eval() function for Wesnoth is significantly more complicated than Go.

I'm particularly impressed by how it uses information about opponents past moves to guess where hidden units might be. Making smart guesses about unknowns determined by an adversary is very much nontrivial

Huh? The Wesnoth AI doesn't use information about opponent's past moves at all, least of all to make guesses about where hidden (ambushing?) units are.

David

[mowerpower]

Well, if we are talking about to play a decent game against a strong human, I would say if you take a fairly small Wesnoth map, perhaps in the region of 20x20 (same size as a Go board) and want a computer to just play on that map, with a certain set of factions, with no fog of war, it might be reasonably close.

If you're talking about the more general problem of making an AI play well on any Wesnoth map (or simply any map below a certain size such as 50x50) I would say that Wesnoth is substantially more complicated.

And if you're talking about solving Wesnoth (as in, making an AI that will always guarantee the highest % possible of a win) then I would say there is no comparison between that and solving Go. (though each is completely infeasible to solve with current technology).

Most humans play Go on 19x19 boards, but the rules are perfectly scaleable, and AI researchers are generally interested in scale-independent AIs, just as we are for Wesnoth.

I have a gut feeling that there are certain features of go that make pruning hard, that don't seem to me to me to have similarly complex analogues in Wesnoth.

I think though that there are also certain features of Wesnoth which can also make pruning hard. Additionally, I think writing an eval() function for Wesnoth is significantly more complicated than Go.

Maybe so, but we know that Go is PSPACE-complete.

I'm particularly impressed by how it uses information about opponents past moves to guess where hidden units might be. Making smart guesses about unknowns determined by an adversary is very much nontrivial

Huh? The Wesnoth AI doesn't use information about opponent's past moves at all, least of all to make guesses about where hidden (ambushing?) units are.

I understood Noyga's remarks in AI vs. Nightstalk/Ambush/Fog as saying the AI did just that. Apologies if I have been spreading misinformation.

Postscript: Sorry I ducked some of the points you made: short of time, will come back to them...

[Jami]

One thing about AI development that has always bugged me: why are we having the AI consider risks and tactics differently than we play?

Obviously, every player has a differing method on how they think (or don't think) though a turn. However I seriously doubt that many players, even the average or good ones, consider every single option available to them for every unit when preparing a play that spans several turns.

Rather, most players tend to be more goal-oriented. Weather it be 'move scouts to steal free villages' or 'conservative attack on a mixed for' or even 'Force though a line of fighters to kill a valuable weakened unit'.

I wonder if we haven't been trying the wrong solution, trying to make a technically perfect AI rather than an all-around good tactical AI.

Unfortunately, I do not have enough experience with python to consider making an AI. However, I think that a significant portion of the wesnoth player base would agree with my analysis that a technically perfect but tactically poor AI will lose over 90% of the time to a technically average but tactically sound player.

But, I'm just an artist and dabbling WML jockey, pay no attention to me. ^^

[Max]

I've seen lists of changes that are planned for 1.5. One thing that I would appreciate if you spent some effort working on during the 1.5 development is the AI.

where can i find this list?

i'm only playing campaigns, so this maybe doesn't apply to multiplayer:

just a thought: create an ai that focuses on outperforming the player in terms of ressources. try to capture as many villages as possible, don't risk attacks. recruit whenever possible.
isn't it likely that such an ai would perform better against human players on most maps?

but i guess it would be quite a boring experience...

gameplay should be fun - ai should take this into account
it should be challenging - doesn't matter to me if this is only accomplished be assigning more resources to the computer
ai should not make your opponent look dumb

maybe we should focus on the last part?

[stupidjaguar]

I am impressed that an AI that evaluates quickly enough to not cause a lag exists at all, considering that Wesnoth's gameplay borders on a chaotic system... there is randomness, and as Dave said, small errors lead to disastrous results.

I'm not that spectacular of a program writer, so wouldn't it be beneficial to post something that explained how the AI processes things? For example, (this is no comparison but it's what I thought of), my calculator came with a manual that for some complex functions, would explain which expressions were simplified first, and to what extent so that they don't become numbers, and whether they remain as variables or not, etc. I think that some sort of documentation on how the AI handles its task would be a better springboard for ideas from non- or amateur programmers like me.

If this information already has a place on Wesnoth, please refer me.

[Max]

If this information already has a place on Wesnoth, please refer me.

http://www.wesnoth.org/wiki/WritingYourOwnAI

it would really be nice to implement an experimental chess-like approach. e.g. just focusing (once only for each turn) on one 5x5 square with the most units.