<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Genetic approach to artificial intelligence in gaming
Introduction
In this training, I want to focus on the algorithm and not on its performance, this will be for a later study-case.
Artificial intelligence has always been present in games, so the player can play even alone.
Finding some complex problems to solve shouldn't be a hard task.
Let's take a real game and try to make an artificial intelligence which solves the game.
I choosed a french TV game "Le compte est bon". Let's explains the rules
Step1:  Now, we need to generate our population, this means for each candidate we will generate random DNA 
Step2:  Now, we would like to score our population 
Step3:  If we are lucky, we have found the solution on the first generation. But it is unlikely on more complex problems.
For the fun lets make some stats of the generation
Step4:  Now that we have our first generation and we know what it looks like, we can proceed to selection.
Selection implementation
If we just generate a new random population, our algorithm would be nothing else than a bruteforce.
The selection step makes everything. So how do we proceed ?
After a few runs, it looks like the distance from the goal grows slowly except a very few number of with an enormous distance due to random.
This is good! This means we have a lot of interesting solutions.
Let's try the following approach for selection 
Step5:  Combination and mutation, creating the next generation
In this part, we will parse the DNA code of each candidates of s1 in order to build the tree.
Because it is a simple calcul, it is also a valid Python code. We could use the library RedBaron, lets import it
Step6:  Now we need to parse a pair of candidates, in order to return a new one. How do we proceed ?
I suggest that 
Step7:  Now that we are able to generate a child from two parents, let's make our couples
Step8:  And generate our new population
Step9:  The whole process
<ASSISTANT_TASK:>
Python Code:
import random
elements = list(range(1, 11)) * 2 + [25, 50, 75, 100]
game = random.sample(elements, 6)
goal = random.randint(100, 999)
print goal, ':', game
Explanation: Genetic approach to artificial intelligence in gaming
Introduction
In this training, I want to focus on the algorithm and not on its performance, this will be for a later study-case.
Artificial intelligence has always been present in games, so the player can play even alone.
Finding some complex problems to solve shouldn't be a hard task.
Let's take a real game and try to make an artificial intelligence which solves the game.
I choosed a french TV game "Le compte est bon". Let's explains the rules:
a goal number is randomly choosen between 100 and 999
6 numbers are randomly choosen from the set : [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100]
with only the basic integer operations + - * / and the 6 numbers, you have to find the goal number
each of the 6 numbers can only be used once
Example
goal number: 247
set : [3, 5, 7, 100, 25, 1]
solution :
3 * 7 = 21
5 * 25 = 125
125 + 21 = 146
146 + 100 = 246
246 + 1 = 247
We can represent the whole calcul in one line : (3 * 7) + (5 * 25) + 100 + 1
Which can also be represented as a tree :
+
 / \
1   +
   / \
 100  +
     / \
    /   \
   *     *
  / \   / \
 3  7   5  25
Where genetics can help us
About genetic programming
Genetic programming consists on applying the rules of genetic evolution to our algorithm.
On a random population, we determine which candidate solves the problem the best.
This step is called evaluation.
The next step is to select the candidates that will be the parents of the next generation. This step is called selection.
We select random parts of both parents DNA to build a new one, and then apply a random mutation so the new candidate is unique.
We repeat this process until we have a new population to evaluate.
The most important part is in the selection step. Once we scored each candidate in the evaluation step we obviously must select the bests to make sure the next generation is closer to the answer.
But building an elite will prevents DNA diversity and the population could never find the solution.
It is important also to include less good candidate, as they can carry intersting genes to pass.
Example
Lets say we have randomly generated a set of tree :
*              *           
 / \            / \          
1   -          7   +         
   / \            / \        
 100  +         100  +       
     / \            / \      
    /   \          /   \     
   +     /        -     /    
  / \   / \      / \   / \   
 3  7  25  5    3  25 5   1
Those tree could represent the DNA of our population. Genes would be each operators and links to the leafs.
We can easily select part of each tree to insert into a new one as in DNA combination.
Then randomly change an operator or switch leafs as in random mutation.
Evaluation would consist on parsing the tree, and get the distance to the goal number : abs(goal - tree_result).
The first generation
First, we need to generate the game :
End of explanation
# the DNA is just the calcul in a string
def random_dna(game):
    # we want random links to node, so we need to shuffle the game
    game_shuffled = list(game)
    random.shuffle(game_shuffled)
    
    # let start with an empty dna
    dna = ''
    i = 0
    while i < len(game_shuffled):
        try_dna = dna
        if i > 0:
            try_dna += random.choice([' * ', ' / ', ' + ', ' - '])
        
        try_dna += str(float(game_shuffled[i]))
        
        # we check that the result is still an int before recording the random gene
        check_result = eval(try_dna)
        if check_result == int(check_result):
            dna = try_dna
            i += 1
    
    return dna
    
test_dna = random_dna(game)
test_res = eval(test_dna)
assert test_res == int(test_res)
population_size = 1000
def first_generation(population_size=1000):
    return [random_dna(game) for _ in range(population_size)]
population = first_generation(population_size)
print 'Test:', test_dna, '=', test_res
print 'Population Size:', population_size
print 'Population:'
for dna in population[:5]:
    print '->', dna, ' = ', eval(dna)
print '-> ...'
for dna in population[-5:]:
    print '->', dna, ' = ', eval(dna)
Explanation: Now, we need to generate our population, this means for each candidate we will generate random DNA :
End of explanation
def score(dna):
    return abs(goal - eval(dna))
scored_population = sorted([(dna, score(dna)) for dna in population], key=lambda item: item[1])
def show_scored_population(scored_population):
    for dna, score in scored_population[:5]:
        print '->', dna, ' = ', eval(dna), '\t|', score
    print '-> ...'
    for dna, score in scored_population[-5:]:
        print '->', dna, ' = ', eval(dna), '\t|', score
show_scored_population(scored_population)
Explanation: Now, we would like to score our population :
End of explanation
from collections import OrderedDict
import math
def generation_stats(generation):
    scores = [c[1] for c in generation]
    
    stats = OrderedDict((
        ('avg', float(sum(scores)) / len(scores)),
        ('min', min(scores)),
        ('max', max(scores)),
        ('stdev', None),
        ('q1', None),
        ('med', None),
        ('q3', None)
    ))
    
    variance = float(sum([(s - stats['avg'])**2 for s in scores])) / len(scores)
    stats['stdev'] = math.sqrt(variance)
    
    q1idx = len(scores) / 4
    stats['q1'] = scores[q1idx]
    
    q3idx = 3 * len(scores) / 4
    stats['q3'] = scores[q3idx]
    
    if len(scores) % 2 == 0:
        i1idx = len(scores) / 2
        i2idx = i1idx + 1
        
        i1, i2 = scores[i1idx], scores[i2idx]
        stats['med'] = (i1 + i2) / 2
    
    else:
        medidx = len(scores) / 2 + 1
        stats['med'] = scores[medidx]
    return stats, scores
def plot_stats(stats, scores, gen=0):
    rows = zip(*stats.items())
    dim = [0.05, 0.80, 0.9, 0.15]
    # Figure 1: min avg/q3 max color graph
    fig1 = plt.figure(figsize=(18, 3))
    a1x = fig1.add_axes(dim)
    cmap1 = matplotlib.colors.ListedColormap(['g', 'b', 'r'])
    bounds1 = [
        stats['min'],
        min(stats['q3'], stats['avg']),
        max(stats['q3'], stats['avg']),
        stats['max']
    ]
    norm1 = matplotlib.colors.BoundaryNorm(bounds1, cmap1.N)
    cbl1 = matplotlib.colorbar.ColorbarBase(
        a1x,
        cmap=cmap1, norm=norm1,
        spacing='proportional',
        orientation='horizontal'
    )
    # Figure 2: min q1 med q3 color graph
    fig2 = plt.figure(figsize=(18, 3))
    a2x = fig2.add_axes(dim)
    cmap2 = matplotlib.colors.ListedColormap(['g', 'b', 'y'])
    bounds2 = [stats['min'], stats['q1'], stats['med'], stats['q3']]
    norm2 = matplotlib.colors.BoundaryNorm(bounds2, cmap2.N)
    cbl2 = matplotlib.colorbar.ColorbarBase(
        a2x,
        cmap=cmap2, norm=norm2,
        spacing='proportional',
        orientation='horizontal'
    )
    a1x.set_xticklabels([
        'min',
        'avg' if stats['avg'] <= stats['q3'] else 'q3',
        'avg' if stats['avg'] > stats['q3'] else 'q3',
        'max'
    ])
    a2x.set_xticklabels(['min', 'q1', 'med', 'q3', 'max'])
    # Figure 3: scores line chart
    fig3, a3x = plt.subplots()
    a3x.plot(scores)
    a3x.grid(True)
    a3x.set_ylabel('Score')
    a3x.set_xlabel('Candidate')
    a1x.set_title('Generation: {0}'.format(gen))
    plt.show()
stats1, scores1 = generation_stats(scored_population)
print json.dumps(stats1, indent=2)
plot_stats(stats1, scores1)
Explanation: If we are lucky, we have found the solution on the first generation. But it is unlikely on more complex problems.
For the fun lets make some stats of the generation:
End of explanation
def selection(generation, stats):
    parents = []
    
    q1 = filter(lambda c: c[1] < stats['q1'], generation)
    q2 = filter(lambda c: stats['q1'] <= c[1] < stats['med'], generation)
    q3 = filter(lambda c: stats['med'] <= c[1] < stats['q3'], generation)
    q4 = filter(lambda c: stats['q3'] <= c[1], generation)
    
    for q in [q1, q2, q3, q4]:
        parents += q[:len(q) / 2]
    
    return parents
s1 = selection(scored_population, stats1)
show_scored_population(s1)
stats_s1, scores_s1 = generation_stats(s1)
print json.dumps(stats_s1, indent=2)
plot_stats(stats_s1, scores_s1)
Explanation: Now that we have our first generation and we know what it looks like, we can proceed to selection.
Selection implementation
If we just generate a new random population, our algorithm would be nothing else than a bruteforce.
The selection step makes everything. So how do we proceed ?
After a few runs, it looks like the distance from the goal grows slowly except a very few number of with an enormous distance due to random.
This is good! This means we have a lot of interesting solutions.
Let's try the following approach for selection : the 50% best candidates of each quartile in this generation.
End of explanation
from redbaron import RedBaron, BinaryOperatorNode, FloatNode
red = RedBaron(s1[0][0])
print 'Example:', s1[0][0]
red.help()
Explanation: Combination and mutation, creating the next generation
In this part, we will parse the DNA code of each candidates of s1 in order to build the tree.
Because it is a simple calcul, it is also a valid Python code. We could use the library RedBaron, lets import it:
End of explanation
def gen_child(parents_dna):
    # reimport things because it will be used in a IPython parallel engine
    from redbaron import RedBaron
    import random
    tmpred = RedBaron(parents_dna[0])
    child = RedBaron(parents_dna[1])
    
    # Choose random operator from parent a
    operators = tmpred.find_all('binary_operator')
    op = random.choice(operators[1:])  # we don't want the root operator
    
    # Find and remove all leafs from child
    nbs = [float(nb.value) for nb in op.find_all('float')]
    
    # mark the nodes as empty
    for node in child.find_all('float'):
        if float(node.value) in nbs:
            if node.parent.first is node:
                node.parent.first.replace('None')
            
            elif node.parent.second is node:
                node.parent.second.replace('None')
    # keep going until nothing is done (which means there is no more empty nodes)
    reparented = True
    while reparented:
        reparented = False
        for node in child.find_all('binary_operator'):
            if node.first.value == 'None' and node.second.value == 'None':
                reparent = 'None'
            elif node.first.value == 'None':
                reparent = node.second.dumps()
            elif node.second.value == 'None':
                reparent = node.first.dumps()
            else:
                continue
            if node.parent.parent is None:
                node.replace(reparent)
                reparented = True
            elif node.parent.first is node:
                node.parent.first.replace(reparent)
                reparented = True
            elif node.parent.second is node:
                node.parent.second.replace(reparent)
                reparented = True
    
    # Combine parents DNA with a mutation: a random operator
    notint = True
    while notint:
        combine = '{0} {2} {1}'.format(
            op.dumps(),
            child[0].dumps(),
            random.choice(['+', '-', '*', '/'])
        )
        res = eval(combine)
        
        if res == int(res):
            notint = False
    child[0].replace(combine)
    print '.'
    return child.dumps()
child = gen_child((s1[0][0], s1[-1][0]))
test_child = eval(child)
assert test_child == int(test_child)
print child, '=', test_child
Explanation: Now we need to parse a pair of candidates, in order to return a new one. How do we proceed ?
I suggest that :
we copy parent b's DNA into child c
then we choose randomly a BinaryOperatorNode in parent a's DNA and find all FloatNode() it contains
each of thoose nodes are deleted from c's DNA, as well as the useless operators
we insert the choosen BinaryOperatorNode into c's DNA with a new randomly choosen BinaryOperatorNode
Example :
Step 1:
*              *           
 / \            / \          
1   -          7   +         
   / \            / \        
 100 (+)        100  +       
     / \            / \      
    /   \          /   \     
   +     /        -     /    
  / \   / \      / \   / \   
 3  7  25  5    3  25 5   1
Step 2:
```
  *              *         
 / \            / \        
1   -          x   +       
   / \            / \      
 100 (+)        100  +     
     / \            / \    
    /   \          /   \   
   +     /        -     /  
  / \   / \      / \   / \ 
 3  7  25  5    x   x x   1  
/ \            / \        
1   -         100  1       
   / \                     
 100 (+)                   
     / \                   
    /   \                    
/                 
  / \   / \                
 3  7  25  5               
```
Step 3:
*    
    / \   
   +   \  
  / \   \ 
100  1   +                     
        / \                     
       /   \                    
      +     /                   
     / \   / \                  
    3   7 25  5
End of explanation
def make_couples(selected):
    parents = []
    
    for _ in range(4):
        _set = list(selected)
        
        while len(_set) > 1:
            i = random.randrange(0, len(_set))
            a = _set.pop(i)
            i = random.randrange(0, len(_set))
            b = _set.pop(i)
            parents.append((a[0], b[0]))
    
    return parents
Explanation: Now that we are able to generate a child from two parents, let's make our couples:
End of explanation
def new_population(selected, population_size):
    population = []
    couples = make_couples(selected)
    
    while len(population) < population_size:
        parents = random.choice(couples)
        population.append(gen_child(parents))
    
    return population
Explanation: And generate our new population:
End of explanation
def next_generation(population, gen):
    scored_population = sorted([(dna, score(dna)) for dna in population], key=lambda item: item[1])
    show_scored_population(scored_population)
    for i in range(len(scored_population)):
        if scored_population[i][1] == 0:
            print 'WIN:', i, ':', scored_population[i][0]
        
        else:
            break
    stats, scores = generation_stats(scored_population)
    print json.dumps(stats, indent=2)
    plot_stats(stats, scores, gen)
    selected = selection(scored_population, stats)
    return new_population(selected, len(population)), gen + 1
def main(popsize=1000, nsteps=100):
    pop, gen = first_generation(popsize), 0
    while nsteps > 0:
        pop, gen = next_generation(pop, gen)
        nsteps -= 1
main(popsize=10, nsteps=30)
Explanation: The whole process
End of explanation
<END_TASK>