Thanks togelius for the survey of the current state of the art around GVGAI! It will be interesting to see how adversarial methods influence future game design. Is a perfectly "instinctual" game possible? One that can never be beaten by any machine but that even a two-year old can master immediately?
Great article and great paper. Similar set of questions that get asked as part of AutoML, including the idea of hyper-heuristics, but in the AI community instead of data science. Thanks for the insights.
Glad you submitted this as I've needed an update of game AI field. A bit different than it was in my day but still shows what I argued all along: hybrid methods will be the best. Far game generation, I agree that generating many new, unpredictable experiences for the algorithm is ideal. I also agree it's within computational reach. Doesn't necessarily take AI, though.
For instance, much of that could be done with declarative, dynamic programming with templates, aspects, or constraint solvers. Idea being you create objects with relationships, attributes, and constraints. Let's look at an item object. It might have physical properties such as shape, size, movement speed, acceleration speed, ability to phase in/out, invisibility, and area of effect. It might have reactive properties where any of that changes in a specific way upon physical interaction, game event, or global setting. It might have effects on players that changing any existing attribute's value, remove one, or add one. It might cause a pre-registered event in game or for player with specific or random values input. Any of this can be programed using available languages as taking inputs, performing a computation on them, and producing output. Declarative aspect means that, after each is created with constraints or types, inference algorithms (even if-then's if you're masochist) can produce an imperative implementation that lines them all up properly for an actual game.
I'm not sure what the difficulty will be to do such things for an entire game rather than one item. However, one item on a map interacting with global & one, player's state trying to do all of the above might make a nice testbed. Then a number of items. Then a number of players. Whatever method works easily to solve it and generate efficient code gets used when approach is expanded to apply a similar range of attributes to player, map, NPC's, or even passage of time itself.
Just some thoughts on that. Haven't read your papers about specific algorithms yet. Did download Panorama for later reading. So, is anything close to what I described for generating a game engine from descriptions of parts in a way I described items? I think that, once enough stuff was loaded in, would generate a combinatorial explosion like wannabe AI's have never seen (and couldn't cheat easily).
Glad you liked it! We have done some work on trying to generate complete games - an overview of it can be found in this book chapter:
http://pcgbook.com/wp-content/uploads/chapter06.pdf
The most similar to what you describe is probably the ASP approach to game generation.
Thanks for link anyway. Yeah, it's a subset of my approach but a good one for clear intro to subject. As they were describing it, my mind drifted back to attempts at automated programming. I've seen recent work under banner program synthesis. In any case, I was thinking how they specified facts & constraints to force generation of results could be applied to software-rewriting. You start with unsafe code expressed with certain meaning/semantics, extract those as abstract rules, and then use them + safety heuristics to synthesize equivalent program that's safe.
While interesting, this research is not on the path to "true" artificial intelligence. It may solve playing a majority of video games given enough effort, but that is not the author's stated goal. Why do I think this?
The representations of the various algorithms are not unified. The answer to the question "what algorithm lies halfway between JinJerry and YOLOBOT" is difficult to answer. This is because they are discrete solvers who's implementations cannot be seamlessly blended. It is only at the level of their decision outputs that they share a common language.
The strength of natural intelligence derive partly from the fact that all strategies are implemented using the same components. Strategies can be described as sparse activation patterns of a neural substrate. Any strategy can be added to, subtracted from, or otherwise combined with another because the activations have a common representation language. The choice is never "either/or" for natural intelligence but "how much of which?"
This problem is also found in the meta-selection problem. The decision tree used to choose a component algorithm (even if applied repeatedly throughout the course of a game) doesn't allow for strategic blending, and itself is not implemented in a language common to the strategies.
In contrast, biological strategies are selected by competition between signals from many lower level systems and top down control and predictions. Ultimately a decision such as "fight or flight" comes down to how strongly a sparse set of neurons if firing and which motor paths are suppressed and which are activated. Because both the strategies and the evaluation of those strategies are implemented in a common substrate, you can blend, adapt, compare and update all aspects of the system. This is crucial to the adaptability and speed of natural intelligence.
Edit: I should note I am in full agreement with the author that simulated environments (of which video games are an example) are going to be essential for the creation of "true" AI. My comments relate specifically to the line of inquiry in the papers described.
Why do you think human cognitive processes don't resemble "discrete solvers who's implementations cannot be seamlessly blended"? Humans often get 'caught half-way' between a fight-or-flight response and a calm, analytical solution to a problem, and end up doing nothing. There's no strategy-blending there.
Humans can learn blended strategies by practice, but by doing so they're neuroplastically creating a single new blended-strategy strategy (which can poke at subgraphs of its component strategies' synapses), rather than simultaneously activating two strategies. You can learn to play a game that combines Tetris and a platformer (e.g. Wario's Woods)—and you'll become skilled at this faster if you've played both Tetris and platformers before—but learning this skill won't help you at all in becoming better at multitasking two separate, concurrently-running games of Tetris and a platformer. The synthesized strategy is its own concrete node, not an enhancement of the original nodes to enable efficient blending.
---
ETA: I suppose that it might be that "poking at subgraphs" thing that you're getting at, though? When a human learns a game, it gets better at playing all games, because there are individual "subroutines" that can be retried and, if successful, reused to accelerate the learning of other games.
Adding this feature to a GGP model wouldn't require "blending" (i.e. fluent instantaneous synthesis of strategy-components), but it would achieve a similar gain in performance. Programming the GGP algorithm to factor the decision-algorithm implementations it generates into hierarchies of small, modular black-box implementations, rather than large, monolithic black-box implementations, would get you a gradually-building "library of functions" that the GGP algorithm could attempt to "slot in" in new algorithms as it's synthesizing them.
I agree with your premise that the answer to "what algorithm lies halfway between JinJerry and YOLOBOT" is difficult to ascertain but I have heard of zero effort at trying to answer such a question.
In the end I could see a scenario where all strategy algorithms are ran in parallel with some understanding of the number of turns required for each strategy choice to provide payoff. That net can then weigh the choices and choose the relevant strategy algorithm for a period of time until it deems changing strategy algorithms is appropriate.
Things can become even blurrier if the net can choose components from multiple algorithms (depending on the game and the strategy). There are a few whole directions I'd want to go with this work if I were pursuing it.
This is a great post. (EDIT: Great Blog all around!). The grid of how different algorithms perform is particularly nice. I would love to see how that grid with new algorithms (specifically those new algorithms that make use of multiple algorithms).
Also, the name hyper-heuristics sounds like a recently made up term to stand out in search queries. The more long established name for it has been meta-heuristics (which is included as a keyword in the paper linked as "hyper-heuristics"). Meta because they are heuristics of algorithm selection rather than heuristics of solving a specific problem and heuristics because, as iandanforth mentioned, this is not a low dimension continuous differentiable problem space that lends itself to an optimal solution.
The difference between meta-heuristics and hyper-heuristics is that the former is a much broader concept, including such things as genetic algorithms. Hyper-heuristics is specifically about selecting among heuristics, which excludes e.g. evolutionary algorithms. Graham Kendall, one of the inventors of the concept, explains that they would have called it meta-heuristics if that name was not already taken.
... so hyper heuristics is meta-heuristics except leaving out one of your most promising options -- genetic algorithms? Or just refusing to use that at the meta stage? The difference still seems dubious. Your paper with the grid includes genetic algorithms to select from, so I guess it is not using GA at the meta level. Hyper as in a hypercube selection space of options? Maybe not because you use a decision tree for selection. It seems like the field could benefit from a regularization of terms. I still don't see what separates it from meta heuristics except for a name the limitations don't seem established. It seems hyper-heuristics is to meta-heuristics like the cloud is to network computing. Market speak does change -- not much you can do about that. The terminology is a nitpick -- fascinating papers.
Meta-heuristics as conceptualized by many (most?) does not include selection among algorithms. Hyper-heuristics does. It's fine if some of the algorithms selected among are meta-heuristics. Yes, this is very confusing, and yes, better terminology is needed. In particular, we should probably stop using the term meta-heuristics, because it has too many incompatible meanings.
OT: I accidentally swipe left/right every time I'm on blogspot, taking me to the previous/next post. Maybe I'm just fat-fingering all around, but this is a horrible UX.
The source of data is a lot of simulations we ran ourselves. All of the games can be won or lost - there's also a score measure as well, but that was not used in producing that graphic.
So something like digdug being black means that no algorithm has progressed through all levels to completely beat the game? That seems like a high bar to set for a "win".
22 comments
[ 0.23 ms ] story [ 64.9 ms ] threadThanks togelius for the survey of the current state of the art around GVGAI! It will be interesting to see how adversarial methods influence future game design. Is a perfectly "instinctual" game possible? One that can never be beaten by any machine but that even a two-year old can master immediately?
For instance, much of that could be done with declarative, dynamic programming with templates, aspects, or constraint solvers. Idea being you create objects with relationships, attributes, and constraints. Let's look at an item object. It might have physical properties such as shape, size, movement speed, acceleration speed, ability to phase in/out, invisibility, and area of effect. It might have reactive properties where any of that changes in a specific way upon physical interaction, game event, or global setting. It might have effects on players that changing any existing attribute's value, remove one, or add one. It might cause a pre-registered event in game or for player with specific or random values input. Any of this can be programed using available languages as taking inputs, performing a computation on them, and producing output. Declarative aspect means that, after each is created with constraints or types, inference algorithms (even if-then's if you're masochist) can produce an imperative implementation that lines them all up properly for an actual game.
I'm not sure what the difficulty will be to do such things for an entire game rather than one item. However, one item on a map interacting with global & one, player's state trying to do all of the above might make a nice testbed. Then a number of items. Then a number of players. Whatever method works easily to solve it and generate efficient code gets used when approach is expanded to apply a similar range of attributes to player, map, NPC's, or even passage of time itself.
Just some thoughts on that. Haven't read your papers about specific algorithms yet. Did download Panorama for later reading. So, is anything close to what I described for generating a game engine from descriptions of parts in a way I described items? I think that, once enough stuff was loaded in, would generate a combinatorial explosion like wannabe AI's have never seen (and couldn't cheat easily).
http://pcgbook.com/wp-content/uploads/chapter08.pdf
Thanks for link anyway. Yeah, it's a subset of my approach but a good one for clear intro to subject. As they were describing it, my mind drifted back to attempts at automated programming. I've seen recent work under banner program synthesis. In any case, I was thinking how they specified facts & constraints to force generation of results could be applied to software-rewriting. You start with unsafe code expressed with certain meaning/semantics, extract those as abstract rules, and then use them + safety heuristics to synthesize equivalent program that's safe.
The representations of the various algorithms are not unified. The answer to the question "what algorithm lies halfway between JinJerry and YOLOBOT" is difficult to answer. This is because they are discrete solvers who's implementations cannot be seamlessly blended. It is only at the level of their decision outputs that they share a common language.
The strength of natural intelligence derive partly from the fact that all strategies are implemented using the same components. Strategies can be described as sparse activation patterns of a neural substrate. Any strategy can be added to, subtracted from, or otherwise combined with another because the activations have a common representation language. The choice is never "either/or" for natural intelligence but "how much of which?"
This problem is also found in the meta-selection problem. The decision tree used to choose a component algorithm (even if applied repeatedly throughout the course of a game) doesn't allow for strategic blending, and itself is not implemented in a language common to the strategies.
In contrast, biological strategies are selected by competition between signals from many lower level systems and top down control and predictions. Ultimately a decision such as "fight or flight" comes down to how strongly a sparse set of neurons if firing and which motor paths are suppressed and which are activated. Because both the strategies and the evaluation of those strategies are implemented in a common substrate, you can blend, adapt, compare and update all aspects of the system. This is crucial to the adaptability and speed of natural intelligence.
Edit: I should note I am in full agreement with the author that simulated environments (of which video games are an example) are going to be essential for the creation of "true" AI. My comments relate specifically to the line of inquiry in the papers described.
Humans can learn blended strategies by practice, but by doing so they're neuroplastically creating a single new blended-strategy strategy (which can poke at subgraphs of its component strategies' synapses), rather than simultaneously activating two strategies. You can learn to play a game that combines Tetris and a platformer (e.g. Wario's Woods)—and you'll become skilled at this faster if you've played both Tetris and platformers before—but learning this skill won't help you at all in becoming better at multitasking two separate, concurrently-running games of Tetris and a platformer. The synthesized strategy is its own concrete node, not an enhancement of the original nodes to enable efficient blending.
---
ETA: I suppose that it might be that "poking at subgraphs" thing that you're getting at, though? When a human learns a game, it gets better at playing all games, because there are individual "subroutines" that can be retried and, if successful, reused to accelerate the learning of other games.
Adding this feature to a GGP model wouldn't require "blending" (i.e. fluent instantaneous synthesis of strategy-components), but it would achieve a similar gain in performance. Programming the GGP algorithm to factor the decision-algorithm implementations it generates into hierarchies of small, modular black-box implementations, rather than large, monolithic black-box implementations, would get you a gradually-building "library of functions" that the GGP algorithm could attempt to "slot in" in new algorithms as it's synthesizing them.
In the end I could see a scenario where all strategy algorithms are ran in parallel with some understanding of the number of turns required for each strategy choice to provide payoff. That net can then weigh the choices and choose the relevant strategy algorithm for a period of time until it deems changing strategy algorithms is appropriate.
Things can become even blurrier if the net can choose components from multiple algorithms (depending on the game and the strategy). There are a few whole directions I'd want to go with this work if I were pursuing it.
Disclaimer: My PhD advisor was the originator of this idea.
https://en.wikipedia.org/wiki/General_video_game_playing
Also, the name hyper-heuristics sounds like a recently made up term to stand out in search queries. The more long established name for it has been meta-heuristics (which is included as a keyword in the paper linked as "hyper-heuristics"). Meta because they are heuristics of algorithm selection rather than heuristics of solving a specific problem and heuristics because, as iandanforth mentioned, this is not a low dimension continuous differentiable problem space that lends itself to an optimal solution.
The difference between meta-heuristics and hyper-heuristics is that the former is a much broader concept, including such things as genetic algorithms. Hyper-heuristics is specifically about selecting among heuristics, which excludes e.g. evolutionary algorithms. Graham Kendall, one of the inventors of the concept, explains that they would have called it meta-heuristics if that name was not already taken.
OT: I accidentally swipe left/right every time I'm on blogspot, taking me to the previous/next post. Maybe I'm just fat-fingering all around, but this is a horrible UX.
1) What is the source data for that plot?
2) You specify "lighter = better", but how are they normalized across games and algorithms? How is better and worse quantified to get a "lightness"?
Edit: Found #2 in the second paper. Still don't know what 25 wins is white and 0 wins is black means? How do you "win" some of these?
Two papers are here:
http://julian.togelius.com/Mendes2016HyperHeuristic.pdf
http://julian.togelius.com/Bontrager2016Matching.pdf
Togelius' work ignores a core paradigm, of which we are aware of the human brain; neuroplasticity.
If one of togelius' solvers fails, all bets are off, the artilect is lobotomized.
See deepmind's "self-encoding" work: http://www-personal.umich.edu/~reedscot/iclr_project.html