Dices genetic

gen_dice.cpp

#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;
}