?

Log in

AlbertJayNock

A Quick Pick Generator Written In Python

A few years ago we used python as our introductory programming language, and I needed to learn it. So I started writing lots of python programs in order to familiarize myself with the language, and what started out as a professional obligation quickly became an addiction (when you think about it, it's kind of nice when that happens).

One of the programs I wrote was a genetic algorithm to generate quick picks for powerball. That is, five random numbers plus a powerball pick. I generated the 5 random numbers using a genetic algorithm. For the uninitiated, a genetic algorithm is one that treats candidate solutions as if they were genes in a gene pool and "mutates" them and combines them with each other until a gene emerges that is sufficiently " fit". Fitness is defined as closeness to the desired solution to the problem. (I remember when I first told my mother about genetic algorithms she gave me her "you little scamp" look and asked if i was making it up.)

I did NOT define fitness as a combination more likely to win since, in spite of what the folks hawking lottery systems will try to tell you, all combinations are equally likely. What i did was to make each member of the gene pool a bit string, and define fitness as having exactly five bits equal to one.. The positions of the one bits would then be the lottery pick numbers.

One might ask why I would take such a Rube Goldberg approach to generating quick picks. There were two reasons. The first reason is that I was at least as interested in giving myself a good exercise in python programming as I was in finding lottery numbers.

The second reason has to do with randomness. The random number generators programmiing languages  have do not generate truly random numbers. That is why they are properly called pseudo-random number generators. John Von Neumann once said "Anyone who uses arithmetic methods to produce random numbers is in a state of sin ". That's a bit extreme, but his point  that no algorithm can generate truly random numbers was well made, since after all, there is an underlying algorithm.

But achieving true randomness is like computing the exact value of pi...you can never get there, but you can get as close as you like. Something as complex as a genetic algorithm would get you closer to true randomness. Greater randomness is preferable in lottery picks. You are no more likely to win with a more random selection of numbers, BUT you are less likely to have to share your prize if you do win.

So below is the program. The "cut here" lines  mark it's beginning and end. I've tested it on both Windows and Linux platforms, and it works for me. You will need a python interpreter, and you can download one of those at python.org. In the output I call the 5 picked numbers "the lucky set". This does not mean they really are lucky.

#-------cut here-------
import random
GENESIZE=56
POPSIZE=20
CROSSPROB=.25
MUTPROB=.05
def randomize(gene):
    i=0
    while i<GENESIZE:
        if random.random()<.5:
            gene[i]=1
        else:
            gene[i]=0
        i=i+1
def initialize(pop):
    i=0
    while i<POPSIZE:
        pop[i]=GENESIZE*[0]
        randomize(pop[i])
        i=i+1
def toset(gene):
    set=[]
    i=0
    while i<GENESIZE:
        if gene[i]==1:
            set.append(i+1)
        i=i+1
    return set
   
def tostring(gene):
    outstr=""
    for x in gene:
        outstr=outstr+str(x)
    return outstr

def printgene(gene):
    print tostring(gene)
def flip (gene,pos):
    gene[pos]=1-gene[pos]

def cross(gene1,gene2,pos):
    temp1=gene1[pos:]
    temp2=gene2[pos:]
    k=pos
    for x in temp1:
        gene2[k]=x
        k=k+1
    k=pos
    for x in temp2:
        gene1[k]=x
        k=k+1

def count_ones(gene):
    sum=0
    for x in gene:
        sum+=x
    return sum

def eval(gene):
    temp=abs(GENESIZE-abs(count_ones(gene)-5))
    if temp==0:
        temp=1
    return temp

def alter(pop):
    crosscount=0
    for i in range(POPSIZE):
        if random.random()<CROSSPROB:
   
            if crosscount==0:
                gene1=pop[i]
                crosscount=1
            else:
                pos=random.randrange(1,GENESIZE-2)
                cross(gene1,pop[i],pos)
                crosscount=0

    j=0  
    while j<POPSIZE*GENESIZE:
        if random.random()<MUTPROB:
            flip(pop[j/GENESIZE],j%GENESIZE)
        j=j+1

def select(pop):
    fitness=POPSIZE*[0]
    cum_prob=POPSIZE*[0]
    total_fitness=0
    for i in range(POPSIZE):
        fitness[i]=eval(pop[i])
        total_fitness+=fitness[i]

    prob=fitness[0]/float(total_fitness)
    cum_prob[0]=prob
    i=1
    while i<POPSIZE:
        prob=fitness[i]/float(total_fitness)
        cum_prob[i]=prob+cum_prob[i-1]
        i=i+1
    newpop=[]
    for i in range(POPSIZE):
        roulette_wheel=random.random()
        if roulette_wheel<cum_prob[0]:
            newpop.append(pop[0])
        else:
            j=1
            done=0
            while j<POPSIZE and not done:
                if roulette_wheel<cum_prob[j]:
                    newpop.append(pop[j])
                    done=1
                j=j+1
       
random.seed()
pop=POPSIZE*[[]]
initialize(pop)
pick5pos=-1
count=0
best_fitness=0
while pick5pos==-1 and count<10000:
    alter(pop)
    select(pop)
    for x in pop:
        temp_fitness=eval(x)
        if temp_fitness>best_fitness:
            best=x[:]
            best_fitness=temp_fitness
    pop[0]=best[:]

    i=0
    while i<POPSIZE and pick5pos==-1:
        if count_ones(pop[i])==5:
            pick5=pop[i]
            pick5pos=i   
        i=i+1
    count=count+1
   
if pick5pos>=0:
    print "lucky set is ",toset(pick5)
else:
    print "no lucky string found"
print "powerball is", random.randrange(1,42)
#----cut here-------------




Comments

Good entry and nice work... I find that's actually a very commonly misunderstood fact about computers and randomness. Sometimes people have seen evidence of poor random number generation in games and when it sinks in it's just like 'ohh!' but otherwise it's fun when they're confused on why the computer can't just 'pick a number'. A good excersize it to have the person sit down and try to write a set of context-free directions to just pick any random number.

Not that the numbers most anybody picks are random anyway. I remember the time a teacher asked two students to pick between 1 and a 100 to solve some conflict. One student just said '100.'
The other student logically said, '99', increases his chances by a large factor.

It did end up being 100 though...

How do you generate random numbers in real life, though? I mean, even a ping pong ball rolling in a cage has some set of kinetic motions that define it. It's essentially random to us as we don't have the information to predict its outcome, but it's theoretically possible, right? The ping pong ball in the cage is just following the algorithim dictated by the space it's travelling through... Or does the unknowable quantum states somehow interfere to introduce true randomness into the equation?

You raise an interesting question as to whether anything is truly random. But as you point out, the ping pong balls in the lottery machine is essentially random, since determing the factors of which ones come up would be too complex for us to do.

That's why I think it's necessary to describe degrees of randomness. I did this in my original post, but I must confess I was not very rigorous. But you can look at a sequence of numbers and say that one is "more random" than the other.

For instance, below are two sequences of numbers, neither of which is random (since both were generated by an algorithm). However, most people would say that the second is closer to true randomness than the first.

1 2 3 4 5 6 7 8 9 10
35 13 51 68 57 76 34 79 38 17