help on coding finite state automata

[Linh Chi Nguyen]

Dear All,
I'm a complete newbie in racket and need help in coding finite state machine/automata. Please pardon any of my ignorance.

Thanks to this post of Tim Thornton, I see a very good way to code FSM:
http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d

I'd summarise it as following:
A finite state automaton has a number of states and each state has a name plus many transition rules. He structures it in racket as following:

(struct automaton (current-state states))
(struct state (name actions))
(struct action (event result))

A simple automaton can be like this:
(define simple-fsm (fsm 'A
(list (fstate 'A (list (action 0 'A)
(action 1 'B)))
(fstate 'B (list (action 0 'B)
(action 1 'A))))))

The automaton is in state A which has 2 transition rules:
- if event 1 happens, the automaton jumps to state B,
- if event 0 happens, it stays in state A.

Then he writes some functions to update the automaton after each event (in the post). Plus this function he omits (I guess):
(define fsm-update-state old-fsm new-state)
(struct-copy automaton old-fsm [current-state new-state]))

HERE IS THE QUESTION:

Using this way, after each event, there'd be a NEW automaton created. So I'm worried about scaling. I'd like to generate 100 automata. In each cycle, I'd pair the automata to interact for 50 times. Which means that there'd be 100 new automata created for every single cycle. And I'd like to run at least 1000 cycles.

Would there be any problem with scaling? If yes, is there a way around this?

Any kind of comments and suggestions are welcomed and appreciated,
Thank you really much,
Chi

[Michael Titke]

On 03/09/2015 16:29, Linh Chi Nguyen wrote:
> Dear All,
> I'm a complete newbie in racket and need help in coding finite state machine/automata. Please pardon any of my ignorance.
>
> Thanks to this post of Tim Thornton, I see a very good way to code FSM:
> http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d

Looks interesting! When I first heard of finite state machines they were
presented to me as an abstract model
of computers in general. AFAIR finite state automatons are used to teach
how to realize really fast orthography checks but for me these were more
connected to the concept of directed cyclic graphs.

>
> HERE IS THE QUESTION:
>
> Using this way, after each event, there'd be a NEW automaton created.

That's because of pure functional programming as the post states.

> So I'm worried about scaling. I'd like to generate 100 automata. In each cycle, I'd pair the automata to interact for 50 times. Which means that there'd be 100 new automata created for every single cycle. And I'd like to run at least 1000 cycles.
>
> Would there be any problem with scaling? If yes, is there a way around this?

With the knowledge of a regular computer already being such an automaton
(in some way) I have learned
to appreciate the /case/ form for data driven programming. Especially if
one doesn't care about past states (which will need memory one way or
the other) it's probably better to describe the automaton "from inside"
and see the whole program (or some part of it) as an automaton. For
event driven programs nowadays (at least in Racket) we only need to
define the actions as regular procedures or callbacks.

[Neil Van Dyke]

If your FSM are defined at compile-time, you can write a macro (in
`syntax-rules` or `syntax-case`) that transforms FSMs defined in your
FSM macro language to efficient Racket code.

Even with a macro, there are a few popular ways to do it, but I suggest
trying to make your state transitions be Racket tail calls.

Neil V.

[Paulo Matos]

Which reminds me of Shriram's awesome paper:
http://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/

Enjoy!

--
Paulo Matos

[mrmyers.ra...@gmail.com]

You might want to take a look at https://github.com/mromyers/automata
specifically, https://github.com/mromyers/automata/blob/master/examples.rkt
and https://github.com/mromyers/automata/blob/master/machines.rkt
I more or less just use the definition that was in my textbook: you provide a transition function, and the DFA or NFA just uses stream-fold to get the extended transition. I used a bunch of generics stuff to try to generalize everything past the point of practicality, but it's still reasonably fast.
It's not documented, but use (in-machine? M seq) to check for acceptance, (extended-transition M start seq) for final state(s).

There's also a minimization function and nfa->dfa conversion in there, but they might have some bugs.

[Nguyen Linh Chi]

Wow as much as i appreciate and try to see through all the answers, i have to confess that i'm a first year Phd student in economics. So writing macro is too far for me now.

I'd just process with struct.. And see how expensive it is for my agent based model. Hopefully i can show you the code some day, regarding all these suggestions, if still relevant.

Thank you,
Chi

> --
> You received this message because you are subscribed to a topic in the Google Groups "Racket Users" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/racket-users/4o1goSwrLHA/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to racket-users...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[mrmyers.ra...@gmail.com]

On Friday, September 4, 2015 at 1:34:38 AM UTC-4, Linh Chi Nguyen wrote:
> Wow as much as i appreciate and try to see through all the answers, i have to confess that i'm a first year Phd student in economics. So writing macro is too far for me now.
>
> I'd just process with struct.. And see how expensive it is for my agent based model. Hopefully i can show you the code some day, regarding all these suggestions, if still relevant.
>
> Thank you,
> Chi
>
> On 04/set/2015, at 03:25, mrmyers.ra...@gmail.com wrote:
>
> > On Thursday, September 3, 2015 at 10:29:33 AM UTC-4, Linh Chi Nguyen wrote:
> >> Dear All,
> >> I'm a complete newbie in racket and need help in coding finite state machine/automata. Please pardon any of my ignorance.

Hi Linh.

One problem with doing things that way is that it creates a lot of temporary things that need to be cleaned up. The nice thing about a finite-state-machine is that you only need to keep track of one thing (current state) while it runs.

In the code I linked above, a finite state machine (I use "dfa" or "deterministic finite automata") is defined as something with a 'transition function' δ(p,a) = q which, given a state p and symbol a, returns a new state q. It also has to have an initial state, and an accept? function to determine which states are to be accepted.

I also wrote some helpful macros to make defining one a lot easier. You can write

(define M
(dfa (alphabet: '(a b))
(table: [sa : x sb]
[sb : sa x]
[x : x x])
(start: sa)
(accept: sb)))

(in-machine? M '(a b a b a b))

to accept only lists that contain alternating seqences of 'a followed by 'b.

If you make your alphabet a string or list of characters, it can scan strings or lists of characters for acceptance instead. If the alphabet had been "ab",
everything else could be kept the same, but you could write
(in-machine? M "ababab")

You can use symbols, numbers, or whatever you'd like to represent states, just list the transitions for each state in the order of the alphabet you supplied.

Lastly, if you're not just interested in whether it accepts or not, and want to know the final state, use
(extended-transition M s1 '(a b a b a b))

[Jens Axel Søgaard]

Hi Linh,

There are many different representations of finite state machines.

If you "just" need to simulate a single machine, a simple and efficient

approach is to represent each state as a Racket function (see example below).

#lang racket

(require racket/generator)

;; The turn-stile example from Wikipedia.

;;   https://en.wikipedia.org/wiki/Finite-state_machine#Example:_coin-operated_turnstile

;; Current State  Input   Next State   Output

;;   LOCKED       coin    UNLOCKED     unlock turnstile so customer can push through

;;   LOCKED       push      LOCKED     none (custome can't move through)

;; UNLOCKED       coin    UNLOCKED     none

;; UNLOCKED       push      LOCKED     when customer is through, lock turnstile

(define inputs '(coin push push push coin coin push))

(define get-input (sequence->generator inputs))

(define (LOCKED)

  (match (get-input)

    ['coin    (displayln "turnstile is unlocked")

              (UNLOCKED)]

    ['push    (displayln "you can't move through locked turnstile")

              (LOCKED)]

    [_        (DONE)]))

(define (UNLOCKED)

  (match (get-input)

    ['coin    (displayln "no need to pay when the turnstile is unlocked")

              (UNLOCKED)]

    ['push    (displayln "customer goes through, turnstile is locked")

              (LOCKED)]

    [_        (DONE)]))

(define (DONE)

  (displayln "no more inputs"))

(LOCKED) ; start turnstile in a locked state

    

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

--
Jens Axel Søgaard

[Nguyen Linh Chi]

Dear mrmyers, I cloned your repo however it's true that i complete have no idea about macro yet. It'd be nice for further reading as i'd work on this problem for long.

As soegaard suggests on IRC, to avoid the problem of creating new machines after every interaction, i'd try to make the struct #:mutable. Hope that'd be good.

Thanks for great advice,

Chi

--

Nguyen Linh Chi

[Michael Myers]

You might want to take a look at https://github.com/mromyers/automata
specifically, https://github.com/mromyers/automata/blob/master/examples.rkt
and https://github.com/mromyers/automata/blob/master/machines.rkt

I more or less just use the definition that was in my textbook: you provide
a transition function, and the DFA or NFA just uses stream-fold to get the
extended transition. I used a bunch of generics stuff to try to generalize
everything past the point of practicality, but it's still reasonably
fast.

It's not documented, but use (in-machine? M seq) to check for acceptance,
(extended-transition M start seq) for final state(s).

There's also a minimization function and nfa->dfa conversion in there, but

they're a bit fragile, so use at your own risk.

[mrmyers.ra...@gmail.com]

Sorry for the duplicate, this was sent yesterday, and only arived just now.

[Nguyen Linh Chi]

Dear All,
thanks for all your help, im writing the code to generate a population of fsm, playing a repeated game and the population evolves over time. (no mutation yet). here on my github just fyi:

https://github.com/ayaderaghul/sample-fsm

Btw, the blogger suggests that because the automaton only needs to know the current-state, if the population scales big, we just need to separate the current-state as a single atom outside the machine itself (for better performance).

I hope this may helps make the thread more complete.

--
You received this message because you are subscribed to a topic in the Google Groups "Racket Users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/racket-users/4o1goSwrLHA/unsubscribe.
To unsubscribe from this group and all its topics, send an email to racket-users...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Nguyen Linh Chi

[Matthias Felleisen]

I forked, Racket-ized, and gained some speed (~2x). 

You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

[Linh Chi Nguyen]

Thank you very much,
Im trying to see it. However Im very unfamiliar with module in racket.

So far I can only answer you this:

about your comment

> [define survivors (drop population speed)]
> ;; MF: THIS LOOKS LIKE IT MAY "RESURRECT" AUTOM. THAT ARE ALIVE
> [define successors (randomise-over-fitness accum-fitness population speed)]

The point of the simulation is that it "ressurect" already available automata, regarding their fitness. Hence who has higher fitness gets more offspring and grows in size gradually (at the expense of the poor doers).

What is not right here is the word "ressurect" and it catches your intuition.

I'm not a native English speaker and they are complaining that I should get a native English speaker to proofread my paper. Sorry for that :)

[Linh Chi Nguyen]

ok i've been trying to see through the code.

I'm not sure how github works but I pushed the changes in my repo again (https://github.com/ayaderaghul/sample-fsm/blob/master/fsm0.rkt). Basically, I rewrite the automaton module (description and behavior) because previously I made a confusion between the number of the states and the number of actions for each state. Now the automaton is less readable but more simple.

I also add some test that can be run with
```
~laptop$ raco test fsm0.rkt
```

However I dont know to run this code without a repl.
Because the whole file fsm0.rkt is a module and it has many nested modules inside, and the command i need is in the nested one. There is a special module that has this command:

```
(module* main #f
(run))
```

So if i want to run a trial of the file, i open a repl:

```
~laptop$ racket
> (require (submod "fsm0.rkt" tv))
> (run)
```
and it runs and plot the result.

I dont want to open a repl. How to run the command right in the terminal (Because later on i want to run the command with arguments in the terminal)? for example, I've tried this but it doesnt work:

```
~laptop$ racket fsm0.rkt '(require (submod "fsm0.rkt" tv))' '(run)'
```

Thank you,
Chi

[Linh Chi Nguyen]

Sorry for the emails.

But I'd like to post that the question of how to require a module then evaluate a command is answered here:

https://groups.google.com/forum/#!topic/racket-users/byL7W1yktas

by Daniel.

Thank you so much for all your help and patience,
chi

[Matthias Felleisen]

I have pushed some more cleanups, more speed. 

I added another question to the “spawning” procedure. 

[byron...@starshine.us]

Chi, if you have really like finite state automata, you might be interested in a new product from Micron called the Automata Processor (AP) http://www.micronautomata.com. A single chip has (I think) 256K fsa elements operating in massive parallelism. It's particularly designed for things like "graph analysis, pattern matching, and data analytics", and can recognize large numbers of complex patterns simultaneously in streams of data at near gigabit rates.

The AP is implemented as an co-processor (with up to 8 chips) for a PC, and currently has a C-based API development environment and API. It could sorely use a Racket interface and development environment.

Byron

[Linh Chi Nguyen]

I dont know how the email group work. If someone keeps receiving emails out of interest, please notice me.

Thanks Bryan for the suggestion, it's nice to know, however Im not able to afford upgrading now.

And Matthias, for your notice of the spawning process
```
(define (randomise-over-fitness accumulated-payoff-percentage population speed)
(for/list ([n (in-range speed)])
[define r (random)] ;; SHOULDN"T THIS LINE BE OUTSIDE OF THE for/list COMPREHENSION?
(for/and ([p (in-list population)][a (in-list accumulated-payoff-percentage)]
#:break (< r a))
p)))
```

The randomly generated r has to be inside the for/list loop. Because if it's outside, then there is only one random number generated at the beginning, and the newly spawn automata will keep being the same one repeatedly.

For example, when the learning speed is s = 10, it means that, 10 old automata should be replaced with 10 new ones. And the replacement should be done in 10 different places in the population.

This procedure is called an independent bernoulli draw. We independently draw a random number (associated with an automaton) for 10 times. How likely an automaton is chosen depends on its own fitness (its interval in the unit scale of the accumulated percentages.)

[Matthias Felleisen]

I pushed some more changes.

-- All automata code is now in the automata modules.
-- It is now easy to explore different implementations of automata.

1. Eliminating your last side-effects came for free or possibly a small gain in performance.
2. Replacing your list-based automata with automata that use a transition matrix was the real gain,
but of course this transformation reduces generality.

Right now, the code uses about 1/6 of the time your original program consumed.
This measurement is extremely rough and probably wouldn't stand up to statistically
rigorous methods. Close enough.

I may try to add types later today.

[Gustavo Massaccesi]

Sorry for not testing before posting, but in this code:

(define (randomise-over-fitness accumulated-payoff-percentage population speed)
(for/list ([n (in-range speed)])
[define r (random)]

(for/and ([p (in-list population)]
[a (in-list accumulated-payoff-percentage)]
#:break (< r a))
p)))

It looks like the population is stored in a list, and the changes in
the populations create more lists. I think that changing the
implementation to use vectors instead of list would make the code
faster. (But I haven't tested it.)

Also, I think that for/and can be changed to for/last. I guess it will
almost no no change the speed, but it would make the intention
clearer.

Gustavo

[Matthias Felleisen]

for/last: good point.

Based on my previous experience with replacing imperative automata with functional ones,
I don't think replacing the list-based population container with a vector per se will
speed up things much. But the pairing up of neighbors might be a tad faster. Then again
I would have to rewrite shuffle for imperative vectors.

I have pulled out the population for now so that you can play with this:

https://github.com/mfelleisen/sample-fsm

It's easy to run now from the command line.

[Matthias Felleisen]

So I couldn't resist and wrote the vector-based, allocation-minimizing
version of the program. I didn't get that much of a performance gain.

I might still change the fitness representation (into a vector) or
integrate it into 'population' (where it belongs from an SE perspective).
I doubt this will do much better in terms of speed. A speed-up of 6x
will have to do for now.

Code at the same old link:

> https://github.com/mfelleisen/sample-fsm

[Alex Knauth]

What about Alexis King's persistent vectors?

[Matthias Felleisen]

Take a crack at it.

I am pretty sure I have introduced the proper level of representation
independence (I can hear Ben laugh all the way now — Typed Racket
doesn’t have types) and the typed documentation is pretty solid. (I’ll
do types later to validate.)

[Linh Chi Nguyen]

Matthias you work like a machine, too fast.

Anyway, I have no idea what is type or not type.

But I have some general remarks:

1. A general automaton can have many states, say, 10 states.

so the action in each state can be either cooperate or defect (this is a deterministic automaton, for a probabilistic one, they can even randomise between cooperate or defect, but the case of deterministic and probabilistic should be separated far).

it means that, even for a 2 state automaton, it can happen that both state use the same cooperate action.


other small notices
- the all defect automaton start with defecting and always defecting so its code is : defect defect defect... not cooperate defect defect... (same for the all cooperates one)

- i'm considering to add a mutation phase at the end of each cycle (ie choose some random automaton and mutate their code) but im working very slow.

- why dont you define a (match-pair ...) function separately? you insert it in the (match-population ...). doesnt it deserve to be outside?

- why you use [i (in-range 10)] in all for loop? what's the difference with [i 10]. they both produce stream, right?

[Benjamin Greenman]

- why you use [i (in-range 10)] in all for loop? what's the difference with [i 10]. they both produce stream, right?

Yes, but `in-range` runs faster because of "types". Here's a little example:

#lang racket/base

(define N (expt 10 7))

(time (for ([n (in-range N)])  (void)))

;; cpu time: 36 real time: 36 gc time: 0

(time (for ([n N])  (void))) 

;; cpu time: 635 real time: 635 gc time: 0

[Alex Knauth]

I've started on that, but shuffle doesn't exist properly yet for generic collections. I could just use (shuffle (sequence->list ....)), but, what would be the best way of representing this? Generic collections give you the freedom of creating a new type of data structure just for shuffled sequence, so would it be best to do that, or something else?

[Matthias Felleisen]

1. Your code is a good example for something that we could use as a benchmark, and working on it has helped me find a couple of problems in drracket and typed racket. Thanks for triggering my activity. I'll stop soon.

2. I figured out that your code was general so you could accommodate more situations than the ones you explored. My interest diverges from yours. To me it is now just a cute benchmark. You will be able to use my insights to speed up your performance:

-- factor the program into separate modules/files,
-- make the modules independent of the representations,
-- change automata and population representations to use vectors instead of lists,
-- avoid mutation,
-- eliminate all situations where you use (append l (list x)); instead use cons and reverse the result at the end.

That way you can run the program 6 times faster.

3. Otherwise I think your program needs real testing and I think there are two bugs:

a: I created a pull request for this one:


(define (accumulated-payoff-percentages payoff-list)
(define payoff-sum (apply + payoff-list))
(define-values (accumulated _)
(for/fold ([accumulated (list 0)] ;; change to '(); otherwise you get a list that's too long; your other for loop accidentally compensates for this bug
[init 0])
([y (in-list payoff-list)])
[define next-init (+ init (/ y payoff-sum))]
(values (cons next-init accumulated) next-init)))
(reverse accumulated))

b: I don't know how to fix this one properly:

(define (randomise-over-fitness population fitness speed)

(for/list ([n (in-range speed)])
[define r (random)]

(define candidate
(for/and ([p (in-vector population)]
[f (in-list fitness)]
#:break (< r f))
p))
candidate))

replace last line with something like this:
(or candidate (vector-ref population 0))))

Otherwise there is a non-0 chance otherwise that you get a boolean value eventually. I am not sure which default value you want to throw in.

4. You're right:

-- I re-created the match-pair function when I looked over my code.
-- using in-list and in-vector and in-range speeds up for loops.
-- types are irrelevant to your project. They helped me.

I have pushed the last changes for now. Can we have your permission to use this code for a benchmark in our research world? Thanks.

[Matthias Felleisen]

See repo. I special-purposed shuffle for my data rep.

[Matthias Felleisen]

p.s. One more question. Why do you 'reset' the payoff for automata after each round? Shouldn't they carry along their overall, historical payoff?

[Nguyen Linh Chi]

Hi Mathias, thank you so much for helping me a lot.
You can use the code as you want, i still have tons of them on my github. (Just dont use it against me ok :D )

I'd try to see through your list of suggestions.

About the automata payoff.

There are 2 different things that are always mixed up: round and cycle. In each cycle, automata are matched in pair and play a game for r rounds per match. At the end of each cycle, there is a replacement period (respawning the fittest). In what im doing, the payoff after r rounds is transformed into the fitness, and the strongest automata (biggest payoff) survive. In some sense they already carry on their relative payoff with them just because they survive.

Make the automaton carrying their absolute payoff history over cycles would be intereting to see. I've never thought of that and the coding effort is also a reason i havent tried.

[Nguyen Linh Chi]

the list 0 isnt a bug. I add it because #:break will break the fitness vector at r < f.

For example,
Population : a b c d
Cumulative fitness .2 .5 .7 1

If the random r = .8, it means that the lottery points to the interval of automaton d. But #:break will breaks at .7, and the associated automaton is falsely identified as automaton c.

(Hm, right?)

[Matthias Felleisen]

Welcome to Racket v6.3.0.1.
> (define r .8)
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
'c

Or WORSE:

> (define r (random))
> r
0.011105628290672482
> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
#f

[Gustavo Massaccesi]

:( . I tried few modifications, but I didn't get any improvement. I
think that the recalculation of the population is used very seldom, so
any change there will not affect the speed too much.

Most of the time is used in the matches, but I don't have any
suggestion for it (that doesn't include uglifying the code, and
perhaps are also not useful).

Gustavo

[Nguyen Linh Chi]

Isnt this the reason we should add 0 at the beginning of the list?

[Linh Chi Nguyen]

oh if you dont like adding 0.
maybe you can use the keyword #:final instead of #:break

(they say it does just one more iteration before breaking the loop)

On Wednesday, 14 October 2015 05:53:03 UTC+2, Linh Chi Nguyen wrote:
> Isnt this the reason we should add 0 at the beginning of the list?
>

[Matthias Felleisen]

On Oct 13, 2015, at 11:52 PM, Nguyen Linh Chi <nguyenl...@gmail.com> wrote:

> Isnt this the reason we should add 0 at the beginning of the list?
>
> On 13/ott/2015, at 22:38, Matthias Felleisen <matt...@ccs.neu.edu> wrote:
>
>>
>> Welcome to Racket v6.3.0.1.
>>> (define r .8)
>>> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
>> 'c
>>
>> Or WORSE:
>>
>>> (define r (random))
>>> r
>> 0.011105628290672482
>>> (for/last ([p '(a b c d)][f '(.2 .5 .7 1)] #:break (< r f)) p)
>> #f

No, it is bad programming practice to add a sentinel in one function
that is used by another function. The locations are too far apart,
because programmers reason about function-sized pieces when they
approach code. (I did, I refactored, and I got the failure).

When you code, keep in mind that you write this code for other
people (possibly your older self in six months from now when you
revise the program) and it accidentally runs on a computer.



Here is how I rewrote your function and added a test:

;; -----------------------------------------------------------------------------
;; [Vectorof Automaton] N -> [Listof Automaton]
;; (randomise-over-fitness v n) spawn a list of n fittest automata

;; Nguyen Linh Chi says:
;; This procedure uses an independent Bernoulli draw. We independently

;; draw a random number (associated with an automaton) for 10 times. How
;; likely an automaton is chosen depends on its own fitness (its interval
;; in the unit scale of the accumulated percentages.)

(module+ test
(define p0 (vector (automaton 0 1 't1) (automaton 0 90 't1)))
(define p1 (list (automaton 0 90 't1)))
;; this test case fails if (random) picks a number < .01
(check-equal?
(randomise-over-fitness p0 1) (list (automaton 0 90 't1))))

(define (randomise-over-fitness population0 speed)
(define fitness (payoff-percentages population0))
;; (= (length fitness) (length population))
;; fitness is sorted and the last number is ~1.0
(define population (vector->list population0))

(for/list ([n (in-range speed)])
[define r (random)]

(define last (for/last ([p population] [f fitness] #:final (< r f)) p))
(or last (error 'randomise "the unlikely happened: r = ~e is too large" r))))

the for/last combined with #:final brings across this intention.

The way I have written it, the code also points out that,
at least in principle, the world of floating point numbers
allows for a failure to find a fit enough automaton in this
list. (Yes, it is a very small chance.)

***

QUESTION: why do you accumulate fitness across different automata?
That is, why does payoff-percentages add the payoff of automata_i
to automata_{i+1}? I understand that this means the last automata
will have a fitness level of close to 1 (modulo rounding floating
point numbers).

[chi]

Thanks for answering me many times. I really appreciate.
For the question, if we dont accumulate and randomise that way, how can
we spawn new automata regarding their fitness?

For example,
population: a b c d
payoff: 5 0 8 3 (sum = 16)
relative payoff: 5/16 0/16 8/16 3/16

-> The replacement process is a lottery that gives automaton a 5/16
probability to be chosen, 0 for automaton b, 1/2 for automaton c, 3/16
for automaton d.

In practice, option 1: this process is usually been done by drawing a
unit line, marking intervals with different lengths:

+-----++-------+---+

then you throw a ball randomly in this line, if we see it landing in the
interval with length 3/16, automaton a is chosen. Bigger interval means
better chance of being chosen and it can proliferate over time (counted
by cycles).

Or option 2: we can mark each point on the line associating with an
automaton (however the line is continuous, hence it has infinite points)
at random order. In this marking process, we just need to be sure about
one thing: the number of points for automaton a has to sum up to 5/16 ~
25% length of the whole line, the number of points for automaton c has
to sum up to 50% the length of the line....

-> it's better to put all the points for the same automaton next to each
other so they form a continuous interval (like in option1).

In coding, it's similar. The (random) function throws a ball, and gives
a point but the computer doesnt simply see which automaton the point
belongs to.

So we accumulate the payoff according to the order of the automata in
the population. It's called a cumulative function.
F(a) = p(a) = 5/16
F(b) = p(a) + p(b) = 5/16
...
F(d) = p(a) + p(b) + p(c) + p(d) = 1

so the actual payoff of b will be F(b) - F(a) and so on..
(We can accumulate from the left or from the right).

And now the computer can compare r = (random) with the end point of each
interval, then it knows what automaton interval the point belongs to.

(I dont know who do this first, it's like every person who starts to do
evolution simulation will ask this question, and a person who already
did this practice will tell them, and so on...)

[Matthias Felleisen]

This is perfectly clear and obvious in hindsight. Thanks -- Matthias