Learning AI

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Oct 06, 2004 at 20:42

Hi,

I’m going to make a treatise on Artificial Intelligence for school (I’m in the last year before college now and this is going to be my hmm *big* endproject of secondary school). I’ve gathered quite alot of information already but I can’t seem to find decent tutorials (writing a tick tack toe AI != decent :)) about coding an AI in C++. I’ve tried coding a bit in prolog and lisp but that didn’t get me far either (except for solving a few logic problems). Is there anyone here that can point me in the right direction?

Thanks in advance,
- Ciri

BTW has anyone checked the Golem Project (search google for it, the first match you find) it’s quite nice what they achieved.

28 Replies

Please log in or register to post a reply.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Oct 06, 2004 at 22:53

do you have an idea in which direction you want to go ?

board games ?
group behaviour (like flocking algorithms) ?
neural networks ?
genetic algorithms ?

just a few examples…

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Oct 07, 2004 at 05:58

Yes, I have 2 options (the 2 directions that I describe in my treatise):
- Making an AI for a game (could be any board game)
- Making an AI that evolves and develops itself through the darwinism process (like create a world with environement variables and a few classes of ‘life forms’ that adapt themselves to the envioronement)

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Oct 07, 2004 at 06:55

Well if u have the choice i would go for a self evolving Neural network.
Neural nets work verry simple u just have a neuron with inputs and each input is connected to a neuron in the layer above. Just put the data into the first layer and propagate down to the last layer.
If u encode the weights of the connections into a genome then u can get a genetic algorithm to use your preferred darwin approch to evolve.
quite simplet actualy there is a lot on aijunky.com

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Oct 07, 2004 at 07:30

Neural nets aren’t much for learning about intelligence though. They are pretty much black box solutions (though there are some research areas that hope to remove this)

I suggest you start simple. Start with a finite state machine, with each state being the current behavior.

Amit has some good sections on pathfinding and gets a little into AI as well http://theory.stanford.edu/\~amitp/GameProgramming/

I also highly suggest http://ai-depot.com/ but keep in mind there are many advanced techniques described there. Dont let this overwhelm you. Try to find the easier stuff and start there.

Keep in mind fuzzy logic to help make your algorithms seem more “real”.

Once you have the basics down you can start into the cooler areas like genetic algorithms and neural nets. These are ways to grow or train a solution to a problem that is very difficult if not impossible to define in an easily solveable way.

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Oct 07, 2004 at 12:42

Well u dont really need the basics of other types of AI before u start on funny little things like Neural Nets. Sometimes it might be even better since u just read the theory and dont start thinking well this works like that and i know this part.
Neural-Nets are indeed a black box but they are so easy to implement and to combine with a genetic algorithm that it is ideal for things like school projects.
They impress most teachers since they look complex, they are complex at first but verry easy to implement and to test.

Finit state machines are not real inteligence since they are well verry limited and predictable ( and a lot to code ) Pathfinding well technicaly it could fall into the AI department but and A* is nice to implement but if u really want to learn get a simple tile based boardgame sit in front of it and try to determine your thinking process and implement that. I did this once for a small AI programm that in its testphase behaved just like I would do.

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Oct 07, 2004 at 13:11

Interesting, I will look into the neural networks thing and see how far I get :) thank you very much!

[edit: Wow that was really what I was looking for, again, thanks !! ]

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Oct 22, 2004 at 08:02

Mind letting us know how the project went. I really would like to know if it went well and what u made eventualy. Just curious i think but i myself like AI topics and maby i can now learn something from u :)

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Oct 28, 2004 at 21:12

I will translate it (the original version will be in Dutch) and post it here when it’s finished, but it probably won’t be finished before february 2005 so… :)

341007dfa292866b6a2eed801b5b026e
0
Polar_Sleuth 101 Nov 01, 2004 at 02:03

Another place to look:

http://ai.eecs.umich.edu/people/laird/gamesresearch.html

John Laird has been doing Artificial Intelligence research for many years. He developed an AI engine called Soar. Originally it was developed to pilot simulated enemy jet fights for military flight simulators. It is now public domain.

The latest research projects include creating an AI player for Quake II (i.e., Quakebot) that is capapble of exploring and mapping levels, learning from the actions of others, learn from its own successes and mistakes, and can even “anticipate” the actions of other players. There are several papers on the subject available via the above website.

The Quakebot Tutorial:
ai.eecs.umich.edu/soar/tutorial/old/Part5.doc

The tutorial was/is part of an AI course at the University of Michigan.

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 01, 2004 at 09:32

@ciri

I will translate it (the original version will be in Dutch) and post it here when it’s finished, but it probably won’t be finished before february 2005 so… :) [snapback]13425[/snapback]

Hey your dutch nice me too. always nice to see felow countrymen on a forum.
Ill w8 till the version is ready altough when i was at school i could just hand in my assignments in enlish it saved me the translation:) I always code in enlish and if the documentation found on the internet is also enlish i prefer the rest of my projects to be also enlish ( saves context switch from 1 language to the other when working on it )
Good luck with the project.

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 01, 2004 at 10:54

grrr. english. Note the ‘g’

Sorry for the nitpick, but 4 times was my breaking point.

We should probably get some articles up on AI. There is talk on neural nets, but no article up about it. Perhaps I will give it a writeup during my winter break.

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 03, 2004 at 07:51

O sorry did not notice that. Well at least i was consitent. Im verry bad at all natural languages so please forgive my frequent spelling errors.

BTW i still think that communication was ment to communicate so as long as the recepient understands the message there is nothing wrong with it :)

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 03, 2004 at 09:11

true, no hostility meant

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 03, 2004 at 11:13

@NomadRock

true, no hostility meant [snapback]13612[/snapback]

No offence taken. Im used to people pointing out mistakes all the time.

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 03, 2004 at 17:11

Back to the topic at hand..

Ciri, any noteable progress?

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Nov 09, 2004 at 17:34

Yes I finished about 16 pages on Neural Networks. Here’s a *huge* recourse of articles on anything science-related (there about 10.000 articles about AI):

http://www.sciencedirect.com

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 09, 2004 at 17:49

So where are you thinking of taking this?

There are a lot of topics in advanced neural network design.

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Nov 09, 2004 at 19:45

I’m going to follow 2 paths, neural networks and genetic algorithms. Then I’m going to combine both and program an implementation of the combination in a problem solving application (I’m not sure yet what problem I’m going to choose).

It’s not going to be anything too advanced as these are my first steps into the field of artificial intelligence :)

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 10, 2004 at 07:21

Eh well Neural nets and genetic algoritmhs are easy to combine. If u make a good design of what u want to do with them combining will be almost as easy as implementing the Neural Net.
If u get a good problem for your solution ( he he normaly we work the other way around ) let me know i have searched for a good problem myself but stopped my own NN project by lack of a good problem.

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 10, 2004 at 07:59

These are some classic examples:

Optical character recognition.
Voice recognition.
Facial recognition.

starting to see the pattern?

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 10, 2004 at 09:16

Yes that are indeed nice examples but not that easy to make a program for :(.
It gets harder if u want a simple program that uses a NN to do stuff since most problems involve a lot of coding even before u start putting the NN inside.

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 10, 2004 at 13:59

Ok, here is an easy starter for Optical character recognition.

Define your input as 8x16 bits. Each bit corresponds to either a white or black pixel. Thus you have 128 input nodes. For output nodes you could have one for each character you will use, or simply 8 nodes representing the ASCII bits. I suggest you try it both ways.

Then grab yourself a 8x16 font (there are many) and train the thing. Once you are done test it on normal input. Also try changing some pixels, and notice how it still gets them mostly right. Now try combining two characters, and notice how it gives a .5 for both of them (if you use the first option of outputs)

Now allow greyscale input.

Now allow larger more general input and scale it down yourself using a good filter before running it through the net.

Now write a program that breaks an image up into rows and columns and runs each sector through the net and see if you can decode in image containing text into a text file.

See if you can write a program that lets you write on the screen with your mouse one character at a time, and feed the scaled results through your net.

Now it isn’t all that difficult is it?

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 11, 2004 at 10:53

Well they are not really hard but it is a lot of coding and debugging. And determine the number of hidden layers and nodes in the layer is not trivial either.
It is just not a program u can make in lets say 16 hours or something and i was looking for a program that could be made verry quick that i could verry simply test and even work out on paper ( for debugging ).
Im in a fulltime job and i dont have much time for programming at home :( so i want small simple things.
But i might start on your idea it sounds not that hard.

Db48ec9bf6c4bcacdd3cc1b1cc3573b4
0
ciri 101 Nov 11, 2004 at 14:21

If you make any progress make sure to post pseudo or normal source codes :)

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 11, 2004 at 15:47

Well if u want i have a complete set of sourcecode for a NeuralNet that can be generated from a genome. The only part missing is the generation of the genome but it is a lot more then i can post here.
If you want i can see if i can get from my laptop to my internet PC and mail it to you the code is not that bad and little documented.

1c7757ea91b5bbf7a4d2cf0563b9e872
0
sumedhs 101 Nov 13, 2004 at 13:58

NNs & GA is a good combination. Infact competitive learning or Darwinizm gives good & fast results. However there are some inherent problems that I faced while doing a projet which implements evolutionary NNs (Or NN + GA).
GA works on the principle of making the strong stronger & eliminating the weak. Now as for NNs; as rightly put by most; NN is a blackbox, you can never know why it behaves the way it behaves, just by looking at it. In fact you cant even know what it does, unless somebody tells you about the specifications.
Thus we can weigh or judge an entire NN (as a whole) for its strengths as compared to other trained NNs. Then maybe use GA for picking the strongest & mutation or crossover. But my point is that its very difficult to judge that what part of a perticular NN is the stronger one & what part is the weaker one. In other words what is it that is making the NN strong (in the gameplay) cannot be easily detected.
Hence if you consider a GA approach where each NN is a chromosome then its possible to find out how good the entire chromosome is.. but its very difficult to find which part of that perticular chromosome is stronger (or is making the chromosome stronger). In conventional GA if you want to do a crossover / mutation you will want to identify that part in a chromosome & make it better also identify the weaker part & replace it or make it better too. But this is not easily possible in NN + GA.

Just a passing thought. But let me clear myself. Inspite of this problem, NN+GA is a very good approach to solve the set of AI problem (that its meant for).

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 13, 2004 at 17:22

Well that is the problem but it will be hard to compare 2 NN when they are not the same. I was ( time constraints froze the project :( ) implementing a NN with GA that will just create the NN even adding neurons and connections between them.
I have not got to the point of really testing all of it so the problem could emerge in my project as well.
But u dont want to optimize 1 neuron of the NN since u want a global optimalisation not a local one. If 1 neuron gets improved you can destabilize the entire NN and just end up with a NN that is actualy worst then the original one.

Sorry if im not clear i cant seem to find the correct words sometimes.

1c7757ea91b5bbf7a4d2cf0563b9e872
0
sumedhs 101 Nov 15, 2004 at 07:50

That is very correct ShadowHawk!
You will not want to optimize a single neuron in an NN but maybe you have streams on Composite NN. Like say for example you have one NN that plays defensive strategy, other NN that plays attacking strategy & you form a composite NN at the top of both the NNs which will decide whats the best move to play right now. (This is not simple aggregation).
What I meant was that I was myself locked in difficulties when I wanted to optimize a part of NN.
As for comparing 2 NNs a very simple approach which is commonly used in NN + GA implementations is that make the NN play series of games & the fitness functions (of GA) is simply the number of wins.