Skip to content

Instantly share code, notes, and snippets.

@Randl
Created August 1, 2015 19:20
Show Gist options
  • Save Randl/6a04760abb9994f28b29 to your computer and use it in GitHub Desktop.
Save Randl/6a04760abb9994f28b29 to your computer and use it in GitHub Desktop.
Dices genetic
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>
#include <random>
#include <string>
#include <sstream>
using namespace std;
const int sides = 6;
const int pop_size = 25;
const int min_v = -10, max_v = 100, sum_v = 60;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> dist(0,sides-1);
int from_string(string &s) {
stringstream ss(s);
int result;
ss >> result;
return result;
}
struct dice {
array<short, sides> values;
double f;
dice() {
values = {0, 0, 0, 0, 0, 0};
f = 0.0;
}
dice(array<short, sides> v): values(v), f(0) {}
dice(const dice& d): values(d.values), f(d.f) {}
dice(string s) {
int i = 0, c = 0;
while(i < s.size() && c < sides) {
if (s[i]=='[') {
++i;
string tmp = "";
while (s[i] != ']') {
tmp += s[i];
++i;
}
values[c] = from_string(tmp);
values[c] = values[c] > min_v ? (values[c] < max_v ? values[c] : max_v) : min_v;
++c;
}
++i;
}
if (accumulate(values.begin(), values.end(), 0) != sum_v) {
values.fill(0);
for(int i = 0; i < sides-1; ++i)
values[i] = sum_v/sides;
values[sides-1] = sum_v - accumulate(values.begin(), values.end(), 0);
}
f = 0.0;
}
dice& operator=(const dice& d) {
values=d.values;
f = d.f;
return *this;
}
};
std::ostream &operator<<(std::ostream &os, dice const &d) {
for (int i = 0; i < sides; ++i)
os << "[" << d.values[i] << "]";
return os;
}
bool operator>(const dice& d1, const dice& d2) {
return d1.f > d2.f;
}
bool operator<(const dice& d1, const dice& d2) {
return d1.f < d2.f;
}
bool operator==(const dice& d1, const dice& d2) {
return d1.values == d2.values;
}
vector<dice> testing_pop;
double winning_prob(const dice d1, const dice d2) {
const int win_score = 100, run_n = 1000;
int sc1=0, sc = 0;
for (int i = 0; i < run_n; ++i) {
int score1 = 0, score2 = 0;
while(score1 < win_score && score2 < win_score) {
int a1 = dist(gen), a2 = dist(gen);
int res = d1.values[a1] - d2.values[a2];
if (res > 0)
score1 += res;
else
score2 -= res;
}
++sc;
if (score1 > win_score)
++sc1;
}
return (double)sc1/sc;
}
double fitness(dice d, vector<dice> test) {
double score = 0;
for (auto it = test.begin(); it != test.end(); ++it)
score += winning_prob(d, *it);
score /= test.size();
return score;
}
void fill_tp(vector<dice>& test) {
test.push_back(dice("[-10][-10][-10][-10][0][100]"));
test.push_back(dice("[-9][-9][-9][-9][-4][100]"));
test.push_back(dice("[0][0][0][15][15][30]"));
test.push_back(dice("[10][10][10][10][10][10]"));
test.push_back(dice("[3][5][9][11][15][17]"));
test.push_back(dice("[1][5][11][11][11][21]"));
test.push_back(dice("[-10][-10][20][20][20][20]"));
test.push_back(dice("[8][8][10][11][11][12]"));
test.push_back(dice("[-7][1][1][6][27][32]"));
test.push_back(dice("[0][0][0][0][60][0]"));
test.push_back(dice("[11][11][11][11][11][5]"));
test.push_back(dice("[5][5][-10][-10][20][50]"));
test.push_back(dice("[25][20][15][10][0][-10]"));
test.push_back(dice("[-10][-10][-10][-10][50][50]"));
test.push_back(dice("[20][30][20][10][-10][-10]"));
test.push_back(dice("[-10][14][14][14][14][14]"));
test.push_back(dice("[50][50][-10][-10][-10][-10]"));
test.push_back(dice("[1][1][1][1][1][55]"));
test.push_back(dice("[61][-1][-10][-10][18][2]"));
test.push_back(dice("[13][13][13][13][13][-5]"));
test.push_back(dice("[25][10][10][10][5][-10]"));
test.push_back(dice("[30][-10][30][-10][30][-10]"));
test.push_back(dice("[2][2][2][2][2][50]"));
test.push_back(dice("[-10][0][17][17][18][18]"));
test.push_back(dice("[-6][-6][-6][-6][53][31]"));
test.push_back(dice("[30][30][30][-10][-10][-10]"));
test.push_back(dice("[20][15][10][5][5][5]"));
test.push_back(dice("[-10][8][14][15][16][17]"));
test.push_back(dice("[-10][2][26][14][16][12]"));
test.push_back(dice("[-10][-9][-8][47][29][11]"));
test.push_back(dice("[10][10][10][10][11][9]"));
test.push_back(dice("[9][11][9][11][9][11]"));
test.push_back(dice("[39][33][-3][-3][-3][-3]"));
test.push_back(dice("[4][8][15][16][23][-6]"));
test.push_back(dice("[90][10][-10][-10][-10][-10]"));
test.push_back(dice("[27][27][27][-7][-7][-7]"));
test.push_back(dice("[-9][-9][15][21][21][21]"));
test.push_back(dice("[7][8][9][11][12][13]"));
test.push_back(dice("[44][11][4][1][0][0]"));
test.push_back(dice("[-10][12][12][12][12][12]"));
test.push_back(dice("[-5][5][0][20][20][20]"));
test.push_back(dice("[-1][-1][-1][-1][0][64]"));
test.push_back(dice("[12][12][12][12][6][6]"));
test.push_back(dice("[-8][-8][10][22][22][22]"));
test.push_back(dice("[-8][-8][-8][-8][-8][100]"));
test.push_back(dice("[100][-8][-8][-8][-9][-7]"));
test.push_back(dice("[7][13][11][9][5][15]"));
test.push_back(dice("[-10][14][14][14][8][20]"));
test.push_back(dice("[-10][-10][21][19][19][21]"));
test.push_back(dice("[9][10][11][9][10][11]"));
test.push_back(dice("[0][1][2][5][13][38]"));
test.push_back(dice("[-9][1][11][13][21][23]"));
test.push_back(dice("[-10][10][45][-10][20][5]"));
test.push_back(dice("[11][11][11][11][11][5]"));
test.push_back(dice("[6][9][4][20][21]"));
test.push_back(dice("[25][25][5][5][5][-5]"));
test.push_back(dice("[3][5][7][11][17][17]"));
test.push_back(dice("[0][20][20][0][20][0]"));
test.push_back(dice("[8][12][10][10][10][10]"));
test.push_back(dice("[10][-10][20][-20][30][30]"));
test.push_back(dice("[28][38][14][0][-10][-10]"));
test.push_back(dice("[16][6][20][-5][32][-9]"));
test.push_back(dice("[27][27][27][-7][-7][-7]"));
test.push_back(dice("[-9][5][15][16][16][17]"));
test.push_back(dice("[40][40][-10][-10][0][0]"));
test.push_back(dice("[5][27][3][11][7][7]"));
test.push_back(dice("[-9][-9][20][20][20][18]"));
test.push_back(dice("[-9][-4][-2][5][8][62]"));
test.push_back(dice("[4][6][10][11][14][15]"));
test.push_back(dice("[25][15][15][15][0][-10]"));
test.push_back(dice("[10][-5][20][-10][30][15]"));
test.push_back(dice("[-10][-10][-10][-9][1][98]"));
test.push_back(dice("[0][0][10][13][17][20]"));
test.push_back(dice("[9][10][15][9][5][12]"));
test.push_back(dice("[3][5][7][11][13][21]"));
test.push_back(dice("[-10][-9][-8][30][29][28]"));
test.push_back(dice("[-10][-10][20][20][20][20]"));
test.push_back(dice("[-10][6][16][16][16][16]"));
test.push_back(dice("[-9][10][14][14][14][17]"));
test.push_back(dice("[14][14][14][19][9][-10]"));
}
dice generate_dice() {
int mx = max_v, mn = min_v;
dice d;
int sum = 0;
for (int i = 0; i < sides - 1; ++i) {
uniform_int_distribution<int> val(mn, mx);
d.values[i] = val(gen);
if (d.values[i] < min_v || d.values[i] > max_v) {
cout << "s: " << sum << ", m: " << mn << "," << mx << "v: " << d.values[i] << endl;
int x;
cin >>x;
}
sum += d.values[i];
mn = max((sum_v - sum) - max_v * (sides - i - 2), min_v);
mx = min((sum_v - sum) - min_v * (sides - i - 2), max_v);
}
d.values[sides-1] = sum_v - accumulate(d.values.begin(), d.values.end(), 0);
return d;
}
void generate_population(array<dice, pop_size>& pop) {
for (int i = 0; i < pop_size; ++i)
pop[i] = generate_dice();
}
array<dice, pop_size> mutate(array<dice, pop_size> old_pop) {
geometric_distribution<int> ch(1.0/(pop_size));
array<dice, pop_size> mutants;
for (int i = 0; i < pop_size; ++i) {
int m = ch(gen);
m = m > pop_size - 1 ? pop_size - 1 : m;
uniform_int_distribution<int> genes(0, sides-1);
int g1 = genes(gen), g2 = genes(gen);
while (g2==g1)
g2 = genes(gen);
int sum = old_pop[m].values[g1] + old_pop[m].values[g2];
int mn = max(min_v, sum - max_v);
int mx = min(max_v, sum - min_v);
uniform_int_distribution<int> val(mn, mx);
int new_gene = val(gen);
mutants[i]=old_pop[m];
mutants[i].values[g1] = new_gene;
mutants[i].values[g2] = sum - new_gene;
}
return mutants;
}
array<dice, pop_size> gen_children(array<dice, pop_size> old_pop) {
geometric_distribution<int> ch(1.0/(pop_size));
array<dice, pop_size> children;
for (int i = 0; i < pop_size; ++i) {
int p1, p2;
p1 = ch(gen);
p1 = p1 > pop_size - 1 ? pop_size - 1 : p1;
p2 = ch(gen);
p2 = p2 > pop_size - 1 ? pop_size - 1 : p2;
while (p2==p1) {
p2 = ch(gen);
p2 = p2 > pop_size - 1 ? pop_size - 1 : p2;
}
uniform_real_distribution<double> parts(0.3, 0.7);
double fath_p = parts(gen);
array<short, sides> *father = &old_pop[p1].values, *mother = &old_pop[p2].values;
int sum = 0, mn = min_v, mx = max_v;
for(int j = 0; j < sides - 1; ++j) {
int gene = (int)((double)(*father)[j] * fath_p + (double)(*mother)[j] * (1-fath_p));
gene = gene < mn ? mn : gene > mx ? mx : gene;
children[i].values[j]=gene;
sum += gene;
mn = max((sum_v - sum) - max_v * (sides - j - 2), min_v);
mx = min((sum_v - sum) - min_v * (sides - j - 2), max_v);
}
children[i].values[sides-1] = 0;
children[i].values[sides-1] = sum_v - accumulate(children[i].values.begin(), children[i].values.end(), 0);
}
return children;
}
array<dice, pop_size> next_g(array<dice, pop_size> old_pop) {
array<dice, pop_size> mutants, children, new_pop;
mutants = mutate(old_pop);
children = gen_children(old_pop);
double chance = 1.0 / pop_size;
uniform_real_distribution<double> ch(0, 1);
int m_num = pop_size / 6, ch_num = pop_size / 6, top_num = pop_size / 7, else_num = pop_size - m_num - ch_num - top_num;
int count = 0;
for (int i = 0; i < m_num; ++i) {
bool chosen = false;
vector<int> inside;
int j = 0;
while (!chosen)
if (ch(gen) < chance && find(inside.begin(), inside.end(), j) == inside.end()) {
new_pop[count] = mutants[j];
inside.push_back(j);
chosen = true;
++count;
} else if (j < pop_size - 1)
++j;
else
j = 0;
}
for (int i = 0; i < ch_num; ++i) {
bool chosen = false;
vector<int> inside;
int j = 0;
while (!chosen)
if (ch(gen) < chance && find(inside.begin(), inside.end(), j) == inside.end()) {
new_pop[count] = children[j];
inside.push_back(j);
chosen = true;
++count;
} else if (j < pop_size - 1)
++j;
else
j = 0;
}
for (int i = 0; i < top_num; ++i) {
new_pop[count] = old_pop[i];
++count;
}
for (int i = 0; i < else_num; ++i) {
new_pop[count] = generate_dice();
++count;
}
for (int i = 0; i < pop_size; ++i)
for (int j = i + 1; j < pop_size; ++j)
if (new_pop[i] == new_pop[j]) {
new_pop[j] = generate_dice();
i = 0;
break;
}
return new_pop;
}
int main() {
const int num_g = 20000;
array<dice, pop_size> population;
generate_population(population);
// population[0] = dice("[10][10][10][10][10][10]");
fill_tp(testing_pop);
for (int i = 0; i < num_g; ++i) {
for (int i = 0; i < pop_size; ++i)
population[i].f = fitness(population[i], testing_pop);
sort(population.begin(), population.end());
reverse(population.begin(), population.end());
cout << "-----------------\nPopulation " << i << endl;
for (int i = 0; i < pop_size; ++i) {
cout << population[i] << ": " << population[i].f << endl;
}
population = next_g(population);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment