1.5 request
Moderator: Forum Moderators
Re: 1.5 request
No, it doesn't do this, precisely because of the problems you describe. That is a big reason it's so weak.mowerpower wrote: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.Dave wrote: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.
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
- Posts: 250
- Joined: November 19th, 2007, 7:46 pm
- Location: One among the Fence
Re: 1.5 request
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.
Glory in Blood...Needs Programming Help!
If you have time, check out my ongoing serial story...
The Hidden: Secrets of the Future's Past
If you have time, check out my ongoing serial story...
The Hidden: Secrets of the Future's Past
-
- Posts: 41
- Joined: December 17th, 2007, 12:38 pm
- Location: Berlin, Alexanderplatz
Re: 1.5 request
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.Dave wrote:No, it doesn't do this, precisely because of the problems you describe. That is a big reason it's so weak.mowerpower wrote: 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.
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.
Re: 1.5 request
Did I miss something or did you provide no arguments for this funny conclusion what so ever?mowerpower wrote: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.
"If gameplay requires it, they can be made to live on Venus." -- scott
-
- Posts: 41
- Joined: December 17th, 2007, 12:38 pm
- Location: Berlin, Alexanderplatz
Re: 1.5 request
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).Soliton wrote:Did I miss something or did you provide no arguments for this funny conclusion what so ever?
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
Re: 1.5 request
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'.mowerpower wrote: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).Soliton wrote:Did I miss something or did you provide no arguments for this funny conclusion what so ever?
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
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
- Posts: 41
- Joined: December 17th, 2007, 12:38 pm
- Location: Berlin, Alexanderplatz
Re: 1.5 request
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 wrote: 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'.
Re: 1.5 request
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:mowerpower wrote: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 wrote: 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'.
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
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
- Posts: 41
- Joined: December 17th, 2007, 12:38 pm
- Location: Berlin, Alexanderplatz
Re: 1.5 request
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.Dave wrote: i.e. several orders of magnitude greater than the Go example. And this analysis ignores many of the complexities of Wesnoth, ...
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.
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 nontrivialDave wrote:...and the much greater difficulty in writing an eval() function for Wesnoth vs Go.
Re: 1.5 request
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.mowerpower wrote: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.Dave wrote: i.e. several orders of magnitude greater than the Go example. And this analysis ignores many of the complexities of Wesnoth, ...
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 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.mowerpower wrote: 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.
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.mowerpower wrote: 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
David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
-
- Posts: 41
- Joined: December 17th, 2007, 12:38 pm
- Location: Berlin, Alexanderplatz
Re: 1.5 request
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.Dave wrote: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).
Maybe so, but we know that Go is PSPACE-complete.Dave wrote: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.mowerpower wrote: 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 understood Noyga's remarks in AI vs. Nightstalk/Ambush/Fog as saying the AI did just that. Apologies if I have been spreading misinformation.Dave wrote: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.mowerpower wrote: 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
Postscript: Sorry I ducked some of the points you made: short of time, will come back to them...
Re: 1.5 request
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. ^^
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. ^^
~Jami
Re: 1.5 request
where can i find this list?Velensk wrote: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.
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
- Posts: 81
- Joined: September 20th, 2007, 1:15 am
- Location: Where the shadows lie
Re: 1.5 request
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.
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.
I am of two minds; I shall be complete when I can bring them into harmony.
Re: 1.5 request
http://www.wesnoth.org/wiki/WritingYourOwnAIstupidjaguar wrote:If this information already has a place on Wesnoth, please refer me.
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.