A* over a Bayesian Network.
https://en.wikipedia.org/wiki/A*_search_algorithm
Why Can a Machine Beat Mario but Not Pokemon?
11–20 of 76 posts
Re: Why Can a Machine Beat Mario but Not Pokemon?
#12A* over a Bayesian Network. https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/Bayesian_network
What would your admissable heuristic be?
Re: Why Can a Machine Beat Mario but Not Pokemon?
#13The complexity of Pokemon is much lower than the author implies. It's not really an open world game. There are lots of choke points where your branching factor is limited drops down to two, continue forward to the next trainer or go back and regroup. There is no issue regrouping in Pokemon, you always end up stronger. There is also very little punishment for pushing fowards and failing, you lose half your money and m…
All of the details you're referring to are way above the level of any machine that plays Mario. For SMB1 the branching factor is uncommonly low. Pokemon has an extremely high branching factor by comparison. This being measured at the level of controller inputs and memory content outputs. SMB1 can be beaten by applying random controller inputs, measuring the player's x value, and seeing what works. Yes, you do need to…
To be fair to the machine, a human wouldn't even be able to tell what game they're playing, let alone be able to finish it, if all he had to go on was the raw memory values in response to controller inputs. The fact that Mario can be beaten at all given such an incredible dearth of information is impressive.
RPGs and action adventure games like Pokemon or Zelda are too laden with human-specific cultural details: heroes, villains, a world, exploration, battle, progress.
Think of Zelda for example. The wooden sword is not even necessary until the final encounter with Gannon. This isn't even immediately obvious to a human player: he knows that the hero needs a sword to defeat the villain. These are all cultural details a human already knows before beginning to play the game. The machine, on the other hand, knows the sword only as a bit in memory that causes a different branch to be taken in response to pressing the A button; a branch that returns to the main loop very quickly without any other obvious indication of progress. Yes, if used at the right time with the right position and direction, thrusting Link's sword causes enemies' health values to decrease. But since there are multiple ways to kill every enemy in the game (except Gannon) the sword is a luxury until the end.
Re: Why Can a Machine Beat Mario but Not Pokemon?
#14A* over a Bayesian Network. https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/Bayesian_network
What would your admissable heuristic be?
Discover as much of the map as possible? Talk to as many NPCs as possible? Try to get as many different dialogues from NPCs as possible? (I assume that to get to the you won dialogue means you encounter more dialogues than if you cleverly lose.)
Re: Why Can a Machine Beat Mario but Not Pokemon?
#15A* over a Bayesian Network. https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/Bayesian_network
What would your admissable heuristic be?
I could go many ways with that but I guess it depends how much we assume about the a.i.
However, although the card game came out after the video game, I actually have thought about this pokemon a.i. a fair amount and I think its fair to same that the video game is in many ways a visualization of a card game and the traversing of the map isn't as critical as it seems.
We know that the video game can't be beat without collecting x amount of Pokemon, so my thoughts on which heuristic would be to start there before even worrying about the battle system. Consider how a game of starcraft works, is a pokemon battle system more advanced than starcraft a.i.? I don't think so but open to being convinced otherwise.
Re: Why Can a Machine Beat Mario but Not Pokemon?
#16I think the battling issue may be a hard one for AI to deal with alone, though not so much in terms of the main game. Remember, the main story is meant to be beatable by people who don't want to think very much and who don't really care about training their team beyond 'reach a certain level'. Hence in the main story, 'grind until you significantly outlevel the next opponent' would probably be an optimum strategy for…
Is the battle system much different than playing blackjack with your own deck?
Imagine a world where someone can buy and trade towards a deck with 90% aces going up a person with 80% aces.
Re: Why Can a Machine Beat Mario but Not Pokemon?
#17Earlier quoted context omitted.
What would your admissable heuristic be?
Discover as much of the map as possible? Talk to as many NPCs as possible? Try to get as many different dialogues from NPCs as possible? (I assume that to get to the you won dialogue means you encounter more dialogues than if you cleverly lose.)
With the bayesian mesh you could arbitrarily apply heuristics over what otherwise looks pretty similar to a simple coordinate map.
If you happen to die near a certain node you could add an ajacent node of "scary" or whatever. Reverse idea for nodes where you get free food and pokemon.
Re: Why Can a Machine Beat Mario but Not Pokemon?
#18I think the battling issue may be a hard one for AI to deal with alone, though not so much in terms of the main game. Remember, the main story is meant to be beatable by people who don't want to think very much and who don't really care about training their team beyond 'reach a certain level'. Hence in the main story, 'grind until you significantly outlevel the next opponent' would probably be an optimum strategy for…
Given the results obtained by the OpenAI in Dota[1] (with asymmetrical teams nonetheless) I am pretty confident RL could be used to train a pretty efficient pokemon pvp agent. From my experiences the nuances and mindgames/predictions in a pokemon battle are much simpler than those in a high level chess/go game.
I would say the model isn't as straightforward as the Mario or Sonic AI players, but is still achievable. Actually, I wish I had more time because this is definetly a project I would like to tackle.
Re: Why Can a Machine Beat Mario but Not Pokemon?
#19Buuut I thought we already have bots that beat Civilization by reading the instruction manual?
Re: Why Can a Machine Beat Mario but Not Pokemon?
#20I think the battling issue may be a hard one for AI to deal with alone, though not so much in terms of the main game. Remember, the main story is meant to be beatable by people who don't want to think very much and who don't really care about training their team beyond 'reach a certain level'. Hence in the main story, 'grind until you significantly outlevel the next opponent' would probably be an optimum strategy for…
I think one major difference between pvp games and games like mario/pokemon campaign is that in the former case, the machine is competing with a meat learning algorithm. That is, it doesn’t have to find a good enough solution to a static map, but best an alternative optimization strategy (powered by wetware) before it can reasonably claim success.
That, and ofc, games with a competitive scene come about because of their complexity: a pvp game is not expected to be “won” in the fashion that a single player game can be. In fact, ideally there would be no perfect/optimal play; merely optimal play given a particular meta, which should shift as the meta does (a near-optimal strategy is found, but as it becomes common, a normally weak but counter-strategy becomes more useful, in a perfect world this would be acyclic)