Someone of you knows where I can find information, articles and results about deterministic vs non deterministic algorithm in gaming AI? I''ve to write something on, and I think that someone has already done it! But I can''t find it... Please help me! Tanx

I will recommend "Mathematical Methods for Artificial Intelligance and Autonomous Systems", by Giardina and Dougherty, ISBN: 0135609135 as a reference on finite state machines ("FSM"). You can find this book at Barnes & Noble at:

http://search.barnesandnoble.com/booksearch/isbnInquiry.asp?userid=2WL0GADXID&isbn=0135609135&itm=2

This text includes material on the usual deterministic FSMs, fuzzy automata, stochastic automata (very often incorrectly called "fuzzy FSMs" in the game programming world) and lattice automata, among other things.

-Predictor
http://will.dwinnell.com

Tanx! I''ll read that book...

But I don''t need info only about FSM or Neural Nets separately... I need some articles on their comparison...
For example, the difference in terms of behaviour, computational time or use of resources in a virtual bot designed in both FSM and Neural Nets (or GA)...

I''ve to compare deterministic and non deterministic algorithms and I''ve to pay attention on that comparison...

Anyone should have studied this topic, I hope... but I can''t find any result...

However tanx a lot for your reply!

What do you mean by non-deterministic? All computer algorithms are deterministic as far as I know. It''s just a case of how transparent the process is.

I think non-deterministic means that the enemies might do different things even if you do the same exact thing every time. That''s just a guess.

--------------------------------------
I am the master of stories.....
If only I could just write them down...

quote: Original post by Kylotan
What do you mean by non-deterministic? All computer algorithms are deterministic as far as I know. It''s just a case of how transparent the process is.

So how would you describe an algorithm that branched based on the perception of a stochastic event in the environment (and yes, let''s assume the event is truly stochastic, like the emmision of a gamma photon from a radioactive isotope)? Is the algorithm deterministic given the input, deterministic or stochastic if we ignore the input, or does the input count as part of the computational algorithm and hence make the algorithm stochastic?

Cheers,

Timkin

quote: Original post by Kylotan
What do you mean by non-deterministic? All computer algorithms are deterministic as far as I know. It''s just a case of how transparent the process is.

SMP search algorithms in game playing programs (chess, etc.) are non-deterministic. You get some really weird and unpredictable results sometimes.

If a program, given the same input, behave the same way each run, then I would argue it is deterministic. This would be particuarly important for tracking down bugs -- if it wasn''t deterministic over the input, debugging would be much more difficult.

quote: Original post by BrianL
If a program, given the same input, behave the same way each run, then I would argue it is deterministic. This would be particuarly important for tracking down bugs -- if it wasn't deterministic over the input, debugging would be much more difficult.

But there are certainly programs that given the same input don't behave the same... in particular, programs where the entire history of inputs affects the state of the system and where past actions also determine the state of the system. What if the selection of actions A or B is based on a randomly generated number. Is the action outcome (final state of the system) stochastic? What if we used a truly random event to generate the choice... like the example I gave above (radio isotope decay)?

There are some who argue that there are no truly stochastic events in the universe... that every event perceived to be stochastic is at some finer resolution a deterministic event based on causal principles. I think its sufficient to say that at some level a system may be perceived as stochastic. Thus, there are certainly algorithms that when viewed at an appropriate resolution can be considered stochastic, rather than deterministic.

Cheers,

Timkin

[edited by - Timkin on February 10, 2004 12:35:04 AM]

Interesting replies, indeed!
Simply, non deterministic means that with the same input, the output generated by the algorithm could be different each time...
This is why FSM are considered deterministic algorithm and GA or Neural Nets are non deterministic...

In a graphic representation a non deterministic algorithm is a node with two or more branches in output with the same label.

Probability and stochastic are the keyword...

Sure, debugging is more difficult... but nothing else on their comparison?
Seems to be an interesting topic...

Byez