AI based on Deep Learning

Discussion of all aspects of the game engine, including development of new and existing features.

Moderators: Forum Moderators, Developers

name
Posts: 336
Joined: January 6th, 2008, 3:32 am

Re: AI based on Deep Learning

Post by name » December 15th, 2017, 7:07 pm

Alarantalara wrote: The biggest practical issues I can see with any ideal Wesnoth AI (not just ML based) is the problem that units and maps can and do have arbitrary WML associated with them.
Why not make supporting custom units and maps a secondary priority though? If you had an AI that is much better than default AI at the basic multiplayer maps and multiplayer factions, that is a mighty improvement by itself.
Tad_Carlucci wrote: My point: just because something is feasible does not mean it's affordable.
What exactly is the something you are thinking of though? Is it an AI that plays to some degree better than other Wesnoth AIs or is it a perfect opponent that no human player can beat?

You do not have to have the resources or results of Deep Mind or OpenAI to improve a bit beyond Wesnoth Default AI, do you?

Tad_Carlucci
Developer
Posts: 289
Joined: April 24th, 2016, 4:18 pm

Re: AI based on Deep Learning

Post by Tad_Carlucci » December 15th, 2017, 10:53 pm

An AI is hard. Look at the work so far just handling simple games like chess and go. It's like, OK, we just figured out we can rub two sticks and make fire, so how about we build a hydrogen bomb? My opinion: all the hype about how smart AIs are is just that: hype. We're nowhere near Singularity and won't be for a long time. And the sort of AI which can walk up to a game like Wesnoth and just get it is far beyond that.
I forked real life and now I'm getting merge conflicts.

User avatar
Elder2
Posts: 352
Joined: July 11th, 2015, 2:13 pm

Re: AI based on Deep Learning

Post by Elder2 » December 15th, 2017, 11:09 pm

I would love to see such an ai, even though I do not believe it could surpass humans, especially considering varying maps. I think the only way for it to have any decent chance against a good human opponent is for it to play with humans for really a lot of games so only then it wold learn something. And I think even then basically there still would be tricks left, or situations, however you want to call it, it wouldn't know and you could use to outplay it. Or maybe you could come up with new ones to specifically counter its playstyle. Basically even if it could calculate the most likely outcome of a fight in one turn or 2, and even if it could do it properly (which I doubt would be possible, its complicated), even then if it got tricked in some way it wouldn't help it.

name
Posts: 336
Joined: January 6th, 2008, 3:32 am

Re: AI based on Deep Learning

Post by name » December 16th, 2017, 12:37 am

Tad_Carlucci wrote:An AI is hard. Look at the work so far just handling simple games like chess and go. It's like, OK, we just figured out we can rub two sticks and make fire, so how about we build a hydrogen bomb? My opinion: all the hype about how smart AIs are is just that: hype. We're nowhere near Singularity and won't be for a long time.
I agree that is all hype, but no one said anything about fusion bombs or a technological singularity in this thread about improving current Wesnoth AI. ;)
Tad_Carlucci wrote:And the sort of AI which can walk up to a game like Wesnoth and just get it is far beyond that.
It does not have to understand the whole game to be worthwhile, it only has to improve the state of the existing Wesnoth AI.
ElderofZion wrote:I would love to see such an ai, even though I do not believe it could surpass humans, especially considering varying maps.
Not all humans are equally skilled though and more competent AIs teach new players to be more decent at online play than less competent AIs.

Also, you can give additional income to an AI player to make it more of a match for an experienced human player. However, this also changes the nature of the game, as instead of two skilled players with equal forces, you have now a small skilled force against a zombie horde style opponent. A somewhat more intelligent AI will be able to provide the same level of challenge with somewhat fewer extra units. So even an experienced player receives an improved offline experience (such as when playing through a campaign).

User avatar
Sapient
Inactive Developer
Posts: 4445
Joined: November 26th, 2005, 7:41 am
Contact:

Re: AI based on Deep Learning

Post by Sapient » December 16th, 2017, 6:23 am

Here is a quote from milwac's updated idea on Dec 13, 2017: "The primary reward is of course leaderkills in N v N games"

Now, let's take a typical decision made in Wesnoth. One unit is moved from hex A to hex B, where B here may be dozens of different possibilities. That is not even considering whether or not it attacks. Now imagine the number of turns, decisions, and random chances that could happen between that one decision and the end of the game where a winner or loser is decided. It's truly astronomical. The relationship between that one decision and the end result of the game is going to be an extremely weak relationship (until maybe you get to a few decisions near the end of the game).

That is not to say that an AI based on Deep Learning is impossible, but the strategy outlined by milwac would be prohibitively costly. Having said that, the ability to run AIs against each other from the command line already exists (Try searching the forums for "nogui"). So if you want to prove me wrong by all means give it a try and I would love to see it.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."

User avatar
Pentarctagon
Forum Administrator
Posts: 3483
Joined: March 22nd, 2009, 10:50 pm
Location: Earth (occasionally)

Re: AI based on Deep Learning

Post by Pentarctagon » December 16th, 2017, 7:28 am

Sapient wrote:Here is a quote from milwac's updated idea on Dec 13, 2017: "The primary reward is of course leaderkills in N v N games"

Now, let's take a typical decision made in Wesnoth. One unit is moved from hex A to hex B, where B here may be dozens of different possibilities. That is not even considering whether or not it attacks. Now imagine the number of turns, decisions, and random chances that could happen between that one decision and the end of the game where a winner or loser is decided. It's truly astronomical. The relationship between that one decision and the end result of the game is going to be an extremely weak relationship (until maybe you get to a few decisions near the end of the game).

That is not to say that an AI based on Deep Learning is impossible, but the strategy outlined by milwac would be prohibitively costly. Having said that, the ability to run AIs against each other from the command line already exists (Try searching the forums for "nogui"). So if you want to prove me wrong by all means give it a try and I would love to see it.
Though given that leader kills are the primary goal, I assume there could also be weights given to secondary goals such as taking villages, killing regular units, not getting its own units killed, etc.
99 little bugs in the code, 99 little bugs
take one down, patch it around
-2,147,483,648 little bugs in the code

User avatar
Elder2
Posts: 352
Joined: July 11th, 2015, 2:13 pm

Re: AI based on Deep Learning

Post by Elder2 » December 16th, 2017, 9:13 am

@Cold_steel it would have to be a rather significant income advantage and if that is the case then I do not see much difference from standard wesnoth AI. Also why do you think it would enhance campaign experience? Exactly the opposite would happen, devs would have to rewrite campaign scenarios and many scenarios would also most likely become much longer, if you lower AI's gold yet make it significantly more intelligent it will take longer to defeat it than if it had more gold and was a standard AI.
I doknow that and I was referring to the best human players. Also I do not believe the AI cwould be able play like a human and thus it is doubtful whether it cold really do that, if we are referring to skills against human opponents. Though it probably could do that to a degree, but still matches with ai would be longer than they are now so what is the point.

User avatar
Sapient
Inactive Developer
Posts: 4445
Joined: November 26th, 2005, 7:41 am
Contact:

Re: AI based on Deep Learning

Post by Sapient » December 16th, 2017, 11:29 am

Pentarctagon wrote: Though given that leader kills are the primary goal, I assume there could also be weights given to secondary goals such as taking villages, killing regular units, not getting its own units killed, etc.
I'm not sure about that. If you are analyzing a replay, and judging whether a move made on turn 2 was a good move or not, is your "Primary" criterion for that evaluation really going to be based on the final outcome of the match? It seems like a poor approach.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."

User avatar
Pentarctagon
Forum Administrator
Posts: 3483
Joined: March 22nd, 2009, 10:50 pm
Location: Earth (occasionally)

Re: AI based on Deep Learning

Post by Pentarctagon » December 16th, 2017, 4:38 pm

Sapient wrote:
Pentarctagon wrote: Though given that leader kills are the primary goal, I assume there could also be weights given to secondary goals such as taking villages, killing regular units, not getting its own units killed, etc.
I'm not sure about that. If you are analyzing a replay, and judging whether a move made on turn 2 was a good move or not, is your "Primary" criterion for that evaluation really going to be based on the final outcome of the match? It seems like a poor approach.
I mean something like: you take a village on turn 2, then lose it on turn 7 along with the unit that took it. Depending on the unit, was gold gained or lost?

Every individual move might have a practically non-existent relationship to killing the leader, but particular actions like killing enemy units, leveling up your units, or taking villages would have a much stronger correlation.
99 little bugs in the code, 99 little bugs
take one down, patch it around
-2,147,483,648 little bugs in the code

name
Posts: 336
Joined: January 6th, 2008, 3:32 am

Re: AI based on Deep Learning

Post by name » December 16th, 2017, 5:18 pm

ElderofZion wrote:@Cold_steel it would have to be a rather significant income advantage and if that is the case then I do not see much difference from standard wesnoth AI.
It is much different or little different depending proportionately on how much better the AI ends up being versus standard AI.
ElderofZion wrote:devs would have to rewrite campaign scenarios and many scenarios would also most likely become much longer, if you lower AI's gold yet make it significantly more intelligent it will take longer to defeat it than if it had more gold and was a standard AI.
Rewriting a scenario to make it more dynamic is not a bad thing. If it takes longer to defeat (and this is undesirable) either reduce its gold or shorten the campaign by removing the least meaningful scenarios to compensate.
ElderofZion wrote: Also I do not believe the AI could be able play like a human and thus it is doubtful whether it could really do that, if we are referring to skills against human opponents.
From what I have seen/read, the best machine learning developed AI players do not necessarily play like the best human players. They deploy completely alien strategies that do not necessarily look effective to advanced human players at first, but are ultimately lethal to them. These same strategies might eventually have been developed by the human player community after hundreds more years of play.

This is because, while the AI is limited by having fairly simple (and "weak") intelligence, we are limited by the number of experiences we can have to learn from. It can run games against its own improving self, faster than we can play it or each other. And these AI versus AI games can be run on any number of machines at once, so it receives thousands, millions, billions of times more experiences even though it learns so much less than we do from each individual experience.

However, it useful to keep in mind that using this approach to get this quality of result is prohibitively expensive for all but the most popular games being attacked by AI divisions of major corporations with all the human intelligence and expensive computing hardware that comes with that. It might take another 10 to 20 years of computing power getting exponentially cheaper before such a thing as an unbeatable-by-humans Wesnoth AI is affordable.
ElderofZion wrote:Though it probably could do that to a degree, but still matches with ai would be longer than they are now so what is the point.
Playing against a human takes longer than playing against an AI. So what is the point of playing against a human?

User avatar
Elder2
Posts: 352
Joined: July 11th, 2015, 2:13 pm

Re: AI based on Deep Learning

Post by Elder2 » December 16th, 2017, 5:52 pm

"It is much different or little different depending proportionately on how much better the AI ends up being versus standard AI."
Yeah but I was rather referring to the necessary significant income advantage which I do believe would be necessary. in the end it is still fighting hordes of units.
"Rewriting a scenario to make it more dynamic is not a bad thing. If it takes longer to defeat (and this is undesirable) either reduce its gold or shorten the campaign by removing the least meaningful scenarios to compensate."
We already have a lot of dynamic scenarios in campaigns, what makes you think that a new deep learning ai would make the already present scenarios more dynamic? And about the second part I do not think it is so simple.
From what I have seen/read, the best machine learning developed AI players do not necessarily play like the best human players. They deploy completely alien strategies that do not necessarily look effective to advanced human players at first, but are ultimately lethal to them. These same strategies might eventually have been developed by the human player community after hundreds more years of play.
Really? What made you think that? I have heard about AlphaGo and AlphaZero and from what I have read and seen the strategies employed by these 2 ais do not differ much from already present strategies in the community, just that machines execute everything better.
This is because, while the AI is limited by having fairly simple (and "weak") intelligence, we are limited by the number of experiences we can have to learn from. It can run games against its own improving self, faster than we can play it or each other. And these AI versus AI games can be run on any number of machines at once, so it receives thousands, millions, billions of times more experiences even though it learns so much less than we do from each individual experience.
Yes, machines constructed to be the best at one single task usually are the the best at that one task. And yes a program can play millions of games against itself and will usually be better than players who played hundreds or thousands games, but there are still examples of games at which machines fail and humans are still better despite the incredible increase in computing power over the years. So there is absolutely no guarantee that a machine could surpass human at wesnoth.


However, it useful to keep in mind that using this approach to get this quality of result is prohibitively expensive for all but the most popular games being attacked by AI divisions of major corporations with all the human intelligence and expensive computing hardware that comes with that. It might take another 10 to 20 years of computing power getting exponentially cheaper before such a thing as an unbeatable-by-humans Wesnoth AI is affordable.
Maybe but still, there is no guarantee that an ai can surpass human especially in such non deterministic game as wesnoth as there are still games out there where despite efforts to create ais stronger than humans it hasn't yet been done.
"laying against a human takes longer than playing against an AI. So what is the point of playing against a human?"
Because humans can actually play well and like I said i do not believe even such a deep learning ai would be able to surpass humans. It is not as fun to slowly dismantle ai based on its rigid playstyle, like eg fred, and a deep learning ai would most likely have that too, i do not believe an ai can be liberated from this aspect of ai gameplay. Humans use varying strategies and this makes even playing the longer games with them fun, even though a game with a human need not necessarilly be longer than a game against ai.

name
Posts: 336
Joined: January 6th, 2008, 3:32 am

Re: AI based on Deep Learning

Post by name » December 16th, 2017, 7:24 pm

ElderofZion wrote: We already have a lot of dynamic scenarios in campaigns, what makes you think that a new deep learning ai would make the already present scenarios more dynamic?
Most campaign scenarios are set against Default AI and a turn limit. Mixing in scenarios where the player is opposed by a smarter AI would add variety at the very least. For example with HttT, if loyalist forces were commanded by a smarter AI even if northerners remained under control of the existing rush AI.
ElderofZion wrote: Really? What made you think that? I have heard about AlphaGo and AlphaZero and from what I have read and seen the strategies employed by these 2 ais do not differ much from already present strategies in the community, just that machines execute everything better.
The OpenAI bot for League of Legends. Go and Chess are ancient games, so we humans may have had enough experience collectively to develop the best possible strategies. But DotA and Wesnoth are quite recent games by comparison.
ElderofZion wrote:So there is absolutely no guarantee that a machine could surpass human at wesnoth.
That is correct. If it is going to happen, the first to fall will be a much more popular turn based strategy game of the same complexity as Wesnoth. Then, only many, many years later should you expect to see such a thing for Wesnoth itself because we have no money to develop it. ;)
ElderofZion wrote:Humans use varying strategies and this makes even playing the longer games with them fun, even though a game with a human need not necessarily be longer than a game against ai.
AIs can shift between (pre-developed) strategies as well and there are AIs for other games that do this to varying degrees. Once you have enough of these strategies and adequate rules for when to switch between them, you can conceivably have an AI with too many strategies combined with too unpredictable of strategy switching mechanisms to be boring through predictability.

User avatar
milwac
Posts: 27
Joined: April 9th, 2010, 11:40 am

Re: AI based on Deep Learning

Post by milwac » December 18th, 2017, 3:05 pm

Since a lot of replies have been made and most of them pertain to what is or what is not possible within the realm of AI algorithms today, I will try to answer them the best I can. But first, I would like to talk about some technicalities regarding the possible design of input features.
The biggest practical issues I can see with any ideal Wesnoth AI (not just ML based) is the problem that units and maps can and do have arbitrary WML associated with them. While adding some form of search (probably Monte Carlo given the ridiculous branching factor) can address these issues, the simulation is frustratingly expensive.
To look ahead a full turn needs a search depth of 20+ moves (10 units per player * 2 players) by about turn 3 and for some maps, eventually well over 100 (e.g. any 8+ player map) just to see what the next turn might look like.
Because turn schedules are also arbitrary as is map terrain by turn (Aethermaw), simulating to the next turn at some level is required. And unfortunately, the map on the next turn can be randomized (see multiplayer map Dark Forecast for one of the more dramatic examples, though it's also), so the ideal approach is to do full simulations into the next turn and not just a quick single check that just ends the turn and provides the next map state as additional input.
I agree. I defined an atomic move as just 1. A single hex movement by any unit OR 2. A recruit action OR 3. An attack from a single unit (all strikes from attacking and defending unit). Now, naturally, a turn would consist typically of a sequence of such moves. The game state may change (little to none, or drastically) after every atomic move. The first job of the AI is to optimize this very sequence of atomic moves. This means, perfecting play of a single turn, without looking further ahead at all.

Once the AI has successfully done this, we would notice a considerable strength in the AI gameplay now and then itself. Why do I say this? The typical mistakes that the default AI makes is in recruiting, attacking and movement. Indeed most games in Wesnoth are lost due to a single bad turn, where one should have ideally retreated but pushed too hard to attack and ended up losing after that one bad turn.The elements of ZoC and forming lines of units are part of a single turn. Moving scouts to the edges so that they remain undetected are also mostly single turn strategies. Now some may say, rushing all in, in the first turn, or pushing for an all out attack, which decides who wins or loses in a single turn, are good strategies. Well they can be good if you can win 90% of games like that against any general faction, otherwise it is just a general case of non determinism stemming from the fact that atomic attacks in Wesnoth are non-deterministic. A good strategy in Wesnoth IMO, should be one which always maximizes the chances of winning, and minimizes the chances of losing. This would, I believe, lead to an AI which believes in minimizing risk and maximizing opportunity, and would probably try to slowly outmaneuver an opponent rather than win in 4 turns.

To further improve the AI, it needs to learn even deeper strategical concepts like contesting central villages, attacking on flanks etc.. which will come after it has almost perfected playing a single turn well. Given that enumerating all unit descriptions, terrain types and map arrangements will result in an exploding array of inputs to train on, we may reduce the number of input features, as a first attempt, to make the problem somehow tractable. This could be a basic count of useful attributes like number of attacked and defended hexes, expected unit attack damage on both sides etc. If someone can tell me how this information can be extracted it'll be very helpful to visualize and examine first, using real replays. Please feel free to message me directly as well, if you think you can and are willing to help in this regard. Any pointers to links will also be helpful as I found the AI pages in the wiki somewhat overlapping and a bit confusing.

Now onto the general questions that many of you have raised.

Some are confused about the overall vision for having a strong AI. I don't know actually. This is what I want to find out. There was no need of building a chess AI or a Go AI, other than trying to find out what it can or can't do. Today chess is not dead, as previously thought of when AIs started defeating humans. In fact, on the contrary, chess has become richer due to lines and strategies discovered by chess engines, and the skills of human players all around the world have improved due to engines. AI essentially democratized expert chess knowledge, rather than it being restricted to a few elite master circles only. I am not thinking so far ahead about bundling a Wesnoth AI with the game, or how it might affect campaigns if done so (Although, I feel a very easy way of dealing with this is to introduce an extra level - 'very difficult' or something like that. I'm sure good players will not complain as some of them have, reportedly, finished campaigns on the highest difficulty setting without losing a single unit. That's what I find lacking in the game - campaigns are not challenging enough for good players). I just want to try this out as an interesting exercise.

That said, I do believe an AI capable of beating the best human players most of the time, is possible. Whether some of us can do it, or DeepMind needs to do it, I don't know :) One of you said that a Wesnoth AI can be decent enough only if it learnt from humans. This in fact, has been proven to be a slow and inefficient strategy in general. Reinforcement learning is what AlphaZero and AlphaGoZero used to beat the best human players. It is the technique by which an AI learns by playing against itself. This is a much faster way to learn anything, and leads to strategies that may have taken humans hundreds of years to develop, or worse, never seen at all. This is why it is not restricted to learning from only those moves that humans have at some point conceived. I think this is what we should use to develop a Wesnoth AI, rather than using human vs human replays.

Talking about chess a bit, a reinforcement learning AI like AlphaZero does not play like a typical AI (like DeepBlue or Stockfish) in the sense that it doesn't evaluate millions of moves by doing a brute force search. Instead it only requires a few thousand candidate moves as its evaluation function (the function that determines how good or bad a given position is) is much more accurate and complex as compared to the static evaluation functions of typical AIs. It also does not play like a human - who typically sacrifices some material for near immediate tactical advantages - instead it sacrifices material in order to gain long term positional advantages with better piece activity.

Another key feature of reinforcement learning is 'delayed reward'. When I said, killing the opponent's leader is the aim of an N v N game - the delayed reward in this case is the leader-kill. The algorithm is trained in such a way that all situations that can lead to a leader-kill are given high values and all situations that lead to such situations are also given high values and so on. Of course there can be good and bad moves in between and a match can be lost with a single good or bad move. Such patterns are accounted for by sampling a lot of possible directions probabilistically from a given state of the game and all those future states evaluated to determine whether the current state is a good state to be in, or not. As we know, Wesnoth has a a huge branching factor, and so how we deal with this is still up for discussion at this point. But the core idea is - yes, it is possible to assign intermediate rewards to any given state of the game and determine how good or bad it is for a said player.

mattsc
Posts: 1055
Joined: October 13th, 2010, 6:14 pm
Location: Wandering, mostly aimlessly

Re: AI based on Deep Learning

Post by mattsc » December 18th, 2017, 3:42 pm

milwac wrote:This could be a basic count of useful attributes like number of attacked and defended hexes, expected unit attack damage on both sides etc. If someone can tell me how this information can be extracted it'll be very helpful to visualize and examine first, using real replays.
I do not know how useful this is for your purpose, or if at all, but there is a machine-learning AI setup (recruiting only) in the AI-demos add-on. Check out the ml_utils folder and lua/ml_*.lua files. I was not involved in this effort at all so I'm afraid that I don't know anything about it, and the person doing this had to leave for real-life reasons before it was complete, but I believe the setup is functional. So maybe you can get something out of it ...

User avatar
milwac
Posts: 27
Joined: April 9th, 2010, 11:40 am

Re: AI based on Deep Learning

Post by milwac » December 18th, 2017, 9:43 pm

mattsc wrote:
milwac wrote:This could be a basic count of useful attributes like number of attacked and defended hexes, expected unit attack damage on both sides etc. If someone can tell me how this information can be extracted it'll be very helpful to visualize and examine first, using real replays.
I do not know how useful this is for your purpose, or if at all, but there is a machine-learning AI setup (recruiting only) in the AI-demos add-on. Check out the ml_utils folder and lua/ml_*.lua files. I was not involved in this effort at all so I'm afraid that I don't know anything about it, and the person doing this had to leave for real-life reasons before it was complete, but I believe the setup is functional. So maybe you can get something out of it ...
This is an excellent resource mattsc, thank you! While I look through this code, perhaps I can be a bit more specific about what I'm looking for right now, and ask : are there some simple functions that I can write in a script in Python or Lua to access in game properties like - side to move, villages each side has, types of units available, positions of units, reachable hexes for a unit etc.? I wish to visualize these properties while a game/replay is being played, and see which ones could be useful as input features, before I think about the AI code itself.

Post Reply