one of those cool programs that you just have to share...

Coders forum. Discuss techniques, swap code snippets, ask for help etc. relating to all forms of software development.
User avatar
venusian
Baaaaaaa!
Baaaaaaa!
Posts: 6655
Joined: Wed Nov 06, 2002 2:22 pm 0
Location: South Gloucestershire

Post by venusian »

The Commodore PET screen is 40x25 . Using the standard PETSCI 2x2 block characters you can do 80x50 graphics in monochrome. That's 4000 bits; 2^4000 images. At approximately the PET's refresh rate, 64 frames per second, that'd take 2^3994 seconds. Rounding to 64 seconds per minute, that's be 2^3986 minutes. At 64 minutes per hour, that's 2^3980 hours. Let's helpfully give outselves 32 hours in the day. That's 2^3975 days. 512 days per year - 2^3966 years. 1024 years in a millenium - 2^3956 millenium.

It's going to take a while, but just wait until we upgrade to VIC-20 graphics.
User avatar
Dvorak
Baaaaaa!
Baaaaaa!
Posts: 4560
Joined: Wed May 08, 2002 7:37 am 0
Yahoo Messenger: d3dxquaternion
Location: Germany

Post by Dvorak »

Why wandering sequentially through really huge spaces? :D

Take for instance the human genome. That's not just a 256 byte sequence.
3×10^9 bases on one DNA strand, each base either A, G, C or T (each base therefore coding 2 bits) resulting in a 715 MB sequence.
Now, does Nature walk sequentially through the space of all possible 715 MB strings in search of cool human-like beings?

(Insert dramatic rhetorical pause here)

Nay, it doesn't.
So, let's learn from Mother Nature.

[DISCLAIMER: The following algorithm will not work if you believe in Intelligent Design]
Generate a random bit sequence representing a (random) image, program, sound - you name it.
Not just one but, say, 200.
That's your population.
Loop: Decide which of them are interesting, and which are not.
(Either by looking/trying/listening at them or by some kind of automated evaluation function)
Drop the worst.
Take the 10 best.
Allow the best to have sex.
(I termed it so just for the effect. What I mean is: Generate from randomly chosen two of the best parent images child images by crossing-over their bit sequences, i.e. taking one part from one parent, the rest from the other parent. Cut at a random bit location).
Do some random mutations (arbitrary bit flips) if you like.
Add the new children to the population.
Goto Loop as long as you like.

Well, that's it basically.
It's called Genetic Algorithms and is pretty cool. :)

You can e.g. evolve neural networks, too, if you represent the weights as a bit sequence.
Hm, maybe even pixel shader.
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
User avatar
Kemper_Boyd
Sheepie Whore
Sheepie Whore
Posts: 11967
Joined: Wed Jul 31, 2002 9:15 pm 0

Post by Kemper_Boyd »

Yes, but how do you evaluate Doom5 out of a gigabyte search space?
You'd still be pissing in the ocean even with very capable scoring methods.

Mother Nature may not try every possibility but it still does a metric
shitload of work.

And to make another point Mother Nature didn't go searching for human
beings. They are just one interesting outcome from potentially gazillions
of lifeforms.

It's the old find a type and finding an instance problem. :)
User avatar
Little stoned kiwi
Baaaaaa!
Baaaaaa!
Posts: 4598
Joined: Mon Oct 27, 2003 6:05 am 0
Location: Christchurch

Post by Little stoned kiwi »

I read Out of Control:The New Biology of Machines, quite a few years ago now, and it changed the way I think about the world. I recommend it to anyone enjoying this thread.

The only real problem with evolutionary methods is that they are unpredictable, it's very difficult to recreate the exact same results repeatedly. Inefficience is another, you can generate a result, but it won't necessarily be the quickest or best solution. Inflexability, you can't crack open the solution you bred and alter it - if you can understand it.

Maths is a good application: say you have a (math)function and want to find the maximum value within a set range. You can have the computer 'breed' inputs and test the outputs, encouraging selection amongs those that produce high values. Trouble is, you don't know if your system generated a truly accurate result(which depends heavily on your selection process). It may not be any quicker than checking every possible input variable.
At the end of the day, it may just be easier to crack open a calculus book...
If they think you're crude, go technical; if they think you're technical, go crude. I'm a very technical boy.
User avatar
Dvorak
Baaaaaa!
Baaaaaa!
Posts: 4560
Joined: Wed May 08, 2002 7:37 am 0
Yahoo Messenger: d3dxquaternion
Location: Germany

Post by Dvorak »

Kemper_Boyd wrote:And to make another point Mother Nature didn't go searching for human
beings. They are just one interesting outcome from potentially gazillions
of lifeforms.

It's the old find a type and finding an instance problem. :)
Yes, she wasn't searching, but she did find.
And that's what I find most interesting: start an open-ended evolution and see where it will take you to. :)
Just don't expect Quake 5 somewhere on the evolutionary trajectory.

In a more profane view: Genetic Algorithms are nothing but an optimisation tool among other tools.
For some problems they are appropriate, for others they're not. Little stoned kiwi gave some hints at the disadvantages:
Little stoned kiwi wrote:unpredictable...inefficient...inflexible
True. No method for control freaks.
But still fascinating for those who dare not walking n-spaces (with n >> any large number). :)
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
User avatar
Dvorak
Baaaaaa!
Baaaaaa!
Posts: 4560
Joined: Wed May 08, 2002 7:37 am 0
Yahoo Messenger: d3dxquaternion
Location: Germany

Post by Dvorak »

Little stoned kiwi wrote:At the end of the day, it may just be easier to crack open a calculus book...
If calculus can provide you with an direct algorithm to your problem, then no optimisation algo is needed,
since analytical solutions are always better than numerical ones.
But the power of differential equations for modelling real-world problems is quite limited.
You can find yourself stuck even with simple looking equations, when there is no (closed or even none) solution.

No finding of Quake 5 through Diff Eqns, I tell you. :)
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
User avatar
Little stoned kiwi
Baaaaaa!
Baaaaaa!
Posts: 4598
Joined: Mon Oct 27, 2003 6:05 am 0
Location: Christchurch

Post by Little stoned kiwi »

Dvorak wrote:
Little stoned kiwi wrote:At the end of the day, it may just be easier to crack open a calculus book...
If calculus can provide you with an direct algorithm to your problem, then no optimisation algo is needed,
since analytical solutions are always better than numerical ones.
But the power of differential equations for modelling real-world problems is quite limited.
You can find yourself stuck even with simple looking equations, when there is no (closed or even none) solution.

No finding of Quake 5 through Diff Eqns, I tell you. :)
That remark was in the context of my math example. A more general comment may be that it's sometimes just easier to do it the 'hard' way instead of messing around with something that may or (probably)may not work. i.e. if you want Quake 5 then get a design team together to write it, rather than having a super-computer number crunch in the hope it works.
Although your point is valid that genetic programming can be useful for optimizing simple tasks.

One application that excites me is for games. An A.I. that you can't work out because it's always changing according to your actions. Or a game with an eco-system, perhaps your resources are codependent so that you have to be carefull not to plunder them(like you do in most RTS games), or plunder and exaust your enemies resources. :twisted:

I did a little experimentation while at uni because they kept assigning crap little games to write at the end of each programming paper, but I was too busy to really get anything up and running - and the fact that you can't earn any more than 10 out of 10 for meeting requirements wasn't much encouragment either.
If they think you're crude, go technical; if they think you're technical, go crude. I'm a very technical boy.
Mr Sheen
Baaa!
Baaa!
Posts: 182
Joined: Sat Nov 06, 2004 10:59 am 0

Post by Mr Sheen »

Ooo! More great stuff.

Come on then, who's going to help me work this one out here:

I would guess that every program that sets up mode13h in the same way would all start with the same byte sequence, which puts the roughly at point A in the array of possibile combinations...given a start point and the next position in the array space that destroys in initial 13h setup, you have a space that can output visual code.

If someone can give me those two number I will write a distributed code generator that puts out random (but indexed) chunks of code and runs them through debug to find anything that runs without error.

Woooohoo! I can't for the one that says Hello alan on a nice classic sinusy scroll text that is already there! 8O BONG!

Go mathswonderkids! Give me those two magic numbers,13h valid, 13h invalid.
<spam removed>
Mr Sheen
Baaa!
Baaa!
Posts: 182
Joined: Sat Nov 06, 2004 10:59 am 0

Post by Mr Sheen »

ynohtna wrote:You, my lad, need to read Godel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter.
Thank you, it's coming to papa.

I read that Bill Bryson book few months ago too, some of the stats were great, some of the facts were great too, I really enjoyed his curiosity. Earth is an amazing machine that just seems to know how to keep itself running, the salt filters etc, huge long thousand year processes that just work.

I remember his description of Yosemete especially vivid, how you could have a super giant eruption. Really quite sppoky, but good.

laptop excuse, cant tyupe of laptop keyboards
<spam removed>
User avatar
Little stoned kiwi
Baaaaaa!
Baaaaaa!
Posts: 4598
Joined: Mon Oct 27, 2003 6:05 am 0
Location: Christchurch

Post by Little stoned kiwi »

Mr Sheen wrote:Woooohoo! I can't for the one that says Hello alan on a nice classic sinusy scroll text that is already there! 8O BONG!
You need to create a check system that examines the random programs, and giving preference to ones that are close to producing 'Hello alan' in sinusy scroll text. Reiterate and breed the prefered choices, until the output really is 'Hello alan' etc...

So if you already know what 'Hello alan' in scroll text looks like in order to test your population, you may as well just write a program that produces that output...haven't you been paying attention?
If they think you're crude, go technical; if they think you're technical, go crude. I'm a very technical boy.
User avatar
craigt
Baaaa!
Baaaa!
Posts: 896
Joined: Tue Feb 15, 2005 12:23 am 0
Location: Ye Olde Somersetshire

Post by craigt »

failrate wrote:This puts me in a mind of an old science fiction story I read about a team of programmers and engineers employed by a Tibetan cult to calculate the 99.999 names of God. They used iterative generation with certain rules (like a consonant-vowel pair would always be followed by another consonant or something like that) in order to invalidate certain results and minimize the generated set. Great story, wish I could remember the title, as I don't want to spoil the ending :twisted:
Thats 'The Nine Billion Names of God' by Arthur C. Clarke. It's in his 'Of Time and Stars' short stories book, which strangely enough isn't on Amazon.co.uk!

http://www.ffbooks.co.uk/c0/c739.htm
User avatar
wossname
Baa!
Baa!
Posts: 52
Joined: Fri Oct 07, 2005 8:46 pm 0

Post by wossname »

Dvorak wrote:Take for instance the human genome. That's not just a 256 byte sequence.
What????? Oh shit, now I have to make my .STACK bigger.

*mutter, gripe*
I give good code.
Kronos

Post by Kronos »

Nice Windows (half the dos stuff borkes on XP) 256byte demo-ette [urlhttp://www.256b.com/download/351]here[/url]

and two lovely 64k demo's

here

here2

and not forgetting the daddy of 64k Demos Heaven Seven here
User avatar
Glyndwr
Baaaaaa!
Baaaaaa!
Posts: 3802
Joined: Thu Jul 17, 2003 5:12 pm 0
Yahoo Messenger: glyn_richards2003
Location: Norwich

Post by Glyndwr »

Dvorak wrote:
oktup wrote:Are you sure that disassembly is correct? Wouldn't ...

Code: Select all

corrected disassembly
... be correct?

:?:
Looks better, yes. :D
No DBs inside the code, and RET as last statement looks very convincing.
Ha-ha... I was just going to post about the DBs, but too slow again!

Code: Select all

public class Geeks : TheEarth {
}
User avatar
Dvorak
Baaaaaa!
Baaaaaa!
Posts: 4560
Joined: Wed May 08, 2002 7:37 am 0
Yahoo Messenger: d3dxquaternion
Location: Germany

Post by Dvorak »

Glyndwr wrote:Ha-ha... I was just going to post about the DBs, but too slow again!
Indeed. Nine months is slow... :wink:
>take off sunglasses
Seamen and fishermen alike swear to have heard voices in the rising tide. Inhuman screams, some of them say.
Post Reply