(very long) development styles
Jecel Assumpcao Jr
jecel@tunes.org
Fri, 18 Aug 2000 15:18:20 -0300
Hi,
Lynn Maxson and I have been discussing our different approaches to
software development. I suggested that it might be more interesting for
us to discuss concrete examples, I he came up with a simple math
problem (a box has B beetles and S spiders, with a total legs L=6*B+8*S
of 46. What are B and S?) and showed me how he would solve it using his
SL/I system. I coded a simple exhaustive search in Self.
The I proposed a more complex problem of the same style: finding a
solution to the "peg solitaire" game. There is some information about
this at:
http://www.inwap.com/pdp10/hbaker/hakmem/games.html#item75
Unlike most of the problems that I am interested in, this one should
highlight the strengths of such different styles as object oriented
programming, logic programming and functional programming. This very
long email shows my solution using the first two styles. Lynn has coded
this problem in PL/I and is thinking of doing it in SL/I and Trilogy.
He also suggested that if people from the Tunes list could do the same
for other languages (including the various ones they are creating) it
might be a very important addition to the language review subproject.
Most of the examples that have been coded in more than one language are
too trivial to give the reader a good impression of that language. See:
http://www.ionet.net/~timtroyr/funhouse/beer.html
I am sure that you Tunesers can come up with much better examples than
this one, but hopefully this will help make some discussions less
abstract.
I don't expect anyone to really read all the stuff below - the idea is
to give a feel for the two different development styles. While the
first solution took me only five minutes, the second one took well over
an hour (actually, much more since I had to write it down). A text
transcript like this doesn't give a good impression of what Self is
like - we would need a movie for that. But I hope at least some people
can figure out from all this why I have chosen the second development
style for my project.
--Jecel
==================== pseudo Prolog - specification ==================
I don't have a working Prolog implementation on my machines, so this
will be a "paper" solution. Note that it has been a long time since I
have programmed in this language and I no longer remember exactly how
its data structures worked, so I am making up a reasonable
approximation, here.
The first thing is to define the starting board position:
pegsolitaire (
{ '-' '-' 'p' 'p' 'p' '-' '-'
'-' '-' 'p' 'p' 'p' '-' '-'
'p' 'p' 'p' 'p' 'p' 'p' 'p'
'p' 'p' 'p' '.' 'p' 'p' 'p'
'p' 'p' 'p' 'p' 'p' 'p' 'p'
'-' '-' 'p' 'p' 'p' '-' '-'
'-' '-' 'p' 'p' 'p' '-' '-'}, 32, [] ).
This defines a relation between a 49 character array, the number 32 and
an empty list. The array represents the current board situation: 'p' is
a hole with a peg in it, '.' is an empty hole and '-' is a position
that has no hole. The 32 represents the number of pegs remaining (so I
don't have to calculate it from the board, which would make things
slower) and the list represents all the moves we have made so far.
Now comes a relation to find out a board position given a previous one:
pegsolitaire ( board, remaining, moves ) :-
pegsolitaire ( pb, remaining + 1, pm),
aligned ( a, b,c ),
head ( moves, [a, b, c]),
tail ( moves, pm ),
pb[a] = 'p', pb[b] = 'p', pb[c] = '.',
board[a] = '.', board[b] = '.', board[c] = 'p',
match ( board, pb, 0, a, b, c ).
This first line simply says that the previous board position was
different, had one more remaining pin and a different list of moves.
The second line is supposed to gives us three numbers representing
aligned holes (indexes from 0 to 48 into the character array).
The third line says that the moves list starts with a list of the three
numbers representing a move, and the next line say the list continues
with all the elements in the previous moves list.
The next two lines define how the three board positions are supposed to
look like before and after the move. Note that since no '-' character
ever appears in these rules we avoid the corners in the board
automatically. The final line is a horrible trick explained below.
aligned ( from, skip, to ) :- from >= 0,
from < 7*5,
skip = from+7, to = skip+7.
aligned ( from, skip, to ) :- from >= 2*7,
from < 7*7,
skip = from-7, to = skip-7.
aligned ( from, skip, to ) :- from%7 >= 0,
from%7 < 5,
from < 7*7,
from >=0,
skip = from+1, to = skip+1.
aligned ( from, skip, to ) :- from%7 >= 2,
from < 7*7,
from >= 0,
skip = from-1, to = skip-1.
These four rules specify what it means to have three aligned board
positions in terms of array indexes. The define the "eat down", "eat
up", "eat right" and "eat left" rules respectively.
It is a good idea to see if it does what it is supposed to:
aligned ( a, b , c )?
The answer should be something like "a=0, b=7, c=14". Most Prologs
allow you to type ";" or some other character to request additional
answers. There should be 140 answers from this query.
match ( board, previous, position, a, b, c ) :- board[position] =
previous[position], match ( board, previous,
position+1, a, b, c).
match ( board, previous, position, position, b, c ) :- match (
board, previous, position+1, position, b, c).
match ( board, previous, position, a, position, c ) :- match (
board, previous, position+1, a, position, c).
match ( board, previous, position, a, b, position ) :- match (
board, previous, position+1, a, b, position).
match ( board, previous, 49, a, b, c ).
These rules say that all characters in the current board must be
exactly the same as the ones in the previous board except for the three
that are touched by the current move. This is actually an imperative
copy loop badly disguised as a "specification". They say you can
program in Fortran using any language, and here is the proof ;-)
Someone who actually knows logic programming would probably do a much
better job than this. But supposing this pseudo Prolog makes sense this
far, I can now submit a query to check it:
pegsolitaire ( board, 31, moves )?
There should be a total of four different answers from this query, each
showing the board position after the first play and one move. If this
looks ok, I might risk:
pegsolitair ( board, 1, moves)?
This will produce a depth first search and will stop when it reaches
the first solution to the game. I wouldn't be surprised if this took
many days or even weeks. Pressing ";" will send it off into a search
for yet another solution.
The point of all this is that I have specified the problem to be
solved, but not really programmed it. The computer does the rest. Of
course, I cheated a bit with the "match" rules above and it is likely
that a slight reordering of the terms in the rules could change
execution time by a few orders of magnitude! Then I would start adding
things like cut ("!") and fail to make it go faster, and I would be no
longer specifying but truly programming.
==================== Self - exploratory programming =================
I start off by going to a remote region in the world and calling up the
main menu to create a shell object into which I can type in Self expressions.
Actually, I can type in expressions in any object but the shell is a
convenient one.
So I type:
morph copy
and get an "object outliner" for a clone of the prototypical morph object. I
use a menu on this to request "show morph" and get a small, brown rectangle
as a result. I make it bigger and change its color to grey with menus - we
now have a nice board for our game.
Back to the shell, I type:
circleMorph copy
and get a second outliner. The menu option "show morph" gets me a nice, green
circle. It is too big, so I make it smaller and change the color to a redish
grey. Now I copy the circleMorph's "parent*" slot to the background making a
new object and drag the arrow from the original "parent*" slot to point to
this instead. This will give me a convenient place to affect all objects
cloned from this one without affecting other circles in the system. I copy
the "morphTypeName" and "baseDrawOn: c" from traits circleMorph so I can
patch them. I edit the first to read:
morphTypeName = 'holeMorph'
which causes the outliner to change at once - we now have a holeMorph and
no longer a circleMorph. We add a new slot to the holeMorph:
hasPeg <- false
and a slot to its parent:
pegColor <- paint named: 'yellow'
So now I edit the second slot I borrowed from traits circleMorph to read:
baseDrawOn: c = (
c fillCircleCenteredAt: center Diameter: radius double Color: color.
hasPeg ifTrue: [ c fillCircleCenteredAt: center
Diameter: radius Color: pegColor ].
self)
Now I can try telling the holeMorph:
hasPeg: true.
changed
and it works perfectly, though my taste in colors could certainly be
improved. Now we duplicate the holeMorph. Then duplicate the pair of holes.
And again. 8 nice holes in a row, seven of which on top of the grey morph.
The last one is over the edge, however, so I will make the morph a bit larger.
Now I duplicate the row of seven holes. Then the two rows. One more time
and there are now eight rows. Resize the morph again and get rid of the
extra rows plus the set of 2 by 2 holes in each corner. I just embed all
remaining holes in the board (grey morph) and then move it around to see
how it looks.
A new slot for the hole's parent:
leftMouseDown: evt = ( hasPeg: hasPeg not. changed )
Yeah - now I can still pick up the whole board but clicking on a hole
will add a peg or remove it. It is actually possible (but awkward) to
manually play a game at this point.
--~=~= Interlude =~=~--
This already demonstrates a feature of exploratory programming: source-less
objects. There is no piece of code anywhere in the system which specifies
the arrangement of holes on the board. Since I was able to save the whole
system (snapshot) on Saturday and restore it again today, this wasn't a
problem - the working board is on the screen just as I had left it and
with the correct pattern of holes.
This is all very nice, but how do I move this object to another system
(how could I send it to someone via email, for example)? I have been
working on a solution for this kind of thing, which is a much better
alternative than going back to a more traditional development style.
David Ungar's "transporter" is an existing solution, but it doesn't deal
with "loose morphs" very well. He has an interesting paper about all these
issues in pages 28 to 33 of the "Self 4.1 Programming Environment" manual
that comes with the system, so I won't go into more details here.
--~=~= Part 2 =~=~--
After playing around with this object for a while, it becomes annoying to
set the pegs to the initial configuration all the time. So I add this
slot to the morph (board):
centerHole <- ()
Then I point to the center hole in the board and choose "submorphs" from
the right button menu. This shows two choices and I pick "holeMorph", and
then "outliner" from the menu that comes up next. So now I have an outliner
representing the center hole, and I go to the 'centerHole' slot in the board
and drag its arrow to point to that instead of the empty object the line
above created. Now it is simple to create a new slot in the board that
does what I want:
resetBoard = ( morphsDo: [ | :m |
m morphTypeName = 'holeMorph' ifTrue: [ m hasPeg: m != centerHole ]
]
)
And I test it... nothing appears to happen. I have to send "changed" to
the board to see the effect. So I make this expression a button and it
become much easier to play several games to get the feel for the thing.
Note that as things currently stand, if I make a copy of the game board
it won't work right since its "centerHole" slot will be pointing to the
hole in the original board, not its copy of it. We should make a local
version of the "copy" method and fix this, but I won't do it here.
The idea was for the computer to play by itself, however. So I add a new
object to represent a possible move by creating this slot in the board
object:
moveProto = ( | parent* = ( | parent* = traits clonable | ).
from. skip. to
| )
This isn't a very good prototypical object since the move it represents
is wrong (from, skip and to slots are initialized to nil), but I will
actually make use of this in a little while. Now I add another slot to
the board to hold all the possible moves:
allMoves <- list copyRemoveAll
This will also have to be carefully updated if the board is ever copied.
Here is a slot to hold the moves as I build them (in the board object):
currentMove
Nearly all the elements are in place for teaching the computer what moves
are possible. This is the method that does it (in the board object):
holeTouched: hole = ( | backMove |
nil == currentMove ifTrue: [
currentMove: moveProto copy.
currentMove from: hole.
^ self
].
nil == currentMove skip ifTrue: [
currentMove skip: hole.
^ self
].
currentMove to: hole.
allMoves add: currentMove.
backMove: currentMove copy.
backMove from: currentMove to.
backMove to: currentMove from.
allMoves add: backMove.
currentMove: nil
)
Of course, the board won't ever get a 'holeTouched:' message if I don't patch
the slot in the hole parent object like this:
leftMouseDown: evt = ( hasPeg: hasPeg not.
owner holeTouched: self.
changed)
Ok. So now I click on the first hole and not only does its peg go away
but I can see that the currentMove has changed from nil to an object. Looking
at that object I see a holeMorph in the from slot but nil in the other two.
So I click on the hole next to the first and can see it get added to the
currentMove. Click on the third hole and I see currentMove become nil again,
while the allMoves list now includes two objects. So I inspect them to see
if they are ok and there seem to be no bugs so far. Now I dismiss all five
objects (two moves and three holeMorphs) and click on the next three holes.
I check that allMoves does have 4 elements now and then go on to point out
the remaining 17 horizontal moves (and their inverses). Same thing for the
19 vertical moves and allMoves now includes 76 moves total. Now that the
board has a good idea about its own topology, I change its slot in order
not the mess up allMoves:
holeTouched: hole = (self)
In fact, I could now remove the currentMove slot since I don't intend
to use it ever again. But I will leave it in there for now since it might
come in handy for other things. The allMoves is another good example of
an object that is not specified in source code.
Note that the move objects aren't just data structures like in C or Pascal,
but true actors that have an important part in solving this puzzle. So I
will add some methods to their parent:
isValid = (from hasPeg && [skip hasPeg && [to hasPeg not]])
This will allow us to separate those moves that are possible in a given
board configuration from those that are not. If a move is valid, the
computer can use it to change the board:
doIt = (from hasPeg: false. skip hasPeg: false. to hasPeg: true)
While this does get the job done, it goes by too quickly for me to see
exactly what has changed in the board. This method slows things down:
animate = ( | r = paint named: 'red' |
from colorThrobTo: r TimePerThrob: 0.3 NumThrobs: 2.
skip colorThrobTo: r TimePerThrob: 0.3 NumThrobs: 2.
to colorThrobTo: r TimePerThrob: 0.3 NumThrobs: 2.
doIt)
We can test this by sending something like "allMoves first animate" to
the board. That didn't work... a little investigation shows that this
is trying to send "colorAll:" to the holeMorph, but as defined by
circleMorph this doesn't really change the color at all. So I grab a copy
of the method and patch it to change the color, and the animation starts
working perfectly: the affected holes glow red for about half a second
making it easy to see what was moved.
Here is a very interesting expression to evaluate in the context of the
board object:
| valid |
valid: allMoves copyFilteredBy: [ | :m | m isValid ].
valid size < 1 ifTrue: [ ^ 'finished!' ].
(valid at: (random integer: valid size)) animate.
self
I made this into a button. Now I can press it and the computer will choose
one move at random from the currently valid ones. It can now play the game
by itself. Not very well, though - its first random game leaves 7 pegs on
the board, while the second 4 pegs. The animation turned out to be very
neat to watch.
It would now be trivial to code a simple depth first search and be done
with it, but it would take far to long to return the answer. Since I am
interested in any correct solution, a genetic algorithm is a better choice.
A possible game must be somehow coded as a "genome" for the search to be
able to use it. Here is a simple solution: a vector of 32 numbers where
the first number encodes the first move and so on. A move will be encoded
the following way: we will generate a list of possible moves for the
current board configuration (as in the code above) and will use the remainder
of the division of the number by the size of the move list to select a
move from the list. A mutation can simply be incrementing by one a randomly
chosen number from the 32. Note that most games will be shorter than 32
moves - the left over numbers are simply ignored.
This is really a bad genome since incrementing a number in the middle
will change the meaning of all the numbers that follow it. But I am
hoping that it will be good enough for me to get an answer.
It might be interesting for the genome to have some visual representation,
so:
frameMorph copy
I "show morph" and see what looks like a small blue button. That will do.
Now I copy the parent slot to the background and drag the arrow in the
original slot to point to that, so I can make the slot:
morphTypeName = 'genomeMorph'
In the genomeMorph itself, I add this slot:
genes <- vector copySize: 32 FillingWith: 50
and:
cachedScore <- 0
Back to the geneMorph parent object, these slots will be needed:
copy = ( | c | c: resend.copy. c genes: genes copy. c )
mutate = ( | i | i: random integer: genes size.
genes at: i Put: (genes at: i) + 1.
cachedScore: 0)
score = (0 != cachedScore ifTrue: [ ^ cachedScore ].
cachedScore: board play: self.
morphsDo: [ | :m |
m morphTypeName = 'labelMorph' ifTrue: [
m label: cachedScore printString
] "update label, if any"
].
cachedScore)
geneAt: num = (genes at: num)
board = ()
I have to grab the pointer for this last slot and drag it over the the board
object. This will allow the "score" method to work (otherwise the geneMorph
objects would know nothing about boards since I have not yet made any
"global variables". I then add a labelMorph to the geneMorph:
labelMorph copy
with the usual "show morph" and then "embed in morph below". It is too dark,
so I change its color to white. Much better. It still reads 'a labelMorph'
but that will be converted to a number soon enough (when 'score' is first
invoked). The 'play' method in the board object should be simple enough:
play: genome = ( | valid. choice. moveNum <- 0 |
resetBoard.
[valid: allMoves copyFilteredBy: [ | :m | m isValid ].
valid size < 0 ] whileTrue: [
choice: genome geneAt: moveNum.
choice: choice % valid size.
(valid at: choice) doIt.
moveNum: moveNum + 1.
].
32 - moveNum)
This is the most complex piece of code I have written so far, so I will
check it out in the debugger by evaluating "halt. score" in the genomeMorph
object. The first play is downwards - looks ok... second play is up, also
pretty good... third play worked too, so I will just risk letting it
finish from here. Perfect - I got 7 as an answer (now also indicated in
the label in the genome) and the board shows the final configuration.
Now I will make a copy of the genomeMorph:
copy
"show morph" and we get something that look like the first one. The score
shows 7, of course. I'll manually set the cachedScore to 0 and ask for
the score again just to make sure. Yup - the exact same game. Now we send
in a radiation bolt on this second genome ;-)
mutate
Ask for the score and we get 7 again. Hmm... the board looks the same.
Check the genes... yes: gene 19 is now 51. Of course - many mutations have
no direct effect since they are in an ignored part of the genome. But they
could have a future effect if a mutation in an early gene make the game
last longer. Ok, so I will mutate a few more times until one of the first
genes is changed... 3 more times is good enough. Now asking for the score
still returned 7 but with a very different board configuration. One more
mutation and the score falls to 9.
It would be interesting to be able to see what is going on in slow
motion, so I will add a method to the board to play just one step at
a time. I can reuse the "currentMove" slot from before. I will add
a "nowPlaying" slot to hold the genome we are interested in and also
these two methods (all in the board object):
wantsMorph: m Event: evt = ( m morphTypeName = 'genomeMorph' )
addDroppingMorph: m Event: evt = (nowPlaying: m.
currentMove: 0.
resetBoard.
changed)
Now I can just drop a genomeMorph on the board and it is ready to play. The
dropped genomeMorph simply disappears, but that is ok since we can recover
it from the nowPlaying slot in the board (at least until we drop yet another
genomeMorph). A slight variation of the button that was previously created
finishes the job:
| valid. choice |
valid: allMoves copyFilteredBy: [ | :m | m isValid ].
valid size < 1 ifTrue: [ ^ 'finished!' ].
choice: nowPlaying geneAt: currentMove.
choice: choice % valid size.
(valid at: choice) animate.
currentMove: currentMove + 1.
self
Anytime I want to know what game a given genome represents, all I have to
do it grab a copy of it and drop it on the board, then press this button
until the game is over.
All that is left it to create a geneticSearch object. Since this program
has been so graphical up to now, I might as well make this one too:
rowMorph copy
"show morph" yields another ugly, brown box. First thing is to change that
to orange and make its width "shrink wrap". A few extra slots would also
be nice: 'population', 'genNumber', 'numToView'. I'll set the numToView
slot to 10 initially. Here is a method to initialize the search:
setRandom = (
population: vector copySize: 512 FillingWith: 0.
population do: [ | :val. :index |
population at: index Put: genomeProto copyRandom
].
genNumber: 1.
self)
Obviously this needs a 'genomeProto' slot, which I create and make it point
to the first genomeMorph object I created. In the genomeProto's parent
slot I add this method:
copyRandom = ( | c |
c: copy.
c genes do: [ | :val. :index |
c genes at: index Put: (random integer: 33) + 33
].
c mutate.
c)
Since I will be using the relative ranking of the various genomes a lot, it
makes sense to add this method to the genomeProto parent:
< g = (score < g score)
Now we can get a visual clue of how the search is going by adding this method
to the geneticSearch object:
showResults = ( | m |
removeAllMorphs.
m: labelMorph copy.
m label: genNumber printString.
addMorph: m.
0 to: numToView - 1 Do: [ | :i |
addMorph: population at: i "first few elements"
].
m: morph copy.
m color: color.
addMorph: m.
population size - numToView to: population size - 1 Do: [ | :i |
addMorph: population at: i "last few elements"
].
self)
Now I evaluate "setRandom. population sort. showResults" in the geneticSearch
object and get a very strange result. The generation number is 1 and the
first few genomes score 3, 4, 4, 4, 4, 4, 4, 4, 4, 4 while the last few
score 12, 12, 26, 26, 13, 12, 12, 12, 12, 12. I would have expected the
larger scoring genomes at the very end. I'll copy one of them to the board
and see if there is anything strange. It looks ok - I have actually done
this myself (leave 26 pegs on the board when trying to figure out what was
the worse I could do). The other one is simply a reflection of this same
game - there are actually two more, but we wouldn't expect them all to
show up in a population of only 512. The 13 peg game looks ok, as does the
next 12 peg one. So they are only out of order. If I evaluate "(population
at: 511) score" I get 26 as an answer, so obviously the visual representation
is wrong. By changing all the 'addMorph:' to 'addMorphLast:' in the
'showResult' method I get my first generation as I expected it.
For all you "Star Trek" fans out there, I now add the key method to the
geneticSearch object:
nextGeneration = ( | last <- 256. child <- 256 |
[child < 512] whileTrue: [
0 to: last - 1 Do: [ | :mom |
population at: child Put: (population at: mom) copy mutate.
child: child + 1
].
last: last / 2.
].
population sort.
genNumber: genNumber + 1.
self)
This copies the most fit elements from the current generation into the next,
and their mutated versions to replace the weaklings. The guy in front gets
9 children, while someone at rank 250 will get only one. We can showResults
to see:
2 - 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, .. 10, 10, 10, 10, 10, 10, 11, 11, 11, 11
>From now on I will only indicate the first and last two genomes:
3 - 3, 3, ..........12, 13
4 - 3, 3, ..........11, 13
5 - 3, 3, ..........11, 12
This doesn't show it, but all 10 first genomes have a score of 3 in this
generation. A few more times:
6 - 3, 3, ..........13, 26
7 - 3, 3, ..........14, 26
8 - 3, 3, ..........12. 13
9 - 3, 3, ..........12, 12
At this rate it will take quite a while. I will start skipping 10 generations
at a time ('10 do: [nextGeneration]. showResults'):
19 - 3, 3, .........11, 11
29 - 3, 3, .........11, 12
39 - 3, 3, .........12, 12
49 - 3, 3, .........12, 12
How about doing 100 generations at a time? That takes 28 seconds on the
Sun Ultra 5 machine I am using.
149 - 3, 3, .........12, 12
249 - 3, 3, .........12, 12
349 - 3, 3, .........12, 12
449 - 3, 3, .........12, 14
Calculating 1000 generations takes 4 minutes and 44 seconds.
1449 - 3, 3, ......... 11, 14
2449 - 3, 3, ..........12, 14
3449 - 3, 3, ..........12, 14
4449 - 3, 3, ..........12, 12
I decided to skip ahead 10000 generations to see if it looks like there
might be any progress. That should take nearly an hour.
14449 - 3, 3, ........... 12, 14
It doesn't seem like I am getting any progress. I'll take a quick look
at the best and worst genomes... hmmm, they are identical except for a
mutation on the very first gene. It seems that a single genome has totally
dominated the gene pool and the search got stuck. Besides the obvious
problem of the gene encoding being a bad one, the sort in the nextGeneration
method tends to leave all the first genomes alone. If I reverse the population
vector before sorting it, then things might be shaken up a bit. The first
few generations would then be:
1 - 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 ....13, 13, 15, 15, 26, 26, 26, 26, 26, 26
2 - 3, 3, 3, 4, 4, 4, 4, 4, 4, 4 ....10, 10, 10, 10, 10, 10, 10, 11, 11, 26
3 - 3, 3, .... 12, 13
10 - 3, 3, .... 11, 12
50 - 2, 2, ..... 10, 13
100 - 2, 2, ...... 12, 13
500 - 2, 2, .......12, 13
1000 - 2, 2, ....... 13, 13
This certainly is much better. What would be the effect of having a larger
population? The setRandom and nextGeneration methods have to be changed
for that. I edit the nextGeneration so that it works for any power of 2
sized population and setRandom to create a population of 2048.
1 - 3, 3, 3, 3, 3, 3, 3, 4, 4, 4...26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26
2 - 3, 3, 3, 3, 3, 3, 3, 3, 3, 3...12, 12, 12, 12, 13, 14, 26, 26, 26, 26, 26
3 - 3, 3, ... 14, 26
8 - 2, 2, 3, 3, .... 26, 26
10 - 2, 2, ... 13, 14
50 - 2, 2, ... 13, 13
100 - 2, 2, ... 13, 13
500 - 2, 2, .... 13, 13
1000 - 2, 2, .... 13, 13
Since it is now time to go home, I simply leave it running all night in
order to skip ahead 20000 generations.
Well, that didn't help:
21000 - 2, 2, ..... 11, 11
Looking at a few random individuals it is obvious that the whole population
has degenerated into slight variations of one successful individual. Ok,
no more Mr. Nice Guy! Time to get serious and introduce sex into the search.
First we allow a genome to borrow half of the information from another by
writing in the genomeMorph parent object:
mateWith: gen = (
0 to: genes size - 1 By: 2 Do: [ | :g |
genes at: g Put: gen geneAt: g
].
mutate)
And the search is modified to include matings:
nextGeneration = ( | last. child. ps |
ps: population size.
last: ps / 2.
child: last.
[child < ps] whileTrue: [
0 to: last - 1 Do: [ | :mom |
population at: child Put: (population at: mom) mutate.
child: child + 1.
].
last: last / 2.
].
((2 * ps) / 3) to: ps - 1 Do: [ | :me |
(population at: me) mateWith: (population at: (random integer: ps))
]. "the last third of the population has sex"
population reverse sort.
genNumber: genNumber + 1.
self)
Now to see if this has any effect:
1 - 3, 3, 3, 3, 3, 4, 4, 4, 4...26, 26, 26, 26, 26, 26, 26, 26, 26, 26
2 - 3, 3, 3, 3, 3, 3, 3, 3, 3...13, 14, 14, 16, 26, 26, 26, 26, 26, 26
3 - 2, 3, ...26, 26
4 - 2, 3, ...26, 26
5 - 2, 2, ...26, 26
10 - 2, 2, ... 26, 26
50 - 2, 2, ... 26, 26
I am going to get my hopes up and use this expression to skip ahead while
checking for the result:
2000 do: [nextGeneration.
(population at: 1) score = 1 ifTrue: [^self]].
showResults
2050 - 2, 2, .... 26, 26
Now a quick check to see if this is going anywhere... ok - there seems
to be a healthy variation. Skip 20000 ahead:
21986 - 1, 1, 2, 2, 2, 2, 2, 2, 2, 2...14, 26, 26, 26, 26, 26, 26, 26, 26, 26
Wow, that was close! If I had reached generation 22050 without a solution
I would have given up. The two solutions seen above differ only in the last
move: the first one ends with a peg in the middle while the second with a
peg in the very bottom.
I like to use the infinite space in Self's Kansas user interface to spread
my objects around while developing, but now I will bunch them all together
for a family picture... done:
http://www.merlintec.com/pegs.gif