i'm working on a new opensource project now: "Swarm War

happyjack27 · Post by **happyjack27** » Wed Dec 28, 2011 6:27 pm

from the people (err... person, rather) who brought you "EM-nbody", now there's new "Swarm Wars"! A violent video game with crappy graphics and no actual game-playing as of yet!

https://sourceforge.net/projects/swarmwars/

https://sourceforge.net/p/swarmwars/wiki/Home/

i'm developing it in Java. would be nice to at some point run the AI system on a GPGPU. could probably get at least an order of magnitude speed increase from that. but for now just getting a playable game is a big enough project in itself. i can always port a section of the code over later.

happyjack27 · Post by **happyjack27** » Wed Dec 28, 2011 6:48 pm

...also i have a new idea to improve the learning rate (of complex tasks) of recurrent neural nets while simultaneously reducing the computational complexity time. i'm going to use it in the swarm AI and i'm itching to try it out and see how it works!

these may very well turn out to be the smartest little virtual organisms ever sold! err... open-sourced, rather.

GIThruster · Post by **GIThruster** » Wed Dec 28, 2011 8:15 pm

Why would you spend your time making an open source game, when there is such a huge market for cheezy web browser and smart phone games.

If you have the skills to make money coding a game, why give the fruits of your labor away for free?

happyjack27 · Post by **happyjack27** » Wed Dec 28, 2011 8:37 pm

GIThruster wrote:Why would you spend your time making an open source game, when there is such a huge market for cheezy web browser and smart phone games.

If you have the skills to make money coding a game, why give the fruits of your labor away for free?

i do make money as a programmer - 'tis my job 5 days a week. thou one could argue i'm practically giving my skills away for free there, but that's another story...

this here, is a labor of love. and i think the AI is pretty sophisticated. i've never seen anyone combine swarm intelligence + ant colony optimization + genetic evolution + neural nets + back propagation, nonetheless have an evolving reward vector or plasticity matrix for the back-propagation, or do my new trick to reduce the computational time complexity of back-propagation.

so this is going to be a sort of an academic treasure-trove of AI techniques. and I take pleasure in making them available to the world in a clear and well organized framework, that visually shows the results of how they can work together in an entertaining way.

it's an educational resource, both for the end user and the programmer. the goal is to make people smarter. and do something fun to fill my free time.

and frankly i'm not sure the game will be all that fun. it's too automatic. the game plays itself for you, and it constantly gets better at it. the surest path to victory is just to let the AI do all the playing for you. and that's no fun because then you're not doing anything.

you should watch these things go. they learn and play really fast, and i've only activated like 10% of their AI so far, and i haven't even implemented back-propagation yet. i can tell they will simply devastate. nothing for a human to do.

quixote · Post by **quixote** » Thu Dec 29, 2011 7:58 am

If you're interested in opencl in java, there's JavaCL. From your previous work I know you're most familiar with CUDA, so you could also give jcuda a whirl.

I can't speak for javacl, but jcuda worked ok for me when I was doing some extremely basic poc work during an evaluation of amazon's gpu cluster nodes.

happyjack27 · Post by **happyjack27** » Sat Dec 31, 2011 6:03 pm

at the point of implementing learning in the neural nets.
i was thinking it would be supervised learning, but it's unsupervised learning! ahh! makes the problem harder. i think i got a method figured out now though, based on "temporal difference learning". a few details i got to work out in my head though.

this might actually turn out to be smarter than i first anticipated. though activating learning - which is only partially complete, has already halved the frame rate, so we'll see.

i'm keeping the computational complexity time low, but even o(n) is slow for large o's and large n's. they may be very smart, but at they are also slow. and you don't picture swarms as slow-moving. besides, the learning rate and evolution rate are ultimately proportional to the rate of sim time.

on another note, i have a new idea i called "quantum neural nets" until i looked that up and found there already is such a thing. mine is different though. in it, you represent the neural net as a probability field of neural nets. the probability field is stored as a covariance matrix, which is actually stored as its eigenvalues and eigenvectors. (this way updates and selections can be done in much lower computational complexity time.) and then the matrix is updated via CMA-ES after each data point, rather than each generation of the organism. furthermore, you could share the CMA-ES among multiple organisms, thus improving its convergence.

so really each time step you're replacing the creatures brain with an entirely new one selected from the cma-es's virtual population, while maintaining the values of any internal state variables. so its "memories" remain the same, but its brain structure is determined by an evolving quantum field.

it obviously has a considerably higher computational cost. but the idea is that insofar as the brain is electromagnetic, it really operates via quantum fields, and there's probably constructive and destruction interference among the fields which make it really more like a covariance matrix -- you know, something that you'd do orthogonal decomposition on to get the independant components of the field. and the collapse of the wave function is a selection from that matrix. so it's a model that may be more biologically accurate, considering that a quantum field description is more physically accurate than a particle-based description.

happyjack27 · Post by **happyjack27** » Thu Jan 05, 2012 10:36 pm

thinking of how to reduce the cpu load for the n x n organism interactions, came up w/a new datastructure, that could potentially reduce n x n spatial problems (such as, oh, polywell simulations?) to nearly O(n)! got to write it up and try it out. see what happens when you let your curiosity take you where it leads you?

ScottL · Post by **ScottL** » Fri Jan 06, 2012 12:35 am

happyjack27 wrote:thinking of how to reduce the cpu load for the n x n organism interactions, came up w/a new datastructure, that could potentially reduce n x n spatial problems (such as, oh, polywell simulations?) to nearly O(n)! got to write it up and try it out. see what happens when you let your curiosity take you where it leads you?

Spatial weight matrix of some sort?

hanelyp · Post by **hanelyp** » Fri Jan 06, 2012 2:31 am

If interaction is strictly local, a spacial index of entities can help a lot. For mid range interaction that can tolerate some lag, I've experimented with a model roughly based on diffusion.

happyjack27 · Post by **happyjack27** » Fri Jan 06, 2012 1:42 pm

sort of like a quadtree ( http://en.wikipedia.org/wiki/Quadtree ). or for the 3-d case, octree. ( http://en.wikipedia.org/wiki/Octree ). but it's really more of a multi-scalar grid, as it's a static datastructure as opposed to a dynamic one like a tree. when a particle moves it only has to read and update a few cells in each layer of the quad/oct tree for the coordinates it's at. (i'm going w/9-center and 8 surrounding.) so the computation time is proportional to the number of particles times the logarithm of the spatial resolution. so yeah, factor out the spatial resolution and it's _precisely_ O(n). for example, reading the value of a scalar at coordinates x,y is something like: sum{level = 1 to max} {2^(-level)*(value[level][x/2^level][y/2^level]-value[level-1][x/2^(level-1)][y/2^(level-1)])}. so you see the time to read a scalar field is directly proportional to the number of levels, which is proportional to the logarithm of the resolution. and reading a gradient would just be a constant multiple of the time to read a scalar.

so yeah, a combination of spatial indexing and spatial weight matrix. a collection of spatial weight matrices at exponentially telescoping scales.

part of the idea is that the resolution of the grids decays proportionally to the how much a particle that far away would be weighted. this way you maximize the self-entropy, and thus information density, of the grids. a nice elegant effect is that a 2-d grid at half the resolution is going to have 4 times the number of particles it covers on average, so as you see as the weight of the grid scales down, the particle count scales up, compensatoraly. (is that even a word?) the recursive telescoping of the grid scales reflects the diminishing interaction of particles further away from each other. at each higher scale level, you're dropping bits of spatial information (by using a lower resolution) at a rate proportional to the loss in significance of that information, given that the particle is further away.

a rather elegant solution, imo.

seedload · Post by **seedload** » Fri Jan 06, 2012 2:31 pm

With your experience in AI and my experience in OpenGL and Android game development and Skipjack's artistic ability and 3D modelling skills, we could probably whip up a pretty great Android game.

happyjack27 · Post by **happyjack27** » Fri Jan 06, 2012 2:57 pm

oh yeah, and the scaling function for the collection of grids can be arbitrarily chosen to exactly match the scaling function of the interacting force. i.e. it need not be an exponentially telescoping grid, it can be whatever it needs to be to make it so that on average each scale-level of the grid has about the same contribution to the final scalar (or gradient) value of the field at each sample point.

happyjack27 · Post by **happyjack27** » Fri Jan 06, 2012 2:59 pm

seedload wrote:With your experience in AI and my experience in OpenGL and Android game development and Skipjack's artistic ability and 3D modelling skills, we could probably whip up a pretty great Android game.

well i'll be happy to add anyone as a member to the swarm wars repository, if that interests you. the subversion (versioning system) is broken right now, though, so i suppose there's really no point.

and andriod screen size might be too small for it.

happyjack27 · Post by **happyjack27** » Fri Jan 06, 2012 3:25 pm

these are the graphics right now:

https://sourceforge.net/p/swarmwars/screenshot/sw2.PNG

not all that bad, but not all that good, either. and i have quite the todo list:

https://sourceforge.net/p/swarmwars/wiki/Home/

happyjack27 · Post by **happyjack27** » Fri Jan 06, 2012 4:11 pm

I call it "Proportional Entropy Telescoping Multi-Scalar Grid", or "PetSalt".