|
|
Post by maciej on Aug 25, 2015 9:11:48 GMT -8
Dear GGP fellows, Recently, we have published our survey on what was going on in the GGP and the new GVGP research (V for Video) in years 2011-2014. 2015 is not there due to a long submission process, it was submitted long ago. My sincere apologies if anyone was accidentally omitted. We did not mean to exclude anyone, but we based exclusively on research papers. It is not super detailed, since we cite 90 papers and going into very details with each of them would be unfeasible. Naturally, we have included our work too, because we could ;-) I hope that someone may find it useful e.g. you can show it to people who want to get into GGP. It has been published as open-access, so of course it's free: www.hindawi.com/journals/tswj/2015/986262/Best Regards!
|
|
|
|
Post by alandau on Aug 26, 2015 22:03:32 GMT -8
Thanks to you and your colleagues for all the work to put this together. One of the papers caught my eye, the one suggesting that search focused entirely on novelty may work better than focusing on an objective function for many problems, even when the goal is to maximize that function: eplex.cs.ucf.edu/papers/lehman_ecj10.pdfI find this intuitively satisfying; think about writing an AI for a platformer game. Basically, you have a wide search space (I can be in lots of places with lots of velocities), but only some of those states have interesting properties (I'm on the high ledge) that can be parlayed into other interesting states (I can make the long jump to the right now). The way the tree of exploration gets built out (or the function from original state space to useful state space gets defined?) evens out the search space occupied by these different groups of states, relative to their original numbers in the full state expansion. This feels analogous to our mind creating categories for these different states and assigning more equal amounts of attention to the different categories as we consider our options. (The trick, of course, is figuring out a useful measurement of novelty... I'm still working my way through the paper.) That also reminded me of an article I saw a while back ( fivethirtyeight.com/features/stop-trying-to-be-creative/ ) about a site called Picbreeder that develops images through user-guided evolution, and how selecting for the most unique variants (as opposed to the thing that looks the most like what you're hoping to make it look like) tends to be the best way to produce unexpected and interesting images down the line. And lo and behold -- one of the people behind Picbreeder was an author of that paper. |
|
|
|
Post by Andrew Rose on Aug 28, 2015 5:05:06 GMT -8
Alex, I haven't read the Lehman paper yet, but "Width-based planning for General Video-Game Playing", which appears in the GIGA-15 proceedings, produces an iterated widening based on novelty. IW(1) aggressively prunes the tree such that it only explores states in which a new proposition has become true that hasn't been seen as true before. IW(2) only explores states in which there's a unique pair of propositions that have become true. Etc.. Note that, for a game with N base propositions, IW(1) is an O(N) algorithm, IW(2) is an O(N^2) algorithm, etc.. IW(N) will explore the entire game tree. (The max. branching factor acts as part of the constant factor though, so it still doesn't help with 6-player Guess 2/3rds of the average, but it might be useful for other games.) |
|
|
|
Post by maciej on Aug 28, 2015 12:37:02 GMT -8
Novelty sounds really interesting for me, although currently I am doing something very much different from GGP.
I have found, though, that many nice ideas which work for various domains actually have detrimental effect when implemented in a MCTS/UCT based GGP player. My MINI-Player has always used the so-called Exploration heuristic, among the others, to guide the Monte Carlo phase. The idea was to look at the most differing states to the situation before (defined by a few last visited states => which selected a representant among themselves). It worked for me, especially in the parallelized setup. I have found that the more time a simulation takes the better it scales up with my parallelization. So if I could to improve the simulations somehow but make them slower I would take that.
|
|
