Genetic Algorithms

[mmavipc]

[QUOTE=noctune9;27405988]I'm not saying that, but how is training a neural network not using a genetic algorithm? It's all a bunch numbers being mutated, bred, assigned fitness, etc.[/QUOTE]

AFAIK training a nerual network is assigning an output for an input to a certain artificial neuron. No GA in that.

[s0ul0r]

My first test:
[IMG]http://img39.imageshack.us/img39/9928/ss20110115020649.png[/IMG]

I have keyframes for all the joints ( 15 in count, with 1 second between each of them)
Each keyframe gets a random motor speed for each joint.
Breeding is performed by crossing the keyframes of 2 parents together, mutating with a 10% chance per keyframe.
right now 1 test takes 30 seconds (twice the complete circle of a motion)
I might just let it run throughout the night and see if it gets better.

[Niteshifter]

Someone should make a GA for QWOP :v:

[s0ul0r]

That would actually be quite easy :D
If you could read out the distance...

[mmavipc]

I started work on a spellfinder for magicka, but i got bored.
[cpp]// Genetic Magicka.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <memory.h>
#include <string.h>
#include <math.h>
#include <iostream>

#pragma warning(disable : 4018)
#pragma warning(disable: 4244)

#define SPELL_DAMAGE_EARTH 150
#define SPELL_DAMAGE_ICEEARTH 275
#define SPELL_DAMAGE_ICE 180
#define SPELL_DAMAGE_LIGHTNING 250
#define SPELL_DAMAGE_LIFE -180
#define SPELL_DAMAGE_ARCANE 225
#define SPELL_DAMAGE_FIRE 40
#define SPELL_DAMAGE_COLD 25
#define SPELL_DAMAGE_STEAM 280
#define SPELL_DAMAGE_BARRIER_ICE 275
#define SPELL_DAMAGE_SELF_FIRE 40
#define SPELL_DAMAGE_SELF_EARTH 100
#define SPELL_DAMAGE_SELF_ARCANE 200
#define SPELL_DAMAGE_SELF_ICE 120
#define SPELL_DAMAGE_SELF_STEAM 80
#define SPELL_DAMAGE_SELF_LIGHTNING 80
#define SPELL_DAMAGE_SELF_POISON 50
#define SPELL_STRENGTH_WATER 70

int EARTH = 1, ICE = 0x100, LIGHTNING = 0x10, LIFE = 0x40, ARCANE = 0x20, FIRE = 8, COLD = 4, STEAM = 0x200, WATER = 2;
int STATUSEFFECTS = 0x64e;

enum SpellType
{
SPRAY = 0,
PROJECTILE,
SHIELD,
BEAM,
ST_LIGHTNING,
};
enum CastType
{
NORMAL = 0,
AREA,
WEAPON,
};

SpellType gType;

float ScaleDmg(float iAmount, float iMagnitude)
{
return iAmount * sqrt(iMagnitude);
}

int min(int iMin, int iValue)
{
if(iValue < iMin)
{
return iMin;
}
return iValue;
}

int Fitness(CastType cType, char* spell)
{
SpellType type = SPRAY;
int iWater = 0, iEarth = 0, iLife = 0, iArcane = 0, iFire = 0, iLightning = 0, iCold = 0;
int iIce = 0, iSteam = 0;
int iElements = 0;
int iSpell = 0;
static char *cSpell = new char[5];
static char *cSpellCopy = new char[5];
memset(cSpellCopy, 0, 5);
int csi = 0;
int csiCopy = 0;
int iDamage = 0;
for(int i = 0; i<strlen(spell); i++)
{
switch(spell[i])
{
case 'D':
if(iElements != 5)
{
cSpell[csi] = 'D';
csi++;
iEarth++;
}
iElements++;
if(iLightning)
{
if(iElements != 6)
{
iEarth--;
iLightning--;
iElements-=2;
}
else
{
iLightning--;
iElements--;
}
bool bDGone = false, bAGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(iElements != 5)
{
if(cSpell[j] == 'D' && !bDGone)
{
bDGone = true;
continue;
}
}
if(cSpell[j] == 'A' && !bAGone)
{
bAGone = true;
continue;
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'A':
if(iElements != 5)
{
cSpell[csi] = 'A';
csi++;
iLightning++;
}
iElements++;
if(iEarth || iWater)
{
if(iElements != 6)
{
iLightning--;
iElements-=2;
}
else
{
iElements--;
}
char cRemove = 0;
for(int j = csi; j >= 0; j--)
{
if(cSpell[j] == 'D')
{
cRemove = 'D';
iEarth--;
break;
}
if(cSpell[j] == 'Q')
{
cRemove = 'Q';
iWater--;
}
}
bool bUGone = false, bAGone = false;
csiCopy = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(cSpell[j] == cRemove && !bUGone)
{
bUGone = true;
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'A' && !bAGone)
{
bAGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'W':
if(iElements != 5)
{
cSpell[csi] = 'W';
csi++;
iLife++;
}
iElements++;
if(iArcane)
{
if(iElements != 6)
{
iLife--;
iElements-=2;
}
else
{
iElements--;
}
iArcane--;
bool bWGone = false, bAGone = false;
csiCopy = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(iElements != 5)
{
if(cSpell[j] == 'W' && !bWGone)
{
bWGone = true;
continue;
}
}
if(cSpell[j] == 'A' && !bAGone)
{
bAGone = true;
continue;
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'S':
if(iElements != 5)
{
cSpell[csi] = 'S';
csi++;
iArcane++;
}
iElements++;
if(iLife)
{
iLife--;
if(iElements != 6)
{
iArcane--;
iElements-=2;
}
else
{
iElements--;
}
bool bWGone = false, bAGone = false;
csiCopy = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(cSpell[j] == 'W' && !bWGone)
{
bWGone = true;
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'A' && !bAGone)
{
bAGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'F':
if(iElements != 5)
{
cSpell[csi] = 'F';
csi++;
iFire++;
}
iElements++;
if(iCold)
{
if(iElements != 6)
{
iFire--;
iElements--;
}
iCold--;
iElements--;
bool bFGone = false, bRGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(cSpell[j] == 'R' && !bRGone)
{
bRGone = true;
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'F' && !bFGone)
{
bFGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
else if(iWater || iIce)
{
if(iElements != 6)
{
iFire--;
}
iElements--;
char cRemove = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(cSpell[j] == 'Q')
{
cRemove = 'Q';
iWater--;
iSteam++;
cSpell[j] = 'X';
break;
}
if(cSpell[j] == 'Y')
{
cRemove = 'Y';
iIce--;
iWater++;
}
}
bool bUGone = false, bFGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(cSpell[j] == cRemove && !bUGone)
{
bUGone = true;
if(cRemove == 'Y')
{
cSpellCopy[csiCopy] = 'Q';
csiCopy++;
}
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'F' && !bFGone)
{
bFGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'R':
if(iElements != 5)
{
cSpell[csi] = 'R';
csi++;
iCold++;
}
iElements++;
if(iFire)
{
iFire--;
if(iElements != 6)
{
iCold--;
iElements--;
}
iElements--;
bool bRGone = false, bFGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(iElements != 5)
{
if(cSpell[j] == 'R' && !bRGone)
{
bRGone = true;
continue;
}
}
if(cSpell[j] == 'F' && !bFGone)
{
bFGone = true;
continue;
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
else if(iWater || iSteam)
{
if(iElements != 6)
{
iCold--;
}
iElements--;
char cRemove = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(cSpell[j] == 'Q')
{
cRemove = 'Q';
iWater--;
iIce++;
cSpell[j] = 'Y';
break;
}
if(cSpell[j] == 'X')
{
cRemove = 'X';
iSteam--;
iWater++;
}
}
bool bUGone = false, bRGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(cSpell[j] == cRemove && !bUGone)
{
bUGone = true;
if(cRemove == 'Y')
{
cSpellCopy[csiCopy] = 'Q';
csiCopy++;
}
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'R' && !bRGone)
{
bRGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
case 'Q':
if(iElements != 5)
{
cSpell[csi] = 'Q';
csi++;
iWater++;
}
iElements++;
if(iLightning)
{
if(iElements != 6)
{
iWater--;
iElements--;
}
iLightning--;
iElements--;
bool bQGone = false, bAGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(iElements != 5)
{
if(cSpell[j] == 'Q' && !bQGone)
{
bQGone = true;
continue;
}
}
if(cSpell[j] == 'A' && !bAGone)
{
bAGone = true;
continue;
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
else if(iFire || iCold)
{
if(iElements != 6)
{
iWater--;
}
iElements--;
char cRemove = 0;
for(int j = csi - 1; j >= 0; j--)
{
if(cSpell[j] == 'F')
{
cRemove = 'F';
iFire--;
iSteam++;
cSpell[j] = 'X';
break;
}
if(cSpell[j] == 'R')
{
cRemove = 'R';
iCold--;
iIce++;
cSpell[j] = 'Y';
break;
}
}
bool bUGone = false, bQGone = false;
csiCopy = 0;
for(int j = 0; j < csi; j++)
{
if(cSpell[j] == cRemove && !bUGone)
{
bUGone = true;
continue;
}
if(iElements != 5)
{
if(cSpell[j] == 'Q' && !bQGone)
{
bQGone = true;
continue;
}
}
cSpellCopy[csiCopy] = cSpell[j];
csiCopy++;
}
csi = csiCopy;
memcpy(cSpell, cSpellCopy, csiCopy);
}
if(iElements==6)(iElements=5);
break;
}
}
//iSpell |= i*;
if(iArcane)
{
type = BEAM;
iSpell |= ARCANE;
}
if(iEarth)
{
iSpell |= EARTH;
}
if(iIce)
{
iSpell |= ICE;
}
if(iSteam)
{
iSpell |= STEAM;
}
if(iLightning)
{
type = BEAM;
iSpell |= LIGHTNING;
}
if(iCold)
{
iSpell |= COLD;
}
if(iLife)
{
type = BEAM;
iSpell |= LIFE;
}
if(iFire)
{
iSpell |= FIRE;
}
if(iWater)
{
iSpell |= WATER;
}

if(iEarth || iIce)
{
type = PROJECTILE;
}

switch(type)
{
case PROJECTILE:
break;
switch(cType)
{
case AREA:
if((iSpell & 0x64e) != 0)
{
if((iSpell & (STEAM | FIRE | COLD | WATER)) != 0)
{
iDamage += min(1, iFire)*40;
}
if(iSpell & LIFE)
{
iDamage += ScaleDmg(-80, iLife);
}
}
iDamage += ScaleDmg(SPELL_DAMAGE_FIRE, iFire);
iDamage += ScaleDmg(SPELL_DAMAGE_COLD, iCold);
iDamage += ScaleDmg(SPELL_DAMAGE_STEAM, iSteam);
iDamage += ScaleDmg(SPELL_DAMAGE_LIGHTNING, iLightning);
iDamage += ScaleDmg(SPELL_DAMAGE_BARRIER_ICE, iIce);
iDamage += ScaleDmg(SPELL_DAMAGE_LIFE, iLife);
iDamage += ScaleDmg(SPELL_DAMAGE_ARCANE, iArcane);
break;

case NORMAL:
if(iEarth)
{
iDamage += SPELL_DAMAGE_EARTH * iEarth * iEarth;
iDamage += SPELL_DAMAGE_ICEEARTH * iIce * iIce;
}

if(iIce)
{
iDamage += SPELL_DAMAGE_ICE;
iDamage += ScaleDmg(SPELL_DAMAGE_ARCANE, iArcane);
iDamage += ScaleDmg(SPELL_DAMAGE_LIGHTNING, iLightning);
iDamage += ScaleDmg(SPELL_DAMAGE_LIFE, iLife);
iDamage += ScaleDmg(SPELL_DAMAGE_LIFE, iLife);
break;
}
break;
}
break;
case BEAM:
if(iSpell & 0x64e)
{
if((iSpell & (STEAM | FIRE | COLD | WATER)) != 0)
{
iDamage += min(1, iFire)*40;
}
}
if(iSpell & LIFE)
{
iDamage += ScaleDmg(-80, iLife);
}
iDamage += ScaleDmg(SPELL_DAMAGE_FIRE, iFire);
iDamage += ScaleDmg(SPELL_DAMAGE_COLD, iCold);
iDamage += ScaleDmg(SPELL_DAMAGE_STEAM, iSteam);
iDamage += ScaleDmg(SPELL_DAMAGE_LIGHTNING, iLightning);

iDamage += ScaleDmg(SPELL_DAMAGE_SELF_FIRE, iFire);
iDamage += ScaleDmg(SPELL_DAMAGE_COLD, iCold);
iDamage += ScaleDmg(SPELL_DAMAGE_SELF_STEAM, iSteam);
iDamage += ScaleDmg(SPELL_DAMAGE_SELF_LIGHTNING, iLightning);

iDamage += min(1, iLife)*SPELL_DAMAGE_LIFE;
iDamage += min(1, iArcane)*SPELL_DAMAGE_SELF_ARCANE;

if(iWater)
{
iDamage += SPELL_STRENGTH_WATER * iWater;
}
break;
}

return iDamage;
}

void Evolve(CastType cType, char** &pPop, int iPop)
{
for(int i = iPop/2; i<iPop; i++)
{
memcpy(pPop[i], pPop[i-iPop/2], 11);
int start = rand()%10;
for(int j = start; j<10; j++)
{
int k = rand()%10;
switch(rand()%7)
{
case 0:
pPop[i][k] = 'Q';
break;
case 1:
pPop[i][k] = 'W';
break;
case 2:
pPop[i][k] = 'R';
break;
case 3:
pPop[i][k] = 'A';
break;
case 4:
pPop[i][k] = 'S';
break;
case 5:
pPop[i][k] = 'D';
break;
case 6:
pPop[i][k] = 'F';
break;
}
}
}
int *dmg = new int[iPop];
for(int i = 0; i < iPop; i++)
{
dmg[i] = Fitness(cType, pPop[i]);
}
bool bSorting = true;
while(bSorting)
{
bSorting = false;
for(int i=0; i<iPop-1; i++)
{
if(dmg[i] < dmg[i+1])
{
int dmgtmp = dmg[i];
char* chartmp = pPop[i];
pPop[i] = pPop[i+1];
dmg[i] = dmg[i+1];
pPop[i+1] = chartmp;
dmg[i+1] = dmgtmp;
bSorting = true;
break;
}
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int icType;
std::cout << "Normal = " << NORMAL << ", Area = " << AREA << ", Weapon = " << WEAPON << std::endl;
std::cout << "Cast type: ";
std::cin >> icType;
CastType cType = (CastType)icType;
int iPop = 0;
std::cout << "Population: ";
std::cin >> iPop;
char **pPop = new char*[iPop];
for(int i = 0; i < iPop; i++)
{
pPop[i] = new char[11];
memset(pPop[i], 'A', 10);
pPop[i][10] = 0;
}
//memcpy(pPop[0], "DQRQRQRQRD", 11);
while(true)
{
static unsigned int uiGen = 0;
uiGen++;
Evolve(cType, pPop, iPop);
std::cout << "Generation: " << uiGen << "'s best combo: \"" << pPop[0];
std::cout << "\" DMG: " << Fitness(cType, pPop[0]) << std::endl;
}

system("PAUSE");
return 0;
}

[/cpp]

[HeatPipe]

I doubt anyone will read this code.

[Venice Queen]

My god man, refactor that Fitness function

[sim642]

I think cpp etc. tags should have maximum number of lines that it shows. If some has more than that it makes scrollbar.

[Darwin226]

Cpp tags don't work at all on Chrome 10...
At least not for me.
And when they did on the non-beta version it was some messed up green version that looked like it's padding is wrong.
The one before the forum update worked and looked ok.

[RyanDv3]

You might try reloading the page, sometimes they don't work for me either. (I'm on chrome)

[Randdalf]

[QUOTE=Azur;27388912]Neural networks ARE stupid. Not stupid as in the concept of them, but stupid as in you need a lot of them to do anything remotely interesting and they can forget how to do things if they don't do it for a while.[/QUOTE]

He meant stupid as in the sense that you write all this code to do something, but you can actually just express the desired result of a neural network in differential equations, rather than going through training etc.

[mmavipc]

[QUOTE=Venice Queen;27766608]My god man, refactor that Fitness function[/QUOTE]

I take the, It works, and is fast enough for me, approach to coding.

[Venice Queen]

[QUOTE=mmavipc;27783201]I take the, It works, and is fast enough for me, approach to coding.[/QUOTE]

it works until you want to change something or debug it.

Have fun unit testing that function too!

[mmavipc]

[QUOTE=Venice Queen;27788328]it works until you want to change something or debug it.

Have fun unit testing that function too![/QUOTE]

I had to debug it about 10 times to get it to work right.

Edit: Btw, your avatar is creepy

[Niteshifter]

GA fitness functions:

[img]http://imgs.xkcd.com/comics/genetic_algorithms.png[/img]