Is this language generic/mighty enough to be used for a generic game AI?
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.
I came up with the following idea:
The input is an array of N integers.
The genetic program consists of up to N ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.
The ASTs can be arbitrary complex and consist only of four arithmetic operators (+,-,*,/) and can operate on constants and fixed elements of the given array (no random access).
So for [N=3], we have 3 ASTs, for example:
a[0] = a[0] + 1
a[1] = a[0] + a[1]
a[2] = a[0] * 123 + a[1]
The N ASTs are executed one after another and this is repeated infinitely.
Now my question, is this system "mighty" enough (turing complete?) or will it fail to solve some kinds of problems common for an game AI?
artificial-intelligence abstract-syntax-tree evolutionary-algorithm genetic-programming turing-complete
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
add a comment |
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.
I came up with the following idea:
The input is an array of N integers.
The genetic program consists of up to N ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.
The ASTs can be arbitrary complex and consist only of four arithmetic operators (+,-,*,/) and can operate on constants and fixed elements of the given array (no random access).
So for [N=3], we have 3 ASTs, for example:
a[0] = a[0] + 1
a[1] = a[0] + a[1]
a[2] = a[0] * 123 + a[1]
The N ASTs are executed one after another and this is repeated infinitely.
Now my question, is this system "mighty" enough (turing complete?) or will it fail to solve some kinds of problems common for an game AI?
artificial-intelligence abstract-syntax-tree evolutionary-algorithm genetic-programming turing-complete
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
1
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39
add a comment |
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.
I came up with the following idea:
The input is an array of N integers.
The genetic program consists of up to N ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.
The ASTs can be arbitrary complex and consist only of four arithmetic operators (+,-,*,/) and can operate on constants and fixed elements of the given array (no random access).
So for [N=3], we have 3 ASTs, for example:
a[0] = a[0] + 1
a[1] = a[0] + a[1]
a[2] = a[0] * 123 + a[1]
The N ASTs are executed one after another and this is repeated infinitely.
Now my question, is this system "mighty" enough (turing complete?) or will it fail to solve some kinds of problems common for an game AI?
artificial-intelligence abstract-syntax-tree evolutionary-algorithm genetic-programming turing-complete
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.
I came up with the following idea:
The input is an array of N integers.
The genetic program consists of up to N ASTs, each of which takes input from some of the array elements and writes its output to a single specific array element.
The ASTs can be arbitrary complex and consist only of four arithmetic operators (+,-,*,/) and can operate on constants and fixed elements of the given array (no random access).
So for [N=3], we have 3 ASTs, for example:
a[0] = a[0] + 1
a[1] = a[0] + a[1]
a[2] = a[0] * 123 + a[1]
The N ASTs are executed one after another and this is repeated infinitely.
Now my question, is this system "mighty" enough (turing complete?) or will it fail to solve some kinds of problems common for an game AI?
artificial-intelligence abstract-syntax-tree evolutionary-algorithm genetic-programming turing-complete
artificial-intelligence abstract-syntax-tree evolutionary-algorithm genetic-programming turing-complete
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
edited Nov 4 '18 at 10:37
codymanix
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
asked Nov 3 '18 at 20:46
codymanixcodymanix
17.7k1475131
17.7k1475131
1
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39
add a comment |
1
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39
1
1
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39
add a comment |
2 Answers
2
active
oldest
votes
From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.
Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
|
show 2 more comments
The abstract syntax tree (AST) is equal to a program flow which is formulated in a domain specific language. If the language consists of possible commands: up, left, down, right a possible AST would be: up, up, up, left. What genetic programming is trying to do is to evolve the AST, that means to figure out many different program flows for solving a game. Instead of only evolving the AST the much better idea is to evolve the grammar. That means, to modify the domain specific language in which the AST is formulated. For example, by adding an additional command like “gocenter”. The new language contains now of 5 possible actions: gocenter, up, left, down, right and it is possible to test out new kind of populations. To systematically evolve a grammar it is needed to learn the grammar by interaction. That means, we are starting with an empty grammar and add carefully new possible action commands. In the literature this is described as “grammar induction” and means to take an input stream from human interaction and generate the new language from scratch. With this grammar it is possible to evolve possible ASTs.
quote: “Grammatical Evolution (GE) is a grammar-based form of Genetic
programming that specifies the syntax of possible solutions through a
context-free grammar” source: Perez, Diego, et al. "Evolving behaviour
trees for the mario ai competition using grammatical evolution."
European Conference on the Applications of Evolutionary Computation.
Springer, Berlin, Heidelberg, 2011.
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53135384%2fis-this-language-generic-mighty-enough-to-be-used-for-a-generic-game-ai%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.
Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
|
show 2 more comments
From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.
Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
|
show 2 more comments
From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.
Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
From my perpective the Turing completness of the system is not the main problem here. When using a genetic algorithm to evolve some kind of a strategy applied to some game environment one of the features of the algorithm - that would be helpful - is - I believe - that the small change in the "genome" of the solution lead to a reasonably small change in the behavior. If this is not true then every mutation or cross over can produce an entity that behaves completely different and in this kind of landscape it can be problematic for the genetic algorithm to arrive to some optima - as the landscape of the fitness function is not continuous enough.
Having said that it makes sense to me to try to somehow encode a form of decision tree in the genome and evolve that. However - from my experience - the genetic algorithms in AI for games works best when used to "compute" the optimal values of some parameters of some particular behavior then to "evolve" the behavior itself.
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
answered Nov 9 '18 at 10:58
Michal BidaMichal Bida
1,047524
1,047524
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
|
show 2 more comments
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
The decision tree in the genome must have the syntax of an abstract syntax tree. Which means, that the grammar follows production rules. This formal grammar has to be evolved, no the genetic algorithm itself.
– Manuel Rodriguez
Nov 10 '18 at 10:25
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
Isn't the AST I was proposing a generalisation of a decision tree? Could you please elaborate what you mean by "formal grammar has to be evolved"?
– codymanix
Nov 10 '18 at 20:34
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@codymanix The abstract syntax tree (AST) is the program flow. It's textual representation is sourcecode in a domain specific language for example: “walk, walk, opendoor, walk”. The allowed elements in the AST are called a grammar. A grammar will check, if concrete sourcecode is valid or not. In the example problem two things can be evolved: the grammar itself and a concrete action sequence in the grammar.
– Manuel Rodriguez
Nov 10 '18 at 21:50
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
@Manuel Rodriguez but doesn't this additional step of even evolving the grammar itself make the problem even harder? I would think you need to fix something - e.g. the grammer used - here to have a chance of arriving to some reasonable solution when running the evolutionary algorithm on your population.
– Michal Bida
Nov 11 '18 at 11:17
1
1
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
The baseline for evolving the grammar is the domain itself. The grammar is grounded to the cost function of the population. e.g. Grammar g1 produced AST a1 which produced costs of c1. This signal has to be communicated back, so that the grammar evolves to g2 which produces AST a2 and can generate a better costs of c2. In that kind of feedback loop the domain remains constant. All the grammars are evolved over the same domain.
– Manuel Rodriguez
Nov 11 '18 at 11:32
|
show 2 more comments
The abstract syntax tree (AST) is equal to a program flow which is formulated in a domain specific language. If the language consists of possible commands: up, left, down, right a possible AST would be: up, up, up, left. What genetic programming is trying to do is to evolve the AST, that means to figure out many different program flows for solving a game. Instead of only evolving the AST the much better idea is to evolve the grammar. That means, to modify the domain specific language in which the AST is formulated. For example, by adding an additional command like “gocenter”. The new language contains now of 5 possible actions: gocenter, up, left, down, right and it is possible to test out new kind of populations. To systematically evolve a grammar it is needed to learn the grammar by interaction. That means, we are starting with an empty grammar and add carefully new possible action commands. In the literature this is described as “grammar induction” and means to take an input stream from human interaction and generate the new language from scratch. With this grammar it is possible to evolve possible ASTs.
quote: “Grammatical Evolution (GE) is a grammar-based form of Genetic
programming that specifies the syntax of possible solutions through a
context-free grammar” source: Perez, Diego, et al. "Evolving behaviour
trees for the mario ai competition using grammatical evolution."
European Conference on the Applications of Evolutionary Computation.
Springer, Berlin, Heidelberg, 2011.
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
add a comment |
The abstract syntax tree (AST) is equal to a program flow which is formulated in a domain specific language. If the language consists of possible commands: up, left, down, right a possible AST would be: up, up, up, left. What genetic programming is trying to do is to evolve the AST, that means to figure out many different program flows for solving a game. Instead of only evolving the AST the much better idea is to evolve the grammar. That means, to modify the domain specific language in which the AST is formulated. For example, by adding an additional command like “gocenter”. The new language contains now of 5 possible actions: gocenter, up, left, down, right and it is possible to test out new kind of populations. To systematically evolve a grammar it is needed to learn the grammar by interaction. That means, we are starting with an empty grammar and add carefully new possible action commands. In the literature this is described as “grammar induction” and means to take an input stream from human interaction and generate the new language from scratch. With this grammar it is possible to evolve possible ASTs.
quote: “Grammatical Evolution (GE) is a grammar-based form of Genetic
programming that specifies the syntax of possible solutions through a
context-free grammar” source: Perez, Diego, et al. "Evolving behaviour
trees for the mario ai competition using grammatical evolution."
European Conference on the Applications of Evolutionary Computation.
Springer, Berlin, Heidelberg, 2011.
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
add a comment |
The abstract syntax tree (AST) is equal to a program flow which is formulated in a domain specific language. If the language consists of possible commands: up, left, down, right a possible AST would be: up, up, up, left. What genetic programming is trying to do is to evolve the AST, that means to figure out many different program flows for solving a game. Instead of only evolving the AST the much better idea is to evolve the grammar. That means, to modify the domain specific language in which the AST is formulated. For example, by adding an additional command like “gocenter”. The new language contains now of 5 possible actions: gocenter, up, left, down, right and it is possible to test out new kind of populations. To systematically evolve a grammar it is needed to learn the grammar by interaction. That means, we are starting with an empty grammar and add carefully new possible action commands. In the literature this is described as “grammar induction” and means to take an input stream from human interaction and generate the new language from scratch. With this grammar it is possible to evolve possible ASTs.
quote: “Grammatical Evolution (GE) is a grammar-based form of Genetic
programming that specifies the syntax of possible solutions through a
context-free grammar” source: Perez, Diego, et al. "Evolving behaviour
trees for the mario ai competition using grammatical evolution."
European Conference on the Applications of Evolutionary Computation.
Springer, Berlin, Heidelberg, 2011.
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
The abstract syntax tree (AST) is equal to a program flow which is formulated in a domain specific language. If the language consists of possible commands: up, left, down, right a possible AST would be: up, up, up, left. What genetic programming is trying to do is to evolve the AST, that means to figure out many different program flows for solving a game. Instead of only evolving the AST the much better idea is to evolve the grammar. That means, to modify the domain specific language in which the AST is formulated. For example, by adding an additional command like “gocenter”. The new language contains now of 5 possible actions: gocenter, up, left, down, right and it is possible to test out new kind of populations. To systematically evolve a grammar it is needed to learn the grammar by interaction. That means, we are starting with an empty grammar and add carefully new possible action commands. In the literature this is described as “grammar induction” and means to take an input stream from human interaction and generate the new language from scratch. With this grammar it is possible to evolve possible ASTs.
quote: “Grammatical Evolution (GE) is a grammar-based form of Genetic
programming that specifies the syntax of possible solutions through a
context-free grammar” source: Perez, Diego, et al. "Evolving behaviour
trees for the mario ai competition using grammatical evolution."
European Conference on the Applications of Evolutionary Computation.
Springer, Berlin, Heidelberg, 2011.
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
edited Nov 13 '18 at 10:09
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
answered Nov 12 '18 at 20:58
Manuel RodriguezManuel Rodriguez
311214
311214
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
add a comment |
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
That is really an interesting approach. Do you have any example where this actually worked? I mean the state space of possible grammar actions can be infinite. Do you somehow constrain this or do you just hope it will evolve correctly?
– Michal Bida
Nov 13 '18 at 9:56
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53135384%2fis-this-language-generic-mighty-enough-to-be-used-for-a-generic-game-ai%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Sounds like Computer Science would be a better fit for this question.
– usr2564301
Nov 3 '18 at 21:24
Thanks for commenting. Is my post clear enough or is some information missing? Maybe I can improve my question.
– codymanix
Nov 4 '18 at 10:39