As readers of this forum know, I attempted to collect a group of people to discuss some of the issues raised in a recent thread on this website about the Coevolution Task Force itself. This attempt was only marginally successful: Despite the post here and on the GECCO wiki, interest in such a discussion was modest.
Nevertheless, a few of us did sit down to talk about the TF. Our conversation touched on three main questions ... some of which we answered there, some of which I've pieced together after subsequent email exchanges.
1. What is the "Computational Intelligence and Coevolution Task Force"? 2. How do "we" and our activities relate to it? 3. On a broader level, what might be some of the goals of the coeovlution community?
I'll take them in turn
1. COEVOLUTION TASK FORCE
For those that do not know (I didn't): The IEEE has what they call the "Computational Intelligence Society" ( http://ieee-cis.org/ec/ ), which has the goal of promoting research, development, and teaching of such techniques. It is composed of a number of "Technical Committees", subgroups with more focused fields of study ... evolutionary computation is one. As far as I can see the ECTC is analogous to ACM SIGEVO ... it has a governing board, by-laws, helps organize conference and other events, etc.
Those who have interests in a subfield of study that they believe would benefit from an even more focused group may propose such to the ECTC. Indeed, the "Coevolution working group" was established by Graham Kendall a couple of years ago. It took the form of a largely inactive mailing list. I don't know if anything else came of it.
Recently this group was converted to a "Task Force", and we moved to a Google group, rather than a simple mail list. Phi has already covered what this means in previous posts. The inference I have taken is that the advantage to being a part of such a group is to consolidate discussion and possibly receive some resources from IEEE to sponsor some events, etc. In exchange, the TF has to demonstrate to IEEE that it is a productive use of such resources.
As far as I can tell the "Computational Intelligence" prefix to the group's name is merely a hierarchical artifact: The Coevolution task force is a part (ultimately) of the Computational Intelligence Society ... the task force is dedicated to the field of coevolutionary computation.
2. HOW "WE" RELATE
The group of people with whom I most commonly collaborate for activities and events related to coevolution have historically operated in a very informal, self-organizing fashion. We neither consider ourselves operating "officially" as an extension of the ACM nor of IEEE. We're just a group of people who share an interest and expertise in coevolutionary computation.
Nevertheless, it was clear and not surprising that most of us involved in the GECCO discussion have participated more in the ACM events than the IEEE events. The relevance here was that we were all fairly unknowledgeable about what the task force had done in IEEE contexts.
As an informal group, we've accomplished quite a bit (an example list appears elsewhere in a contemporary post). And part of our discussion centered around what we would be gaining and losing if we shifted our activities to be under one umbrella or another. Would there be a loss of autonomy? What kind of resources would be available to us? Etc.
We concluded that we'd like to know more about what the IEEE folks are up to in the coevolution community, and we'd like for them to know more about what we are doing. In that sense, a periodic discussion on this web resource might be quite useful. Moreover, if the TF can facilitate something for our community in a way that we, ourselves, could not, then that might be worth exploring. However, I do not have the sense that we had any specific ideas on this front over and above what we are already accomplishing in our informal setup.
I think this point was left very much unresolved.
3. BROADER GOALS
We all agreed that the coevolutionary computation community has made a lot of great progress over the last few years, but also admitted there were some things bothering us. There is the concern that the same people are publishing at about the same rate: We aren't growing. There's also the perception that contemporary views of coevolution that include a clearer formal foundation are not being considered in applied studies as much as we'd like, and that coevolution really isn't raising in scope within the general EC community.
How we might use IEEE resources to accomplish these goals is unclear to us. More generally we'd no specific ideas on how to remedy these issues ... we are already holding workshops, tutorials, discussion forums, etc. The high-level question here is: Is it better to address these issues top-down (IEEE Task Force) or bottom-up (informal, ad-hoc organizations?
The more specific question is what could be done about it, regardless?
One idea is to target students a bit more carefully. We might hold a separate workshop-like event for students where we try to provide as much funding for them to attend as possible, provide a strong set of background lectures in foundational elements of coevolution, have competition on realistic problems, and maybe even have a few broader discussions that graduate students might find useful (funding, publishing, job hunting, etc.).
We might also try to develop a competition in one or both of the major conferences. I know GECCO has a mechanism for such things.
Another idea is to push harder for strong example applications where the advantage of a properly constructed coevolutionary algorithms were clear, etc.
Thanks Paul for this very thoughtful and useful report, and for organising the meeting at GECCO.
I volunteer to organise a similar meeting at CEC. Perhaps those interested could reply to me.
One concrete suggestion to make the foundations of coevolutionary algorithms more widely considered (in particular, better known to IEEE people, if there is such a concept!) might be a special issue of IEEE TEC on coevolution. Any volunteers for guest editors?
I've noticed quite a few papers published in TEC or in IEEE conferences that use coevolution. Games is one area where coevolution seems to be a natural approach. Another active area recently is various new coevolution-based multi-objective optimisation algorithms. I would personally like to see this work take more account of proper foundations.
The competitions idea is also a good one. CEC does indeed have a competitions program. In fact, I am responsible for EC competitions at next year's WCCI in Hong Kong, and would welcome a coevolution-based competition proposal. The call for proposals may be found on the conference home page at http://www.wcci2008.org/index.htm.
cheers
On Jul 25, 7:28 pm, "R. Paul Wiegand" <p...@tesseract.org> wrote:
> As readers of this forum know, I attempted to collect a group of > people to discuss some of the issues raised in a recent thread on this > website about the Coevolution Task Force itself. This attempt was > only marginally successful: Despite the post here and on the GECCO > wiki, interest in such a discussion was modest.
> Nevertheless, a few of us did sit down to talk about the TF. Our > conversation touched on three main questions ... some of which we > answered there, some of which I've pieced together after subsequent > email exchanges.
> 1. What is the "Computational Intelligence and Coevolution Task > Force"? > 2. How do "we" and our activities relate to it? > 3. On a broader level, what might be some of the goals of the > coeovlution community?
> I'll take them in turn
> 1. COEVOLUTION TASK FORCE
> For those that do not know (I didn't): The IEEE has what they call > the "Computational Intelligence Society" (http://ieee-cis.org/ec/), > which has the goal of promoting research, development, and teaching of > such techniques. It is composed of a number of "Technical > Committees", subgroups with more focused fields of study ... > evolutionary computation is one. As far as I can see the ECTC is > analogous to ACM SIGEVO ... it has a governing board, by-laws, helps > organize conference and other events, etc.
> Those who have interests in a subfield of study that they believe > would benefit from an even more focused group may propose such to the > ECTC. Indeed, the "Coevolution working group" was established by > Graham Kendall a couple of years ago. It took the form of a largely > inactive mailing list. I don't know if anything else came of it.
> Recently this group was converted to a "Task Force", and we moved to a > Google group, rather than a simple mail list. Phi has already covered > what this means in previous posts. The inference I have taken is that > the advantage to being a part of such a group is to consolidate > discussion and possibly receive some resources from IEEE to sponsor > some events, etc. In exchange, the TF has to demonstrate to IEEE that > it is a productive use of such resources.
> As far as I can tell the "Computational Intelligence" prefix to the > group's name is merely a hierarchical artifact: The Coevolution task > force is a part (ultimately) of the Computational Intelligence > Society ... the task force is dedicated to the field of coevolutionary > computation.
> 2. HOW "WE" RELATE
> The group of people with whom I most commonly collaborate for > activities and events related to coevolution have historically > operated in a very informal, self-organizing fashion. We neither > consider ourselves operating "officially" as an extension of the ACM > nor of IEEE. We're just a group of people who share an interest and > expertise in coevolutionary computation.
> Nevertheless, it was clear and not surprising that most of us involved > in the GECCO discussion have participated more in the ACM events than > the IEEE events. The relevance here was that we were all fairly > unknowledgeable about what the task force had done in IEEE contexts.
> As an informal group, we've accomplished quite a bit (an example list > appears elsewhere in a contemporary post). And part of our discussion > centered around what we would be gaining and losing if we shifted our > activities to be under one umbrella or another. Would there be a loss > of autonomy? What kind of resources would be available to us? Etc.
> We concluded that we'd like to know more about what the IEEE folks are > up to in the coevolution community, and we'd like for them to know > more about what we are doing. In that sense, a periodic discussion on > this web resource might be quite useful. Moreover, if the TF can > facilitate something for our community in a way that we, ourselves, > could not, then that might be worth exploring. However, I do not have > the sense that we had any specific ideas on this front over and above > what we are already accomplishing in our informal setup.
> I think this point was left very much unresolved.
> 3. BROADER GOALS
> We all agreed that the coevolutionary computation community has made a > lot of great progress over the last few years, but also admitted there > were some things bothering us. There is the concern that the same > people are publishing at about the same rate: We aren't growing. > There's also the perception that contemporary views of coevolution > that include a clearer formal foundation are not being considered in > applied studies as much as we'd like, and that coevolution really > isn't raising in scope within the general EC community.
> How we might use IEEE resources to accomplish these goals is unclear > to us. More generally we'd no specific ideas on how to remedy these > issues ... we are already holding workshops, tutorials, discussion > forums, etc. The high-level question here is: Is it better to > address these issues top-down (IEEE Task Force) or bottom-up > (informal, ad-hoc organizations?
> The more specific question is what could be done about it, regardless?
> One idea is to target students a bit more carefully. We might hold a > separate workshop-like event for students where we try to provide as > much funding for them to attend as possible, provide a strong set of > background lectures in foundational elements of coevolution, have > competition on realistic problems, and maybe even have a few broader > discussions that graduate students might find useful (funding, > publishing, job hunting, etc.).
> We might also try to develop a competition in one or both of the major > conferences. I know GECCO has a mechanism for such things.
> Another idea is to push harder for strong example applications where > the advantage of a properly constructed coevolutionary algorithms were > clear, etc.
I agree with Philip's comment on the need for coevolutionary approaches to multi-objective algorithms to take better account of new theory. My own work has drawn strong ties between coevolution and multi-objective optimization. More broadly, Pareto coevolution can be seen as a set of concepts and class of algorithms which make the connection explicit. There has been quite a bit of work on this topic recently, including my own dissertation as well as a recent book chapter I co-authored with Edwin de Jong for a new book on Multi-objective Problem Solving from Nature. Of course I have a vested interest in seeing the connections between coev and MOO made as strong as possible Still, I think any approach to coev could benefit by taking account of recent theoretical advances.
Regarding a competition, I think tic-tac-toe is a good challenge problem because:
(a) it's a small game with simple, known minimax strategy, giving a benchmark for progress
(b) it has a small, easily enumerable set of board configurations, allow strategies to be written out explicitly and examined critically
(c) there's a nice history of work on tic-tac-toe, starting with Michie's MENACE, through Susan Epstein's Hoyle system, to more recent work in coev
(d) it's proven to be particularly challenging for coevolutionary algorithms for some as-yet-obscure reason. some attempts, like Pete Angeline's, never resulted in optimal strategies (though he made the problem harder than it needed to be, as he was exploring other questions than finding optima). others, like Rosin's, required specially-designed representations and a huge number of evaluations before optimal solutions were found.
Even modern coevolutionary algorithms like Sevan's Nash memory tend to have trouble with tic-tac-toe. I have some thoughts on why this is, but it's very much an open question how we could get coevolution to efficiently find optimal tic-tac-toe strategies. A metric of success would be the ability to evolve optimal players using fewer evaluations than Rosin did and a weaker representation -- that'd be a publishable result, it seems to me.
The CA majority problem isn't a bad choice either, as there is also a good history of work on it (including Sevan's). I personally prefer tic-tac-toe, though.
> Thanks Paul for this very thoughtful and useful report, and for > organising the meeting at GECCO.
> I volunteer to organise a similar meeting at CEC. Perhaps those > interested could reply to me.
> One concrete suggestion to make the foundations of coevolutionary > algorithms more widely considered (in particular, > better known to IEEE people, if there is such a concept!) might be a > special issue of IEEE TEC on coevolution. Any > volunteers for guest editors?
> I've noticed quite a few papers published in TEC or in IEEE > conferences that use coevolution. Games is one area where > coevolution seems to be a natural approach. Another active area > recently is various new coevolution-based multi-objective > optimisation algorithms. I would personally like to see this work take > more account of proper foundations.
> The competitions idea is also a good one. CEC does indeed have a > competitions program. In fact, I am responsible for > EC competitions at next year's WCCI in Hong Kong, and would welcome a > coevolution-based competition proposal. > The call for proposals may be found on the conference home page at > http://www.wcci2008.org/index.htm.
> cheers
> On Jul 25, 7:28 pm, "R. Paul Wiegand" <p...@tesseract.org> wrote: > > GECCO REPORT
> > As readers of this forum know, I attempted to collect a group of > > people to discuss some of the issues raised in a recent thread on this > > website about the Coevolution Task Force itself. This attempt was > > only marginally successful: Despite the post here and on the GECCO > > wiki, interest in such a discussion was modest.
> > Nevertheless, a few of us did sit down to talk about the TF. Our > > conversation touched on three main questions ... some of which we > > answered there, some of which I've pieced together after subsequent > > email exchanges.
> > 1. What is the "Computational Intelligence and Coevolution Task > > Force"? > > 2. How do "we" and our activities relate to it? > > 3. On a broader level, what might be some of the goals of the > > coeovlution community?
> > I'll take them in turn
> > 1. COEVOLUTION TASK FORCE
> > For those that do not know (I didn't): The IEEE has what they call > > the "Computational Intelligence Society" (http://ieee-cis.org/ec/), > > which has the goal of promoting research, development, and teaching of > > such techniques. It is composed of a number of "Technical > > Committees", subgroups with more focused fields of study ... > > evolutionary computation is one. As far as I can see the ECTC is > > analogous to ACM SIGEVO ... it has a governing board, by-laws, helps > > organize conference and other events, etc.
> > Those who have interests in a subfield of study that they believe > > would benefit from an even more focused group may propose such to the > > ECTC. Indeed, the "Coevolution working group" was established by > > Graham Kendall a couple of years ago. It took the form of a largely > > inactive mailing list. I don't know if anything else came of it.
> > Recently this group was converted to a "Task Force", and we moved to a > > Google group, rather than a simple mail list. Phi has already covered > > what this means in previous posts. The inference I have taken is that > > the advantage to being a part of such a group is to consolidate > > discussion and possibly receive some resources from IEEE to sponsor > > some events, etc. In exchange, the TF has to demonstrate to IEEE that > > it is a productive use of such resources.
> > As far as I can tell the "Computational Intelligence" prefix to the > > group's name is merely a hierarchical artifact: The Coevolution task > > force is a part (ultimately) of the Computational Intelligence > > Society ... the task force is dedicated to the field of coevolutionary > > computation.
> > 2. HOW "WE" RELATE
> > The group of people with whom I most commonly collaborate for > > activities and events related to coevolution have historically > > operated in a very informal, self-organizing fashion. We neither > > consider ourselves operating "officially" as an extension of the ACM > > nor of IEEE. We're just a group of people who share an interest and > > expertise in coevolutionary computation.
> > Nevertheless, it was clear and not surprising that most of us involved > > in the GECCO discussion have participated more in the ACM events than > > the IEEE events. The relevance here was that we were all fairly > > unknowledgeable about what the task force had done in IEEE contexts.
> > As an informal group, we've accomplished quite a bit (an example list > > appears elsewhere in a contemporary post). And part of our discussion > > centered around what we would be gaining and losing if we shifted our > > activities to be under one umbrella or another. Would there be a loss > > of autonomy? What kind of resources would be available to us? Etc.
> > We concluded that we'd like to know more about what the IEEE folks are > > up to in the coevolution community, and we'd like for them to know > > more about what we are doing. In that sense, a periodic discussion on > > this web resource might be quite useful. Moreover, if the TF can > > facilitate something for our community in a way that we, ourselves, > > could not, then that might be worth exploring. However, I do not have > > the sense that we had any specific ideas on this front over and above > > what we are already accomplishing in our informal setup.
> > I think this point was left very much unresolved.
> > 3. BROADER GOALS
> > We all agreed that the coevolutionary computation community has made a > > lot of great progress over the last few years, but also admitted there > > were some things bothering us. There is the concern that the same > > people are publishing at about the same rate: We aren't growing. > > There's also the perception that contemporary views of coevolution > > that include a clearer formal foundation are not being considered in > > applied studies as much as we'd like, and that coevolution really > > isn't raising in scope within the general EC community.
> > How we might use IEEE resources to accomplish these goals is unclear > > to us. More generally we'd no specific ideas on how to remedy these > > issues ... we are already holding workshops, tutorials, discussion > > forums, etc. The high-level question here is: Is it better to > > address these issues top-down (IEEE Task Force) or bottom-up > > (informal, ad-hoc organizations?
> > The more specific question is what could be done about it, regardless?
> > One idea is to target students a bit more carefully. We might hold a > > separate workshop-like event for students where we try to provide as > > much funding for them to attend as possible, provide a strong set of > > background lectures in foundational elements of coevolution, have > > competition on realistic problems, and maybe even have a few broader > > discussions that graduate students might find useful (funding, > > publishing, job hunting, etc.).
> > We might also try to develop a competition in one or both of the major > > conferences. I know GECCO has a mechanism for such things.
> > Another idea is to push harder for strong example applications where > > the advantage of a properly constructed coevolutionary algorithms were > > clear, etc.
I also think tic-tac-toe is currently an important domain because it *should* be easy but isn't. However, I think it would be most informative to separate the genetic encoding from the coevolutionary algorithm because in tic tac toe the genetic encoding can be a significant factor in success.
Therefore, what I think would be useful is to agree on a single encoding. It is actually possible with today's processors to find a perfect player without coevolution through an exhaustive evaluation that tests all possible game positions (minus ones that are simply continuations of completed games). That is, an optimal strategy can be evolved using such a non-coevolutionary exhaustive evaluation as a proof of concept that the encoding can indeed solve tic-tac-toe perfectly.
One we know that, it becomes interesting to pit different coevolutionary techniques against each other with that same encoding in each case. Then we would know the coevolutionary methodology is the only determining factor in differing performance.
ken
On Jul 25, 5:31 pm, "Anthony Bucci" <abu...@gmail.com> wrote:
> I agree with Philip's comment on the need for coevolutionary approaches to > multi-objective algorithms to take better account of new theory. My own > work has drawn strong ties between coevolution and multi-objective > optimization. More broadly, Pareto coevolution can be seen as a set of > concepts and class of algorithms which make the connection explicit. There > has been quite a bit of work on this topic recently, including my own > dissertation as well as a recent book chapter I co-authored with Edwin de > Jong for a new book on Multi-objective Problem Solving from Nature. Of > course I have a vested interest in seeing the connections between coev and > MOO made as strong as possible Still, I think any approach to coev could > benefit by taking account of recent theoretical advances.
> Regarding a competition, I think tic-tac-toe is a good challenge problem > because:
> (a) it's a small game with simple, known minimax strategy, giving a > benchmark for progress
> (b) it has a small, easily enumerable set of board configurations, allow > strategies to be written out explicitly and examined critically
> (c) there's a nice history of work on tic-tac-toe, starting with Michie's > MENACE, through Susan Epstein's Hoyle system, to more recent work in coev
> (d) it's proven to be particularly challenging for coevolutionary algorithms > for some as-yet-obscure reason. some attempts, like Pete Angeline's, never > resulted in optimal strategies (though he made the problem harder than it > needed to be, as he was exploring other questions than finding optima). > others, like Rosin's, required specially-designed representations and a huge > number of evaluations before optimal solutions were found.
> Even modern coevolutionary algorithms like Sevan's Nash memory tend to have > trouble with tic-tac-toe. I have some thoughts on why this is, but it's > very much an open question how we could get coevolution to efficiently find > optimal tic-tac-toe strategies. A metric of success would be the ability to > evolve optimal players using fewer evaluations than Rosin did and a weaker > representation -- that'd be a publishable result, it seems to me.
> The CA majority problem isn't a bad choice either, as there is also a good > history of work on it (including Sevan's). I personally prefer tic-tac-toe, > though.
> Anthony
> On 7/25/07, phi <PhilipHings...@gmail.com> wrote:
> > Hi Paul, everyone
> > Thanks Paul for this very thoughtful and useful report, and for > > organising the meeting at GECCO.
> > I volunteer to organise a similar meeting at CEC. Perhaps those > > interested could reply to me.
> > One concrete suggestion to make the foundations of coevolutionary > > algorithms more widely considered (in particular, > > better known to IEEE people, if there is such a concept!) might be a > > special issue of IEEE TEC on coevolution. Any > > volunteers for guest editors?
> > I've noticed quite a few papers published in TEC or in IEEE > > conferences that use coevolution. Games is one area where > > coevolution seems to be a natural approach. Another active area > > recently is various new coevolution-based multi-objective > > optimisation algorithms. I would personally like to see this work take > > more account of proper foundations.
> > The competitions idea is also a good one. CEC does indeed have a > > competitions program. In fact, I am responsible for > > EC competitions at next year's WCCI in Hong Kong, and would welcome a > > coevolution-based competition proposal. > > The call for proposals may be found on the conference home page at > >http://www.wcci2008.org/index.htm.
> > cheers
> > On Jul 25, 7:28 pm, "R. Paul Wiegand" <p...@tesseract.org> wrote: > > > GECCO REPORT
> > > As readers of this forum know, I attempted to collect a group of > > > people to discuss some of the issues raised in a recent thread on this > > > website about the Coevolution Task Force itself. This attempt was > > > only marginally successful: Despite the post here and on the GECCO > > > wiki, interest in such a discussion was modest.
> > > Nevertheless, a few of us did sit down to talk about the TF. Our > > > conversation touched on three main questions ... some of which we > > > answered there, some of which I've pieced together after subsequent > > > email exchanges.
> > > 1. What is the "Computational Intelligence and Coevolution Task > > > Force"? > > > 2. How do "we" and our activities relate to it? > > > 3. On a broader level, what might be some of the goals of the > > > coeovlution community?
> > > I'll take them in turn
> > > 1. COEVOLUTION TASK FORCE
> > > For those that do not know (I didn't): The IEEE has what they call > > > the "Computational Intelligence Society" (http://ieee-cis.org/ec/), > > > which has the goal of promoting research, development, and teaching of > > > such techniques. It is composed of a number of "Technical > > > Committees", subgroups with more focused fields of study ... > > > evolutionary computation is one. As far as I can see the ECTC is > > > analogous to ACM SIGEVO ... it has a governing board, by-laws, helps > > > organize conference and other events, etc.
> > > Those who have interests in a subfield of study that they believe > > > would benefit from an even more focused group may propose such to the > > > ECTC. Indeed, the "Coevolution working group" was established by > > > Graham Kendall a couple of years ago. It took the form of a largely > > > inactive mailing list. I don't know if anything else came of it.
> > > Recently this group was converted to a "Task Force", and we moved to a > > > Google group, rather than a simple mail list. Phi has already covered > > > what this means in previous posts. The inference I have taken is that > > > the advantage to being a part of such a group is to consolidate > > > discussion and possibly receive some resources from IEEE to sponsor > > > some events, etc. In exchange, the TF has to demonstrate to IEEE that > > > it is a productive use of such resources.
> > > As far as I can tell the "Computational Intelligence" prefix to the > > > group's name is merely a hierarchical artifact: The Coevolution task > > > force is a part (ultimately) of the Computational Intelligence > > > Society ... the task force is dedicated to the field of coevolutionary > > > computation.
> > > 2. HOW "WE" RELATE
> > > The group of people with whom I most commonly collaborate for > > > activities and events related to coevolution have historically > > > operated in a very informal, self-organizing fashion. We neither > > > consider ourselves operating "officially" as an extension of the ACM > > > nor of IEEE. We're just a group of people who share an interest and > > > expertise in coevolutionary computation.
> > > Nevertheless, it was clear and not surprising that most of us involved > > > in the GECCO discussion have participated more in the ACM events than > > > the IEEE events. The relevance here was that we were all fairly > > > unknowledgeable about what the task force had done in IEEE contexts.
> > > As an informal group, we've accomplished quite a bit (an example list > > > appears elsewhere in a contemporary post). And part of our discussion > > > centered around what we would be gaining and losing if we shifted our > > > activities to be under one umbrella or another. Would there be a loss > > > of autonomy? What kind of resources would be available to us? Etc.
> > > We concluded that we'd like to know more about what the IEEE folks are > > > up to in the coevolution community, and we'd like for them to know > > > more about what we are doing. In that sense, a periodic discussion on > > > this web resource might be quite useful. Moreover, if the TF can > > > facilitate something for our community in a way that we, ourselves, > > > could not, then that might be worth exploring. However, I do not have > > > the sense that we had any specific ideas on this front over and above > > > what we are already accomplishing in our informal setup.
> > > I think this point was left very much unresolved.
> > > 3. BROADER GOALS
> > > We all agreed that the coevolutionary computation community has made a > > > lot of great progress over the last few years, but also admitted there > > > were some things bothering us. There is the concern that the same > > > people are publishing at about the same rate: We aren't growing. > > > There's also the perception that contemporary views of coevolution > > > that include a clearer formal foundation are not being considered in > > > applied studies as much as we'd like, and that coevolution really > > > isn't raising in scope within the general EC community.
> > > How we might use IEEE resources to accomplish these goals is unclear > > > to us. More
OK - time to show my ignorance... I've quickly had a look at a few papers, but I guess I don't get it! How can tic-tac-toe be any challenge? The game tree is tiny. Not much opportunity for something hard like, say, opponent modelling.
Is it something about co-evolution that makes it hard? Would it be hard for standard evolution (or whatever the right name for not co-evolution, but still evolution is). I realise you'd need a fitness measure: say performance against perfect play, or maybe against a random player.
phi
On Jul 27, 9:54 am, Kenneth Stanley <kstan...@cs.ucf.edu> wrote:
> I also think tic-tac-toe is currently an important domain because it > *should* be easy but isn't. However, I think it would be most > informative to separate the genetic encoding from the coevolutionary > algorithm because in tic tac toe the genetic encoding can be a > significant factor in success.
> Therefore, what I think would be useful is to agree on a single > encoding. It is actually possible with today's processors to find a > perfect player without coevolution through an exhaustive evaluation > that tests all possible game positions (minus ones that are simply > continuations of completed games). That is, an optimal strategy can > be evolved using such a non-coevolutionary exhaustive evaluation as a > proof of concept that the encoding can indeed solve tic-tac-toe > perfectly.
> One we know that, it becomes interesting to pit different > coevolutionary techniques against each other with that same encoding > in each case. Then we would know the coevolutionary methodology is > the only determining factor in differing performance.
> ken
> On Jul 25, 5:31 pm, "Anthony Bucci" <abu...@gmail.com> wrote:
> > I agree with Philip's comment on the need for coevolutionary approaches to > > multi-objective algorithms to take better account of new theory. My own > > work has drawn strong ties between coevolution and multi-objective > > optimization. More broadly, Pareto coevolution can be seen as a set of > > concepts and class of algorithms which make the connection explicit. There > > has been quite a bit of work on this topic recently, including my own > > dissertation as well as a recent book chapter I co-authored with Edwin de > > Jong for a new book on Multi-objective Problem Solving from Nature. Of > > course I have a vested interest in seeing the connections between coev and > > MOO made as strong as possible Still, I think any approach to coev could > > benefit by taking account of recent theoretical advances.
> > Regarding a competition, I think tic-tac-toe is a good challenge problem > > because:
> > (a) it's a small game with simple, known minimax strategy, giving a > > benchmark for progress
> > (b) it has a small, easily enumerable set of board configurations, allow > > strategies to be written out explicitly and examined critically
> > (c) there's a nice history of work on tic-tac-toe, starting with Michie's > > MENACE, through Susan Epstein's Hoyle system, to more recent work in coev
> > (d) it's proven to be particularly challenging for coevolutionary algorithms > > for some as-yet-obscure reason. some attempts, like Pete Angeline's, never > > resulted in optimal strategies (though he made the problem harder than it > > needed to be, as he was exploring other questions than finding optima). > > others, like Rosin's, required specially-designed representations and a huge > > number of evaluations before optimal solutions were found.
> > Even modern coevolutionary algorithms like Sevan's Nash memory tend to have > > trouble with tic-tac-toe. I have some thoughts on why this is, but it's > > very much an open question how we could get coevolution to efficiently find > > optimal tic-tac-toe strategies. A metric of success would be the ability to > > evolve optimal players using fewer evaluations than Rosin did and a weaker > > representation -- that'd be a publishable result, it seems to me.
> > The CA majority problem isn't a bad choice either, as there is also a good > > history of work on it (including Sevan's). I personally prefer tic-tac-toe, > > though.
> > Anthony
> > On 7/25/07, phi <PhilipHings...@gmail.com> wrote:
> > > Hi Paul, everyone
> > > Thanks Paul for this very thoughtful and useful report, and for > > > organising the meeting at GECCO.
> > > I volunteer to organise a similar meeting at CEC. Perhaps those > > > interested could reply to me.
> > > One concrete suggestion to make the foundations of coevolutionary > > > algorithms more widely considered (in particular, > > > better known to IEEE people, if there is such a concept!) might be a > > > special issue of IEEE TEC on coevolution. Any > > > volunteers for guest editors?
> > > I've noticed quite a few papers published in TEC or in IEEE > > > conferences that use coevolution. Games is one area where > > > coevolution seems to be a natural approach. Another active area > > > recently is various new coevolution-based multi-objective > > > optimisation algorithms. I would personally like to see this work take > > > more account of proper foundations.
> > > The competitions idea is also a good one. CEC does indeed have a > > > competitions program. In fact, I am responsible for > > > EC competitions at next year's WCCI in Hong Kong, and would welcome a > > > coevolution-based competition proposal. > > > The call for proposals may be found on the conference home page at > > >http://www.wcci2008.org/index.htm.
> > > cheers
> > > On Jul 25, 7:28 pm, "R. Paul Wiegand" <p...@tesseract.org> wrote: > > > > GECCO REPORT
> > > > As readers of this forum know, I attempted to collect a group of > > > > people to discuss some of the issues raised in a recent thread on this > > > > website about the Coevolution Task Force itself. This attempt was > > > > only marginally successful: Despite the post here and on the GECCO > > > > wiki, interest in such a discussion was modest.
> > > > Nevertheless, a few of us did sit down to talk about the TF. Our > > > > conversation touched on three main questions ... some of which we > > > > answered there, some of which I've pieced together after subsequent > > > > email exchanges.
> > > > 1. What is the "Computational Intelligence and Coevolution Task > > > > Force"? > > > > 2. How do "we" and our activities relate to it? > > > > 3. On a broader level, what might be some of the goals of the > > > > coeovlution community?
> > > > I'll take them in turn
> > > > 1. COEVOLUTION TASK FORCE
> > > > For those that do not know (I didn't): The IEEE has what they call > > > > the "Computational Intelligence Society" (http://ieee-cis.org/ec/), > > > > which has the goal of promoting research, development, and teaching of > > > > such techniques. It is composed of a number of "Technical > > > > Committees", subgroups with more focused fields of study ... > > > > evolutionary computation is one. As far as I can see the ECTC is > > > > analogous to ACM SIGEVO ... it has a governing board, by-laws, helps > > > > organize conference and other events, etc.
> > > > Those who have interests in a subfield of study that they believe > > > > would benefit from an even more focused group may propose such to the > > > > ECTC. Indeed, the "Coevolution working group" was established by > > > > Graham Kendall a couple of years ago. It took the form of a largely > > > > inactive mailing list. I don't know if anything else came of it.
> > > > Recently this group was converted to a "Task Force", and we moved to a > > > > Google group, rather than a simple mail list. Phi has already covered > > > > what this means in previous posts. The inference I have taken is that > > > > the advantage to being a part of such a group is to consolidate > > > > discussion and possibly receive some resources from IEEE to sponsor > > > > some events, etc. In exchange, the TF has to demonstrate to IEEE that > > > > it is a productive use of such resources.
> > > > As far as I can tell the "Computational Intelligence" prefix to the > > > > group's name is merely a hierarchical artifact: The Coevolution task > > > > force is a part (ultimately) of the Computational Intelligence > > > > Society ... the task force is dedicated to the field of coevolutionary > > > > computation.
> > > > 2. HOW "WE" RELATE
> > > > The group of people with whom I most commonly collaborate for > > > > activities and events related to coevolution have historically > > > > operated in a very informal, self-organizing fashion. We neither > > > > consider ourselves operating "officially" as an extension of the ACM > > > > nor of IEEE. We're just a group of people who share an interest and > > > > expertise in coevolutionary computation.
> > > > Nevertheless, it was clear and not surprising that most of us involved > > > > in the GECCO discussion have participated more in the ACM events than > > > > the IEEE events. The relevance here was that we were all fairly > > > > unknowledgeable about what the task force had done in IEEE contexts.
> > > > As an informal group, we've accomplished quite a bit (an example list > > > > appears elsewhere in a contemporary post). And part of our discussion > > > > centered around what we would be gaining and losing if we shifted our > > > > activities to be under one umbrella or another. Would there be a loss > > > > of autonomy? What kind of resources would be available to us? Etc.
> > > > We concluded that we'd like to know more about what the IEEE folks are > > > > up to in the coevolution community, and we'd like for them to know > > > > more about what we are doing. In that sense, a periodic discussion on > > > > this web resource might be quite useful. Moreover, if the TF can > > > > facilitate something for our community in a way that we, ourselves, > > > > could not, then that might be worth exploring. However, I do not have > > > > the sense that
If you think tictactoe is easy, then I'd say show me some results. Replicate Rosin and see if you can do better. :-)
Or:
Don Michie showed training MENACE against minimax did not produce very good players; he did that work in the 60's? 70's? Susan Epstein's 1994 ideal trainer article in Machine Learning argues the case more fully, for more games. She also argues against using random legal move generators for training. Though the game tree is small, training against either minimax or a random player still sends you into bizarre paths of the tree and does not sample the configs you're likely to see in practice. Random legal move generators also don't have coordinated strategy across moves. There's danger of forking in tictactoe. A good player will try to set up forks, but doing so requires coordinating at least two moves. A random legal move generator is unlikely to do that consistently. So a player trained against a random player is unlikely to have learned how to protect against forks (you can try all this yourself and see how tricky it is pretty easily).
Michie trained MENACE by playing good moves (e.g., those selected by minimax) frequently, but then purposely choosing poor moves once in awhile. As far as I remember he didn't have a system for choosing "poor" moves; I think he used his own intuition and knowledge about what parts of the game tree had already been explored.
A common observation when coevolving tictactoe players is that the population rapidly converges onto players which draw one another. Finding players that win seems to be hard. If you pressure the players to win, then you have almost no gradient (because players found early in the run cannot win very much). If you pressure players to draw, then you get stuck with a bunch of players who draw but don't win. Various weightings of those two objectives don't seem to help the getting stuck bit.
Naturally, using a good representation helps with those issues. Tictactoe is small enough that you can learn the evaluation function as a table. But that's cheating, because you can't do that for bigger games (without taking account of symmetries and without excluding terminal boards, tictactoe still only has ~5,500 configurations. What does checkers have, 10^40? You can't store a lookup table, and you have a paucity of stimulus problem with RL). If you try to learn a neural network representation of the evaluation function instead, as you'd have to do with bigger games, then you run into problems.
Check out Pete Angeline's 1993 paper on evolving/coevolving tictactoe players (he argues that coevolved players are less brittle than those evolved against fixed opponents). Chris Rosin's 1997 PhD dissertation reports experiments on tictactoe, also (and even with a "nice" representation, coevolving an optimal player requires billions of games to be played).
> OK - time to show my ignorance... I've quickly had a look at a few > papers, but I guess I don't get it! > How can tic-tac-toe be any challenge? The game tree is tiny. Not much > opportunity for something hard like, > say, opponent modelling.
> Is it something about co-evolution that makes it hard? Would it be > hard for standard evolution (or whatever the right name > for not co-evolution, but still evolution is). I realise you'd need a > fitness measure: say performance against perfect play, or > maybe against a random player.
> phi
> On Jul 27, 9:54 am, Kenneth Stanley <kstan...@cs.ucf.edu> wrote: > > I also think tic-tac-toe is currently an important domain because it > > *should* be easy but isn't. However, I think it would be most > > informative to separate the genetic encoding from the coevolutionary > > algorithm because in tic tac toe the genetic encoding can be a > > significant factor in success.
> > Therefore, what I think would be useful is to agree on a single > > encoding. It is actually possible with today's processors to find a > > perfect player without coevolution through an exhaustive evaluation > > that tests all possible game positions (minus ones that are simply > > continuations of completed games). That is, an optimal strategy can > > be evolved using such a non-coevolutionary exhaustive evaluation as a > > proof of concept that the encoding can indeed solve tic-tac-toe > > perfectly.
> > One we know that, it becomes interesting to pit different > > coevolutionary techniques against each other with that same encoding > > in each case. Then we would know the coevolutionary methodology is > > the only determining factor in differing performance.
> > > I agree with Philip's comment on the need for coevolutionary > approaches to > > > multi-objective algorithms to take better account of new theory. My > own > > > work has drawn strong ties between coevolution and multi-objective > > > optimization. More broadly, Pareto coevolution can be seen as a set > of > > > concepts and class of algorithms which make the connection > explicit. There > > > has been quite a bit of work on this topic recently, including my own > > > dissertation as well as a recent book chapter I co-authored with Edwin > de > > > Jong for a new book on Multi-objective Problem Solving from > Nature. Of > > > course I have a vested interest in seeing the connections between coev > and > > > MOO made as strong as possible Still, I think any approach to coev > could > > > benefit by taking account of recent theoretical advances.
> > > Regarding a competition, I think tic-tac-toe is a good challenge > problem > > > because:
> > > (a) it's a small game with simple, known minimax strategy, giving a > > > benchmark for progress
> > > (b) it has a small, easily enumerable set of board configurations, > allow > > > strategies to be written out explicitly and examined critically
> > > (c) there's a nice history of work on tic-tac-toe, starting with > Michie's > > > MENACE, through Susan Epstein's Hoyle system, to more recent work in > coev
> > > (d) it's proven to be particularly challenging for coevolutionary > algorithms > > > for some as-yet-obscure reason. some attempts, like Pete Angeline's, > never > > > resulted in optimal strategies (though he made the problem harder than > it > > > needed to be, as he was exploring other questions than finding > optima). > > > others, like Rosin's, required specially-designed representations and > a huge > > > number of evaluations before optimal solutions were found.
> > > Even modern coevolutionary algorithms like Sevan's Nash memory tend to > have > > > trouble with tic-tac-toe. I have some thoughts on why this is, but > it's > > > very much an open question how we could get coevolution to efficiently > find > > > optimal tic-tac-toe strategies. A metric of success would be the > ability to > > > evolve optimal players using fewer evaluations than Rosin did and a > weaker > > > representation -- that'd be a publishable result, it seems to me.
> > > The CA majority problem isn't a bad choice either, as there is also a > good > > > history of work on it (including Sevan's). I personally prefer > tic-tac-toe, > > > though.
> > > Anthony
> > > On 7/25/07, phi <PhilipHings...@gmail.com> wrote:
> > > > Hi Paul, everyone
> > > > Thanks Paul for this very thoughtful and useful report, and for > > > > organising the meeting at GECCO.
> > > > I volunteer to organise a similar meeting at CEC. Perhaps those > > > > interested could reply to me.
> > > > One concrete suggestion to make the foundations of coevolutionary > > > > algorithms more widely considered (in particular, > > > > better known to IEEE people, if there is such a concept!) might be a > > > > special issue of IEEE TEC on coevolution. Any > > > > volunteers for guest editors?
> > > > I've noticed quite a few papers published in TEC or in IEEE > > > > conferences that use coevolution. Games is one area where > > > > coevolution seems to be a natural approach. Another active area > > > > recently is various new coevolution-based multi-objective > > > > optimisation algorithms. I would personally like to see this work > take > > > > more account of proper foundations.
> > > > The competitions idea is also a good one. CEC does indeed have a > > > > competitions program. In fact, I am responsible for > > > > EC competitions at next year's WCCI in Hong Kong, and would welcome > a > > > > coevolution-based competition proposal. > > > > The call for proposals may be found on the conference home page at > > > >http://www.wcci2008.org/index.htm.
> > > > > As readers of this forum know, I attempted to collect a group of > > > > > people to discuss some of the issues raised in a recent thread on > this > > > > > website about the Coevolution Task Force itself. This attempt was > > > > > only marginally successful: Despite the post here and on the > GECCO > > > > > wiki, interest in such a discussion was modest.
> > > > > Nevertheless, a few of us did sit down to talk about the TF. Our > > > > > conversation touched on three main questions ... some of which we > > > > > answered there, some of which I've pieced together after > subsequent > > > > > email exchanges.
> > > > > 1. What is the "Computational Intelligence and Coevolution Task > > > > > Force"? > > > > > 2. How do "we" and our activities relate to it? > > > > > 3. On a broader level, what might be some of the goals of the > > > > > coeovlution community?
> > > > > I'll take them in turn
> > > > > 1. COEVOLUTION TASK FORCE
> > > > > For those that do not know (I didn't): The IEEE has what they > call > > > > > the "Computational Intelligence Society"
> If you think tictactoe is easy, then I'd say show me some results. > Replicate Rosin and see if you can do better. :-)
> Or:
> Don Michie showed training MENACE against minimax did not produce very > good players; he did that work in the 60's? 70's? Susan Epstein's 1994 > ideal trainer article in Machine Learning argues the case more fully, for > more games. She also argues against using random legal move generators for > training. Though the game tree is small, training against either minimax or > a random player still sends you into bizarre paths of the tree and does not > sample the configs you're likely to see in practice. Random legal move > generators also don't have coordinated strategy across moves. There's > danger of forking in tictactoe. A good player will try to set up forks, but > doing so requires coordinating at least two moves. A random legal move > generator is unlikely to do that consistently. So a player trained against > a random player is unlikely to have learned how to protect against forks > (you can try all this yourself and see how tricky it is pretty easily).
> Michie trained MENACE by playing good moves (e.g., those selected by > minimax) frequently, but then purposely choosing poor moves once in awhile. > As far as I remember he didn't have a system for choosing "poor" moves; I > think he used his own intuition and knowledge about what parts of the game > tree had already been explored.
> A common observation when coevolving tictactoe players is that the > population rapidly converges onto players which draw one another. Finding > players that win seems to be hard. If you pressure the players to win, then > you have almost no gradient (because players found early in the run cannot > win very much). If you pressure players to draw, then you get stuck with a > bunch of players who draw but don't win. Various weightings of those two > objectives don't seem to help the getting stuck bit.
> Naturally, using a good representation helps with those issues. Tictactoe > is small enough that you can learn the evaluation function as a table. But > that's cheating, because you can't do that for bigger games (without taking > account of symmetries and without excluding terminal boards, tictactoe still > only has ~5,500 configurations. What does checkers have, 10^40? You can't > store a lookup table, and you have a paucity of stimulus problem with RL). > If you try to learn a neural network representation of the evaluation > function instead, as you'd have to do with bigger games, then you run into > problems.
> Check out Pete Angeline's 1993 paper on evolving/coevolving tictactoe > players (he argues that coevolved players are less brittle than those > evolved against fixed opponents). Chris Rosin's 1997 PhD dissertation > reports experiments on tictactoe, also (and even with a "nice" > representation, coevolving an optimal player requires billions of games to > be played).
> Anthony
> On 8/2/07, phi <PhilipHings...@gmail.com> wrote:
> > OK - time to show my ignorance... I've quickly had a look at a few > > papers, but I guess I don't get it! > > How can tic-tac-toe be any challenge? The game tree is tiny. Not much > > opportunity for something hard like, > > say, opponent modelling.
> > Is it something about co-evolution that makes it hard? Would it be > > hard for standard evolution (or whatever the right name > > for not co-evolution, but still evolution is). I realise you'd need a > > fitness measure: say performance against perfect play, or > > maybe against a random player.
> > phi
> > On Jul 27, 9:54 am, Kenneth Stanley <kstan...@cs.ucf.edu> wrote: > > > I also think tic-tac-toe is currently an important domain because it > > > *should* be easy but isn't. However, I think it would be most > > > informative to separate the genetic encoding from the coevolutionary > > > algorithm because in tic tac toe the genetic encoding can be a > > > significant factor in success.
> > > Therefore, what I think would be useful is to agree on a single > > > encoding. It is actually possible with today's processors to find a > > > perfect player without coevolution through an exhaustive evaluation > > > that tests all possible game positions (minus ones that are simply > > > continuations of completed games). That is, an optimal strategy can > > > be evolved using such a non-coevolutionary exhaustive evaluation as a > > > proof of concept that the encoding can indeed solve tic-tac-toe > > > perfectly.
> > > One we know that, it becomes interesting to pit different > > > coevolutionary techniques against each other with that same encoding > > > in each case. Then we would know the coevolutionary methodology is > > > the only determining factor in differing performance.
> > > > I agree with Philip's comment on the need for coevolutionary > > approaches to > > > > multi-objective algorithms to take better account of new theory. My > > own > > > > work has drawn strong ties between coevolution and multi-objective > > > > optimization. More broadly, Pareto coevolution can be seen as a set > > of > > > > concepts and class of algorithms which make the connection > > explicit. There > > > > has been quite a bit of work on this topic recently, including my > > own > > > > dissertation as well as a recent book chapter I co-authored with > > Edwin de > > > > Jong for a new book on Multi-objective Problem Solving from > > Nature. Of > > > > course I have a vested interest in seeing the connections between > > coev and > > > > MOO made as strong as possible Still, I think any approach to coev > > could > > > > benefit by taking account of recent theoretical advances.
> > > > Regarding a competition, I think tic-tac-toe is a good challenge > > problem > > > > because:
> > > > (a) it's a small game with simple, known minimax strategy, giving a > > > > benchmark for progress
> > > > (b) it has a small, easily enumerable set of board configurations, > > allow > > > > strategies to be written out explicitly and examined critically
> > > > (c) there's a nice history of work on tic-tac-toe, starting with > > Michie's > > > > MENACE, through Susan Epstein's Hoyle system, to more recent work in > > coev
> > > > (d) it's proven to be particularly challenging for coevolutionary > > algorithms > > > > for some as-yet-obscure reason. some attempts, like Pete > > Angeline's, never > > > > resulted in optimal strategies (though he made the problem harder > > than it > > > > needed to be, as he was exploring other questions than finding > > optima). > > > > others, like Rosin's, required specially-designed representations > > and a huge > > > > number of evaluations before optimal solutions were found.
> > > > Even modern coevolutionary algorithms like Sevan's Nash memory tend > > to have > > > > trouble with tic-tac-toe. I have some thoughts on why this is, but > > it's > > > > very much an open question how we could get coevolution to > > efficiently find > > > > optimal tic-tac-toe strategies. A metric of success would be the > > ability to > > > > evolve optimal players using fewer evaluations than Rosin did and a > > weaker > > > > representation -- that'd be a publishable result, it seems to me.
> > > > The CA majority problem isn't a bad choice either, as there is also > > a good > > > > history of work on it (including Sevan's). I personally prefer > > tic-tac-toe, > > > > though.
> > > > Anthony
> > > > On 7/25/07, phi <PhilipHings...@gmail.com> wrote:
> > > > > Hi Paul, everyone
> > > > > Thanks Paul for this very thoughtful and useful report, and for > > > > > organising the meeting at GECCO.
> > > > > I volunteer to organise a similar meeting at CEC. Perhaps those > > > > > interested could reply to me.
> > > > > One concrete suggestion to make the foundations of coevolutionary > > > > > algorithms more widely considered (in particular, > > > > > better known to IEEE people, if there is such a concept!) might be > > a > > > > > special issue of IEEE TEC on coevolution. Any > > > > > volunteers for guest editors?
> > > > > I've noticed quite a few papers published in TEC or in IEEE > > > > > conferences that use coevolution. Games is one area where > > > > > coevolution seems to be a natural approach. Another active area > > > > > recently is various new coevolution-based multi-objective > > > > > optimisation algorithms. I would personally like to see this work > > take > > > > > more account of proper foundations.
> > > > > The competitions idea is also a good one. CEC does indeed have a > > > > > competitions program. In fact, I am responsible for > > > > > EC competitions at next year's WCCI in Hong Kong, and would > > welcome a > > > > > coevolution-based competition proposal. > > > > > The call for proposals may be found on the conference home page at > > > > >http://www.wcci2008.org/index.htm .
> > > > > > As readers of this forum know, I attempted to collect a group of > > > > > > people to discuss some of the issues raised in a recent thread > > on this > > > > > > website about the Coevolution Task Force itself. This attempt > > was > > > > > > only marginally successful: Despite the post here and on the > > GECCO > > > > > > wiki, interest in such a discussion was modest.
> > > > > > Nevertheless, a few of us did sit down to talk about the
|
