Qbasicnews.com

QBasic => QB Discussion & Programming Help => Topic started by: qbiscool on March 06, 2004, 01:45:03 AM



Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 01:45:03 AM
I was wondering if anybody knew how to write a genetic algorithim or a evolutionary algorithm. I need help becuase i am interested in writing AI and need to know what i need to write it.

If any body knows any good tutorials that i could read on it please tell me


Title: Evolutionary Algorithims
Post by: Moneo on March 06, 2004, 01:49:15 AM
I think what you are referring to is heuristic programming, which means that the program "learns" from previous experiences. You're right, AI would be the place to read up on this. I've just heard about it but have no experience.
*****


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 01:51:49 AM
Thank you. I have some expierence writing them but would like to know what the best thing to write them is in(ie. C++, ASM, Batch)


Title: Evolutionary Algorithims
Post by: na_th_an on March 06, 2004, 01:56:27 AM
Well, the most suited languages for learning AI are PROLOG and LISP. This is a wide area, and very interesting. I suggest you to download a prolog interpreter, learn the basics, and then go for AI.


Title: Evolutionary Algorithims
Post by: Moneo on March 06, 2004, 01:58:02 AM
I don't think the language will matter. I suggest you use whatever language you are most proficient in, so you can concentrate on the problem and not be hampered with the language.
*****


Title: Evolutionary Algorithims
Post by: na_th_an on March 06, 2004, 01:59:33 AM
Nah, LISP and PROLOG are specially designed to learn AI. I mean, everything is solved, you just have to code what's needed. You don't have to hassle with data types and stuff you need to build an AI system using another language (a procedural or object oriented language). PROLOG is a predicative language: you set up predicates. You tell the interpreter what to do but not how, if that makes sense.


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 02:00:20 AM
Sorry na_th_an but i agree with moneo. i have never even heard of PROLOG and LITH and i like qbasic the best.

maybe later i will try PROLOG


Title: Evolutionary Algorithims
Post by: na_th_an on March 06, 2004, 02:01:57 AM
Okay, do what you like. But you'll understand the pain to code a minimax algorithm and a A* search in QB, when it is done in 20 lines of code using PROLOG. You have to code a tree structure and lots of recursive functions... No way :P

I've studied lots of AI at college. We use PROLOG, LISP and CLIPs 'cause you go directly to what you want to do.

You can do a natural language interpreter which learns and asks you in 40-50 lines of code using PROLOG, for example.


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 02:03:47 AM
have you ever coded any AI before na_th_an(ie. used PROLOG)
or used qbasic to do it


Title: Evolutionary Algorithims
Post by: na_th_an on March 06, 2004, 02:06:05 AM
I've coded what's called a "WHY/WHERE/WHEN/WHAT" interpreter. It knows some facts, and asks about complementary info. You reply using natural language (well, sorta). Then it learns and uses the aquired knowledge to keep learning.

I coded it for an exam, I mean, you sat on the computer and coded it in 1 hour. It had to work for you to pass :P


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 02:09:38 AM
cool exam(all of ours are just written tests). Were can i find a Prolog interpeter(I googled it and couldnt find it).

Ya and im interested in knowing what a WERE/WHAT/WHEN/WHY interpeter is.


Title: Evolutionary Algorithims
Post by: na_th_an on March 06, 2004, 02:12:29 AM
That was on our last chapter, so I guess it is advanced stuff. You should learn the basics first. I'll try to dig for info and tutorials, just keep tuned.

A good prolog interpreter (free) is SWI Prolog. It has a Windows port that works fairly well. http://www.swi-prolog.org/


Title: Evolutionary Algorithims
Post by: Frobozz on March 06, 2004, 02:15:48 AM
Quote from: "qbiscool"
cool exam(all of ours are just written tests). Were can i find a Prolog interpeter(I googled it and couldnt find it).

Ya and im interested in knowing what a WERE/WHAT/WHEN/WHY interpeter is.


You might want to try here:
http://pauillac.inria.fr/~diaz/gnu-prolog/

Edit:  Darn...  three minutes slow.  :P


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 02:28:08 AM
Has anybody ever read the book prey(great book). That book was what made me want to start AI. i was wondering if prolog could write evolutionary algorithims.

Kinda like making a program and then running it and everytime it is run due to different random circumstances the outcome is always different. that is probaly realy advanced but that is were i want to end up.

Or maybe using low level intellegence(like birds flocking is a result of all the birds thinking "stay close to the bird next to you but dont bump into them) to write a AI program and just see were it takes you.

Please tell me if any of this is possible and if it is hard to do.



PS. How do you spell algorithm


Title: Evolutionary Algorithims
Post by: R@dioman on March 06, 2004, 03:35:49 AM
I don't think true AI would ever be possible the way we're going at it. AI can't be coded because you'll never know if the conscienceness you created is an outcome of many conditional statements that recieves data and outputs it in ways we can understand. The being would have to learn about its surroundings from the begining like we humans have done since birth. But who knows, maybe we are simply an automaton where our conscienceness can be mapped out in one gigantic flow chart.

qbiscool: Yes, I think that is how you spell algorithm


Title: Evolutionary Algorithims
Post by: PlayGGY on March 06, 2004, 03:57:13 AM
Nathan is right: you shouldn't use QB for this.

Lisp would be great, but so would C++/C#, in that it would be easier to hook you AI code to a game (not to say it is impossible using Lisp, of course).  QB doesn't have lots of features (like classes) that makes dealing with this stuff easier.  Wow, imagine a neural net in QB!  That would be one big mess.


Title: Evolutionary Algorithims
Post by: qbiscool on March 06, 2004, 11:36:09 AM
Quote
I don't think true AI would ever be possible the way we're going at it. AI can't be coded because you'll never know if the conscienceness you created is an outcome of many conditional statements that recieves data and outputs it in ways we can understand. The being would have to learn about its surroundings from the begining like we humans have done since birth. But who knows, maybe we are simply an automaton where our conscienceness can be mapped out in one gigantic flow chart.


I think the only way to really create AI is to use low level rules.
(ie. birds dont flock becuase its there instinct. they flock south becuase of certain low level rules like "if its cold start flying" or "stay close to the bird next to you but dont bump into them.)
or how termites create there mounds. they create extreamly complex mounds with a place for fresh oxegen, a place to remove C02 , and a place to get heat from and its all based on  low level rules (like if a termite has been here drop a dirt pellet).

This is the best way becuase with a few simple lines of code you will get a unpredictable program and if you add a few random chances you will get a different program outcome each time.
But the only way to code this kind of AI is to use a distributive proccess with multiple programs, computers, or agents.

If you had a problem you could just let the program solve it for you by adding a few of these low level rules.


Title: Evolutionary Algorithims
Post by: Z!re on March 06, 2004, 12:04:07 PM
[joke]
Or you could just create an entire universe and just have atoms.

"Few" rules, very simple to implement, and youre safe :lol:
[/joke]



I tried making an AI once, I had a type saying stuff like mass, velocity, legs and such...

Then i made my "creatures" ponder around a map, "learning" where to eat and what to eat, ie, brown was dirt, but the creature didn't know that, so ift tried to eat it, it don't get less hungry so dirt gets a lover "score" this went quite well actually.

It ended with a small flock of "grass eaters" (green pixels) and some "predators". The herding was a side effekt that come of the: 'Attack if weaker' statement, the herd is tronger than the lone predator.

It was kinnda cool to see, unfortunately the code is on my old HDD (a 125MB :P ) and I can't get it to work :cry:


But it would be farily "simple2 to write an AI, as long as you give it some boundries, in my code it was animals, so I knew in general what was needed.

Making a "universal" AI like ur mind (*drools*) is impossible. It canšt be done, we can't recreate the logics of human thinking, simply because there is no logic, everyone thinks differently and reason in different ways.

So make it an AI targeted for a specific field, and it's feasable.


(lot's of ramblings, if anything is completely wrong just ignore it, I'm tired)


Title: Evolutionary Algorithims
Post by: Agamemnus on March 06, 2004, 12:09:32 PM
Depends on what AI you want to make.

Quote
..... heuristic programming, which means that the program "learns" from previous experiences.


No, that's not right at all. Heuristic programming is when the AI uses heuristics to search. Heuristics are things that you know about the search that could make it easier for the AI to search: specific opening moves in chess games for example.

Genetic algorithm is very possible in QB. There are many versions of genetic algorithm, but this is the one that is easiest to implement (in QB):

[line number]: IF [some state] THEN {[GOTO [line number1]], [set some state 1]} ELSE {[GOTO [line number 2]], [set some state 2]}

You have N of these lines per "program", or you have a pool of common lines for all programs, or both.

Each "program" has a set of lines that it executes one after the other by following the GOTO rules, and when there is no GOTO in that line, it simply goes to the next line. You can give each program a line execution limit (ie: how many lines it can execute before the next program starts executing), or you can let each program run to the end of the last line. This is not recommended because you will end up with infinite loops. :)

You define a bunch of arrays for each program and the associated lines.

You also need to define what each possible input and output state is. You can also have intermediate steps. Example:

CONNECT 4
INPUT STATE:
byte string (or integer array) that determine the amount of chips in each column.

OUTPUT STATE:
one byte that says where to put the next chip.

There are many different ways to structure the input and output states as well as the array that will allow each "program" access. I like putting the input state, output state, and intermediate state(constant) in one big string, for instance:

110001110110011011 1111110101 101
input state, intermediate/constant state, output state

Each line accesses the values of strings of bits in the string to determine their T/F value. Then, the output state is read off the end and it's the next player's turn.

THEN, you need to figure out a way to recombine each program to make "new" programs. There are BILLIONS of ways to do this. For instance, you can get the top 50% programs and then you can randomly merge them with each other to create another 50% (while the bottom 50% are erased), leaving the initial top 50% intact. You can also have a merging pattern for each program which says what bits should be left behind and what bits should be copied over. You can also have it stay somewhat random and also depend on the relative wins for each program.

You can merge two programs at a time, three at a time, or you can merge each program with all the other programs. There are many ways to do it!

You REALLY need a CLEAR understanding of the input and output states and the FRAMEWORK of your program/game/puzzle/question to be able to do this correctly. STRUCTURE your output in SUCH A WAY so that the output is ALWAYS possible: for connect 4, for example, an output to a filled column should not be allowed.


Title: Evolutionary Algorithims
Post by: R@dioman on March 06, 2004, 09:40:19 PM
Quote
qbiscool wrote: I think the only way to really create AI is to use low level rules.

I believe that's our only hope. It would be an evolution process. Life is so diverse because of the incredibly complex flux in biological ecosystems and physical phenomena. All we are is one manifestation of adaptative process. It's crazy that evolution created the mind. I hear it's more complex than the universe itself. But it was given to us through evolution for the mere fact of survival. All our biological adaptations are yielded for defensive purposes.


Title: Evolutionary Algorithims
Post by: PlayGGY on March 07, 2004, 04:13:37 AM
Quote from: "R@dioman"
Quote
qbiscool wrote: I think the only way to really create AI is to use low level rules.

I believe that's our only hope. It would be an evolution process. Life is so diverse because of the incredibly complex flux in biological ecosystems and physical phenomena. All we are is one manifestation of adaptative process. It's crazy that evolution created the mind. I hear it's more complex than the universe itself. But it was given to us through evolution for the mere fact of survival. All our biological adaptations are yielded for defensive purposes.


If you are to beleive that the mind is purely physical, and is a by-product of evelution, then you need to rethink your other facts.

First, it couldn't be more complex than the universe, because it uses less matter (think about that one).

Second, the mind wouldn't be made for defensive purposes, it would be made for reproductive purposes.  In other words, the mind would be whatever would make it reproduce more.  It wouldn't necessarily be the thing that keeps it alive longer.


Title: Evolutionary Algorithims
Post by: R@dioman on March 07, 2004, 05:10:13 AM
PlayGGY: Evolution will reconfigure life to better defend itself in order to reproduce and stay alive.


Title: Evolutionary Algorithims
Post by: RST on March 08, 2004, 01:45:48 PM
Like you, I read Prey, was intrigued and tried doing some genetic algorthims. I later learned what I've coded only vaguely resembles standard genetic algothims, but if you want programswhere dots learn to navigate mazes or something, I'll see if I can find them.

They're similar to Aga's method. Each organism's "genes" are a series of letters, eg "LFFRWS H:FFDW". Each letter represents an action the organism can perform, and a parser goes through one each click. Certain stimuli, or combinations of stimuli, cause the parser to jump, like if the organism got hungry, the parser would go to H:. Like Aga's beloved GOTOs.  :wink: Then you just stick in the various reproduction methods, fitness testing, etc.

Aga: Could you recommend some resources for learning this stuff?


Title: Evolutionary Algorithims
Post by: PlayGGY on March 08, 2004, 02:10:03 PM
Quote from: "R@dioman"
PlayGGY: Evolution will reconfigure life to better defend itself in order to reproduce and stay alive.


Nope.

The way evolution "picks" what traits are passed on is made and only made by by what reproduces.  It doesn't matter how long you are alive.  Of course, there is usually a bigger chance the longer you are alive that you will reproduce, so in a sense you are right.


Title: Evolutionary Algorithims
Post by: R@dioman on March 08, 2004, 02:27:40 PM
PlayGGY: The first protein cells were created for micro-organisms by the evolution process of natural selection so they wouldn't get eaten by other m-o's. But it's hard to say what's the correct theory. You make good points.


Title: Evolutionary Algorithims
Post by: PlayGGY on March 08, 2004, 05:28:16 PM
Quote from: "R@dioman"
PlayGGY: The first protein cells were created for micro-organisms by the evolution process of natural selection so they wouldn't get eaten by other m-o's. But it's hard to say what's the correct theory. You make good points.


Only if those proteins allowed them to more effectively reproduce.



Actually, I don't really know much about the beginning of life... I don't understand how organisms started using DNA to store how they will be made.  Actually, I don't even know how cells read and interperet DNA/RNA (I do know how it is replicated, however).  Do you?


Title: Evolutionary Algorithims
Post by: Frobozz on March 08, 2004, 06:06:24 PM
Quote from: "PlayGGY"
Actually, I don't really know much about the beginning of life... I don't understand how organisms started using DNA to store how they will be made.  Actually, I don't even know how cells read and interperet DNA/RNA (I do know how it is replicated, however).  Do you?


I don't, but Wikipedia has a brief article on it.  http://en.wikipedia.org/wiki/DNA_replication

I don't actually see why you want to use a genetic algorithm to create an AI.  Why not a neural network?


Title: Evolutionary Algorithims
Post by: PlayGGY on March 08, 2004, 08:10:12 PM
Quote from: "Frobozz"
Quote from: "PlayGGY"
Actually, I don't really know much about the beginning of life... I don't understand how organisms started using DNA to store how they will be made.  Actually, I don't even know how cells read and interperet DNA/RNA (I do know how it is replicated, however).  Do you?


I don't, but Wikipedia has a brief article on it.  http://en.wikipedia.org/wiki/DNA_replication

I don't actually see why you want to use a genetic algorithm to create an AI.  Why not a neural network?


Neural networks aren't always the best thing either, though.  Sometimes, a state machine is best, or, for non-real-time things, brute-forcing sometimes works, though usually not very well.


Title: Evolutionary Algorithims
Post by: Agamemnus on March 09, 2004, 01:41:42 AM
A genetic algorithm *IS* a neural network, except just looks differently on the outside....


Title: Evolutionary Algorithims
Post by: qbiscool on March 15, 2004, 01:26:59 PM
sorry but i agree with r@dioman on this and i never said that i want to create a genetic algorithm or a nueral network(but thanks for the ideas). i started this thread to see if any body could show me some info on evolutionary algorithms.

PS. i found a good site for genetic and nueral things. http://www.scienceforums.com, you might need to change the science to a sci but its good place.

PSS. Please dont yell at me for posting this because i got yelled at for reviveing a old topic. How old can the topic be before it is dead.


Title: Evolutionary Algorithims
Post by: Agamemnus on March 15, 2004, 03:21:00 PM
A "genetic algorithm" is the same thing.......


Title: Evolutionary Algorithims
Post by: qbiscool on March 15, 2004, 06:31:52 PM
from the knowlege i have from AI genetic algorithms is a program that is given certain genes and a goal and gains knowlegde to try to solve the goal. a evolutionary algorithm is a program that is given genes and problems but has no big goal(like get to the big red dot or find the capital of canada) but is given problems and the goal is to grow to overcome them.

Im probaly wrong :)  but that is what i think of them as


Title: Evolutionary Algorithims
Post by: Agamemnus on March 15, 2004, 09:27:41 PM
The goal, then, is to overcome to "problem", just like the "problem" of finding the big red dot..


Title: Evolutionary Algorithims
Post by: PlayGGY on March 15, 2004, 10:33:31 PM
A "genetic alogorithm" isn't necissarily the same thing as a neural net.

An genetic algorithm could be as simple as pairing off the best traits of killed computer-controlled players for re-spawning.  While you could make an NN do that, it wouldn't make any sense to.


Title: Evolutionary Algorithims
Post by: Agamemnus on March 16, 2004, 09:52:04 AM
I shuppose you could say that an evolutionary algorithm is THE algorithm to the universe, life, and everything.

Here's a hint to get you started:

42


Title: Evolutionary Algorithims
Post by: Neo on March 16, 2004, 10:33:20 AM
What's got 42 to do with this?


Title: Evolutionary Algorithims
Post by: RST on March 16, 2004, 01:23:06 PM
Dude. If you want to be an educated, intellectual, productive person You need to read more of the classics.  :lol: